外卖配送路径优化问题研究现状与趋势

唐梦影 杨中华

摘  要：外卖配送路径优化问题一直是外卖配送研究领域的难点和热点。由于配送成本在总成本中占有较大的占比，所以至今以来国内外学者不断提出外卖配送路径优化相关的目标及算法的改进以提高配送效率。为了进一步梳理国内外研究现状，文章针对外卖配送路径优化问题的时间窗、取送要求、随机性、开放型等特点特性，分别针对不同类型的外卖配送路径优化问题，从优化目标和优化算法两个方面进行了较为全面的综述。最后，对外卖配送路径优化领域一些新的研究方向进行了展望。

关键词：外卖配送路径优化；带时间窗的车辆路径问题；取送车辆路径问题；随机性车辆路径问题；开放型车辆路径问题

中图分类号：F713.365.1    文献标志码：A    DOI：10.13714/j.cnki.1002-3100.2024.13.010

Abstract： The optimization of takeaway distribution path has always been the difficulty and hotspot in the research field of takeaway distribution. Since the delivery cost occupies a large proportion in the total cost， domestic and foreign scholars have been constantly proposing the improvement of objectives and algorithms related to the optimization of takeaway distribution paths in order to improve the delivery efficiency. In order to further sort out the current research status at home and abroad， a comprehensive overview is conducted from two aspects： Optimization objectives and optimization algorithms for different types of takeaway distribution path optimization problem. The optimization problem of takeaway distribution path is categorized into different types based on its characteristics such as time window， pickup and delivery requirements， randomness， and openness， etc. Finally， some new research directions in this field are prospected.

Key words： optimization of takeaway distribution path; vehicle routing problem with time windows; vehicle routing problem with pickup and delivery; stochastic vehicle routing problem; open vehicle routing problem

0  引  言

近年来，外卖行业发展迅速，各大外卖平台间的竞争日益增强，每单外卖的利润率不断下降，对配送成本的控制成为外卖平台运营的重点问题。外卖配送路径的优化成为外卖平台控制成本、吸引客流量的关键。

外卖配送问题是指顾客在外卖平台上下达订单后，配送员在服务时间窗内根据订单信息先前往对应的商家点进行取餐，然后将餐品送达到客户手中的路径规划问题。与一般的配送问题存在的区别是，外卖配送具有带时间窗、取送要求、随机性、开放型等特点。国内外文献针对外卖配送中的带时间窗约束、取送要求、路网随机性、配送路径开放型等特点分别进行了研究，建立了考虑不同场景的外卖路径优化模型，并提出了针对性的求解算法。本文期望针对不同场景的外卖路径优化问题，从模型的优化目标和算法设计等两个方面对国内外相关文献进行归纳，厘清外卖配送路径优化领域的研究现状，为学者和行业从业人员提供有益的参考与借鉴。

1  带时间窗的车辆路径问题

带时间窗的车辆路径问题（Vehicle Routing Problem with Time Windows， VRPTW）是在传统车辆路径问题上引入时间窗，将客户期望被服务的时间标识出来，从而尽量在客户能够接受的时间内完成配送或取货任务，以提高物流服务水平和服务质量。外卖配送路径优化问题是一种典型的带时间窗的车辆路径问题，在外卖下单成功后，外卖平台通常都对外卖送达客户的时间有着严格的规定。

1.1  优化目标

配送成本和时间满意度通常是带时间窗的车辆路径问题最关注的两个目标。在通常的研究中，学者基于时间窗约束构建时间惩罚成本并将其纳入配送总成本。将定义为类似的，蒋丽等[1]基于商家和顾客的单侧软时间要求，建立了以距离成本和时间惩罚成本之和最小为目标的外卖配送优化模型；余海燕等[2]基于O2O生鲜外卖的硬时间窗要求，解决了配送距离最小为目标的外卖问题。

与此同时，部分研究以最大化客户时间满意度为目标构建模型。基于顾客期望服务时间窗和到达客户时间点之间的关系，陈萍等[3]利用线性函数量化顾客时间满意度，提出了最大化客户时间满意度的单目标问题；在时间窗约束下，翟劲松等[4]构建了配送时间最短的单目标模型；周成昊等[5]将商圈看作配送中心，以快递员数量和快递员总行驶时间为最小化目标；在同时存在取餐节点时间窗和送餐节点时间窗的场景下，高椿林等[6]对员工满意度的影响因素进行了量化分析，并将员工满意度纳入目标函数中，构建了以配送总成本、客户满意度、员工满意度为目标的优化模型。

