随机旅行时间的外卖O2O配送车辆路径问题

王帅　赵来军　胡青蜜

摘 要：外卖O2O（Online to Offline）是一种典型的移动互联网商业模式。入驻外卖O2O平台的餐饮企业为增强顾客的配送满意度，需要对其配送服务进行规划设计。文章研究外卖O2O平台上饮食类供应商外卖配送中的车辆路径问题（VRP），通过对外卖配送特点的深入分析，采用模拟方法实现了随机旅行时间分布的准确刻画，以最大化顾客满意度为目标，综合考虑配送过程中的约束要求，建立了随机旅行时间的带顾客需求时间窗的VRP问题的数学模型。基于上海市徐汇区某入驻外卖O2O企业配送服务的算例，利用遗传算法完成求解。结果显示本文算法可以有效计算出响应顾客需求的最优车辆路径，分析了顾客完全满意度区间大小、顾客满意度敏感性以及配送车辆数量等因素对配送方案总体满意度水平的影响，提出了提高外卖O2O配送满意度的建议。并针对外卖O2O商户自负配送模式进行了研究，可为外卖O2O平台上饮食类供应商改善配送和提升顾客满意度提供决策支持。

关键词：外卖配送；车辆路径问题；顾客满意度；随机旅行时间；遗传算法

中图分类号：F252.14 文献标识码：A

Abstract： Takeout O2O（Online to Offline）is a typical mobile internet era business model. To promote customer satisfaction degree， takeout suppliers on the O2O platform need to implement proper service delivery planning. In this paper， we focus on the vehicle routing problem（VRP）during the takeout delivery service. We use the simulation method to model the distribution of stochastic travel time， and build mathematical model with considering all the constraints， to maximize customer satisfaction. In this paper， we take a takeout restaurant in Xuhui District in Shanghai which is on a O2O platform as the example， and use genetic algorithm to solve the VRP. The results show that the algorithm fits well. We test factors to assess the influence to the general customer satisfaction. This paper is based on a mainstream pattern of O2O takeout delivery， the self-organizing delivery. The conclusion can provide referential decision support to takeout suppliers and help them promoting customer satisfaction degree.

Key words： takeout delivery； vehicle routing problem； customer satisfaction； stochastic travel times； genetic algorithm

0 引 言

移動互联网正在深刻改变人们的日常生活，外卖O2O（Online to Offline）则是移动互联时代商业模式的典型。在外卖O2O模式下，外卖配送服务是实现Offline的重要环节，目前仍主要由入驻外卖O2O平台的餐饮企业自行承担。在提供服务的过程中，顾客往往约定外卖送达时间，商家需保障外卖的准时送达，一旦外卖未能准时送抵顾客处，顾客满意度会受到影响，顾客会将不满信息反馈到外卖平台以供其他顾客参考，会损伤外卖提供商的品牌效应，对经营业绩产生不良影响。因此，以最大化顾客满意度为目标，合理高效地组织配送服务对进驻O2O平台餐饮企业经营具有重要意义。

