基于蚁群算法的送餐最短路径问题求解研究

文/原丕业张明王岐昌刘晓伟

1.引言

随着人们生活水平提高，外卖点餐越来越受欢迎。对于送餐员来说，短时间内接到的多个订单，配送地点有所差异，且需要较短时间内将外卖送达。因此，送餐员需要考虑如何在最短时间内走完既定的路程并且路程最短。20世纪90年代意大利学者DorigoM 从仿生学的角度出发，最早提出了蚁群算法。蚁群算法（Ant Colony Optimization ACO） 是一种新型的模拟进化的算法，灵感来源于蚂蚁觅食时释放出一种信息素来发现路径的行为[1]。它应用于组合优化的启发式搜索方法，结合其它算法的优点，提出后被广泛应用并深入研究。目前蚁群算法被应用于许多组合优化的问题中，例如旅行商问题（Traveling Salesmen Problem）、网络路径最优化问题等。杨从平（2014）用蚁群算法对快递路径网络优化，降低配送车辆数和路程[2]。邵长旭（2018）等利用蚁群算法解决无人机航点数量较多的多种飞行轨迹问题，使飞行器以最短路径完成任务，减少控制系统的时间损耗，提高任务执行效率[3]。本文以外卖送餐问题为例，采用蚁群算法，对蚁群算法在餐饮行业的应用进行探究，以便解决生活中的实际问题。

送餐问题对时间要求较为严格，送餐员在越短的时间内完成订单，越能够获得消费者满意度。主要是针对送餐员配送多个订单，如何在路线网络中选择最优配送路线快速送餐配送。送餐问题是TSP问题的实际应用。TSP问题是一个局部最优解问题[4]。此问题可描述为：一个旅行商人从某个城市出发依次遍历n个城市，每个城市只能拜访一次，最后回到原出发城市，选择最短的巡回路线[5]。旅行商问题是经典NP问题，在实际应用中，行走路径多含障碍物，故蚁群算法有更加良好契合度。

2.基于蚁群算法的送餐路径优化算法

2.1 蚁群算法基本原理

自然界中蚂蚁的觅食行为不依赖于视觉，靠的是体内分泌的信息素和蚂蚁种群的集体合作，寻找从蚁巢到食物的最短路径。蚂蚁在外出觅食时初始时会进行探索，并释放一种称为信息素（Pheromoe）的化学物质，蚂蚁间借助信息素作为沟通媒介互传递消息[6]。蚂蚁觅食，在行进路径遗留信息素，较短路径较高信息素浓度，其后蚂蚁在路径选择时会优先顺着信息素浓度高的路径行走，最终经若干个蚂蚁的选择，趋向同一条路径[7]。

蚂蚁出巢觅食时一旦找到食物就会马上返巢；若两只以上蚂蚁找到同一食物，行走的不同行径，则过长路径会导致信息素强度比较低，其后的蚂蚁群体会选择信息素浓度较高的路径，最后筛选出一条最短路径。如此以来，蚂蚁种群的这样一种选择方式造成了一种蚂蚁选择路径概率的大小与此路径上信息素浓度大小的正反馈现象，即信息素浓度越大，其后蚂蚁对该路径选择的可能性越大[8]。

2.2 蚁群算法模型构建

Dorigo提出以人工蚂蚁代替真实蚂蚁来模拟觅食。人工蚂蚁与真实蚂蚁既有区别又有联系。两者共同之处：（1）两者都是相互合作的群体；（2）前者也是由信息素来获得群体相互间的信息传递。简单蚂蚁具有以下特征：（1）通过城市间的信息素浓度来选择下一个访问城市时；（2）选择访问一个城市后，将城市计入到禁忌表tabu（k）中，蚂蚁选择的合法路线，不得选择已访问城市。一次循环之后，禁忌表中存放的是蚂蚁群体所产生的巡回路线即蚂蚁的行径路线，随后禁忌表会被清空，蚂蚁进行下一步的自由选择。

初始时刻（t=0时），城市间的信息量相等τij=C(C为常数)。t时刻时，蚂蚁k选择下一个将要访问的城市时的概率由该条路径上的信息素浓度决定：

经过一段时间，蚂蚁行径路线上信息素会产生变化，信息素的更新可以用（2）式来表示：

