带有时间窗的电商物流终端配送研究

袁雨果，高华峰

(1.集美大学 诚毅学院，福建 厦门 361021；2.湖北民族学院 经济与管理学院，湖北 恩施 445000)

带有时间窗的电商物流终端配送研究

袁雨果1，高华峰2,*

(1.集美大学 诚毅学院，福建 厦门 361021；2.湖北民族学院 经济与管理学院，湖北 恩施 445000)

物流配送是支撑电子商务发展的关键环节和重要基础，而电商物流终端配送更是制约配送效率、影响服务质量的关键.以电商物流终端配送为对象，研究时间约束下的带有时间窗的多快递员任务分配和线路优化.将其抽象为一个具有时间窗的团体定向问题，并设计一个四步骤启发式算法进行求解.为验证算法性能，通过构建算例对比该算法和标准遗传算法、粒子群算法的效果差异.方差分析结果表明，该四步骤启发式算法能够获得更好效果.

终端配送；时间窗；团体定向问题；启发式算法

近年来，互联网技术的发展促进了电子商务的迅速发展,而电子商务也成为物流配送业持续发展的重要推动力量[1]；物流配送是支撑电子商务发展的关键环节和重要基础[2-3]，物流配送质量的高低直接影响客户对电商企业的满意程度[4-5].因此，很多业界人士指出，电子商务未来发展的关键症结在于物流配送.正因为如此，近年来国内最具代表性的电商巨头“亚马逊、阿里巴巴和京东”都在物流配送领域动作频繁：如2012年初，亚马逊提出了“云仓储”服务并给出明确操作方案；阿里巴巴不遗余力的推动阿里“菜鸟网络”；京东花费巨资所打造的自有物流体系，其核心价值在于遍及全国各主要城市的“分布式仓储体系”.不管采取哪种方式，他们的目标都是实现“成本低、时效快、服务好”的物流配送目标，而物流终端配送显然是实现这个目标的重点，它是制约配送效率、影响服务质量的关键[6-7].

与一般物流配送不同，电商物流终端配送具有对配送方式要求苛刻、对配送时效要求很高、订单数量大、规模小等特点[8].近年来，为了提升电商物流配送的效率和满意度，电子商务物流终端配送的模式不断丰富[9-12].此外，随着消费观念的转变，有些客户会对配送时间的个性化提出更高的要求：他们愿意支付额外的费用使得物流公司能够根据自己的预约时间进行配送(如以小时为单位).通常而言，对配送时间窗口期的要求越精确(即窗口时间跨度越小)，对物流公司配送的要求就越高，需要支付的配送费用也会越高.对于这种服务，一旦无法在客户预约的时间内完成配送，则物流公司需要承担约定的赔偿责任.面对这种新型和传统配送方式共存的情况，物流公司由于资源的约束(主要是快递员人数以及工作时间的限制)，它们往往需要评估各个配送任务的特征，如配送地址、时间窗口和收益等情况，进而规划出相应的配送线路，从而使总收益最大，该问题可以抽象为带有时间窗的团队定向问题.

定向问题(orienteering problem,OP)最早是由Golden等人提出来的[13]，它起源于定向运动比赛.在该比赛中，每个关卡都有一定的分值，每名参与者都希望在有限的时间内从不同关卡中获得尽可能多的分值[14].在此之后，定向问题被广泛应用在交通规划、物流配送和旅游线路设计等众多领域[15-16].而团队定向问题(team orienteering problem,TOP)则对应于以多名成员为小组所进行的定向运动比赛，在该比赛中，需要为团队中每个成员设计一条线路，目标是使团队所有成员所获得的分值之和最大[17].团队定向问题也被应用在越来越多的领域中[18-19]，而且各种解决该问题的精确算法[20-21]和启发式算法[17-18，22-24]被不断设计出来.近年来，带有时间窗的团队定向问题(TOP with time windows,TOPTW)受到了更多的关注[21，25-27]，主要原因是解决TOPTW的方法与一般TOP有很大的不同.Montemanni和Gambardella设计了蚁群优化[25]、Tricoire等提出变邻域搜索算法(VNS)并嵌入了一个精确算法以解决路径可行性的子问题[28]；Vansteenwegen等设计了一个快速迭代局部搜索算法[26]；Labadie等设计了基于LP的细粒度变邻域搜索算法[27].