外卖配送服务是典型的旅行时间随机的车辆路径规划问题（STVRP）。配送车辆路径规划问题（VRP）最早是由Dantzig和Ramser[1]提出来的，是指存在一定数量顾客的情况下，由配送中心组织车队向顾客配送货物，组织合理的行车路线方案，并能在规定的约束条件下，实现诸如路程最短、成本最小等目的。VRP问题的一个重要分类就是随机性VRP，这是由于在现实生活中，往往会遇到一些不能精确预判结果、但能够判断结果出现规律的随机事件，而STVRP就是随机性VRP的一种。Laporte等人[2]对STVRP进行研究，提出了一种机会约束模型，并利用分枝割算法完成求解。Park和Song[3]改进了一种确定性VRP的求解算法，并构造了3种启发式算法对STVRP进行求解。近年来，亚启发式算法逐渐被应用到STVRP的求解中[4-6]，而其中具代表性的遗传算法因其能有效解决TSP问题等组合优化问题，越来越被应用到为STVRP问题的求解[7-8]。STVRP的求解的难点之一在于对随机性的处理，前人的研究工作中通常采用假设随机旅行时间服从正态分布的方法，例如谢秉磊[9]利用正态分布假设通过遗传算法求解了STVRP的机会约束模型。这类方法的优点是能够有效简化问题，在通用性问题中具备较强参考意义。但同时也存在不足：第一，这种假设使用同一统计分布（包括参数也相同）刻画每段路程对应旅行时间所服从的统计分布，而现实中即使各段路程对应的旅行时间服从正态分布，其均值、方差等参数也往往存在差异，这样表达与现实存在误差；第二，适用条件受限，真实生活中的大量STVRP问题，其旅行时间服从分布特点与正态分布可能相差甚远。因此，近年来STVRP的研究中更加注重对个性化现实问题的研究，魏明[10]对区域公交车调度的模型及算法进行了研究，戴韬等[11]则利用STVRP理论考虑了船舶航线规划问题，而目前O2O领域的VRP问题研究仍然较少。学界对O2O模式的认识及其物流发展的理解在不断深入。吕晓永[12]对O2O模式下电子商务物流配送现状进行分析并提出了相应的对策。张颖春[13]对南京市外卖快餐配送的现状进行了调查了解。赵璐[14]针对有道路限行情形下的集团蔬菜城市配送VRP问题进行了研究并利用遗传算法进行了求解分析。翟恒星[15]针对生鲜O2O电商情形对同城冷链物流配送优化问题进行了研究。对本地O2O商业模式下物流配送的研究近年开始逐渐深入，杨博文[16]等人对O2O餐饮外卖目标市场发展趋势进行了分析，但总体来看，目前外卖O2O情形下的STVRP问题学界的研究仍然较少。

本文所研究的外卖O2O环境下的VRP具有强烈的个性化特点。依据外卖配送特点，本文首先说明外卖O2O环境下的VRP问题是带有需求时间窗的随机旅行时间车辆路径规划问题（STVRP），提出了能够精确刻画随机旅行时间分布的方法，建立了外卖配送VRP模型，进而利用遗传算法完成求解，并进行了灵敏度分析，提出了提高O2O外卖配送满意度的措施。

1 问题描述与分析

1.1 问题描述

本文研究的外卖O2O平台上饮食类供应商的车辆路径问题（VRP）以最大化顾客满意度为目标，具体描述如下：（1）路网中存在单一配送中心，即O2O平台上提供外卖供应的商户；（2）车场多辆摩托车提供外卖配送服务；（3）配送车辆从车场出发，为分布在街区中不同地点的顾客服务，每个顾客仅能由一辆车服务且仅能服务一次，车辆完成全部配送任务后回到配送中心；（4）每个顾客有预设的需求时间窗，当车辆未能在预设的时间窗内抵达时，顾客满意度会受到影响；（5）为了更好地组织配送，餐饮企业一般采用周期配送策略，即每个配送时段集中配送一次，要求车辆从车场出发后尽快返回以响应下一时段配送任务；（6）每辆车所服务顾客的总需求量要在该辆车载货能力之内。由此可见，外卖O2O平台上饮食类供应商的车辆路径问题是带有需求时间窗的随机旅行时间路径规划问题（STVRP）。

1.2 随机旅行时间服从分布刻画

外卖配送车辆为摩托车，受城市道路路况影响小，在道路上的行驶速度可以认为是匀速行驶，其旅行时间随机性的来源主要来自于途中遭遇红灯产生的等待。事实上，配送车辆在遭遇红灯时所经历的等待时间服从均匀分布，假设配送车辆在两点之间行车中经历了n个红灯，则配送车辆在两点之间旅行时间所服从的分布即为n个均匀分布的叠加。

