基于渐进服务半径的自提柜选址算法①

肖卡飞, 孙 咏, 王 嵩, 田 月, 王美吉



基于渐进服务半径的自提柜选址算法①

肖卡飞1,2, 孙 咏2, 王 嵩2, 田 月2, 王美吉2

1(中国科学院大学, 北京 100049)2(中国科学院沈阳计算技术研究所, 沈阳 110168)

物流“最后一公里”是直接面向客户服务的物流末端环节, 直接影响到物流的效率、成本和服务质量. 针对此“最后一公里”问题, 提出基于自提柜的末端物流配送解决方案. 通过引入自提柜渐进服务半径的概念, 用需求点到自提柜的距离来刻画需求点对自提柜的服务满意度,并用凹凸函数来表示, 建立自提柜选址问题的混合整数规划模型. 同时, 充分考虑模型的各项约束性条件, 设计出启发式拉格朗日松弛算法并进行模型求解. 最后, 运用大量算例进行检验, 分析算法的迭代次数、迭代时间等指标, 证明选址模型的准确性和求解算法的有效性, 为实际工程应用提供了理论指导.

最后一公里; 渐进服务半径; 服务满意度; 混合整数规划; 拉格朗日松弛算法

1 引言

物流行业的“最后一公里”问题, 是制约物流企业发展、影响用户满意度的一个重要因素[1]. 就目前而言, 部署自提柜成为各大物流企业或电商平台解决“最后一公里”问题所采取的积极措施. 在我国, 智能自提柜的研发技术已经趋于成熟, 涌现出一批知名企业, 如丰巢科技、乐栈、鸟箱等[2]. 但是, 如何对自提柜进行选址、布局等问题, 国内外尚缺乏深入的研究. 并且, 合理地对自提柜进行选址才能保障效益最大化, 这是一个亟待解决的技术难题. 因此, 本文主要针对具有容量限制的自提柜选址问题进入研究, 提出对应的选址模型、设计求解算法.

2 相关工作

国外研究学者对无人交货接收盒(Unattended reception box)[3], 递送盒(Delivery box)和共享接收盒(Shared reception box)[4,5]等递送方式进行研究, 并实证分析了自提点模式可以极大地减少运输成本[6], 同时论证了两种自提式服务模式中: 有人值守式CDP (Attended CDP)和无人值守式CDP(Unattended CDP)中的无人值守式CDP(即自提柜式自提点模式)能降低1/3的配送成本, 因此自提柜配送模式得到了业界和研究领域的双重肯定. 虽然国内外鲜有直接对自提柜的服务半径和选址问题进行的研究, 但是对于公共设施、应急设施甚至物流配送中心等选址研究已经积累了丰硕的成果. 因此, 自提柜作为一种基于覆盖范围的服务性公共设施, 也具有自己的服务覆盖范围, 即服务半径. 杨晓农、王振蒙[7]等人对基于服务功能的公共设施的服务半径理论进行研究并给出了服务半径的界定、理论基础和功能划分. 杨珺[8]等人对一类带服务半径的服务站截流选址-分配问题进行了研究, 并给出对应的启发式算法, 研究服务站的服务范围. 杨晓飞[9]等人对公交服务半径的影响因素进行了分析, 并给出了服务半径的计算模型和评价方法. 同时也有学者对物流节点中服务半径进行了更深一步研究. 江从发、龚国华[10]等人简单分析了配送中心的服务半径, 并描述了它的决定因素和决定方式, 同时分析了其实现最佳服务半径、达到资源优化利用的一些建议. 高洁、李锦飞[11]分析了物流中心服务水平与服务覆盖范围之间的关系, 提出了一种基于服务水平约束的、综合考虑物流节点的运输成本、配送路线以及覆盖范围的网络选址模型, 并设计了紧急搜索算法来求解该模型.