大多数外卖配送问题将优化目标定义为最大化客户满意度或者最小化配送成本的单目标优化问题，但是也有部分研究构建了多目标优化问题。徐肇元[7]提出了最大化客户时间满意度和最小化配送总成本的多目标问题。

1.2  算法改进

在时间窗约束下，翟劲松等[4]用遗传算法求解了配送时间最短的单目标模型；赵强柱等[8]设计了一种两阶段启发式算法求解无人机骑手联合外卖配送的路径优化模型；其中第一阶段是使用结合K-means的遗传算法，综合考虑顾客地理位置和时间窗要求计算时空距离，对顾客进行聚类，形成骑手初始路径；第二阶段是分别使用改进的变邻域搜索算法和A*算法对骑手和无人机路径进行优化；基于单侧软时间窗的需求，蒋丽等[1]通过设计新的状态转移规则和设置固定阈值来改进蚁群算法，求解需求可延迟的开放式众包配送路径优化问题；在硬时间窗约束下，鞠新诚[9]将配送员对道路的了解程度引入模型中，运用蚁群算法对外卖配送单目标问题进行优化；余海燕等[2]设计滚动时域延迟配送算法，解决了单目标的O2O生鲜外卖配送问题；对于同时存在取餐节点时间窗和送餐节点时间窗的情况，王海燕等[10]基于遗传算法求解包含双节点时间惩罚成本的单目标外卖问题；徐倩等[11]运用改进的自适应大邻域搜索算法求解了多达4 000个节点的、以包含时间惩罚成本的物流配送平台总成本最低为目标的外卖问题。

随着外卖配送的发展，外卖配送的规模逐渐增大，顾客对配送时间的敏感性也逐渐增强。学者们将配送的时间要求引入到了目标函数之中，进行了客户满意度、时间惩罚成本的计算。徐肇元[7]将改进的SWEEP算法和改进的蚁群算法进行结合，运用结合形成的两阶段启发式算法求解了基于客户时间满意度和配送总成本的多目标问题；高椿林等[6]提出基于非支配解集超体积的“HV贡献值”的邻域解评价策略，以及新的拆分和修复算子对自适应大邻域搜索算法进行改进，求解以最小化配送总成本、最大化客户满意度和员工满意度为目标的外卖订单配送路径优化模型。

2  取送货车辆路径问题

在外卖配送过程中，配送员需要根据订单要求先前往相应的商家点完成取货任务，然后将外卖产品配送给对应的客户点，整个过程有着严格的取送次序要求。针对外卖配送的取送特点，学者们也提出了不同的优化模型并以各种求解算法进行了研究。

2.1  优化目标

针对配送车辆服务新需求需返回原点取货的情形，陈嘉俊[12]构建了目标函数为最小化配送时间和总服务成本的优化模型；靳志宏等[13]根据不同站点的情况对取送货任务进行分类安排，并构建了以最大化运输效率为目标的优化模型；熊浩等[14]对取送交叉和外卖配送中多种不稳定因素的实时优化问题进行了深度分析，在优化目标中增加了骑手空驶成本和骑手等待成本两个目标。

2.2  算法改进

对于外卖配送中的取送流程，很多学者设计改进蚁群算法进行求解：蒋丽[1]针对“先取后送”的次序要求，在具有单侧软时间窗的开放式车辆模型中分别设置了单向路径和双向路径，其中，单向路径包含由起点指向商家的和由对应商家指向对应客户的两种路径，双向路径指商家指向不对应客户间的路径；靳志宏等[13]针对离散型场站和聚集型场站分别采取一取一送和多次取餐一次送达的任务安排，并优化了蚁群算法中传统的邻域搜索算子，即用订单显示的成对的商家点与顾客点代替了单个点；鞠新诚[9]构建了考虑骑手对路网熟悉度的多取多送的路径优化数学模型，并开发了三种特殊的邻域搜索算子。

除了改进蚁群算法，学者们也设计了其他算法对外卖配送中的取送问题进行优化。陈嘉俊[12]基于配送车辆服务新需求需返回原点取货的场景，同时考虑到商家会根据顾客位置决定是否进行服务的情况，研究了带有取送货的在线旅行商问题，针对需求点仅在正半轴和需求点在一般网络上分别设计WAO算法和WAE算法；基于配送员在平台上接收来自不同餐厅订单的角度，蔡林等[15]提出了一种具有顺序限制的路径优化算法来实现配送员先取后送的次序要求，该算法首先基于最邻近算法产生初始路径，然后使用LK算法进行优化，最后使用末端-2-opt方法进行二次优化；陈露乾[16]设计了TS-Ropt在线算法来求解实时取送货问题模型，其中，针对取送货需满足先取后送顺序和取送节点成对匹配的要求，分别采用了交换点对算法和内部互换算法来实现路径之间和路径内部的邻域搜素；对于取送交叉和中途接单问题，郭昊颖等[17]设计了考虑订单有序性的初始种群生成方式，随机比对交叉方式和基于订单号的变异方式，对遗传算法进行改进。