例如，配送车辆从A点前往B点，路程2 500m，车辆行驶速度为1 000m/min，期望遭遇2个红灯形成等待，2个红灯周期分别为1分钟和2分钟，则配送车辆在2个红灯形成的等待时间分别服从均匀分布U0，1与U0，2。为了能够方便计算，将2个均匀分布进行叠加处理。采用模拟的办法：利用Python编程语言随机生成1 000组服从U0，1与U0，2的数组，进行求和得到1 000个数以模拟等待时间；对1 000个数字利用统计软件Minitab进行拟合得到结果如图1所示，即等待时间服从统计分布为N1.052，0.6445。配送车辆匀速行驶的时间为2 500m÷1 000m/min=2.5min，由此得到配送车辆在A、B两点间旅行时间服从分布为N1.052+2.5，0.6445，即N3.552，0.6445。

1.3 顧客满意度刻画

在外卖配送服务中，每个顾客有预设的需求时间点，记为t。而在t前后W时间范围内，顾客满意度不受影响，为100%，该时刻区间可以记为a，b，b-a的大小即为2W。当车辆未能在顾客预设的时间窗内抵达时，顾客满意度会受到影响，满意度随抵达时间远离a，b线性下降至0。因此，顾客满意度随配送车辆抵达时刻的对应关系可以刻画为分段函数，如图2所示，t是a，b的中值，顾客满意度敏感性可用满意度线性变化区间斜率的绝对值K表示。在现实配送情形中，可以出于简化问题需求，将车辆可能遭遇的红灯依据等待时长长短分为数种类型。

2 数学模型

3 算法设计

3.1 算法步骤

本文使用遗传算法求解以上STVRP问题，具体算法步骤如下：

步骤1：生成初始种群；

步骤2：计算种群中各染色体适应度；

步骤3：针对种群中的各染色体进行遗传操作；

步骤4：完成遗传操作之后的染色体生成子代种群，判断是否满足算法终止条件，若已满足则执行步骤5，否则返回执行步骤2；

步骤5：从种群中筛选出适应度值最大的染色体，对其进行解码操作，输出对应的路径规划方案。

3.2 编码方法

本文采用整数编码方法。例如某商家使用m辆配送车辆，存在n个顾客节点n≥m，则用整数1至n表示n个顾客节点，用0表示车场。编码方法分3步完成：第一步，对1至n个顾客节点随机排序生成一组排列；第二步，在n个数字之间的n-1个间隔中，随机选择m-1个间隔插入0；第三步，在排列的首尾两端插入0。这样可得到m个配送路径方案，表示所有配送车辆必须从车场出发，配送完再返回车场。

3.3 初始种群生成

设定种群规模为50，初始种群生成通过多步循环完成，每一次循环包括两步核心步骤：

Step1：依据4.2编码方法随机生成1组路径规划方案。

Step2：检验是否满足约束条件，对通过Step1得到的路径规划方案进行约束条件的逐条检验。若未能够通过全部检验，则该路径规划方案将被放弃，重复Step1；否则，该路径规划方案将成为1条初始染色体，若初始种群规模已达到50，则结束循环，否则，重复Step1。

3.4 适应度函数

遗传算法通过不同染色体适应度函数值比较染色体之间的优劣，在选择过程中淘汰适应度函数值劣者，保留适应度函数值较优者，以达到优胜劣汰目的。本文设计的适应度函数即为目标函数。

3.5 复制、交叉和变异

遗传操作包括复制、交叉和变异。本文复制算子为选取最佳保留的轮盘赌复制法；交叉算子采用了MX1[17]；变异算子则采用随机使用两点交换。

3.6 终止条件

本文终止条件为最大迭代次数法与误差范围综合考虑。本文规定最大迭代次数为5 000，当连续2次遗传操作的目标值变化小于1%或抵达最大迭代次数时，算法终止。

4 数值实验

4.1 参数设置

A餐厅是上海市徐汇区某O2O平台上的餐饮企业，将于某日12：00～13：00时间段内对分布其周边区域内的15个顾客需求点提供外卖配送服务，餐厅共有3辆摩托车配送车辆，每个车辆的装载量为35（包装盒数量）。