同时, 王非等人对国外学者研究成果进行总结汇总, 将离散选址问题详细划分8 类子问题[12], 其中覆盖模型已被证明是用于解决选址问题的有效模型之一. 传统的服务半径的研究, 多假设需求者的空间距离在服务半径覆盖范围之内, 将100%接受到该设施点的服务; 而超出服务半径的覆盖范围则100%不接受该设施点的服务, 这种“非黑即白”的评价方式, 属于经典的“二元”覆盖问题. 随着研究的深入, 学者逐渐放松了对完全覆盖的条件限制, 发展了多种覆盖情况的理论. 乔联宝[13]对覆盖类选址问题进行了分类, 并在其基础上给出了各类覆盖问题的数学模型和各类模型之间的内在联系. Daskin[14]和Batta[15]等人基于需求点被服务半径覆盖的不确定性研究, 研究了最大覆盖问题. Home[16]基于服务半径的固定与可变情况, 讨论了条件覆盖下选址问题的动态规划算法. Hassin、Segev[17]研究了可变服务半径的选址问题, 但未对可变半径对服务满意度的影响进行深入定义. Drezner等人[18]提出渐进覆盖模型来解决需求者选址满意度问题. 不同于传统“二元”覆盖问题之处, 渐进覆盖细化覆盖粒度, 将“非1即0”的二元覆盖假设拓展为多元覆盖假设[19], 将覆盖定义为基于覆盖距离的非增函数, 取值范围为[0,1][20], 但是未考虑服务容量的限制. 褚玉婧[21]提出时间满意逐渐覆盖电动汽车充电站选址及算法给本文带来一定的启发.

本文在渐进覆盖的理论基础上, 提出了基于渐进服务半径的自提柜选址模型, 充分考虑服务半径覆盖范围对需求者满意度的影响. 此外, 在模型建立过程中, 综合考虑自提柜的服务容量、服务半径、及需求点的需求量等约束性条件, 对实际生产生活中物流企业、电商企业等布局自提柜提供了科学的决策指导.

3 自提柜选址模型

3.1 问题描述

自提柜作为向客户提供物流服务的末端公共服务设施, 其选址定位问题和服务容量限制, 不仅关系到物流企业的成本投入和市场覆盖范围, 更关系到客户对服务质量满意度评价. 通常距离高密度客户聚集区越近, 越能够提高自提柜的服务范围; 合理的服务容量既关系到物流企业的成本投入又关系到各区域实际需求量来合理规划.

3.2 符号声明

同时定义如下决策变量:

3.3 模型假设

假设1. 不考虑同行业其他竞争者同类设施对本自提柜用户使用情况的影响;

假设2. 使用者的服务半径满意度函数用覆盖距离的凹凸函数来描述, 且对同一类型的自提柜, 所有的使用者均服从同样的覆盖函数;

假设3. 不考虑自提柜设施的建设成本(包括设施占地成本、器材成本及运营和维护成本).

3.4 服务满意度函数

作为一种商用的公共服务设施, 自提柜有自己的服务半径, 且在其最小服务半径覆盖距离内需求点可以被完全覆盖, 在其最大服务半径覆盖距离外的需求点则是完全不可覆盖的, 而两者之间的需求点则是基于一定概率非增的可覆盖情况. 其中完全覆盖表示很满意、不可覆盖表示很不满意、可覆盖表示不同程度的满意度, 用此概念来描述基于覆盖距离的需求点的服务满意度函数.

采用问卷形式对客户对周围服务网点距离的满意度调查情况进行统计分析, 得出在一定距离内客户可以完全接收, 但超过某一距离, 用户会选择性地接收服务, 直至更远的距离, 用户完全不接受其网点的服务. Berman和Krass[22]提出基于距离的凹凸函数, 比较贴切现实生活中距离与覆盖水平的关系, 较好地模拟真实情况.

3.5 模型建立

目标函数:

约束条件:

目标函数(2): 使得总的服务半径覆盖范围最大化和选址效益最大化;

约束条件(3): 每个需求点只能选择一个设施点提供服务, 默认情况下, 当一个需求点被多个自提柜服务范围覆盖时, 选择距离最近的自提柜接受服务;

约束条件(6): 确保所有自提柜设施点对每个需求点提供的服务不超过其需求量;

约束条件(7): 确保所有需求点对每个自提柜设施点的供应量不超过其容量;