3  随机车辆路径问题

由于外卖配送中订单实时出现的动态性特点，近几年越来越多的学者将研究重点关注到了外卖配送中的随机车辆路径问题，以减弱外卖配送中不确定因素对成本和客户满意度的影响。

3.1  优化目标

对于外卖配送中行驶时间不确定的问题，赵向南等[18]假设配送员前往商家和顾客之间的行驶时间满足伽马分布，以运营成本和解的鲁棒性作为优化目标建立优化模型。针对实际路网环境中速度动态改变的情况，杨爱芳[19]利用阶跃函数对速度进行处理，研究了以配送成本和客户满意度作为双目标的单配送中心的外卖配送优化问题。范厚明等[20]针对订单需求的随机和实时性，建立了以超时订单比例、单均配送时间和单均行驶距离为优化目标的动态车辆路径模型。杜丹丹[21]基于一个取餐点，考虑不同时刻商家出餐时间不同的情况，利用AnyLogic仿真软件对商家出餐时间进行了模拟，并在目标函数中增加了车辆超载惩罚成本，构建了以最小化运输成本、时间窗期望惩罚成本及车辆超载惩罚成本之和为目标的规划模型。

外卖配送中的随机因素有很多，一些学者也针对两个及两个以上的随机因素同时进行了研究。李桃迎等[22]针对随机订单需求和随机行驶时间同时进行研究，定义目标函数为外卖配送成本增量总和；其中，对于订单需求随机产生的情形，先采用高斯分布来模拟产生某个时刻的外卖订单数，然后基于订单需求数利用随机数迭代产生每个订单的商家、客户经纬度等信息；而对于随机行驶时间的处理是先假设每条边相互独立且平均速度相同，然后利用每条边的距离除以平均速度对行驶时间进行模糊处理。熊浩等[14]研究了中途接单、临时交通管制、商家出餐时间异常和顾客取餐时间异常四种扰动因素，在目标函数中增加了骑手空驶成本和骑手等待成本两个目标。

3.2  算法改进

外卖配送过程中，动态变化的路网情况导致了随机的行驶速度。肖颖[23]基于同一路段不同时间段配送车辆行驶速度不同的情况，通过设置时间间隔，构建通过时段和路径对实时车速进行匹配的速度分段函数，设计自适应遗传模拟退火算法。针对随机行驶时间的情况，赵向南、邢磊等[18]假设行驶时间满足伽马分布，设计了带有精英策略的非支配排序遗传算法；赵向南[24]通过蒙特卡罗模拟法对不确定旅行时间进行处理，将其纳入外卖配送的混合整数规划模型中，并针对单目标和多目标问题分别设计了禁忌搜索算法和带有精英策略的非支配排序遗传算法进行求解。

外卖配送中不同商家、同一商家不同时间段的餐品准备时间也存在差异。基于随机的订单准备时间，Min-Xia Zhang等[25]采用机器学习的方法利用顾客和商家的历史习惯数据对订单准备时间进行合理预估，设计了混合进化算法，该算法使用水波优化元启发式算法解决订单选择的问题，运用禁忌搜索算法快速优化配送路径；杜丹丹[21]基于一个取餐点，考虑不同时刻商家出餐时间不同的情况，利用AnyLogic仿真软件对商家出餐时间进行了模拟，并设计改进的遗传算法。

外卖配送中订单需求的随机和实时性特点也吸引了众多学者的研究。Yanchao Liu[26]针对外卖配送中订单需求和位置随机的特点，提出使用无人机进行外卖配送的混合整数规划模型，并设计了一种优化驱动的渐进式算法进行求解。陈露乾[16]基于禁忌搜索算法和贪婪算法，借鉴滚动时域策略和再优化策略的思想，设计了TS-Ropt动态在线算法。

外卖配送的实际场景其实是多个随机因素组合出现的情况。近年来很多学者也对多个随机因素同时出现的组合进行了建模与优化。孙宝凤等[27]综合考虑新需求出现、旧需求改变或取消、交通堵塞和配送车辆抛锚四种动态事件的影响，将滚动时域法、禁忌搜索算法和自适应大邻域搜索算法相结合，完善动态算法框架。金玉环[28]同时考虑了取餐时间和行驶时间的随机性，利用排队论建立出餐排队模型确定骑手取餐时间，通过模拟红灯随机等待时间确定行驶时间，设计NSGA-Ⅱ算法求解双目标动态外卖配送路径模型。对于中途接单、临时交通管制、商家出餐时间异常和顾客取餐时间异常四种外卖配送中会出现的扰动情况，熊浩等[14]设计了改进的自适应大邻域搜索算法。

