基于蚁群算法的快递投递最优路径规划设计

摘要：随着我国电子商务的繁荣发展，外卖、网购、快递等电子商务活动已成为人们日常生活的重要组成部分，订单配送的及时性已成为评价各外卖平台、快递公司等电商企业服务质量的重要指标之一。以骑行成本和路况成本为约束，建立最优路径规划模型，设计基于蚁群算法的快递投递最优路径规划算法，在给定时间窗内以目标约束规划出最优投递路径，以合适的投递成本实现订单高效配送，降低投递员的在路上的时间，提升电商企业的服务质量。

关键词：订单配送;成本约束;时间窗;蚁群算法;路径规划

中图分类号：TP311.5      文献标识码：A

文章编号：1009-3044（2022）04-0086-04

1 概述

近年來，随着人民生活水平的逐步提高，年轻一代在日常工作与生活学习中的压力也越来越大，“懒人经济”逐渐兴起，并带动外卖、快递等一众本地生活业务迅猛发展。与此同时，随着劳动成本的提高和作业效率要求的提高，技术革新的步伐也在加快。

随着我国O2O电子商务发展的兴起和日益繁荣，外卖、快递等网上购物下单交易的市场规模在日渐扩大，据不完全统计，我国网购市场日均交易高达上亿单①。面对如此庞大的市场需求，对于网购订单的及时配送就显得尤为重要。各大快递公司与平台为投递员提供有效的路径规划调度与优化则是至关重要的一步。

目前各外卖平台、快递公司相互之间的竞争日趋激烈，订单配送的及时性是影响配送体验亦是顾客网购体验的重要指标。对于各类服务平台与派送企业，需要以不断提高用户订单派送的送货及时性和派送准确性为服务最终目标，与此同时尽可能地减少不必要的成本支出以大幅降低派送成本，以期能够达到提高派送用户体验和降低送货服务成本这两者之间的最佳平衡点。这些正是各类企业赖以生存的根基和发展关键所在，这也正是本文对此展开深入研究所依托的一个现实行业背景。

本文将快递员投递与路径决策模型中的协同优化问题[1-2]综合分析归结为带时间窗的及时投递配送最优路径模型规划问题[3]。根据路径模型和协同问题分析各约束条件下的不同特点，设计快递投递最优路径规划算法研究。最后，根据实际调研与实验数据综合整理，进行综合分析，证明了这种算法的应用效率和计算精度[4-5]。

研究结果表明，本文算法能够有效地帮助快递投递员在高峰时期有大体量的配送订单的情况下高效地规划出最优路径，进而有效地改善快递企业高成本以及快递投递员低效率导致低收入的问题[6]。

2 快递派送过程中的路径分析

快递配送投递是指用户在电商平台向商家下单购物，商家委托有合作的快递企业在一定期限内运送商品至用户手中的商业活动。其中，用户当地的快递站点收到其他分公司运送过来的快件后需及时分配给快递员，再由快递员派送至用户的收货地点，完成“最后一公里”的派送。快递员按照成功派送的快件数取得劳动报酬。因此，派送效率、派送过程中的路径规划对于快递员的收入有着至关重要的影响。

当快递员从快递站点分配到快件开始，便需要思考派送的路径。派送过程中会受到以下几方面现实的问题：

1）购物用户的地理位置相对分散，且又存在单个用户多个快件的情况。

2）配送路况难以预料。各路段的限速情况、车道数、拥挤程度特别是道路口红绿灯等待时间。尤其是晚高峰时期，又极易发生交通事故。

3）特殊极端天气可能影响普通快递的正常配送。特殊极端天气（例如雨雪天气、短时极端恶劣天气）时，造成道路湿滑，会大大影响快递员送货的速度[7]。

3 建立数学模型

从快递企业和快递员的角度分析快件派送路径规划问题，建立快递投递最优路径规划的数学模型。由快递员需要承受的派送快件成本基本有以下几个方面：

1）骑行成本

快递员在派送过程中的骑行成本和派送的距离有着紧密的联系。快递员和目标用户收件地址的订单派送顺序影响着最终的派送距离，有着极大的进一步优化空间。我们可以将骑行成本由下式表示：

α（lij）=dij×s

此处记s是快递员派送过程中派送单位距离的骑行成本，dij表示从节点i至节点j段路径，α（lij）是从上一骑行节点i至下一骑行节点j的骑行成本。

2）路况成本

从上一骑行节点i至下一骑行节点j的任意一段路径，存在影响快递员配送速度的一系列外在现实约束条件，即路况成本。文献[8]给出的该部分从道路限速、红绿灯等待时间、单向车道数三方面考虑设定。