约束条件(8)、(9): 变量取值约束.

4 模型分析与求解

4.1模型分析

以上建立的选址模型是一个混合整数规划模型, 属于NP-hard问题, 随着问题规模的增大或约束条件的增多求解复杂度呈指数增长, 因此在实际应用中, 一般会采用启发式算法进行求解, 故本文设计了基于次梯度算法和拉格朗日松弛法的启发式模型求解算法.

4.2 模型求解

算法分析: 对于NP-hard问题, 最常用的求解方法就是构造启发式算法, 以求尽量接近最优解的可行解. 拉格朗日松弛算法就是求解下界的一种方法, 它的基本原则是将造成问题求解困难的约束条件吸收到目标函数中, 并保持目标函数的线性, 使问题容易求解, 并且实现比较简单和有比较好的性质. 算法的执行过程主要分为两个阶段: 第一阶段为求松弛后的线性规划问题的最优解; 第二阶段为将解整数化, 并考虑其可行性. 在本模型中, 通过分析(3)-(9)的约束条件, 认定条件(3)是“困难约束”, 其余为“简单约束”.

为保证对搜索步长的控制, 将约束式(3)放到目标函数(2)中, 得到拉格朗日松弛问题(2).

目标函数:

约束条件:

(4)至(9)

其中, 令

本文利用次梯度优化来调整拉格朗日乘子的值, 以此逼近最优解, 拉格朗日乘子计算过程如下所示.

算法执行步骤如下: (说明: 基于次梯度算法和改进拉格朗日松弛法的启发式算法)

Step 2. 求解拉格朗日松弛问题. 按以上计算方法计算出,.

Step 9. 终止条件判断. 若满足如下任何条件, 即结束迭代过程.

5 实验仿真

5.1数据集及运行环境

需求点数据集: 本文通过随机算法, 日需求量按照正态分布产生, 需求点到自提柜点的空间距离按照正态分布产生, 需求点个数分别为100、400、1000的三个数据集.

实验环境: 运行环境: Matlab R2013a; 操作系统: Windows 7 旗舰版 64位; 处理器: 英特尔第二代酷睿 i5-2320 @ 3.00GHz 四核; 内存: 4G.

5.2实验结果分析

实验结果表明, 拉格朗格松弛算法在求解0-1整型规划问题上具有良好的运算效果, 见表1和图1.

表1 不同算例下, 拉格朗格松弛算法运行情况

图1 上下界误差(%)随迭代次数增加的变化情况

观察表1可得: 除No.1之外上下界误差绝大部分情况下在3%以下; 平均迭代次数在100到300之间; 覆盖率平均在80%以上, 且随着选址数的增加均能达到较高的覆盖率; 而算例的运行时间均是在30s之内, 不过随着需求点数据量的增多, 算例的运行时间有明显的增长趋势. 然而, 拉格朗日松弛法可以对最优解的上下界进行估计, 在实际工程问题中, 可以根据不 同需要对参数进行相应的调整, 如迭代次数、步长等参数, 以达到自己可接收的近似近似最优解.

6 结语

自提柜配送模式是近年来物流领域发展迅猛的新型配送方式. 本文通过引入自提柜渐进服务半径的概念, 基于需求点到自提柜的距离来刻画需求点对自提柜的服务满意度函数, 建立了自提柜选址问题的混合整数规划模型, 并设计启发式算法进行求解. 通过运用大量算例分析, 验证了模型的准确性和启发式算法的正确性, 证明了求解算法具有很强的收敛性, 同时对于现实生活中物流企业等进行自提柜选址具有很强的指导意义. 但本文中未考虑不同地域及不同服务容量的自提柜建设成本因素, 以及同一地域中不同企业之间同类末端物流方式存在对需求点的竞争关系, 会对模型的准确性和稳定造成一定的影响, 未来本文将对此进行深入研究, 建立更稳健的基于竞争关系和服务成本自提柜选址模型.

1 周速华.以用户体验为核心赢在最后一公里.现代家电, 2015,(3):27–29.

2 刘柳,马英才.智能物流上演“最后一公里”争夺战.互联网经济,2014,(7):16–19.

