路径优化算法在外卖配送中的应用

蔡 林，李英冰，邹子昕

(武汉大学测绘学院，湖北 武汉 430079)

外卖O2O近年来得到极大发展，但其主要矛盾在于对速度掌控力较弱，如何合理安排配送路线是主要因素[1]。如何从配送员或整个外卖配送网络的角度提高运送的速度，一直是值得研究的问题，而提高速度可通过对配送路线进行优化，达到辅助外卖配送决策与提高配送效率的目的[2]。

配送路线优化的出发点是要帮助配送员选出最优或较优路线方案，高效率地去往不同餐厅点和客户所在地，从而节省配送时间，提高消费者满意度。许多学者在这方面展开了相关研究。文献[3]通过分析餐饮O2O外卖客户满意度的特点，基于传统的取送货车辆路径问题模型，提出一个适合餐饮O2O外卖配送的优化模型，并提出了能够有效求解该模型的启发式算法，尽可能提高大量客户的时间满意度。文献[4]通过利用联合调度解决预订模式和即时模式下的外卖生产配送问题，将多车多路径配送和时间窗约束引入生产配送联合调度模型中，主要为订餐高峰期商家进行订单处理提供决策支持。文献[5]设计一种考虑动态需求的外卖配送路径优化模型及算法，基于同时送取货VRP问题的求解策略,引入时间惩罚成本等,通过将商家与客户进行配对，并对其进行聚类，对同一类设计遗传算法，从而获得启发式路径优化方案。针对外卖配送的安全性，文献[6]利用烟花算法解决在其情况下的路径优化问题。

目前现有大多数文献均从多配送员多订单的外卖配送网络角度进行研究，没有考虑从一个配送员在平台上已接收的自不同餐厅订单的角度出发，速度一定的情况下，以时间最短为目标确定最优配送路线。因此本文从配送员角度出发，提出一种具有顺序限制的最短路径优化算法，以达到对配送员到达餐厅点和客户点的先后顺序进行协调安排的目的。

1 外卖配送路径的问题描述

外卖配送问题实际上是一个特殊的TSP问题(旅行商问题)，TSP是路径规划及组合优化领域的NP问题。问题的大致描述是：假设一个商人要拜访n个城市，必须选择所要走路线，路线限制条件是每个城市只能拜访一次，且最后要回到原来出发的城市。路径的选择目标是要求的路径路程为所有路线方案中的最小值。目前已有大量文献对TSP问题进行研究[7]，侧重的研究点主要为结合多种优化机制设计启发式混合算法和提升求解算法的效率与精度[8]。

TSP在实际生活中有许多应用，如旅游路线规划[9]、车间调度[10]、物流配送[11]等，虽然这些问题源于TSP，但又与标准的TSP有所区别。如在物流配送行业，特别是外卖配送行业中，对路线的选择目标是要求经过每一个待配送点且总长度尽可能最短。与标准TSP问题不同的是这类问题通常有一个特定的起点，即配送运输工具当前所在位置；同时最优路线不要求是一个回路，即起始点与终点不一定要相同；除此之外，最重要的是各个中间节点往往有访问顺序的要求，即某些节点必须在访问过另一些节点以后，才能够被访问。在外卖配送过程中，配送员同时接到多家餐厅的配送订单，这些订单对应不同待配送客户，此时配送员希望能够找出一条最优路径，到达所有的餐厅点和用户所在地，且某家餐厅必须要在其对应的用户所在地之前到达。本文将这类问题称为具有顺序限制的TSP问题。

假设a1为规定的起始点，某个可行解的路线表示为：S=a1b1a3a2b2b3，即相同下标的字母，a必须出现在b之前。用da1b1表示a1点到b1点的距离，设各点的距离为欧氏距离，满足三角不等式，且da1b1=db1a1。某个可行解的总长度用D表示，对于前述的S路线，其总长度为：D=da1b1+db1a3+…+db2b3。D为配送的总路线长度，但不同的配送路线使其长度不同，如何从众多种路线中寻找一个最优解即本文需解决的问题。

2 具有顺序限制的TSP问题优化解法

2.1 生成初始路线

