基于双节点时间窗的外卖配送路径优化研究

王海燕 戴 雪

(福州大学经济与管理学院， 福建福州 350108)

一、引言

随着通信基础设施的完善和移动互联网的迅猛发展，截至2020年6月，手机上网人数达9.32亿，占网民比99.2%。[1]移动支付和移动导航为外卖行业的发展奠定了技术和设施根基，外卖服务己深入大众生活。外卖也由原来的高补贴抢占用户和商家战略转移到提高服务质量上来。配送人员由经验自行规划配送路径会导致顾客不满意，并且配送人员会因此受到惩罚，外卖平台流失客源风险增加、商家订单量也可能随之减少。因此，为外卖规划最优的配送路径具有现实意义。

在外卖行业相关问题研究方面，学者从外卖行业发展现状、平台商业模式、消费者行为、食品安全等问题展开探索。敬小玲等通过SWOT分析法，总结了外卖行业的优势、劣势以及目前所存在的问题。[2]赵雪冉和孙永波对外卖平台商业模式的内涵及特征进行了论述，并分析了目前平台发展存在的问题以及外卖闭环关键因素，为外卖平台的进一步发展提出了相关建议。[3]Yeo et.al,Hu & Chen从消费者满意度水平方面进行了分析。[4][5]取送货问题最早由Desaulniers等在2002年正式给出定义和数学模型，并用启发式算法进行求解。[6]Soumia I等在车辆路径问题中首次引入时间窗概念。[7]Landrieu等研究了禁忌搜索算法求解单一车辆的带时间窗的取送货问题。[8]余建军等在生鲜外卖配送路径研究中，引入灾变操作的遗传算法与节约里程算法进行对比，结果表明改进的遗传算法可以得到更优的组合。[9]

在考虑满足顾客时间窗的外卖配送路径优化研究中，刘旺盛等、李萍等、李桃迎等均在目标函数中考虑顾客节点超时而产生的成本。[10][11][12]而实际情况中，有些销量多，名气大的商家有权要求配送员在规定时间内到达商家点取餐，以保证外卖送达到顾客手中的口感。因此，本文考虑商家和顾客双节点时间窗的外卖配送车辆路径研究，建立车辆运输成本和双节点时间惩罚成本为目标的模型，针对外卖先取餐后送餐、时间窗约束、载重约束、商家和客户节点配对的关系，设计符合外卖配送情景的遗传算法对外卖配送路径进行优化。

二、问题描述和模型构建

(一)问题描述

在外卖配送的过程中，配送员从配送中心出发，去往商家节点取餐，途经所有订单的取送餐节点，且同一订单先取餐后送餐，订单重量不能超过最大载重量，最后从顾客节点还回配送中心。如果配送员超时到达商家节点或顾客节点，均要承担一定的惩罚成本。因此，平台应优化配送路径，尽可能让配送员在时间窗内到达取送餐节点，使成本之和达到最小。

在实际情况中,外卖配送中存在一对多的情形,包括多名顾客向一家商家下单和一名顾客同时向多家商家下单，这大大增加了模型的复杂性。因此设立虚拟点对顾客和商家点需求进行拆分，使得商家节点和顾客节点一一对应。如图1左边，原先顾客1、2向商家1下单，顾客3向商家2、3下订单，出现顾客和商家一对多、多对一情形。引入虚拟点，让每笔订单都只有一对一的商家和顾客。商家1的虚拟点为商家4，顾客3的虚拟点为顾客4，如图1右边所示，使同一订单中商家和顾客达到一一对应，简化模型。

图1 虚拟点示意

(二)问题假设

1. 所有配送车辆一样，即各类参数(电压、载重量、功率、最大行驶里程等)相同。

2. 配送车辆匀速行驶，不考虑天气、交通等特殊情况影响。

3. 配送车辆无最大行驶里程约束。

4. 每份外卖重量已知。

5. 配送中心、顾客、商家的位置已知及其之间为欧式距离。

6. 不考虑特殊订单，比如单个订单的重量超过配送车辆的最大载重量。

7. 为确认骑手能准点出发，准时上班，骑手应先去配送中心集合再开始前往商家点取餐进行配送。

(三)符号定义

A={2,4,6,8,…,2n}：表示所有商家节点(包括虚拟商家节点)集合。

B={3,5,7,…,2n+1}：表示顾客节点(包括虚拟顾客节点)集合。订单数为n，订单取送餐节点配对点为{(2,3),(4,5),(6,7),…,(2n,2n+1)}。

N=A∪B:商家节点和顾客节点集合。