在本算例中，图2中W的值为10min，K值为1，数据由某外卖O2O平台入驻餐饮企业提供。顾客和配送中心的位置信息如图3所示；表1显示了各顾客点的需求信息（包装盒数量）和预期抵达时间信息（图2中t值），预期时间为17则表示顾客期望于12：17外卖送抵，表1显示由于受到学生和白领午餐时间的影响，t值基本集中于12：00～12：30之间；表2罗列了可连通各点之间的距离，均来自于地图的真实可行路径距离，其它未在表格中显示的两点间距离表示该两点之间不能够直接相通，配送摩托车车辆在道路上平均速度250m/min，据此可以得到在不考虑红灯引起的等待的情况下车辆在各点之间的旅行时间。出于简化问题，将车辆可能遭遇的红灯分为两种类型：一种红灯在一个周期内红灯时长为1min，即车辆遇到此红灯后等待时间服从U0，1，可称为短红灯；另一种红灯在一个周期内红灯时长为2min，即车辆遇到此红灯后等待时间服从U0，2，可称为长红灯。配送车辆在每两点之间行驶期望遭遇的红灯数量和组合如表3所示，例如：2，1表示车辆在此弧上行驶期望遇到2个长红灯和1个短红灯。根据1.2有关外卖O2O旅行时间分布刻画的分析方法可以得到配送车辆在各段弧上可能发生的旅行时间服从的统计分布，再与不考虑等待情况下匀速运动时间合并，可得到可连通各点之间车辆旅行时间分布如表4所示。

4.2 实验结果

根据4.1中算例数据，设置遗传算法所需参数：初始种群数量为100，交叉率0.3，变异率0.1，求解算例。

由实验结果可知，路径规划方案构成3条回路：0-2-3-4-5-6-7-0，

0-12-11-10-9-8-0，0-13-1-14-15-0（见图4），顾客平均满意度为：84.7%，经检验，实验结果满足各项约束条件。

为了检测算法的稳定性，在0，30之间随机产生10组由15个数字构成数组，用以表示15个顾客点预期配送车辆抵达的时间，均在12：00，12：30时间范围内，利用本文的算法进行求解，结果显示顾客平均满意度介于79%至92%的区间内，与平均值85.2%的差距在±8%以内。这表明本文算法稳定性良好，可以用以求解此类STVRP问题，协助O2O餐饮平台入驻店家完成日常配送的车辆调度和路径规划。

4.3 灵敏度分析

本文主要着重考察以下3个因素对总体配送方案满意度的影响：顾客完全满意度区间大小、顾客满意度敏感性以及配送车辆数量。

根据图2描述，W的大小的2倍表示顾客满意度达到100%的时间窗口宽度；K表示直線斜率绝对值，即顾客满意度在线性变化区间随时间线性变化的速度。因此，W可以用来刻画顾客完全满意度区间大小，K可以用来衡量顾客满意度的敏感性，K值越大表明顾客敏感性越强。接下来考察对顾客完全满意度区间大小和顾客满意度的敏感性对总体配送方案满意度的影响。

（1）考察顾客满意度对总体配送方案满意度的影响。令K绝对值为1，通过改变W大小，观测总体顾客满意度水平随之变化的趋势，表5和图5显示了实验结果。结果显示，总体配送服务质量随顾客满意度时间区间的扩大而增长，但增长变化率不断减小，当W>10后，总体满意度达到85%，满意度提升速度变得极为缓慢。因此，对于商户要通过商业活动如延时送达赠送代金券等活动尽可能诱导顾客的完全满意度区间扩大，以本文算例为例，维持送达时间在客户预期时间±10min以内对保证满意度影响重大。当W从10增加到20的过程中，满意度从85%上升至99%，但配送方案仅在0-2-3-4-5-6-7-0，0-12-11