当一个配送员接收所有订单后，有餐厅位置和客户位置，需在此基础上进行初始路线的生成，初始路线的生成采用最邻近算法。最邻近算法采用一种广度优先的最短优先思想[12]，只是在搜索过程中必须满足顺序限制，即餐厅点必在对应的客户点之前。

采用算法生成初始路线步骤如下：

(2) 建立路径队列S，将起始点a1插入S中。

(3) 从P中选择距当前点最近的一个点xi作为该路线的下一点，将此点从P中删除，并放入S的末尾。

(4) 若xi∈A，则将∀bi∈B加入P中；否则，转入步骤(5)。

(5) 若P=∅，则结束，S即为所求得路径；否则，转入步骤(3)。

经过邻近算法已生成一个可行解S，即配送员经过所有餐厅且配送给客户的初始路线，并以此解为基础，进行算法优化。

2.2 LK算法优化

LK算法为文献[13]提出的一种局部搜索优化算法,它是在k-opt局部搜索算法[14]的基础上通过改变k来实现的，该算法能高效求解组合优化问题的近似解，能使配送路线S更小化，LK算法可以与许多智能化算法在求解TSP问题组合时使用，如蚁群算法[15]。原始的LK算法是使用随机产生的路径作为算法的初始解，但文中应用最邻近算法生成初始解，即可行解S。

首先使用3-opt算法，算法流程如下：

(1) 从起始点开始，选择一个与之相连的点x，选择一条以x为顶点的，不属于初始路线S的边e1，设远端端点为xi。

(2) 选择与xi相连的一个顶点xi+1，选择以xi+1为端点的一条不属于初始路线S的边e2，设远端端点为xj。

(3) 选择与xj相连的一个顶点xj+1，并连接该点与起始点之间的边。

(4) 记d1=de1+de2+de3，d2=da1x+dxixi+1+dxjxj+1，若d1

(5) 若找完所有的点，且SM≠S，则用SM替换S作为当前结果，返回步骤(1)；否则，若还未找遍所有点，则返回步骤(2)，从当前点的下一点开始寻找。

(6) 若找完路径上所有点，则结束，当前的SM即为寻找出的优化解。

2.3 使用末端-2-opt方法优化

由于配送路线具有起始点且不要求最终路径形成回路，则使用3-opt和2-opt算法所进行的优化不会涉及路径上的最后一点，因此要对涉及末端点的可能优化情况进行单独分析，在这里只考虑2-opt的优化。算法步骤如下：

(2) 连接xixn，记为em1，连接xi+1xn，记为em2。

经过最邻近算法、LK算法、末端-2-opt算法后，得到配送员经过餐厅地点和客户点的一条优良可行路线，且是具有顺序限制的。

3 试验及分析

本文最后分别选取9个、16个、25个、52个点共4组试验数据，分别包括餐厅点和客户点，依次利用最邻近算法、LK算法及末端-2-opt进行计算，结果见表1，通过比较各步骤所得路径长度及运行时间，评价算法的优化效果。

表1 各算法计算结果

由表1知经末端-2-opt算法优化后所得长度最短,且LK算法在最邻近算法上也有所提升，证明本文算法优化是有效的。

以9个点的数据为例，各算法所画出路径如图1所示。图中圆形为餐厅点，三角形为客户点，箭头代表起始路线方向，数字相同的餐厅点与客户点代表两者存在对应关系。从图中可知3种算法均能有效算出一条可行解，从路径长度方面比较，LK算法能够优化由最邻近算法给出的初始路线，末端-2-opt算法能对LK算法得出的路线继续优化。由最邻近算法生成初始路线，路线曲折且较长，经过3次算法优化后，路径大幅度缩短，更适合配送路线方案的选择。

4 结 语

本文从外卖配送员角度出发，提出了一种解决具有顺序限制的TSP问题的优化解法。优化过程包括由最邻近算法生成初始解，然后使用LK算法(3-opt、2-opt)优化，最后使用末端-2-opt方法优化。试验结果表明，该方法有效缩短了路径的总长度，如能运用在实际的配送行业中，将提高配送行业的工作效率，节约成本。