在文献[8]中，β表示路况成本，dij表示从节点i至节点j段路径，l为单位路径长度，perf表示段位路径的路况成本，包括在配送过程中从i节点到j节点的红绿灯停等总时间light（tk）、道路限速f（v）、单向车道数N。若取单位路径长度为无穷小，则在该段路径内快递员的骑行速度可视为匀速，则派送单位距离的记为v，v应当小于该段路径限制的最高时速V。

4 应用求解

将地图抽象成图可以高效地解决本路径规划问题。以各地的主要交叉路口为该地图的每个节点，以每个交叉路口的节点与交叉路口节点之间的每条道路为一条图的边，以每条道路的路径长度为边的权重。如果这条路径有方向且为单向的，那么就可以在地图上画出两个节点之间的一条有向边;如果该段路径是有方向的且是双向的，则在两个节点之间以不同方向分别画一条边。这样，将整个地图抽象到一个有向加权重图中。到目前为止，我们要解决的问题是找到有向加权图的两个顶点之间的最短路径。

如图1所示为抽象路径拓扑，以A、B为起始点为例，骑行成本D1可由A、B之间的具体路径长度确定，路况成本D2则由A、B段路径上两次红绿灯、限速40公里（设定权值为0.4）及当时的拥挤程度（初始化权值为0.5）来确定。将各节点之间各要素权值带入算法中优化迭代，即可求出起始点间的最优路径。

若忽略骑行成本路况成本等等一系列限制条件，则经典算法最短路径算法可以很好地解决这个问题，更加准确地说，是单源最短路径算法。文献[9]中单源最短路径算法，它的主要核心逻辑是：

1）设置一个初始的数组nodes，然后利用这个数组来添加设定的初始节点行驶至每一个其他节点的记路径长度length。

2）将初始节点到其余节点的距离设置为∞，起始顶点的length值初始化为0，并且需要把它添加进优先队列之中。

3）从这个优先队列中取出length最小的节点，此处可以记为node_min，然后考察这个节点可达的所有节点node_next。假若最小节点的距离值length加上最小节点node_min与下一节点node_next之間边的权重w小于下一节点node_next当前的距离值length，即存在另一条更短的路径，它经过最小节点node_min到达下一节点node_next。将该节点node_next的距离值length更新为node_min的length值加上边的权重w。然后，把node_next加入优先级队列中。

3）重复步骤2），直到找到顶点t或者队列为空。

4）额外设置两个变量数组pioneer_node和 array。前者的作用是为了还原最短路径，它记录每个顶点的前驱节点。运用递归的方法，输出最优规划路径。以array数组规避将同一个顶点重复加入优先级队列中。当某个顶点的距离值length执行更新操作后，若该顶点节点已存在于优先级队列中，则无须重复添加进去。

单源最短路径算法并不完全适用于快递投递最优路径规划问题。因为在该问题下还需要考虑到骑行成本与路况成本。以路况成本中红绿灯等待时间为例。每经过一条边，就要经过一个边的红绿灯。实际上，对于该约束条件，我们只不过需要把每条边的最终权值相应改为1即可，算法还是不变，可以接着使用本文先前所述的最短路径算法。不过，边的初始和最终权值为1，也就相当于无权图了，同时亦可以灵活地运用广度优先搜索算法求出最终的最短路径即最优规划方案。

确定派单路径规划，运用蚁群算法思想，在处理完成当前时间段内参与配单的所有快递员对所有订单价值判断后，采用km带权二分图完全匹配算法，提供快递员与订单之间的最优匹配。快递员在分配订单后，还需解决单快递员多订单的情况下，在最短时间内完成订单的处理，即一类不需要形成回路旅行商变体[10-11]。

针对该问题，文献[9]在分配订单较少的情况下可以直接采用动态规划遍历所有情况得出最优解，但是当分配订单较多的情况下，其传统算法的遍历时间复杂度高达O（n！），故本文基于蚁群算法构建快递员订单派送路径规划算法，其基本概念源于蚂蚁寻食，是在初始点经过多个需求点后，返回原点的过程中通过信息素的方式标记各自行走路径，参照信息素的浓度选择方向[12]。

文献[12，13]给出的蚁群算法可描述为：

Step1：蚂蚁每经过一节路径，便在该段路径上留下信息素。

Step2：初次遇见路径节点即路口，随机选择其中任一路径。选择路径的同时，释放信息素以反映该路径的长度等相关信息。

Step3：路径的直线长度越长，留在该蚂蚁路径上的蚂蚁信息素含量浓度相对越低，反之则信息素含量浓度越高。此后每当其中有一只蚂蚁再次觅食来到一个路口时，系统便会自动选择一个信息素含量浓度较高的路径并进行再次觅食。

Step4：信息素浓度较高的路径被蚁群多次重复觅食，其留在路径上的信息素浓度随之增加，最终形成最优路径。

Step5：算法结束，得到最优路径。