3 McKinnon AC, Tallam D. Unattended delivery to the home: an assessment of the security implications. International Journal of Retail & Distribution Management, 2003, 31(1): 30–41.

4 Punakivi M, YrjoÈlaÈ H, HolmstroÈm J. Solving the last mile issue: Reception box or delivery box. International Journal of Physical Distribution & Logistics Management, 2001, 31(6): 427–439.

5 Punakivi M, Tanskanen K. Increasing the cost efficiency of e-fulfilment using shared reception boxes. International Journal of Retail & Distribution Management, 2002, 30(10): 498–507.

6 McLeod F, Cherrett T, Song L. Transport impacts of local collection/delivery points. International Journal of Logistics, 2006, 9(3): 307–317.

7 杨晓农,王振蒙.基于服务功能的公共图书馆服务半径理论研究.图书馆,2014,(6):17–19.

8 杨珺,张敏,陈新.一类带服务半径的服务站截流选址-分配问题.系统理论与实践,2006,26(1):117–120.

9 杨晓飞,马健宵,仲小飞.公交服务半径及服务水平研究.森林工程,2011,27(1):61–64.

10 江从发,龚国华.配送中心最佳服务半径分析.物流技术,2003,(9):19–20.

11 高洁,李锦飞.基于服务水平的区域物流中心优化选址模型研究.物流技术,2005,(10):279–281.

12 王非,徐渝,李毅学.离散设施选址问题研究综述.运筹与管理,2006,15(5):64–69.

13 乔联宝.覆盖类选址问题分类及研究综述.物流科技,2015,38(3):59–66.

14 Daskin M. A maximum expected covering location model: fprmulation, properties and heuristic solution. Transportion Science, 1983, 17(1): 48–70.

15 Batta R, Dolan J. The maximal expected covering location problem: Revisited. Transportation Science, 1989, 23(4): 277–287.

16 Home J, Smith J. Dynamic programming algorithms for the conditional covering problem on path and extended star graphs. Networks, 2005, 46(4): 177–185.

17 Hassin R, Segev D. The multi-radius cover problem. Lecture Notes in Computer Science, 2005, 3608: 24–35.

18 Drezner Z, Wesolowsky GO, Drezner T. The gradual covering problem. Naval Research Logistics, 2004, 51(6): 841–855.

19 Saaty TL. Fundamentals of Decision Making and Priority Theory with the Analytic Hierarchy Process. RWS Publications, 1994.

20 Berman O, Krass D. The generalized maximal covering locationproblem. Computers & Operations Research, 2002, 29(6): 563–581.

21 褚玉婧,马良,张慧珍.时间满意逐渐覆盖电动骑车充电站选址及算法.数学的实践与认识,2015,45(10):101–106.

22 Berman O, Krass D. The generalized maximal covering location problem. Computers and Operations Research, 2002, 29(6): 563–581.

Location Algorithm of Lifting Cabinet Based on Gradual Service Radius

XIAO Ka-Fei1,2, SUN Yong2, WANG Song2, TIAN Yue2, WANG Mei-Ji2

1(University of Chinese Academy of Sciences, Beijing 100049, China)2(Shenyang Institute of Computing Technology, Chinese Academy of Sciences, Shenyang 110168, China)

The “last mile” in logistic is the terminal link of logistic service for users, and directly affects the efficiency, cost and service quality of logistic. This paper presents a solving method based on lifting cabinet for the “last mile” in logistic (this problem). Based on the concept of gradual service radius, and the relationship between service satisfaction and distance from the demand point to lifting cabinet, this paper proposes a mixed integer programming model for lifting cabinet’s location problem. Moreover, this paper designs a heuristic Lagrange’s relaxation algorithm by taking into full account of the various constraints factors to solve the model. Finally, illustrative examples further analyze the number of iterations, iteration times and other indicators, which show the correctness of the results in this paper and the good performance of the proposed method.

last mile; gradual service radius; service satisfaction; mixed integer programming; Lagrange’s relaxation algorithm

2016-06-12;

2016-07-25

[10.15888/j.cnki.csa.005630]