4  开放车辆路径问题

外卖配送车辆路径问题不同于一般的旅行商问题，单个配送员的配送路径往往是不要求从配送中心出发，并且在完成最后一个客户点的配送任务后返回配送中心的，属于开放车辆路径问题。但是，很多外卖配送路径优化的研究中，研究者还是会将其作为旅行商问题处理，以减弱操作难度。为了对这一情况进行改进，近年来，很多的学者也将开放型车辆问题的处理方式运用到外卖配送的优化中。

4.1  优化目标

针对配送员完成所有商家节点配送任务后无需返回起始点的情况，朱桐等[29]构建了最小化总配送成本的外卖配送路径优化模型，其中总配送成本包括距离成本和惩罚成本；王中普[30]以最小化订单服务延迟成本为目标函数，进行了动态开放链的无人机群外卖配送研究。

4.2  算法改进

对于配送员完成最后一个配送任务后无需返回配送中心的情况，蒋丽等[1]添加了配送任务必须在顾客处结束，且配送完无需返回起始点的约束条件，并利用改进蚁群算法求解带有软时间窗的需求可延迟的开放式车辆路径优化模型；蔡林等[15]首先基于最邻近算法产生初始路径，然后使用LK算法进行优化，最后使用末端-2-opt方法进行二次优化来设计具有顺序限制的路径优化算法；朱桐等[29]设计混合遗传算法求解带时间窗约束、配送顺序限制、开放型的外卖配送问题；王中普[30]设计了变邻域模拟退火算法用于动态开放链的无人机群外卖配送研究。

5  结论与展望

本文结合外卖配送的特点从带时间窗车辆路径问题、取送货车辆路径问题、随机车辆路径问题、开放车辆路径问题等四个方面对外卖配送路径优化的研究现状进行了总结和分析，发现：

（1）根据外卖配送的特点出发，从带时间窗、取送货、随机、开放型等几个角度探讨后，发现外卖配送路径优化领域中近几年针对随机车辆路径问题研究的文献较多，其中随机车辆路径问题主要考虑订单需求随机、配送行驶时间随机、订单准备时间随机等三个方面。

（2）在外卖配送路径优化的目标函数方面，随着研究的深入，优化目标也从仅考虑外卖平台的利益扩展到综合考虑平台运营成本、客户满意度、骑手目标等多个方面；优化目标的类型也从早期的最小化配送成本扩展到最小化配送成本、最大化客户满意度、最小化时间惩罚成本、最小化配送距离、最大化员工满意度、最大化配送效率、解的鲁棒性、超时订单比例等多个方面。

（3）在外卖配送路径优化的算法改进方面，随着外卖节点规模的扩大，求解不同问题的元启发式算法被设计和运用的越来越多，以扩大搜索规模提高解的运算速度；针对外卖配送的动态特点，算法中出现了多种算法混合、机器学习、滚动时域算法的运用等方面的改进。

外卖配送路径优化属于组合优化问题，随着外卖需求的持续增加，基于不同场景的新目标和算法也不断被提出，因此建议未来重点关注以下研究问题：

（1）将启发式算法与机器学习进行结合，提高算法对动态场景的适用性。在实践过程中，外卖运营平台很难会针对不同的配送场景运用不同的算法进行求解，所以当算法能根据动态场景的特点自动进行调整时，就能更好地针对不同的环境进行配送路径的指导。

（2）加强对动态场景下多目标权重设定的研究。不同场景下侧重的目标往往会不同，以顾客时间窗为例，当配送时间超出时间窗时，有的顾客可能会接受赔偿的方式，而有的顾客可能会直接选择取消订单，所以要针对不同的情况对同一目标赋予不同的权重。

（3）外卖配送过程中多种扰动因素的组合研究。外卖配送的过程中存在多个潜在的扰动因素，应对可能出现的扰动因素组合预测并进行场景的划分，以尽可能小地减弱扰动因素对配送时间的影响。

参考文献：

[1] 蒋丽，王静，梁昌勇，等. 基于改进蚁群算法的众包配送路径研究[J]. 计算机工程与应用，2019，55（8）：244-249.

[2] 余海燕，唐婉倩，吴腾宇. 带硬时间窗的O2O生鲜外卖即时配送路径优化[J]. 系统管理学报，2021，30（3）：584-591.

