0 引言

随着科技的快速发展，人们的生活变得更加便利．外卖行业蓬勃发展，使得人们能够在互联网上购买自己想要和需要的物品．外卖行业在日常生活中显得越来越重要，同时对于外卖配送服务的要求也越来越高．外卖配送服务的流程是客户在第三方平台购物下单，商家接受订单后，平台的外卖配送员根据订单信息进行外卖配送服务．在正常情况下一位外卖配送员在同一时间段中所需要配送的外卖可能会有多个，在外卖配送过程中会因为配送路线安排不合理导致订单无法及时送达等问题．在外卖平台系统的设置中，配送超时是不被允许的，一旦出现配送超时的问题，客户对外卖配送员的评价可能为差评，将造成外卖配送员收入降低、奖金被扣等负面影响^[1-3]．

外卖配送问题，可以简化为带有时间窗和容量限制的车辆路径问题^[4]．针对车辆路径问题（VRP），常见的求解方法有遗传算法^[5]、蚁群算法^[6]、禁忌搜索^[7]等智能算法．遗传算法是通过模拟生物进化适者生存的过程，在解决组合优化问题时使用选择、交叉、变异操作找出全局最优解．遗传算法的操作较简单，在不同的邻域可以表现出很好的兼容性，但是在解决具有针对性，并且要求一定精度的问题时，算法所得到的解在局部表现得不令人满意^[8]．禁忌搜索算法需要对每个可能的解进行检查，因此搜索效率较低．蚁群算法（Ant Colony Optimization，ACO）的基本思想是模拟蚂蚁寻找食物的过程，当得到一条有效路径时会释放一定的信息素标记该路径，对其他蚂蚁起到引导作用，从而加速整个搜索过程^[9]．蚁群算法可以处理大规模的解空间，并且自适应地调整搜索范围，因此蚁群算法对多种组合优化和运输调度问题具有较好效果．近年来，国内外学者们针对基本蚁群算法易陷入局部最优解和收敛速度慢的缺点，进行了大量的改进研究．Zhang等^[10]将邻近启发式算法与蚁群算法结合，提高了算法的性能和求解的质量; 王晓东等^[11]引入节约矩阵U引导蚂蚁搜索，通过不同搜索时段采用不同的信息素挥发因子，平衡优化蚁群算法中权重的分配，提高算法的性能; Donati等^[12]使用多蚁群系统（MACS-VRPTW）算法求解VRPTW问题，通过设计多个蚁群系统对多目标进行优化，提高求解速度和解的质量; Kalayci等^[13]基于蚁群系统（ACS）和可变邻域搜索（VNS）的混合算法，防止算法求解陷入局部最优解，提高算法的性能和解的质量; 李琳等^[14]将蚁群系统（ACS）与最大最小蚂蚁系统（MMAS）结合，并且设计在算法不同阶段采用不同的信息素蒸发策略防止陷入局部最优，用2-opt和2-opt*方法对每次迭代所得最优解进行局部优化，提高算法性能．针对传统智能算法易出现局部最优解情况，Blum等^[15]提出进化算法（EA）与大规模邻域搜索算法（Large Neighborhood Search，LNS）结合可以提高进化算法生成解的质量，从而提高算法的性能; 徐倩等^[16]提出一种自适应大规模邻域搜索算法求解外卖配送车辆调度问题，提高了外卖配送效率．

为了解决外卖配送路径规划问题，本文提出一种改进蚁群算法（Improved Ant Colony Optimization，IACO），综合考虑外卖配送员在进行外卖配送过程中的实际情况，对外卖配送路径进行规划．外卖配送过程中不仅有时间窗要求，对配送数量同样有要求，并且要求配送总路径尽可能短．因此，本文所研究的外卖配送过程可以简化为有时间窗约束和车载容量约束的车辆路径问题（CVRPTW）．引入外卖配送过程中以费用最小为目标的罚函数，建立外卖配送的数学模型，结合蚁群算法和大规模邻域搜索算法（LNS）对所建立的数学模型进行分析求解，并通过仿真实验对模型和所提出的改进蚁群算法进行验证分析．

本文的贡献为:1）从外卖配送员的角度出发，在外卖配送过程中考虑到时间窗约束、容量约束和最短总路径，所设计的算法更加贴近实际; 2）根据外卖配送员配送过程的实际情况设计合理的外卖配送数学模型，以配送过程中的费用最小为目标设计罚函数，充分考虑到对于配送员的最优方案的设计; 3）将蚁群算法和大规模邻域搜索算法结合，提高单一算法的求解质量，并且合理运用在本文所设计的外卖配送方案模型中，通过仿真结果验证了所提出算法的有效性，从而提高外卖配送效率．