-10-9-8-0，0-13-1-14-15-0和0-8-9-10-11-12-0，0-7-6-5-4-3-2-0，0-15-14-1-13-0之中切换。这表明即使在商户提供服务的过程中完全满意区间扩大到一定程度，一个相对优化的方案已经出现，即使商户继续致力于改善顾客的完全满意度区间但配送方案并不会发生显著调整，满意度也仅微幅上升，因此商家继续商业活动投入就变得得不偿失。

（2）考察顾客满意度的敏感性对总体配送方案满意度的影响。令W稳定为10，改变K的绝对值大小，观测总体顾客满意度水平随之变化的趋势，表6和图6显示了实验结果。结果显示，调整K值大小路径方案仅发生有2种变化，2种方案对应图6的表现是满意度随K变化的速率存在差异，这反应了顾客在满意度敏感性不同情况下配送方案的差异。同时，满意度随K增大而下降，表明了顾客敏感性越高时商户的配送服务越难以保证高满意度。因此，对于商户而言，通过市场行为去准确描述和改善顾客满意度的敏感性对总体服务质量改善具有重要意义。

（3）考察配送车辆数量对总体配送方案满意度的影响。分别改变配送车辆数量为2、3、4、5、6，得到总体满意度变化如图7所示。结果显示，当使用2辆配送车辆时，平均满意度水平最低，为72%；当使用4辆配送车辆时平均满意度水平最高，为86%；3辆、5辆和6辆配送车辆对应平均满意度水平分别为85%、83%和83%。配送车辆从2辆增加至4辆的过程中，总体满意度水平不断上升，但当使用5辆配送车辆时，可能导致配送车辆过早抵达顾客处，反而引起了顾客满意度下降，而6辆车和5辆车产生的满意度基本持平，这是由于两种配送方案中每辆车负责的顾客数量已经很少，引起的满意度差异也变得更为有限。配送车辆数量从3辆增加至4辆，平均满意度仅增加了1%，考虑到使用4辆配送车辆引起更多的固定成本投入和人员工资成本支出，对于商户而言使用3辆配送车辆是最优选择。需要注意的是，当商家配备更多的配送车辆时，满意度反而下降，这是由整点配送规则引起的，结果表明如果严格按照整点配送策略而非按需配送，则更多的配备车辆反而影响总体满意度水平，由此可以发现外卖配送策略的复杂性：按需配送适合每辆车负责顾客数量极少的情形，而从配送管理规范化和规模化角度讲，以整点配送为代表的周期配送策略更有意义，但需要认真计算配送成本寻找出最为合适的配送车辆数量。

5 结束语

随着移动互联时代的到来，外卖O2O配送正在蓬勃发展，引起了餐饮从业人员和O2O平台的关注。本文研究了旅行时间随机的外卖O2O配送VRP问题。考虑到外卖O2O配送特点，利用模拟方法准确的对旅行时间服从分布进行刻画，并以顾客满意度为优化目标，综合考虑装载量、按时返回、每一顾客点仅被服务一次等限制条件，建立了外卖O2O配送车辆路径问题模型，并对上海市徐汇区某入驻外卖O2O平台餐饮企業配送路径方案进行算例分析。

敏感性分析表明：（1）实验结果显示伴随顾客完全满意度区间不断宽松，满意度提升速度不断放缓，且当完全满意度达到一定宽度时，满意度提升速度变得极为缓慢，同时配送方案也逐渐稳定，这表明在一定商业活动投入后从商家的决策上将已经不发生变化，满意度的进一步提升并不依赖于规划的效率而来自于商业活动对顾客满意度区间特点的影响。（2）实验结果表明在顾客满意度敏感性较强时，即使相同配送方案也将造成满意度降低。因此，餐饮企业在提供配送服务时要努力通过商业活动和市场行为改善消费者的满意度变化特点，一方面提高完全满意度区间，另一方面改善消费者满意度灵敏性；同时也要兼顾成本，在总体满意度水平已经较高的情况下，由于配送方案同样趋于稳定，继续的商业投入变得不再经济。（3）当对配送车辆数量进行改变时，随车辆数量增加时，总体满意度水平先升后降。当顾客总体满意度达到一定程度时，配送车辆越多反而由于可能提前送达导致总体满意度下降。因此，结合考虑到固定成本投入和人员工资成本支出，对商户而言应该选择一个最优的配送车辆数量。本研究为入驻外卖O2O平台的餐饮企业日常运营中车辆配送路径的选择提供决策支持。