[3] 陈萍，李航. 基于时间满意度的O2O外卖配送路径优化问题研究[J]. 中国管理科学，2016，24（S1）：170-176.

[4] 翟劲松，台玉红. 基于时间窗约束下的外卖配送路径优化[J]. 物流科技，2018，41（3）：15-18.

[5] 周成昊，吕博轩，周翰宇，等. 以商圈为中心的O2O动态外卖配送路径优化模型与算法[J]. 运筹学学报，2022，26（3）：17-30.

[6] 高椿林，张维存，许建. 考虑员工满意度的多目标外卖订单配送路径优化研究[J]. 河北工业大学学报，2023，52（1）：86-96.

[7] 徐肇元. 基于两阶段启发式算法的多目标外卖配送优化分析[J]. 测试技术学报，2019，33（4）：340-345.

[8] 赵强柱，卢福强，王雷震，等. 无人机骑手联合外卖配送路径优化问题研究[J]. 计算机工程与应用，2022，58（11）：269-278.

[9] 鞠新诚. 考虑骑手对路网熟悉度的O2O外卖配送路径优化[D]. 大连：大连海事大学，2020.

[10] 王海燕，戴雪. 基于双节点时间窗的外卖配送路径优化研究[J]. 福州大学学报（哲学社会科学版），2021，35（6）：42-46.

[11] 徐倩，熊俊，杨珍花，等. 基于自适应大邻域搜索算法的外卖配送车辆路径优化[J]. 工业工程与管理，2021，26（3）：115-122.

[12] 陈嘉俊. O2O模式下配送车辆实时路径选择研究[D]. 重庆：重庆邮电大学，2019.

[13] 靳志宏，鞠新诚，郭加佳，等. O2O模式下外卖骑手的配送路径优化[J]. 大连海事大学学报，2019（4）：55-64.

[14] 熊浩，郭昊颖，鄢慧丽，等. 考虑取送交叉和多种扰动因素的外卖配送路径优化研究[J]. 湖南大学学报（自然科学版），2022，49（10）：92-102.

[15] 蔡林，李英冰，邹子昕. 路径优化算法在外卖配送中的应用[J]. 测绘通报，2019（11）：22-25.

[16] 陈露乾. 基于实时订单的O2O外卖实时取送货路径优化[D]. 北京：北京交通大学，2021.

[17] 郭昊颖，熊浩，任汭杨，等. 允许取送交叉和中途接单的外卖配送路径优化[J]. 系统工程，2022，40（5）：70-81.

[18] 赵向南，邢磊，靳志宏. 考虑不确定行驶时间的双目标外卖配送路径优化[J]. 大连海事大学学报，2019，45（4）：65-72.

[19] 杨爱芳. 外卖配送路径优化研究[D]. 西安：西安电子科技大学，2020.

[20] 范厚明，咸富山，王怀奇. 动态需求下考虑订单聚类的外卖配送路径优化[J]. 系统仿真学报，2023，35（2）：396-407.

[21] 杜丹丹. 考虑商家出餐时间的外卖即时配送优化研究[J]. 物流工程与管理，2023，45（5）：138-142.

[22] 李桃迎，吕晓宁，李峰，等. 考虑动态需求的外卖配送路径优化模型及算法[J]. 控制与决策，2019，34（2）：406-413.

[23] 肖颖. 时变路网下M公司外卖众包配送派单及路径优化研究[D]. 重庆：重庆大学，2021.

[24] 赵向南. 考虑不确定因素的外卖配送路径优化研究[D]. 大连：大连海事大学，2020.

[25]  ZHANG M X， WU J Y， WU X， et al. Hybrid evolutionary optimization for takeaway order selection and delivery path planning utilizing habit data[J]. Complex & Intelligent Systems， 2021（8）：4425-4440.

[26]  LIU Y. An optimization-driven dynamic vehicle routing algorithm for on-demand meal delivery using drones[J]. Computers & Operations Research， 2019，111：1-20.

[27] 孙宝凤，杨悦，史俊妍，等. 考虑真实场景动态事件的动态取送货问题[J]. 浙江大学学报（工学版），2020，54（8）：1604

-1612，1644.

[28] 金玉环. 考虑随机时间的外卖配送路径优化研究[D]. 西安：长安大学，2021.

[29] 朱桐，江欢. 基于遗传算法的外卖配送路径优化研究[J]. 轻工科技，2020（12）：51-53，93.

[30] 王中普. 基于动态开放链的无人机群外卖配送路径优化研究[D]. 沈阳：沈阳建筑大学，2022.