1 外卖配送问题描述

本文研究的问题是针对一个外卖配送中心向多位顾客配送外卖或在一个紧凑的商业区向多位顾客进行外卖配送的场景．因此，该外卖配送路径规划问题可以描述为在满足配送员车载容量约束和送餐时间窗约束的前提下，对配送员的外卖配送路径进行合理规划，以提高配送效率并满足约束条件．整体规划出的路径需要使车辆的使用数目、配送员行驶总距离和违反约束条件的惩罚函数的各项成本之和达到最小．对本文所研究的问题可以简化为带有时间窗约束和车载容量约束的车辆路径问题（CVRPTW）^[17]．因此，对研究的CVRPTW问题提出如下假设:

1）外卖配送员配送起点和终点都为配送中心;

2）所有外卖车辆的车载容量相同，配送容量不能超过车载容量;

3）每位顾客的外卖只能由一位外卖配送员进行配送;

4）每位顾客的外卖质量已知，并且提供送餐时间窗．

数学模型描述如下:

设K为外卖配送中心配送员总数的集合; N为需要配送服务的n个顾客点的集合，N={1，2，3，···，n}; V={0}∪N．

其中:0为配送中心; V_k为车辆访问顾客的集合; i，j表示顾客编号; x_ij|k表示配送员k对顾客i的外卖配送结束后是否需要配送顾客j; y_i|k表示配送员k是否完成了对顾客i的外卖配送; Q表示配送员配送外卖容量的约束; q_i表示顾客i的外卖需求量; C_ij为配送员从i点驶向j点的运输成本; T_E，i为顾客i允许的最早外卖配送到达时间; T_L，i为顾客i允许的最迟外卖配送到达时间; a_i为配送员到达顾客i的时间．x_i|k，y_i|k为决策变量，当配送员k对顾客i的外卖配送完成后对顾客j进行外卖配送，x_ij|k=1，否则x_ij|k=0; 当顾客i由配送员k进行外卖配送时，y_i|k=1，否则y_i|k=0．

式（1）表示配送员外卖配送过程中费用最小的目标罚函数; 式（2）表示配送员k在配送完顾客i后只配送顾客j，配送员k在配送顾客j之前只配送顾客i; 式（3）表示每个配送员配送外卖的总容量不能超过车载总容量; 式（4）表示每个配送员从配送中心出发，送完最后一个顾客后返回配送中心; 式（5）表示每位顾客只能有一位配送员进行外卖配送; 式（6）表示避免配送过程中产生子回路; 式（7）表示配送员给每位顾客配送外卖到达时间应该在规定的时间窗范围内．

2 改进蚁群算法设计

2.1 蚁群算法原理

蚁群算法是一种源于自然界的放生进化算法，主要思想是蚂蚁在觅食的过程中会在经过的路径留下信息素从而引导整个蚁群的搜索过程，人类通过计算机模拟自然界中蚁群觅食的行为进行蚁群算法的开发．每只蚂蚁都会进行觅食行为，并且在觅食的路径上留下一种特有物质——信息素，其他蚂蚁在经过该路径时，可以感应到该信息素，并以此引导其他蚂蚁觅食．一般情况下，蚂蚁离开巢穴，会选择一条通往目的地的路径，在路径的每一个交叉点上都会将前一只蚂蚁所释放的信息素作为标记来选择接下来前进的路径，以此进行多次迭代可以得到最优路径．

2.2 配送路径生成

配送员k从顾客i所在地方出发到顾客j所在地方那一刻时间为a_j，根据式（7）要求a_j的范围，如果a_j小于顾客j时间窗的左边界，会导致配送员需等待顾客所设定的外卖最早到达时间，影响外卖的配送效率，配送成本增加; 如果a_j大于顾客j时间窗的右边界，会导致配送员配送外卖超时，极易引起顾客差评等不满评价，导致配送员利益受损．因此，在配送员配送外卖的到达时间必须在规定的时间窗范围内，所规划出的路径对于配送员来说比较合理，需要在状态转移过程中加入等待时间的影响因素．当T_E，j≤a_j≤T_L，j时，配送员k外卖配送到顾客j的等待时间t_w，j=0，将t_w，j取一个很小的正数; 当a_j≤T_E，j时，t_w，j=T_E，j-a_j; 当a_j≥T_L，j时，t_w，j=a_j-T_L，j．同时，配送员对顾客配送外卖的时间窗跨度也会影响对配送路径规划，在配送时间窗开始时刻一样的顾客j₁和顾客j₂时，如果顾客j₁的时间窗跨度小于顾客j₂，则顾客j₁对于外卖的配送要求更加紧急，对于配送员来说超时的可能性会越大，因此会优先顾客j₁的外卖配送．在状态转移过程中加入时间窗跨度影响因素f_width，j=T_L，j-T_E，j．