Step6：将最优路径规划在地图上可视化。

文献[12-13]给出的蚁群算法流程图如图2所示。

在该算法实现上，预先给定迭代次数，首次迭代过程中随机设置信息素，后续迭代过程中根据之前迭代留下的信息素浓度判断下一个到达点，最后记录遍历完所有点后，将走过的路径和长度在这次迭代结束后进行比较，得出此次迭代得到的最短路径及长度，重新更新信息素后开启下一个迭代[13-14]。

由于路径选择概率与路径长度成反比，算法迭代完成后形成的信息浓度最高者即为求解的最短或较短路径。文献[12-13]在此过程中路径选择概率具体如下：

该路径选择概率公式主要是计算所有可选节点的能见度和信息素幂乘积占总比，i和j分别作为起点和重点;能见度是i和j之间距离导数即[ηik]=1/dij;[τik]是时间为[τ]时从i到j的信息素浓度;allowedk表示没有信息素的节点集合;α，β作为加权值常数即骑行成本与路况成本。

5 最终规划

基于骑行成本和路况成本约束的最优投递路径规划算法描述如下：

Stepl：定义目标函数和适应值函数。

Step2：初始化抽象拓扑图。

Step3：计算初始成本。

Step4：计算、更新个体最优和全局最优，到达每个节点的成本。

Step5：算法迭代次数完成，获得若干组次优解，转Step 6;否则转Step3。

Step6：根据次优解生成信息素初始分布，蚁群参数初始化。

Step7：分别求解每只蚂蚁转移概率值，以转移概率值移动蚂蚁。

Step8：更新移动蚂蚁的最优值、位置和信息素。

Step9：达到迭代次数，结束。否则，输入最优值，转Step7。

其最优路径规划算法如图3所示：

6 测试结果

基于pycharm集成开发工具，使用python语言编写代码实现算法。调用高德地图提供的API将最终的规划路径可视化，其路径规划如图4～图6所示。

图4所示，以凤起路、武林门为起始点与终点，将其接纬度坐标带入算法运行得到最优路径规划路线。

图5所示，以兰州植物园、第940医院为起始点与终点，将其接纬度坐标带入算法运行得到最优路径规划路线。

图6所示，以西北民族大学兰州体育馆为起始点与终点，将其接纬度坐标带入算法运行得到最优路径规划路线。

如图7所示是最优路径规划算法的迭代结果，平均路径长度与最短路径长度曲线最终趋于平缓，与测试预期符合得很好。

注释：

① https：//www.chinairn.com/scfx/20201209/164700190.shtml.

参考文献：

[1] 宋梦培.粒子群算法和蚁群算法的集成及其应用研究[D].吉首：吉首大学，2020.

[2] 张超.粒子群算法与蚁群算法的改进研究[D].西安：西安工程大学，2019.

[3] 王征，张俊，王旭坪.多车场带时间窗车辆路径问题的变邻域搜索算法[J].中国管理科学，2011，19（2）：99-109.

[4] 周袅，葛洪伟，苏树智.基于信息素的自适应连续域混合蚁群算法[J].计算机工程与应用，2017，53（6）：156-161.

[5] 黄松，田娜，纪志成.基于自适应变异概率粒子群优化算法的研究[J].系统仿真学报，2016，28（4）：874-879.

[6] 王荃菲.快餐外卖配送路径方案研究[D].北京：北京交通大学，2017.

[7] 徐倩.外卖平台骑手派单与路径决策协同优化[D].大连：大连海事大学，2020.

[8] 刘士新，刘玲，张涛.求解VRPBTW的变邻域搜索算法[J].东北大学学报（自然科学版），2008，29（3）：316-319.

[9] every__day.最短路径：地图软件是如何计算出最优出行路径的？[EB/OL] （2019-03-18）.[2021-11-17].https：//blog.csdn.net/every__day/article/details/88633171.

[10] 董红宇，黄敏，王兴伟，等.变邻域搜索算法综述[J].控制工程，2009，16（S2）：1-5，13.

[11] 孟祥萍，片兆宇，沈中玉，等.基于方向信息素协调的蚁群算法[J].控制与決策，2013，28（5）：782-786.

[12] 刘炳姣，石琴，仇多洋，等.基于改进蚁群算法的行驶工况构建及精度分析[J].合肥工业大学学报（自然科学版），2017，40（10）：1297-1302.

[13] 李妍峰，李军，高自友.大规模邻域搜索算法求解时变车辆调度问题[J].管理科学学报，2012，15（1）：22-32.

[14] 王志中.基于改进蚁群算法的移动机器人路径规划研究[J].机械设计与制造，2018（1）：242-244.

收稿日期：2021-12-22

作者简介：乐靖雯（2002—），女，贵州天柱人，本科在读。