C={1}∪A∪B：表示所有点集合，1表示配送中心。

K={1,2,3,…,m}:表示配送车辆集合，k∈K。

ETik：平台规定配送车辆k到达节点i的预计时间，i∈N。

tik:配送车辆k到达节点i的实际时间，i∈N。

Tik:表示配送车辆k在节点i处的服务时间;i∈N。

dij:表示节点i与节点j之间的距离;i∈C,j∈C。

vk:表示配送车辆k平均配送速度;k∈K。

tijk:表示配送车辆k从节点i到节点j的行驶时间，tijk=dij/vk，i∈C,j∈C,k∈K。

bi：顾客点i的送餐量，i∈B。

di：商家点j的取餐量，j∈A。

wijk：配送车辆从离开节点i之后到达节点j之前的载重量，i∈N,j∈N,k∈K。

Q:表示配送车辆的最大装载量。

e:表示配送车辆单位距离的运输成本。

c1:在取餐节点超时的单位时间惩罚成本。

c2：在送餐节点超时t分钟内的单位时间惩罚成本。

c3：在送餐节点超时t分钟外的单位时间惩罚成本，c3>c2。

决策变量：

(四)模型构建

从外卖平台的角度考虑，建立车辆运输成本和时间惩罚成本为目标的模型。

(1)车辆运输成本：

(1)

(2)时间惩罚成本：对于取餐节点超时，超时越长，惩罚成本越大；而送餐节点超时存在两种情况，超时在t分钟内(一般超时)，处于顾客可容忍的时间范围，此时单位时间惩罚成本为c2，而超时超过t分钟外(严重超时)，顾客不满意度加强，此时单位时间惩罚成本为c3(c3>c2)。因此所有订单在取餐节点以及送餐节点超出规定达到时间而产生的成本之和表达式为：

(2)

目标函数：

(3)

约束条件：

式(4)表示每笔订单仅被一辆配送车辆服务一次；式(5)表示一笔订单的取送餐只能由一辆车辆k完成；式(6)表示先取餐后送餐；式(7)表示车辆动态载重平衡；式(8)表示最大载重约束；式(9)表示配送车辆k的取送餐总量相等；式(10)表示配送车辆在每个节点时间计算式；式(11)表示配送车辆k从配送中心出发到达的下一个节点必须是去商家节点取餐，最终必须从顾客节点回到配送中心。

三、求解模型的遗传算法设计

Step1 编码生产：采用自然数编码，把商家和顾客点按照不重复的自然数随机排列。商家和顾客经过虚拟化处理后，设订单数为n，则商家和顾客点都为n，设商家点集合为偶数A={2,4,6,…,2n}，顾客点集合为寄数B={3,5,…,2n+1}，并设配送中心为1。订单配对点{(2,3),(4,5),(6,7),…,(2n,2n+1)}。

Step2 初始化种群：外面配送路径优化与传统的路径优化区别之一在于配送员要严格遵循“先取餐,后送餐”的顺序原则。因此在同一订单中，保证商家在前、顾客在后的顺序随机放入基因中。例如以三笔订单(2,3),(4,5),(6,7)为例，随机生成一条基因4-6-5-2-7-3，保证基因次序的合理性。

Step3 确定适应度：适应值为目标函数的倒数。

Step4 选择：采用轮盘赌选择。

Step5 交叉：随机选择两条染色体采用部分匹配交叉法(PMX)的交叉方法，保证每条染色体的基因只出现一次，并淘汰交叉后不符合配对点顺序的染色体，符合外卖配送要求。交叉过程如图2所示。

图2 交叉过程示意

最后，淘汰不符合配对点顺序的染色体。例如交叉结果中2-5-6-3-8-7-4-9，商家节点4和顾客节点5是订单配对点，应先到点4取餐再去点5送餐，所以不符合要求，将其淘汰。交叉结果的另一条染色体2-8-4-5-6-7-3-9符合要求。

Step6 变异：商家点和顾客点存在一一对应关系，因此需要对同一订单的配对点同时进行交换变异。例如染色体8-4-9-5-2-6-3-7，选取订单1、2，对应配对点{2,3}、{4,5}，为保证每笔订单次序合理性，2和4交换位置，3和5交换位置，形成变异后的子代染色体8-2-9-3-4-6-5-7。

Step7 终止条件：迭代到设定的最大迭代次数，则终止循环。

四、算例研究