状态转移概率P_ij|k（t）表示在第t次迭代时，蚂蚁k从节点i移动到节点j的概率，移动规则如下所示:

其中:P_ij|k（t）为使用轮盘赌法选择点j的概率，可表示为$\frac{{\left[{\tau }_{ij}（t）\right]}^{\alpha }{\left[{\eta }_{ij}（t）\right]}^{\beta }{\left[1/f_{\text{width}，j}\right]}^{\gamma }{\left[1/t_{\mathrm{w}，j}\right]}^{\delta }}{\sum _{j\in N_{i\mid k}}\left({\left[{\tau }_{ij}（t）\right]}^{\alpha }{\left[{\eta }_{ij}（t）\right]}^{\beta }{\left[1/f_{\text{width}，j}\right]}^{\gamma }{\left[1/t_{\mathrm{w}，j}\right]}^{\delta }\right)}$; N_i|k是未被蚁群访问过的节点集合，可以通过概率值选择下一个节点; τ_ij（t）表示在第t次迭代时，节点i与节点j形成的边上的信息素的量; α表示信息素对蚁群搜索的影响大小; η_ij（t）表示形成的边对蚂蚁的可见度大小，η_ij（t）=1/d_ij，d_ij为节点i到节点j的距离，如果两个节点距离越远，表示蚂蚁的可见度越小; β是可见性对蚁群搜索的影响，β越大，蚁群更有可能会采取可见度高的路径; γ表示时间窗跨度因素导致蚂蚁对节点选择影响的大小; δ表示等待时间因素导致蚂蚁对节点选择影响的大小; r为[0，1]上服从均匀分布的随机变量; r₀为控制转移规则的参数，并且0≤r₀≤1．

蚂蚁在访问完该条路径后，会在该路径上留下信息素，对其他蚂蚁起引导作用．每次迭代后，蚂蚁会重复经过该路径，会使得信息素更新，信息素的表达式为

其中:ρ为信息素挥发因子，大小为0＜ρ＜1; Δτ_ij|k（t）表示为第t次迭代的第k只蚂蚁经过路径留下的信息素，初始Δτ_ij|k（0）设为1; L_k表示第k只蚂蚁从配送中心出发到回到配送中心访问的总路径长度; Q为设定的常数，本文实验给定为5．

令一组蚂蚁从配送中心出发，每一只蚂蚁按照式（8）规则选择下一访问节点j，当根据规则找不到合理的下一节点j时，蚂蚁返回配送中心，则该只蚂蚁对应的配送路径规划完成，一组蚂蚁全部遍历完节点后，即生成规划的外卖的配送路径．

2.3 大规模邻域搜索算法（LNS）

大规模邻域搜索算法从蚁群算法所得出的初始解进行优化，通过算法中的“破坏”和“修复”两个阶段对初始解进行优化操作，从而得到最优解．假设通过蚁群算法得到的配送路径为S₀，设定最优解S_best=S₀，即记录当前路径; 将路径S_best中的顾客随机抽出，即进行破坏操作，记录当前的路径为S_d; 对路径S_d进行顾客插入的操作，即进行修复操作，记录当前的路径为S_r．比较路径S_r罚函数的值与最优解路径S_best罚函数的值大小:如果路径S_r罚函数的值小于最优解路径S_best罚函数的值，则认为破坏、修复后的路径S_r优于路径S_best，于是有S_best=S_r，实现更新最优解，否则重新进行破坏、修复两个操作．当满足终止条件的罚函数值时，即输出最优路径S_best，其流程如图1所示．

2.4 改进蚁群算法流程

