基于“动态电子围栏”的即时配送路径优化研究
2020-09-26刘娇田育灵陈嫣叶紫魏荣华
刘娇 田育灵 陈嫣 叶紫 魏荣华
摘 要：即时配送与传统快递有着较大区别，从事即时配送的物流企业和配送员都面临着延迟送货等问题。本文从中途接单出发，基于位置、时间等限制，化时间窗约束为距离约束，引入两层“动态电子围栏”，构建了解决“在配送途中车辆运力有余时是否接下途中出现的新订单”问题的模型，并利用C#开发技术编程验证了模型的有效性。
关键词：即时配送;路径优化;中途接单;动态电子围栏
一、引言
随着生活节奏的加快和“懒人经济”的兴起，社会对即时配送的需求越来越大，其业务范围也由生鲜食品延伸至药品、文件资料等。然而几乎所有电商和配送员都采取“来者不拒、一律接单”的态度，延迟送货时有发生，服务效率低下。在此背景下，许多学者都对即时配送路径优化展开了研究。
张宁通过引入出租车作为补充运力，建立了即时配送问题的整数规划模型。金垚炜针对无人机城市即时配送的定位及路径优化问题，提出了无人机城市即时配送LRP二层规划模型。王征、李婷玉等建立了基于多样化方案池的即时配送订单实时响应方法和基于多预测场景的在线优化调度方法。赵琨、史艳华等构建了满足配送时间窗下的以配送员每次配送收入最大为目标函数的模型。慕静、杜田玉等对时间窗进行模糊化处理，构建客户满意度函数，以最大化众包物流配送人员的收益和客户满意度为目标，建立了众包物流运力调度模型。
以上研究都是在取货位置固定的情况下，对已有订单的筛选、合并和再分配以实现配送成本最低、收益最高等目标。而针对取货点位置不固定的研究则很少，但众包配送中基于社会闲散运力的配送模式的取货点大多不固定，这种模式也存在着延迟配送等问题。在此方面，赵兴龙从网络优化的角度出发，建立了带有时间窗的众包配送路径基本优化模型和动态优化模型。
而本文则从单个配送员的角度出发，构建了解决“在配送途中车辆运力有余时是否接下途中出现的新订单”问题的模型，并利用C#开发技术编程进行了实验验证。
二、问题分析及路径优化模型
1.问题分析
（1）问题描述
“中途接单”问题可以描述为：在一次配送任务中，车上现有n个货物，送货点分别为P1、P2……Pn，配送员依次配送n个货物，直至貨物全部配送完。在配送途中，产生了一些新订单。新订单和车上已有货物都有各自的配送时间窗，若配送员能在规定时间窗内完成已有货物和新订单的配送，则接下新订单可增加配送员的收益，反之，接下新订单不仅不会增加收入，还会影响顾客满意度、信用评分，甚至使配送员受到惩罚。
（2）问题的动态性分析
该问题极具动态性，下面通过案例进行说明。
如图1所示，某时刻，配送员在P0处，车上现有4个货物，送货点分别为P1、P2、P3、P4，字母上方的数字为货物的剩余配送时间，路径上的数字表示从一个点到另一个点需要的时间。
该时刻，订单A出现了，其取货点和送货点分别为Q1和Q2。若接下订单A，现有货物和新订单都能在相应时间窗内完成，配送员收益增加。
但若出现的订单不是A，而是订单B（见图2）、订单C（见图3）和订单D（见图4），则不能接单，因为接下订单B，C，D会分别导致货物3、4和订单D延迟送达。
2.问题解决框架
问题的动态性使传统精确算法难以达到及时响应的时效性要求，为此，本文提出了基于“两层动态电子围栏”的问题解决框架，如图5所示。其中：
第一层“动态电子围栏”：
以新订单出现时配送员位置和车上时间最紧的订单的送货点为定点，以最短剩余配送时间内所能行走的距离为定长的不规则区域。
第二层“动态电子围栏”：
以路径中仅次于Q1的送货点
3.基于“动态电子围栏”的即时配送路径优化模型
假设配送车辆以速度u匀速行驶，车上已有n个货物，其送货点为Pi（i=1，2，…，n），坐标为（xi，yi），质量为mi，体积为vi;配送员的实时位置为P0，其坐标为（x0，y0）。
某时刻出现了一个新订单Q，其取货点和送货点分别为Q1（xq1，yq1）和Q2（xq2，yq2），质量和体积分别为mq和vq。则基于“动态电子围栏”的即时配送路径优化模型可以描述为：
其中，i满足i=1，2，…，n，
模型中的符号含义如下表所示。
三、实验求解及结果分析
本文利用开C#发技术编程实现了基于“动态电子围栏”的即时配送路径优化模型的算法程序，并进行了实验验证。
1.实验参数设置
如图6所示，研究区域为30km×30km的矩形城市区域，车辆以30km/h的速度匀速行驶，配送车辆的额定载重为10kg，额定容积为36L，初始位置为（15.0，15.0），此时车上已有三个货物，其重量、体积、取货点、送货点及配送时间窗如图所示。
2.实验结果及分析
在程序运行前，先生成一些数据作为待判断的新订单。在一组数据中，程序一旦检测到有效订单，便不再检验后续订单，而是重置配送员的位置和已有货物信息。将程序运行20次的结果绘制成路径，如图7所示。
由图7可知，路线集中在出发点附近，因此可认为配送员靠近出发点对配送订单是有优势的，当路线远离出发点时，程序会自动筛选新订单以纠正路线使之逐渐靠近出发点，形成良好循环，这与美团外卖的配送集中在某一范围类似，实验结果符合实际情况，验证了模型的有效性。
四、结论
1.本研究的创新点
（1）“中途接单”问题的订单筛选解决方案
目前即时配送路径优化的研究集中于对已有订单的合并和再分配，几乎不涉及配送途中车辆运力有余时的接单问题。本文则提供了一种解决方案。
（2）“动态电子围栏”的引入
本文提出的“电子围栏”是由椭圆定义延伸而来，基于位置、配送时间等限制条件的不规则区域。“动态”体现在电子围栏的两个焦点——配送员的位置和即将配送的下个订单的送货点都是实时变化的，所以形成的不规则区域也是动态变化的。
2.未来展望
本文的研究立足于较理想的状态，存在以下问题：
（1）在涉及配送时间的计算中，将配送过程简化成了匀速行驶，但现实情况并不一定能保持匀速。
（2）研究只从单個配送员出发，得到的优化结果只是局部优化。
因此，为更好地匹配现实情况，本研究可从以下两方面进行改进：
（1）综合路网拥堵情况、天气状况等，基于时间线建立车辆的行驶速度函数，使车辆的行驶速度尽可能符合实际情况。
（2）可对多个配送员展开研究，探索全局优化时的情况。
参考文献：
[1]张宁.基于众包物流平台的同城快递配送问题研究[D].大连理工大学，2019.
[2]金垚炜.基于二层规划的无人机城市即时配送定位-路径优化研究[D].浙江工商大学，2018.
[3]王征，李婷玉，侯鑫垚.基于多样化方案池的即时配送订单实时响应方法[J].管理科学，2018（6）：92-103.
[4]赵琨，史艳华，史晓霞.基于遗传算法的即时配送路径优化研究[J].现代商贸工业，2019（5）：31-32.
[5]张延强.基于聚类的大规模即时配送问题研究[D].东华大学，2018.
[6]慕静，杜田玉，刘爽，等.基于即时配送和收益激励的众包物流运力调度研究[J].运筹与管理，2018（5）：58-65.
[7]赵兴龙.基于K-means-遗传算法的众包配送网络优化研究[D].北京交通大学，2016.
作者简介：刘娇（1998.11- ），女，四川南充人，本科在读，从事物流与供应链领域研究