本文基于目前全国范围内外卖O2O配送服务的主流形式，即商户自负配送模式进行研究。事实上，在以北上广深为代表的一线城市，目前O2O外卖平台的配送服务正在呈现出新特点，即由外卖O2O平台组建配送团队对商户和顾客提供配送服务。饿了么、美团外卖和百度外卖在内的多家外卖O2O平台巨头企业均在进行自建物流体系的尝试，使得外卖配送服务呈现出了新的特点。因此，对于新形势下外卖O2O平台配送的VRP问题，作者后续将进行进一步研究。

参考文献：

[1] Dantzig G B， Ramser J H. The truck dispatching problem[J]. Management science， 1959，6（1）：80-91.

[2] Laporte G， Louveaux F， Mercure H. The vehicle routing problem with stochastic travel times[J]. Transportation science， 1992，26（3）：161-170.

[3] Park Y B， Song S H. Vehicle scheduling problems with time-varying speed[J]. Computers & Industrial Engineering， 1997，33（3）：853-856.

[4] Chatterjee S， Carrera C， Lynch L A. Genetic algorithms and traveling salesman problems[J]. European journal of operational research， 1996，93（3）：490-510.

[5] Belfiore P， Tsugunobu H， Yoshizaki Y. Scatter search for vehicle routing problem with time windows and split deliveries[J]. Vehicle Routing Problem， 2008（5）：1-14.

[6] 李建，张永，达庆利. 第三方物流多车型硬时间窗路线问题研究[J]. 系统工程学报，2008，23（1）：74-80.

[7] 李向阳. 遗传算法求解VRP问题[J]. 计算机工程与设计，2004，25（2）：271-273.

[8] 张丽萍，柴跃廷. 车辆路径问题的改进遗传算法[J]. 系统工程理论与实践，2002，22（8）：79-84.

[9] 谢秉磊，李军，郭耀煌. 有时间窗的非满载车辆调度问题的遗传算法[J]. 系统工程学报，2000，15（3）：290-294.

[10] 魏明，靳文舟，孙博. 随机旅行时间的区域公交车调度模型及算法[J]. 公路交通科技，2011，28（10）：124-129.

[11] 戴韬，杨稀麟. 考虑时间窗与随机航行时间的船舶航线规划[J]. Computer Engineering and Applications， 2012，48（25）：234

-238.

[12] 吕晓永. O2O模式下电子商务物流配送现状分析及对策研究[J]. 价值工程，2016，35（7）：98-99.

[13] 张颖春，刘爱军. 南京市外卖快餐配送的现状分析与对策思考[J]. 江苏商论，2015（3）：26-29.

[14] 赵璐，赵磊，朱道立. 有道路限行的集团蔬菜城市配送车辆路径问题[J]. 上海管理科学，2013，35（5）：38-45.

[15] 翟恒星. 生鲜O2O电商同城冷链物流配送优化研究[D]. 大连：大连海事大学（硕士学位论文），2015.

[16] 杨博文，王静，段辉. O2O餐饮外卖目标市场发展趋势分析[J]. 科教导刊（电子版），2015（22）：146-147.

[17] Blanton Jr J L， Wainwright R L. Multiple vehicle routing with time and capacity constraints using genetic algorithms[C] // Proceedings of the 5th International Conference on Genetic Algorithms. Morgan Kaufmann Publishers Inc.， 1993：452-459.