将蚁群算法和大规模邻域搜索算法结合，使用大规模邻域搜索算法对蚁群算法所求得的初始解进行优化操作．大规模邻域搜索算法优化初始解的实质是通过将蚁群所遍历路径进行破坏和重新修复操作，防止蚁群陷入局部最优解，从而改善初始解，得到优质解．解决带载重约束和时间窗约束的外卖配送算法原理如图2所示．

2.5 改进蚁群算法步骤

改进蚁群算法的伪代码如表1所示．

3 仿真分析

在MATLAB平台进行仿真实验，对本文所提出的改进蚁群算法、未改进的蚁群算法和遗传算法，针对不同数量的顾客进行外卖配送仿真分析．根据外卖配送实际情况，模拟外卖订单的低峰期和高峰期两个场景，验证本文所提出的改进蚁群算法的有效性．设定外卖订单的低峰期和高峰期顾客人数分别为25和110，配送员由配送中心出发，在规定的时间窗范围内进行外卖配送，最后返回配送中心．设定迭代次数T=50，配送员的最大载货容量设定为15．

3.1 订单数量较少场景仿真分析

表2为25位顾客和配送中心的信息数据，使用MATLAB软件进行模拟配送员进行外卖配送的场景，分别使用未改进的蚁群算法、遗传算法和本文提出的改进蚁群算法进行配送员的配送路径规划，配送路线和罚函数最优值变化曲线分别如图3、图4和图5所示，详细配送路径分别如表3、表4和表5所示．

由图3—5可知:使用蚁群算法在迭代50次后，所得到外卖配送路径的罚函数最优值为8 180; 使用遗传算法在迭代50次后，所得到外卖配送路径的罚函数最优值为6 886; 本文设计的改进蚁群算法在迭代50次后，所得到外卖配送路径的罚函数最优值为6 615．因此，可以求得改进蚁群算法在订单数量较少的场景下，与蚁群算法相比提升性能为19.13%，与遗传算法相比提升性能为3.94%．

3.2 订单数量较多场景下的仿真分析

表6为110位顾客和配送中心的信息数据，使用MATLAB模拟配送员进行外卖配送的场景．分别使用未改进的蚁群算法、遗传算法和本文提出的改进蚁群算法进行配送路径规划．配送路线图和罚函数最优值变化曲线如图6、图7和图8所示，详细配送路径如表7、表8和表9所示．

由图6—8可知:使用蚁群算法在迭代50次后，所得到外卖配送路径的罚函数最优值为3.945×10⁴; 使用遗传算法在迭代50次后，所得到外卖配送路径的罚函数最优值为4.413×10⁴; 改进蚁群算法在迭代50次后，所得到外卖配送路径的罚函数最优值为2.215×10⁴．本文提出的改进蚁群算法在订单数量较多的场景下，与蚁群算法相比，性能提升为43.85%，与遗传算法相比性能提升为49.81%．

3.3 仿真结果分析

由仿真结果可知，当订单数量较少时，蚁群算法、遗传算法和本文所提出的改进蚁群算法都可以根据顾客信息进行合理的外卖配送路径规划，并且最后所得到的路径均未出现违反时间窗等情况．整个外卖配送过程中的一个综合判定，表现为所设定罚函数的最优值大小:最优值越小，说明配送过程中违反约束的情况越少，并且综合配送成本越低，反之则违反约束情况多，并且配送成本高．蚁群算法、遗传算法和本文所提出的改进蚁群算法，进行外卖配送路径规划的罚函数最优值比较，结果如表10所示．根据表10中罚函数的最优值结果分析可得:顾客数量较少时，改进后蚁群算法的性能相比蚁群算法和遗传算法分别提升19.13%和3.94%; 顾客数量较多时，改进后蚁群算法的性能相比蚁群算法和遗传算法分别提升43.85%和49.81%．结果表明，本文提出的改进蚁群算法所求解的外卖配送路径的性能有较大提升，说明所提出的算法是有效的，可以合理运用在订单数量较多的场景．

4 结论

本文研究了有时间窗约束和车载容量约束的VRP问题，提出了一种改进蚁群算法，既有蚁群算法快速寻找解的优点，又有大规模邻域算法优化解质量的优点．结合MATLAB仿真平台进行验证，选取顾客订单数量较少和较多的两个场景，选用蚁群算法、遗传算法和本文所提出的改进蚁群算法进行对照仿真，根据所得到的最优配送方案路线和罚函数的最优值可以得出，本文提出的改进蚁群算法，可以较好地规划外卖配送路径，满足约束要求，合理提升外卖配送效率．

参考文献