以电子商务物流终端配送为研究对象，研究时间约束下的带有时间窗的多快递员任务分配和线路优化.该问题可以分为两个阶段：第一阶段是任务选择与分配，即选择需要当天配送的任务，并将所选任务分配给相应的快递员；第二，根据配送任务的特征(如时间窗、奖惩系数等)，为每个快递员规划配送线路.团体定向问题已经被证明是一个NP难问题，很难通过精确算法对大规模问题进行精确求解.为此，本文设计了一个四步骤的启发式算法对其进行求解.为验证该算法的性能，构建了一个算例进行实验.

1 数学模型构建

本文所研究的问题可以抽象为带有时间窗的团体定向运动问题(TOPTW).在该问题中，每个快递员都是从同一个仓储中心出发，在完成所有配送任务后，又返回相同的仓储中心.由于快递员都有一定的工作时间限制，因此有可能不能完成所有任务的配送.因此该问题的目标是使得所有快递员在有限的工作时间内取得的效益值之和最大.

设快递员人数为P，物流仓储中心为v0，每个任务的配送地址标记为v1,v2,…,vN，每个任务的配送时间窗口期为[Oi,Ei]，如果快递员早于窗口期开始时间Oi到达任务i的配送地址vi，则需要等待；如果他晚于窗口期的结束时间Ei到达，则会产生一定的惩罚，该惩罚为ci.假定延迟的时间越长，惩罚值越高，则该惩罚值如式(1)所示，它与vi的时间窗口[Oi,Ei]、到达vi的时间sip、以及惩罚系数δi有关.如果快递员完成配送任务，则他将得到一个收益值ri.显然，快递员在vi是否有净效益值，取决于ri与pi之差，则该问题的目标函数如式(2)所示，其中yip为0-1变量，若任务vi分配给快递员p，则yip=1，否则yip=0.

cip=δ·max[sip-Ei,0]

(1)

(2)

(3)

(4)

(5)

(6)

(7)

sip≥Oi,∀i=1,2,…,N

(8)

sip≥Ci,∀i=1,2,…,N

(9)

(10)

2 四步骤启发式算法

团队定向问题是一个NP难问题，很难在可接受的时间内通过多项式算法求解其精确值[13].为此，本文设计了一个四步骤启发式算法，包括解编码、初始解集合构造、解集合进化和解集合评估，算法流程如图1.

图1 四步骤启发式算法流程图Fig.1 Framework of the four-stepheuristic algorithm

2.1解编码

2.2初始解集合构造

2)从任务集合中随机抽取若干任务，构建任务序列；

4)拆分任务以确定每名快递员的配送任务及任务配送线路；

5)计算每名快递员完成所有配送任务需要的时长，如果每名快递员的配送时长满足式(3)～(10)的约束条件，则该任务序列为可行解，将其插入到初始解集合中，否则重新返回步骤2)；

6)如果初始解集合IS所包括的可行解数量达到种群规模Q，则结束初始解集合构造过程，否则返回步骤2).

2.3解集合进化

在解的进化过程中，本文采用局部搜索的方式来进行，包括插入、调整和调换等三个算子：

1)插入算子：对于某一可行解，随机地选择一个插入点，并从未选择的任务中随机的选择一个插入该可行解中，若得到的解仍是可行解，且收益大于插入前，则新形成的解替代原来的解.

2)调整算子：对于某一可行解，随机地选择该可行解中的两个任务，并交换所选择的任务.根据原可行解和新产生的解的收益值，采用轮盘赌的方式选择一个替代原可行解.

3)调换算子：对于某一可行解，随机地选择其中一个任务vi，并从未在该解中的任务中随机选择一个收益大于任务vi的任务vj，替代任务vi；若得到的解仍是可行解，则根据原可行解和新产生的解的收益值，采用轮盘赌的方式选择一个替代原可行解.

2.4解集合评估

将进化后的所有解进行评估，首先还是删除掉不可行解，包括具有重复配送解，超过时间约束的解.之后根据目标函数式(2)进行评价.得到最好的Q个解再进入新的一次迭代，直至达到最大迭代次数.在最后一次迭代所得到的解集合中，选择目标函数值最好的任务序列，该序列即为最满意解，作为算法的输出.