为验证算法和模型的有效性，本文选取福州大学旗山校区周围的10个商家节点和10个客户节点来模拟一位配送员的配送情况。通过百度地图坐标拾取器获得经纬度，将经纬度换算成实际距离。[13]外卖订单相关信息如表1所示。配送中心坐标为(3317,5328)。由数据可以看出，商家点坐标有两个是一样的，这是因为两位顾客同时向一位商家点下单。

表1 外卖订单信息及取送餐规定时间

根据实际情况，设置模型所需要的具体参数如表2。

表2 模型及算法参数

由于算法设计，轨迹图中，1为配送中心，偶数为商家，奇数为顾客，10和12为同一商家，就用10表示；14和16为同一商家，用14表示，得到了一条最优的外卖配送路径：1-2-4-3-10/12-14/16-18-20-5-8-11-6-17-9-19-7-21-13-15-1，配送距离为19.9166km，超时惩罚成本为1.0889，总配送成本为11.0472元，配送路径如图3所示。

图3 算例优化配送路线

为验证模型及算法的有效性，对比取餐后立即对其进行送餐的单批配送和先全部取餐后送餐的聚集配送两种方案[14],结果如表3所示。对于聚集配送，因为配送车辆最大载重为12kg,所以进行了两次聚集配送。配送距离比本文优化模式下少行驶2.5km，但超时成本却远大于优化模式下的超时成本。对于一取一送下的单批配送，订单较多情况下会出现严重超时现象，配送距离与超时成本都劣于优化模式。综上对比，本文构建的模型和算法对外卖配送路径优化研究是有效的。

表3 三种送餐方法下的配送路径

五、结论

本文建立了商家节点和客户节点双节点时间窗约束以及严格的先取餐后送餐的配对点配送顺序的外卖配送路径优化问题研究的数学模型，并使用遗传算法完成求解，通过实例验证其可行性。最后，与单批配送和聚集配送进行相比，进一步证明了本文配送模型的有效性。

本文建立外卖配送模型并进行了简化，现实外卖配送中存在各种情况，如随时出现新订单，需要对新出现的订单和未完成的订单进行重新规划路径，以达到最优。接下来将研究随时出现新订单的动态外卖路径。

注释：

[1] 中国互联网络信息中心发布第46次《中国互联网络发展状况统计报告》，《国家图书馆学刊》2020年第6期。

[2] 敬小玲：《“互联网+”背景下外卖行业发展分析》，《市场研究》2018年第1期。

[3] 赵雪冉、孙永波：《外卖O2O平台商业模式分析及发展对策》，《商业经济研究》2017年第3期。

[4] Yeo V.C.S., Goh S.K., Rezaei S., “Consumer experiences; attitude and behavioral intention toward online food delivery (OFD) services”,JournalofRetailingandConsumerServices, vol. 35, no. 5(2017), pp. 150-162.

[5] Hu J.X., Chen X.Y.,“Study on the satisfaction of consumers with online ordering services and its influencing factors in O2O mode: a microcosmic perspective on the provision of takeout services”，InternationalJournalofResearchinSocialSciences, vol. 63, no.8(2018), pp. 230-253.

[6] Desaulniers G.J., Desrosiers A., Erdmann M.M., Solomon F.,“The VRP with pickup and delivery”,EuropeanJournalofOperationalResearch, vol. 33, no. 4(2002), pp. 225-242.

[7] Soumia I., Gendreau M., Potvin J.Y.,“Diversion Issues in Real-Time Vehicle Dispatching”,TransportationScience, vol. 34, no. 4(2000), pp. 378-399.

[8] Landrieu A., Mati Y., Binder Z.,“A tabu search heuristic for the single vehicle pickup and delivery problem with time windows”,JournalofIntelligentManufacturing, vol. 12, no. 5-6 (2001), pp. 479-508.

[9] 余建军、程文琪、吴永忠：《考虑顾客满意度的生鲜外卖路径规划》，《工业工程与管理》2021年第4期。

[10] 刘旺盛、吴球军、严浩洲、敬添俊：《带硬时间窗的外卖配送车辆路径问题》，《集美大学学报》(自然科学版)2020年第6期。

[11] 陈 萍、李 航：《基于时间满意度的O2O外卖配送路径优化问题研究》，《中国管理科学》2016年第S1期。

[12] 李桃迎、吕晓宁、李 峰、陈 燕：《考虑动态需求的外卖配送路径优化模型及算法》，《控制与决策》2019年第2期。

[13] 曾富全、庞 咏：《坐标系转换及相关问题的探讨》，《云南地质》2017年第2期。

[14] 丁艳慧：《美团外卖配送模式选择研究》，硕士学位论文,南京大学,2018年。