ρ 为信息素挥发系数，1-ρ 为信息素持久性；τij（t+a）表示在（t+a）时刻，城市i到j路径的信息素浓度；Δτijk为第k只蚂蚁在a时间段内在城市i到j间产生的信息素浓度，Δτijk为m只蚂蚁在a时间段内在该条路径释放的总信息素浓度。确定Δτij可以用式（3）来表示：

Q为常数，表示信息素强度；Lk为蚂蚁k所走路径长度。

2.3 蚁群算法求解步骤

（1）参数初始化：初始化τij；（2）m 只蚂蚁随机分布到n个城市；（3）将蚂蚁已访城市放入禁忌表（tabu）中；（4）依据公式（1）计算蚂蚁下一步将要选择转移的城市；（5）每迭代一次都将m只蚂蚁走过的路径长度进行计算，得出路径长度数值。（6）在当前迭代次数的条件下，计算蚂蚁行进路线的平均长度和最短距离。（7）根据公式（2）更新信息素。（8）迭代次数加1。nc=nc+1。（nc表示为迭代次数）（9）若迭代次数大于等于预定的迭代次数，则输出计算结果；否，返回步骤（2）。流程图如图1所示：

图1 计算流程图

3.实例验证及结果分析

3.1 实例求解验证

调查选取15个距离坐标，建立城市坐标系，对距离坐标进行检验。参数设置如下：蚂蚁数量m=30，信息素启发因子α=1，期望启发因子β=5，信息素挥发系数ρ=0.1，最大迭代次数NC-max=200，信息数初始化值=100。

坐标为C= （1321，616；4578，1415；3417，1230；5346，1109；1684，2035；4681，1578；2662，679；6110，2132；761，519；5713，1716；4399，2351；2963，1928；2857，3281；4965，3157；2336，2753）

然后对15个坐标进行数据分析，得数据迭代200次后的理论最短路径与迭代收敛图：（见图3、图4）

可以看出在迭代次数进行到10次左右时，该曲线已经收敛趋向于所得出最短路径S=1.5174*104，接近于1.5174*104。说明在本模型中，进行200次迭代运行出的结果具有合理性。

探究蚂蚁数量是否对模型的最优解产生影响，将蚂蚁数量进行分别赋值5、10、15……50，而后分别环运行20次，寻找其中最短路径的最大值、最小值以及平均值。具体数值见表1：

图3 最短路径图

图4 曲线收敛图

表1 蚂蚁数量对路径长度的影响

3.2 运行结果分析

本文假设30只蚂蚁通过15个订餐点，经200次迭代，调试运行20次，求得最短路径，并得最短路径图与曲线收敛图，曲线收敛图表示随着迭代次数的增加，最短路径距离会逐渐收敛于某个值。随后改变蚂蚁的数量来测算蚂蚁数量对平均最短距离的影响，将蚂蚁数量与平均最短距离用折线图进行表示，对蚂蚁数量分别赋值5、10、15……50，由图4可以看出随着蚂蚁数量的增加，平均最短距离也逐渐趋向稳定。

送餐员送餐的过程中可以按照以上仿真结果进行路线行走，经过软件计算出来的行走路线符合送餐过程的要求即：不重复地经过所有送餐点且最终回到原出发点。且经过重复测试，蚂蚁数量增多最终数值越接近优化后的结果，所以仿真的结果是具有说服力的。

4、结论

上述过程可以看作是送餐员不重复的经过15个送餐点，完成外卖配送任务的过程。蚁群算法作为众多智能算法之一，用于解决旅行商问题有较好的计算成果。

TSP问题在，旅游问题、配送送货、推销问题等具有广泛应用，在实际问题中的求解中具有现实研究意义。本文采用蚁群算法，用来求解组合优化问题中的外卖送餐路径规划问题，对巡回路径进行测算，并画出最短路径图和曲线收敛图来验证结果的准确性和可信性。

在对送餐问题和蚁群算法的深层次理解的基础上，建立模型并进行多次、多数值循环调试。得出问题的最优解，实现最初的目标，规划出最短路径，提高送餐效率。但是本文问题研究较浅，无论是理论还是实践方面都还需要进一步的加深研究。