3 算例分析及结果

为了验证四步骤启发式算法的性能，通过构建一个算例，并与标准遗传算法(standard Genetic Algorithm,sGA)和粒子群算法(particle swarm optimization,PSO))进行对比.为了减少误差的干扰，分别用每种方法测试30次，得到的结果如图2所示，而图3为启发式算法其中一次实验的结果，不同颜色表示不同的快递员.

为进一步分析这3种方法的性能是否有差异，采用方差分析(ANOVA)的方法进行验证.3种方法得到的效益值的描述性统计如表1所示.而表2显示了方差分析的结果，由于F=7.364，Plt;0.05，表示这3种方法所取得的效益值存在显著性差异.

表1 描述性统计

表2 方差分析

表3 多重比较(Scheffe)

注：*：均值差的显著性水平为 0.05

为了进一步确定哪种方法存在差异，本文采用了Sheffe方法进行多重分析(如表 3所示)：对于HA和sGA的比较，二者平均效益差为6.201 7，Plt;0.05，说明HA获得的效益值要显著高于sGA；同样地，对于HA和PSO的比较，二者平均效益差为7.017 33，Plt;0.05，也说明HA获得的效益值要显著高于PSO.因此，方差分析的结果表明本文所提的启发式算法明显优于另外两种算法的性能.

4 展望

近年来，电子商务的发展成为推动物流配送业持续发展的重要推动力量，而物流配送也是支撑电子商务发展的关键环节和重要基础，物流终端配送更是制约配送效率、影响服务质量的关键.相比一般物流配送，电商物流终端配送具有订单数量大规模小、用户对物流的配送方式和配送时效要求高且不断呈现个性化和差异化等特点.这些特点使得电商物流终端配送面临众多挑战和机遇.

本文所提出的启发式算法尽管能够较好地解决考虑带有时间窗、具有时间约束的多快递员配送问题.但是随着任务规模的增加，算法的效率还有待提升.此外，在电子商务物流终端配送中，会出现等待客户、运输时间不确定等随机问题.因此，在今后的研究中需要考虑将这些随机性因素.

[1] 符瑛,彭银香.电子商务环境下物流配送模式选择[J].中国管理信息化,2009,12(19):115-117.

[2] 杨朋珏,胡昊,王俊嘉,等.电子商务环境下城市配送末端网点选址模型研究[J].工业工程与管理,2014,19(1):35-40.

[3] 张成志,赵亮.电子商务下的物流配送模式选择研究[J].物流技术,2012,31(19):66-68.

[4] 崔珊珊,陈宏,俆加胜.电商促销井喷需求下的应急商品配送研究[J].中国管理科学,2013(s1):141-147.

[5] HOLDORF S,HAASIS H-D.Last mile delivery concepts in E-Commerce an empirical approach[C]∥2014 8th International Conference on Software,Knowledge,Information Management and Applications(SKIMA),IEEE,2014:1-6.

[6] 詹斌,谷孜琪,李阳.“互联网+”背景下电商物流“最后一公里”配送模式优化研究[J].物流技术,2016,35(1):1-4.

[7] 张锦,陈义友.物流“最后一公里”问题研究综述[J].中国流通经济,2015(4):23-32.

[8] 杨聚平.以客户为中心“最后一公里”配送模式研究[D].北京:对外经济贸易大学,2014.

[9] 詹林敏.电子商务物流最后一公里配送模式研究[D].大连:大连理工大学,2015.

[10] 陈义友,张锦,曾倩,等.最后一公里配送服务选择均衡问题[J].计算机集成制造系统,2016,22(8):2035-2045.

[11] 杨聚平,杨长春,姚宣霞.电商物流中“最后一公里”问题研究[J].商业经济与管理,2014(4):16-22.

[12] 方玺,耿艳.我国快递“最后一公里”收派模式创新探讨[C]∥中国论坛论文集,2012:5-5.

[13] GOLDEN B L,LEVY L,VOHRA R.The orienteering problem[J].Naval Research Logistics,1987,34(3):307-318.

