配送配送区域

第34卷第2期控制与决策Vol.
34No.
22019年2月ControlandDecisionFeb.
2019文章编号:1001-0920(2019)02-0406-08DOI:10.
13195/j.
kzyjc.
2017.
1105考虑动态需求的外卖配送路径优化模型及算法李桃迎,吕晓宁,李峰,陈燕(大连海事大学航运经济与管理学院,辽宁大连116026)摘要:外卖业务模式高度复杂,现有文献中缺少针对外卖配送路径优化问题的研究.
鉴于此,基于同时送取货VRP问题的求解策略,引入时间惩罚成本衡量外卖配送超出时间窗的情况,定义目标函数为外卖配送成本增量总和,包括新订单的固定配送成本、额外配送成本和时间惩罚成本之和.
考虑随机参数对计算复杂程度产生的影响,设定配送区域范围,对新订单进行调度时,已指派但尚未完成的订单仍由原车配送,且将时间惩罚成本作为变动成本修正目标函数,直接去掉时间窗约束,降低算法求解难度.
设计"商家-客户"配对策略,引入k-means对"商家-客户"进行聚类,同一类内设计"商家-客户"遗传算法,得到启发式路径优化方案.
最后,采用随机模拟算法生成动态订单测试算例,通过R语言测试模型及算法的有效性.
关键词:车辆路径问题;外卖配送;k-means聚类;遗传算法;随机模拟算法;动态需求中图分类号:U116.
2文献标志码:ARoutingoptimizationmodelandalgorithmfortakeoutdistributionwithmultiplefuzzyvariablesunderdynamicsdemandLITao-ying,LYUXiao-ning,LIFeng,CHENYan(SchoolofMaritimeEconomicsandManagement,DalianMaritimeUniversity,Dalian116026,China)Abstract:Thebusinesspatternoftakeoutisverycomplexandthereareshotofreferencesfocusingontheoptimizationoftakeoutdistribution.
Inviewofthis,atimepenaltycostisintroducedfordeliveriesoutsideaspeciedtimewindow,whichisbasedonthevehicleroutingproblemwithsimultaneouspickupanddelivery.
Then,theobjectivefunctionissetasthesumoftheincrementalcostsoftakeoutdistribution,whichincludesthexeddistributioncostsaswellastheadditionaldistributioncostandtimepenaltycostofneworders.
Astherandomparametershaveanimpactonthecomputationalcomplexityofthisproblem,aspecieddistributionareaisdesigned,althoughordersthathavenotyetbeencompletedremainwiththeoriginalvehiclewhilenewordersaredispatched.
Thenthetimepenaltycostisusedasavariablecosttomodifytheobjectivefunction,andthetimewindowisremovedtoreducethemathematicalcomplexity.
Weemployk-meansclusteringtogroup"seller–customer"itemsandageneticalgorithmtoidentifytheoptimalroutesforseller–customerpairsinthesamecluster.
Finally,randomsimulationalgorithmisusedtogenerateadynamicordertestdataset,andRlanguageisusedtotesttheeectivenessofthealgorithm.
Keywords:vehicleroutingproblem;takeoutdistribution;k-meansclustering;geneticalgorithm;randomsimulationalgorithm;dynamicsdemand0引言当前有很多C2C外卖平台,如百度外卖、饿了么、美团等.
外卖配送作为餐饮O2O的重要支撑环节,直接影响着互联网餐饮外卖的进一步扩张与发展.
然而,由于区域性限制、时效性要求高、利润点相对较低等诸多原因,外卖配送物流成本居高不下,物流配送优化是外卖平台最大的难题.
传统物流配送优化中的热点问题是设施选址-分配问题(Locationallocationproblem,LAP)、路径优化问题(Vehicleroutingproblem,VRP)和同时送取货VRP问题(VRPwithsimultaneouspickupanddelivery,VRPSPD).
LAP重点是确定配送中心最佳位置,不允许路线巡回访问[1];VRP虽然允许路线巡回访问,但要求开始与结束位置必须为同一配送中心[2],且二者都为先从配送收稿日期:2017-08-21;修回日期:2018-05-25.
基金项目:国家社会科学基金项目(15CGL031);国家自然科学基金项目(71271034);大连市高层次人才创新支持计划项目(2015R063);中央高校基础科研业务费专项基金项目(3132018160,3132016306).
作者简介:李桃迎(1983),女,副教授,博士,从事数据挖掘、复杂网络等研究;陈燕(1952),女,教授,博士生导师,从事数据挖掘、多维信息组织与管理等研究.
通讯作者.
E-mail:ytaoli@126.
com.
第2期李桃迎等:考虑动态需求的外卖配送路径优化模型及算法407中心取货,后向客户配送的过程;VRPSPD为同时送取货的车辆路径问题[3],但所有配送货物都要从配送中心装车送至客户,所有从客户装车的货物都要送至配送中心.
外卖配送和传统物流配送的最大差异在于:1)不是从固定的配送中心取货送往多个收货地;2)取到的货物不是送到固定的几个配送中心;3)所有本车取到的货物都会在本次配送中配送到目的地;4)外卖配送中商家和客户所在地对应于外卖的取货地和送货地,但订单的商家、客户位置也为动态需求,且调度时车辆位置不固定;5)在外卖配送中,为了避免影响餐品质量与口味,一般要求出餐后30min送达客户,与冷鲜品相比,有更严格的配送时间约束,因此外卖配送的距离不能太远,需要对外卖配送划分合理的区域;6)由于天气、交通状况动态变化,送餐员身体状况以及情绪的波动都会对配送时间产生影响.
这些因素的共同影响,使得外卖配送的随机性更强,外卖配送优化过程比传统的车辆优化调度问题更为复杂.
据查阅,现有文献中有关外卖配送优化及其求解方案的研究只有文献[4],其以外卖送达顾客的时间来衡量顾客满意度,未考虑配送的实际成本.
现有文献大部分是关于外卖商业模式[5]、外卖食品的营养与健康[6]等方面,而有关外卖配送优化问题的研究较少,但涉及随机配送时间、时间窗约束VRP问题的研究很多.
马慧茹等[7]将旅行时间引入旅行商问题,构建了旅行商问题的随机机会约束规划模型;李锋等[8]综合考虑行驶距离、行驶时间等因素,设计了一个模拟退火与遗传算法相结合的多目标混合遗传算法,用于计算得到研究问题的最优Pareto集合;张涛等[9]建立了同时送取货的随机旅行时间车辆路径问题(STT-VRPSPD)的机会约束规划模型,构建了分散搜索算法求解策略;张晓楠等[10]认为需要采用两阶段法解决含有不确定性的问题,即先给出预优化模型的计划方案,在参数的状态明确后再进行实时调整;随后,张晓楠等[11]在需求未明的预优化阶段,基于可信性测度理论建立预优化模型,设计了混合分散搜索和变邻域搜索的变邻域分散搜索算法求解;Zarandi等[12]研究了已知配送中心成本、车辆容量约束、客户需求等的配送时间随机优化问题;Ghaari-Nasab等[13]研究了车辆有容量限制的模糊配送时间的配送优化问题;Singh等[14]为解决区间长度确定问题,提出了一种新的时间序列数据离散化技术,将历史时间序列基于模糊时间序列理论进行模糊化;Yolcu等[15]提出了一种组合的模糊时间序列鲁棒方法,通过评估预测方法的性能来验证方法的正确性;Anastasios等[16]以设计最小成本路线的旅行距离为目标,将服务可靠性纳入路由计划中,建立旅行时间为连续型和离散型随机变量的数学模型;Sumaiya等[17]提出一个新的基于蜂群的人工蜂群算法,用来解决多目标软时间车辆路径问题;Duygu等[18]在目标函数中考虑到与时间窗口偏差成比例的惩罚,通过禁忌搜索算法构造可行的车辆路线.
综上,本文研究的外卖配送优化问题为一类特殊的车辆路径问题,即同时具有不确定旅行时间、服务时间、时间窗约束、同时送取货、动态配送需求、商家-客户位置动态变化的车辆路径问题(Vehicleroutingproblemwithsimultaneouspickupanddelivery,stochastictravelandservicetimes,andtimewindows,anddynamicdemand,VRPSPDSTWD).
VRPSPDSTWD在经典的带时间窗VRPSPD中引入动态配送时间、服务时间、配送需求、商家-客户位置动态变化的概念,考虑了各种时间的概率分析情况,同时模拟了订单产生时间间隔的分布情况以及每个订单的商家、客户位置的分布情况,并以时间惩罚成本衡量车辆到达客户时超出时间窗的情况.
定义目标函数为外卖配送成本增量总和模型,包括:1)新订单的固定配送成本、所有未完成订单的配送成本以及直接去掉已指派但尚未完成订单的配送成本;2)变动成本,定义为额外配送成本和时间惩罚成本之和.
本文求解VRPSPDSTWD问题时,设定配送区域范围,对新订单进行调度时,已指派但尚未完成的订单仍由原车配送,且已将时间惩罚成本作为变动成本修正目标函数,直接去掉时间窗约束,降低算法求解难度.
求解算法采用"商家-客户"配对策略、聚类过程、路径优化策略、随机模拟算法,模型有效性通过R语言仿真测试算例验证.
1问题描述及模型建立本文所研究问题可描述如下:某一外卖配送网络有m1个未调度取货地(商家或发货地)和m2个已调度待取货地(商家),对应的商家集合分别为I1={1,2,m1}和I2={1,2,m2},总的商家集合为I=I1∪I2={1,2,m1+m2},λ个可用车辆,n1个未调度客户(对应m1个未分配商家),n2个已调度未送货客户(对应m2个已分配商家),对应的客户集合为J1={m1+m2+1,m1+m2+2,m1+m2+n1}和J2={m1+m2+n1+1,m1+m2+n1+2,m1+m2+n1+n2},客户集合为J=J1∪J2={m1+m2+1,m1+m2+2,m1+m2+n1+n2},408控制与决策第34卷可用配送车辆集合为K={1,2,λ},所有点的集合为V=I∪J={1,2,m1+m2+n1+n2},V2=I2∪J2,边集合E={(i,j)|i,j∈V},每条边的长度为dij,对应配送成本为cij,模糊配送时间为tij=(t1,ij,t2,ij,t3,ij),客户j(j∈J)的需求量为dj=(t1,j,t2,j,t3,j),服务时间为T_servicej,时间窗限制为[ETj,LTj],每次调度的时间间隔为T.
每个边(i,j)对应唯一客户j,即相同商家要给同一客户配货时,只能由同一辆车来服务,且只服务一次.
如果由多个商家同时配货给一个客户,则虚拟为多个客户.
每辆车在没有新的待取货商家时,只能有一条服务路径,起点为距离最近的待取货商家,终点为最后一个客户的位置.
如当前车辆有已取货但未配送的订单,则假定车辆当前的位置即为商家所在地,每个商家可由多辆车为多个客户服务.
车辆和商家均有容量限制,车辆最大容量为Q,商家最大容量为Pi(i∈I).
单位车辆派遣启动成本为C.
决策变量xijk表示车辆k是否直接服务于边(i,j),如车辆k直接服务于边(i,j),则xijk为1,否则为0;zij表示客户j是否被商家i服务,是为1,否为0;bjk表示客户j是否被指定给车辆k配送,是为1,否为0.
额外变量Tijk表示车辆k经过边(i,j)到达节点j的时间,因其与动态需求和时变配送时间均有关,也具有不确定性.
相应的数学模型为minZ=∑T(∑i∈I∑j∈J∑k∈KC*xijk+∑i∈V∑j∈V∑k∈Kcij*xijk+E(G))+E(FF2)(∑i∈I2∑j∈J2∑k∈KC*xijk+∑i∈V2∑j∈V2∑k∈Kcij*xijk+E(G2)).
(1)s.
t.
∑i∈V∑j∈Kxijk=1,j∈J;(2)xijk=0,i∈V,k∈K;(3)∑i∈IZij=1,j∈J;(4)∑i∈Vxijk∑i∈Vxjik=0,j∈V,k∈K;(5)∑i∈I∑j∈JxijkQ,k∈K;(6)∑i∈I∑j∈J∑k∈KxijkλQ;(7)∑i∈S∑j∈Sxijk|S|1,S∈J,k∈K;(8)∑g∈Vxigk+∑h∈Vxjhk1+zij,i∈I,j∈V,k∈K;(9)TqjkTpik+T_servicei,i∈I,j∈J,zij*bjk=1,p,q∈V;(10)Cr(∑i∈V∑j∈Jxijk*djQ)DPI,k∈K;(11)Cr(∑j∈Jzij*djPi)API,i∈I;(12)xijkzij*bjk,i∈I,j∈V,k∈K;(13)Zij,bjk,xijk∈{0,1},i∈I,j∈V,k∈K.
(14)模型为三维指数约束模型,目标函数(1)为最小化的调度前后变动成本增量,由于固定成本直接与客户数、车辆数、商家数目有关,不管如何指派,调度成本都相同,因此不体现在目标函数中.
变动成本包括额外配送成本和时间惩罚成本,而变动成本增量即为完成所有尚未配送客户J配送的变动成本和上次调度后已指派、尚未配送客户J2的变动成本之差.
由于不确定信息不能提前获知,实际发生的额外配送成本和时间惩罚成本无法计算,故采用随机模拟法估算所有可能场景下的期望值E(FF2)和E(G)代替.
由于当前配送满足以客户需求为首要条件,本文不考虑客户需求超过商家容量限制的情况,故额外配送成本FF2仅受客户集合J2与J1距离的影响.
时间惩罚成本G与车辆实际到达时间超出时间窗限制的延迟或等待时间成比例,即当车辆按照一个可行的计划路径安排到达客户时,早于或晚于客户允许的到达时间区间到达,需支付一定的等待成本或延迟成本.
时间惩罚成本的计算公式如下:G=∑j∈V{cwait*max[(ETj∑k∈K∑i∈VTijk),0]}+∑j∈V{cdelay*max[(∑k∈K∑i∈VTijkLTj),0]}.
(15)其中:cwait和cdelay分别表示车辆延迟或提前到达节点的单位惩罚成本;由于Tijk受不确定需求和旅行时间共同影响,无法预测随机性,也无法给出计算公式,故这里直接由模拟场景中车辆实际访问的上一个节点推算,为上一节点的到达时间外加服务时间再加上两点间的旅行时间.
车辆实际到达时间、时间惩罚成本都受动态需求和随机旅行时间共同影响.
第2期李桃迎等:考虑动态需求的外卖配送路径优化模型及算法409约束条件(2)、(3)保证了每个客户仅有一条服务路径,且相同节点或商家之间均没有路径,约束条件(2)同时保证了边(i,j)唯一对应客户j,当一个客户需要从多个商家送货时,该客户虚拟成多个客户;约束条件(4)保证了每个客户仅被分配到一个商家;约束条件(5)为进出平衡约束,保证了每个节点到达和离开它的车辆数相同;约束条件(6)、(7)表示任一车辆当前的待配送订单数不能超过车辆最大容量;约束条件(8)为标准支路消除约束,S为车辆服务于路线的客户集合;约束条件(9)保证了客户与所属的配送商家有路径相连;约束条件(10)保证了车辆先到达商家i取货,之后到达客户j送货;约束(11)、(12)为车辆容量机会约束;约束条件(13)保证了有直接到达的边必须有服务的商家和配送车辆.
2算法及求解由于VRPSPDSTWD问题为NP难问题,精确算法往往很难在有效时间内求解,启发式算法和混合启发式算法成为热点.
考虑到外卖配送的动态需求,每个人都有可能成为配送客户或商家,所以节点数众多,算法的求解效率与最小成本同样重要.
本文设计"基于聚类分析的遗传算法"求解,即采用"三阶段"方案,第一阶段将所有的商家和客户依据订单进行配对处理,得到"商家-客户"对,第二阶段将之前的"商家-客户"对进行聚类,最后阶段对同一类内的"商家-客户"用遗传算法进行求解,算法简称RC_KMGA算法,其算法流程如图1所示.
图1DC_KMGA算法整体流程2.
1"商家-客户"配对策略将外卖订单的商家、客户按照经纬度进行配对.
如订单j对应的"商家-客户"按照商家位置(经度v1,维度v2)、客户位置(经度v3,维度v4)的方式配对,即向量Vj.
2.
2聚类过程k-means算法是最经典、应用最广泛的聚类分析方法,其目标是使类内距离尽可能小,类间距离尽可能大.
本文采用k-means算法对"商家-客户"进行聚类,聚类的数目即为配送车辆的数目.
由于待聚类对象的维度均为经纬度值,各属性的量化标准相同,无需考虑加权问题,且外卖各商家、客户的配送都属于同城内小区域的配送,因此聚类过程中采用欧氏距离不会对聚类结果产生影响.
成本函数F表示为类内距离平方和与类间距离平方和之比,见下式:F(C,T)=∑1lk∑i∈D∑j∈Vτij(vjicli)2∑1lk∑i∈Dτij(vicli)2.
(16)其中:D=1,2,3,4表示待聚类对象的4个维度集合;vji表示对象j的第i维的值;cl表示离对象j最近的类中心;cli表示cl第i维的值;τlj表示对象j是否属于类l,是为1,否为0.
本文的各维对类的重要性相同,且一个对象属于各个类也无偏好.
考虑到传统k-means算法对初始聚类中心的选取比较敏感,中心选取不当时会大大影响迭代次数.
鉴于此,设计密度和网格方法来产生初始聚类中心,改进后的k-means算法具体步骤如下.
Step1:初始化聚类数目k=λ0(λ0=min∞{有效车辆数,当前未完成订单数}).
Step2:初始化k个聚类中心:Step2.
1:对Vj的每个维度i∈D,在其取值范围内求取f=INT(√k)(√k1Q,则保留该类中离中心最近的Q个对象,其他|cl|Q个对象赋给距离次近的类,如果次近的类中对象数已达Q,则转到第3近的类,以此类推,同时调整对应的τlj值.
Step5:计算目标函数F(C,T)的值,更新各类的中心cli,即每个簇中所有对象的平均值cli=∑j∈Vvji*iτlj∑j∈Vτlj.
(18)Step6:重复Step3Step5,直到连续两次F(C,T)相同或迭代达到给定次数.
综上,初始的k值为min{有效车辆数,当前未完成订单数},且k值会随着待配送订单的数目发生变化.
当订单数较少时(非配送高峰),完全可以由配送员自主选择是否愿意配送;但在配送高峰期,订单数较多(订单数车辆数),k值即为当前有效车辆数,因为所有订单都只能由当前有效车辆来配送.
对于每辆车而言,如何快速给出最优方案并节省配送成本成为外卖平台必须要考虑的问题,这也是本文的出发点.
该算法将每个类看作一辆车,类cl中所有对象涉及的商家和客户的配送均由同一辆车来完成,商家即为取货地,客户即为配送地.
2.
3路径优化策略按照上文中的聚类方式,可以确定车辆与订单(商家、客户)直接的配送关系,之后对于每辆车,需要寻找最优配送策略.
本文采用的策略如下.
1)编码形式.
构造一个包含p个基因(p为该车辆要配送的订单数)的解编码,其中每个订单i对应一个基因,每个基因包含2个解编码,前一位为商家i的序号,后一位为客户i的服务序号,p个基因按照商家被车辆服务的顺序排列.
图2是某车对6个订单配送的简单例子,其中方形为商家,圆形为客户.
图26个订单、1辆车对应的解编码形式2)邻域寻优策略.
设计3种寻优策略:交叉、交换和逆序.
交叉和交换主要用于优化商家、客户的服务顺序,交叉是互换随机选择两个基因的商家序号值,交换是互换随机选择的两个基因的商家序号、客户服务顺序,逆序是逆序排列随机选择的两个基因之间的商家序号值.
图3为对应图2的3种寻优策略可能产生的领域解.
图33种寻优策略每次迭代采用蒙特卡罗法(概率法)随机选择3种策略之一构造邻域寻优策略.
令3种寻优策略的选择概率分别为β1、β2、β3,满足β1,β2,β3∈[0,1],且β1+β2+β3=1.
产生的邻域可能是可行解,也可能是不可行解(如图3中交换后的邻域),不可行解引入罚函数修正.
2.
4随机模拟算法考虑到外卖配送基本是在行政区域或外卖商圈进行,对配送区域进行划分时,针对远距离的外卖需求较少,只需要模拟一个区域的外卖订单需求及其配送情况.
同时,外卖订单主要集中在午饭、晚饭的时间范围内.
随机模拟具体步骤如下.
Step1:模拟产生外卖订单需求.
在某个时刻的外卖订单数qt用高斯分布来模拟如下:qt=INT(0.
01*S√2πσe(t)22σ2).
(19)其中:S为该区域办公人员的总数,为外卖订单的高峰时刻,σ为外卖订单需求数变动的扁平程度,INT(·)为下取整函数.
由于午饭高峰期出现在12点,晚饭高峰期出现在18点,中午外卖订单高峰时刻均值=12,晚上=18.
同时,结合外卖订单变化情况,设置σ=0.
5,即68.
2%的外卖配送都出现在峰值前、后半小时内,95.
4%的外卖配送都出现在峰值前、后1小时内.
Step2:模拟产生订单位置.
针对t时刻的订单需求数qt,迭代随机产生每个订单的商家、客户经纬度.
Step2.
1:将所有区域内商家的经、纬度均匀划分为M等分,客户的经、纬度分别均匀划分为N等分,因此商家所在区域被划分为M2个单元,客户所在区域被划分为N2个单元.
一般小区域范围内,可以将经、纬度距离转成直线距离(或GIS中测算的距离),也可按照覆盖该区域内东西、南北方向的长方形均匀地划分成M2个单元.
通常情况下,商家或客户的第2期李桃迎等:考虑动态需求的外卖配送路径优化模型及算法411一个单元面积约为0.
25km2,且单元的中心代表该单元内商家或客户的位置.
Step2.
2:生成(0,1]范围内的随机数α1和α2,INT(α1M)、INT(α2M)记为订单商家所在单元的经、纬度.
Step2.
3:生成一个(0,1]范围内的随机数α3和α4,INT(α3M)、INT(α4M)记为订单客户所在单元的经、纬度.
Step2.
4:重复Step2.
2Step2.
3,共qt次.
Step3:设定车辆动态位置.
针对t时刻的新订单,迭代随机产生每个车辆的当前经纬度.
如车辆处于空闲状态,则指定该车当前位置为默认位置(该区域的中心位置);如车辆在订单配送途中,则依据上一客户位置计算当前位置.
3算例验证及结果分析为了验证RC_KMGA算法求解VRPSPDSTWD问题的有效性,考虑到现有研究中没有结合动态需求的外卖配送的标准测试算例,故本文参照现有外卖O2O配送平台,讨论产生仿真测试集,并给出计算结果.
3.
1测试问题及参数设置基于模型和问题,以及算法的效率,假设该区域内办公人员数S为1000人;车辆在每条边上的运行相互独立且平均速度v相同,为30km/h(0.
5km/m);模糊配送时间tij=dij/v的(0.
75,1.
0,1.
25);车辆的启动成本C为2RMB;每条边对应的配送成本cij为模糊配送时间乘以单位时间成本;考虑外卖配送的实际情况,cwait=0,T_servicej为2m,配送时间窗[ETj,LTj]为(0,30];测试时间为[10:00,14:00];区域范围内商家、客户的经、纬度分别平均分为10个区域,标号为{1,2,10};实验采用R语言在PC机上运行(i7-4800MQ处理器,16G内存,Windows864位操作系统).
通过与经验丰富的外卖调度优化人员的共同商榷,结合实际参数情况,构建8组测试集,记为{R1,R2,R8},具体测试集的属性如表1所示.
同时不失一般性,为邻域搜索策略选定6组参数选择方案,见表2.
表1测试集的参数设置测试集测试集属性车辆数λ/辆订单间隔时间ti/mcdelay/(RMB/m)车辆容量Q单位时间成本uc/(RMB/m)区域范围A/kmR1550.
280.
25R2850.
280.
25R3550.
260.
26R4850.
260.
26R5530.
280.
26R6830.
280.
25R7530.
260.
25R8830.
260.
25表26种邻域选择方案下测试算例重复10次的均值和标准差序号参数取值方案[β1,β2,β3]均值及标准差R1R2R3R4R5R6R7R8meanσmeanσmeanσmeanσmeanσmeanσmeanσmeanσ1[0.
4,0.
3,0.
3]142.
31.
9144.
43.
9136.
79.
0141.
07.
7460.
15.
5237.
911.
1486.
36.
4240.
46.
062[0.
2,0.
2,0.
6]147.
20.
9151.
412.
9150.
24.
8149.
91.
6463.
713.
9242.
83.
4484.
45.
3231.
311.
643[0.
6,0.
2,0.
2]132.
21.
6138.
811.
6137.
76.
6150.
53.
0468.
32.
5227.
25.
7470.
310.
7229.
55.
584[0.
2,0.
6,0.
2]161.
82.
7153.
71.
4135.
08.
7148.
37.
5474.
511.
8239.
211.
3481.
14.
1245.
95.
225[0.
3,0.
2,0.
5]150.
36.
7163.
313.
7135.
66.
9138.
22.
1469.
312.
0239.
211.
3480.
73.
8233.
26.
126[0.
5,0.
2,0.
3]136.
24.
6146.
62.
6132.
34.
9137.
99.
5473.
46.
4244.
34.
0466.
47.
9243.
43.
93.
2计算结果表2同时给出了6种邻域选择方案下8组测试集的10次实验均值(mean)和标准差(σ).
结果显示:方案3中4个算例的均值最小,达到最好解;而方案2中有4个算例的标准差最小,说明该方案的取值较为稳定.
图4设定[β1,β2,β3]=[0.
6,0.
2,0.
2],图4(a)为在ti=3m、cdelay=0.
2RMB/m、Q=8、uc=0.
2RMB/m、A=5km情况下,求解结果随车辆数λ的变化曲线;图4(b)为在λ=8、cdelay=0.
2RMB/m、Q=8、uc=0.
2RMB/m、A=5km情况下,求解结果随订单间隔时间ti的变化曲线;图4(c)为在λ=412控制与决策第34卷8/λ=5、ti=3m、Q=8、uc=0.
2RMB/m、A=5km情况下,求解结果随延迟配送单位时间成本cdelay的变化曲线;图4(d)为在λ=8/λ=5、ti=3m、cdelay=0.
2RMB/m、A=5km情况下,求解结果随车辆容量Q的变化曲线;图4(e)为在λ=8/λ=5、ti=3m、cdelay=0.
2RMB/m、Q=8、A=5km情况下,求解结果随车辆运行单位时间成本uc的变化曲线;图4(f)为在λ=8/λ=5、ti=3m、cdelay=0.
2RMB/m、Q=8、uc=0.
2RMB/m情况下,求解结果随配送区域范围A的变化曲线.
图4求解结果的变化曲线图4的结果显示:1)求解结果先随车辆数λ的增加开始快速下降,随后保持平稳甚至轻微增加.
由此可知,车辆数太少会导致延迟配送成本过高,车辆太多会导致部分车辆利用率较低,7辆车时最优.
2)求解结果随着间隔时间的增加极速下降,之后趋于平稳,该条件主要是模拟客户订单的数量.
结合当前实际情况,每餐配送期单车平均配送20个订单,讨论了间隔时间为3m和5m,在[10:00,14:00]的4个小时内分别会产生169、103个订单的情况.
间隔时间为3m时,8辆车较为合理;间隔时间为5辆车更为合理.
结合各外卖平台的接单情况,3m的间隔时间更为接近实际情况;间隔时间为1m或2m时,产生的顾客数过多,导致配送订单过多,此情况需要划分更细的区域或者增加配送车辆数.
3)8辆车可以按时配送,不存在延迟成本;而5辆车时,求解结果随延迟配送单位时间成本线性增长,说明延迟单位成本与求解结果线性相关,为了降低目标函数,需要尽可能节省延迟成本.
4)求解结果随着车容量的增加而降低,但是在8辆车的情况下,容量大于4时结果不再降低;5辆车的情况下,容量大于14时结果不再降低.
5)求解结果随着单位时间运行成本线性增加,因此需要尽可能地节省车辆的运行时间.
6)求解结果随着区域范围的增大而增大,但是范围较小时,5辆车的结果较好,但随着区域范围的增大,5辆车的配送成本增加较快.
综上,外卖配送优化问题需要着重考虑配送区域范围、区域内配送车辆数、每餐的订单总数及高峰时刻,由此才能确定最优的车辆数,同时确保合理的配送时间、最大的车辆利用率和最小的总成本目标.
本文模型不仅可以弱化偏好值的影响,生成受偏好值影响较小且实时调整变动小的计划方案,还可以稳定偏好值的影响规律,便于决策者找到整体最优的优化方案,非常合理有效.
4结论由于当前缺少有关外卖配送优化问题的研究,本文针对VRPSPDSTWD问题,引入时间惩罚成本,建立了外卖配送成本增量和模型,考虑新订单的固定成本与变动成本,并定义变动成本为额外配送成本和时间惩罚成本之和.
综合考虑多模糊、随机参数的影响,采用"商家-客户"配对策略、聚类过程、路径优化策略、随机模拟算法求解测试算例,验证了算法的有效性,并得出以下结论:1)在VRPSPDSTWD问题中,模糊配送时间、车辆数、订单间隔时间、延迟配送单位时间成本、车辆容量、车辆运行单位时间成本、配送区域范围等每个第2期李桃迎等:考虑动态需求的外卖配送路径优化模型及算法413参数均有可能对配送方案产生影响.
2)本文建立的模型可用于划分配送区域、确定最优车辆数;设计的算法是求解此类问题的较好算法,且可为外卖配送优化问题提供新的求解思路,为外卖配送平台调度者提供辅助决策.
其他模糊外卖配送问题、改进方法、启发式算法和智能优化算法是下一步研究的重点.
参考文献(References)[1]SalhiS,RandGK.
Theeectofignoringrouteswhenlocatingdepots[J].
EuropeanJofOperationalResearch,1989,39(2):150-156.
[2]KaraoglanI,AltiparmakF,KaraI,etal.
Abranchandcutalgorithmforthelocation-routingproblemwithsimultaneouspickupanddelivery[J].
EuropeanJofOperationalResearch,2011,211(2):318-332.
[3]MinH.
Themultiplevehicleroutingproblemwithsimultaneousdeliveryandpick-uppoints[J].
TransportationResearchPartAGeneral,1989,23(5):377-386.
[4]陈萍,李航.
基于时间满意度的O2O外卖配送路径优化问题研究[J].
中国管理科学,2016,24(A1):170-176.
(ChenP,LiH.
OptimizationmodelandalgorithmbasedontimesatisfactionforO2OFoodDelivery[J].
ChineseJofManagementScience,2016,24(A1):170-176.
)[5]王晓文,田新,李凯.
供应链治理结构的影响因素分析—–基于集中式外卖模式的案例研究[J].
软科学,2009,23(7):46-50.
(WangXW,TianX,LiK.
Ananalysisoffactorsinuencinggovernancestructureofsupplychain—BasedontheCaseofDeliverySystem[J].
SoftScience,2009,23(7):46-50.
)[6]KaoEPC.
Apreferenceorderdynamicprogramforastochastictravelingsalesmanproblem[J].
OperationsResearch,1978,26(6):1033-1045.
[7]马慧茹,赵峰,贾利民,等.
基于随机机会约束规划模型的旅行商问题及其求解算法[J].
长安大学学报:自然科学版,2015,35(S1):179-183.
(MaHR,ZhaoF,JiaLM,etal.
Travelingsalesmanproblemanditssolutionalgorithmbasedonrandomchanceconstrainedprogrammingmodel[J].
JofChang'anUniversity:NaturalScienceEdition,2015,35(S1):179-183.
)[8]李锋,魏莹.
求解随机旅行时间的C-VRP问题的混合遗传算法[J].
系统管理学报,2014,23(6):819-825.
(LiF,WeiY.
Hybridgeneticalgorithmforcapacitatedvehicleroutingproblemwithstochastictraveltime[J].
JofSystems&Management,2014,23(6):819-825.
)[9]张涛,余绰娅,刘岚,等.
同时送取货的随机旅行时间车辆路径问题方法[J].
系统工程理论与实践,2011,31(10):1912-1920.
(ZhangT,YuCY,LiuL,etal.
MethodforthestochastictravelingtimeVRPSPDproblem[J].
SystemsEngineering—Theory&Practice,2011,31(10):1912-1920.
)[10]张晓楠,范厚明,李剑锋.
变动补偿的多模糊选址-路径机会约束模型及算法[J].
系统工程理论与实践,2016,36(2):442-453.
(ZhangXN,FanHM,LiJF.
Chance-constrainedmodelandalgorithmforLRPwithmultiplefuzzyvariablesunderchange-reward[J].
SystemsEngineering—Theory&Practice,2016,36(2):442-453.
)[11]张晓楠,范厚明.
模糊需求车辆路径优化及实时调整[J].
上海交通大学学报,2016,50(1):123-130.
(ZhangXN,FanHM.
Optimizationandreal-timeadjustmentforvehicleroutingproblemwithfuzzydemand[J].
JofShanghaiMaritimeUniversity,2016,50(1):123-130.
)[12]ZarandiMHF,HemmatiA,DavariS.
Themulti-depotcapacitatedlocation-routingproblemwithfuzzytraveltimes[J].
ExpertSystemswithApplications,2011,38(8):10075-10084.
[13]Ghaari-NasabN,AhariSG,GhazanfariM.
Ahybridsimulatedannealingbasedheuristicforsolvingthelocation-routingproblemwithfuzzydemands[J].
ScientiaIranica,2013,20(3):919-930.
[14]SinghP,BorahB.
Anecienttimeseriesforecastingmodelbasedonfuzzytimeseries[J].
EngineeringApplicationsofArticialIntelligence,2013,26(10):2443-2457.
[15]YolcuOC,LamHK.
Acombinedrobustfuzzytimeseriesmethodforpredictionoftimeseries[J].
Neurocomputing,2017,247:87-101.
[16]AnastasiosD,PanagiotisPR,ChristosD.
Assessingcustomerservicereliabilityinrouteplanningwithself-imposedtimewindowsandstochastictraveltimes[J].
TransportationScience,DOI:org/10.
1287/trsc.
2017.
0748.
[17]SumaiyaIqbal,KaykobadM,SohelRahmanM.
Solvingthemulti-objectivevehicleroutingproblemwithsofttimewindowswiththehelpofbees[J].
SwarmandEvolutionaryComputation,2015,24:50-64.
[18]DuyguTa,OlaJabali,TomVanWoensel.
Avehicleroutingproblemwithexibletimewindows[J].
ComputersandOperationsResearch,2014,52(A):39-54.
(责任编辑:齐霁)