[14] CHYAO I M,GOLDEN B L,WASIL E A.A fast and effective heuristic for the orienteering problem[J].European Journal of Operational Research,1996,88(3):475-489.

[15] GUNAWAN A,LAU H C,VANSTEENWEGEN P.Orienteering problem:A survey of recent variants,solution approaches and applications[J].European Journal of Operational Research,2016,255(2):315-332.

[16] VANSTEENWEGEN P,SOUFFRIAU W,VAN OUDHEUSDEN D.The orienteering problem:A survey[J].European Journal of Operational Research,2011,209(1):1-10.

[17] CHAO I-M,GOLDEN B L,WASIL E A.The team orienteering problem[J].European journal of operational research,1996,88(3):464-474.

[18] TANG H,MILLER-HOOKS E.Algorithms for a stochastic selective travelling salesperson problem[J].Journal of the Operational Research Society,2005,56(4):439-452.

[19] BUTT S E,CAVALIER T M.A heuristic for the multiple tour maximum collection problem[J].Computers amp; Operations Research,1994,21(1):101-111.

[20] BUTT S E,RYAN D M.An optimal solution procedure for the multiple tour maximum collection problem using column generation[J].Computers amp; Operations Research,1999,26(4):427-441.

[21] BOUSSIER S,FEILLET D,GENDREAU M.An exact algorithm for team orienteering problems[J].4OR:A Quarterly Journal of Operations Research,2007,5(3):211-230.

[22] ARCHETTI C,HERTZ A,Speranza M G.Metaheuristics for the team orienteering problem[J].Journal of Heuristics,2007,13(1):49-76.

[23] KE L,ARCHETTI C,FENG Z.Ants can solve the team orienteering problem[J].Computers amp; Industrial Engineering,2008,54(3):648-665.

[24] VANSTEENWEGENAABBA P.A guided local search metaheuristic for the team orienteering problem[J].European Journal of Operational Research,2009,196(1):118-127.

[25] MONTEMANNI R,GAMBARDELLA L M.Ant colony system for team orienteering problems with time windows[J].Foundations of Computing amp; Decision Sciences,2009,34(4):287-306.

[26] VANSTEENWEGEN P.Iterated local search for the team orienteering problem with time windows[J].Computers amp; Operations Research,2009,36(12):3281-3290.

[27] LABADIE N,MANSINI R,MELECHOVSKY J,et al.The team orienteering problem with time windows:An LP-based granular variable neighborhood search[J].European Journal of Operational Research,2012,220(1):15-27.

[28] TRICOIER F,ROMAUCH M,DOERNER K F,et al.Heuristics for the multi-period orienteering problem with multiple time windows[J].Computers amp; Operations Research,2013,40(5):1516-1519.

责任编辑：高山

StudyonTerminalDistributionofE-commerceLogisticswithTimeWindows

YUAN Yuguo1,GAO Huafeng2,*

(1.Chengyi University College,Jimei University,Xiamen 361021,China; 2.School of Economics and Management,Hubei University for Nationalities,Enshi 445000,China)

The logistics distribution is the important back-up and basis for the development of e-commerce,while the terminal distribution of e-commerce logistics is the key to determining the distribution efficiency and affecting the quality of service.Focusing on the terminal distribution of e-commerce logistics,this paper studies the task assignment and route optimization for the multiple couriers with time windows.This issue can be abstracted as a team orienteering problem with time windows(TOPTW).A four-step heuristic algorithm is proposed to solve the TOPTW.In order to evaluate the performance of the proposed algorithm,an example is given to compare the effect of the proposed algorithm with that of the standard genetic algorithm and the particle swarm optimization.The results of an analysis of variance(ANOVA)indicate that the proposed method performs significantly better than the existing algorithms.

terminal distribution;time windows;team orienteering problem;heuristic algorithm

2017-08-23.

福建省中青年教师教育科研项目(JAS160017)

袁雨果(1989-)，女，主要从事物流管理、旅游供应链管理的研究.*

：高华峰( 1972-)，男，博士，副教授，主要从事企业管理的研究.

1008-8423(2017)04-0394-05

10.13501/j.cnki.42-1569/n.2017.12.009

C931

A