基于贪心蚁群算法的生鲜配送全局路径规划

杨瑞琪，马巧玲，连天娇，郭丹阳，许曙博

（广州城市理工学院,广东广州，510800）

0 引言

随着经济的发展和社会生活水平的提高，各个城市出现交通拥堵现象，给生鲜产品配送带来挑战。生鲜配送的速度会影响到人们健康生活，然而当前社会在生鲜配送上的发展水平较低，需要提高生鲜配送的技术。

对于生鲜配送路径优化问题的研究，许多国内学者进行了大量的研究，并取得一定的成果。文慧君[1]研究了上层为冷链物流优化总成本，下层为优化客户满意度的双层规划模型，使用遗传算法对双层规划模型进行求解。杨雅琪[2]在生鲜连锁店配送路径问题的研究中，考虑到各地区交通拥堵的因素，为有效减少生鲜配送成本，并且提高生鲜配送的准时性。因此为M生鲜连锁店构建出，由蚁群算法和侵入杂草算法相结合的新混合蚁群算法—生鲜连锁店配送促进优化模型。明小菊等[3]以最小化成本为目标创建了冷链配送优化模型，采用莱维飞行和反向学习优化的粒子群算法对粒子群算法进行优化用于模型求解。王永锋[4]针对生鲜产品易腐败的特性，提出建立带时间窗的配送车辆路径优化数学模型，选择混沌遗传算法对模型求解，缩短了运输距离，降低了运输成本。

我国对生鲜产品配送的需求不断增加，为了降低生鲜产品的配送成本，解决路径优化问题，本文采用蚁群算法寻找最优路径，但该算法收敛速度慢、运行时间长、区域搜索能力差。为了弥补蚁群算法的缺点，引入贪心算法提高了蚁群算法的局部搜索能力。考虑到实际生鲜产品配送需求的特点和相关条件的制约，设计了贪心蚁群算法，实施了全球路径规划，达到了配送路径的最佳目的。

1 算法

1.1 蚁群算法

蚁群算法是模仿蚂蚁觅食的行为，是一种仿生算法。蚂蚁在寻找食物的过程中，产生蚂蚁和蚂蚁之间交换信息的机制，即信息素，从而获得食物和当前位置的最佳路径[5]。

传统的蚁群算法是由1991 年由 Marco Dorigo等提出的。在研究过程中发现，蚂蚁觅食的过程中，会在路上释放信息素，而且信息素会随着时间的流逝而挥发，蚂蚁走过的路线越长，留下的信息素挥发多浓度则低，相反越短的路径上面的信息素发挥的时间越短，导致该路径上的信息素浓度高，更容易引导后来的蚂蚁来走这条最短的路径[6]。蚁群算法就是模拟自然界蚁群寻找从蚁巢到食物源间最短路径过程的一种随机搜索算法[7]。但是蚁群算法存在收敛速度慢，容易陷入局部最优解的问题。蚁群算法的执行步骤如图2所示。

图1 蚂蚁的觅食过程

图2 蚁群算法流程

蚂蚁在觅食过程中会在路径上留下信息素，其他蚂蚁则倾向于沿着不同路径上信息素浓度较高的路径走，如果距离相同，则倾向于走浓度较高的路径，经过一段时间后，可以以最短的路径到达目的地。蚂蚁k从选择下一节点的概率公式如式（1）所示 ：

每个蚂蚁个体在通过特定路径时释放信息素，通过所有路径节点后，根据信息素的叠加和挥发机制更新路径中的信息素，更新策略如公式（3）所示：

式中：ρ为信息素挥发系数，（1-ρ）为信息素的残留系数，如果ρ值过小，会导致残留的信息素裹多，则会无法区别路径的长短，∆τij为节点i到节点j信息素的增量，其计算值如式（4）所示 ：

式中：Q为蚁群算法的信息素强度系数。

1.2 贪心算法

贪心算法是一种能够得到某种度量意义下的最优解的分级处理方法，它总是做出在当前看来是最优的选择，也就是说贪心策略并不是从整体上加以考虑它所做出的选择只是在某种意义上的局部最优解算法[8]。贪心算法在路径规划方面，每次仅会选择离当前节点最近的节点，直到所有的节点都选取完毕，就完成路径规划。由于贪心策略总是采用从全局看来是最优的选择，因此并不从整体上加以考虑，不能保证求得的最后解是最佳的。

当贪心算法经常被用于解决优化问题时，为了获得目标函数最优解，将会不断地进行搜索选择。采用循环的动态方式缩小问题、解决问题，不断得出子问题的最优解。例如，在活动选择问题中，我们总是根据一个问题选择结束时间最早的活动，然后根据其余活动选择结束时间最早的活动，直到没有活动以这种方式选择为止。综上所述，将总问题划分成子问题，依次求解子问题的最优解，最后将子问题的最优解整合成总问题的解[9]。

1.3 贪心蚁群算法

针对贪心算法和蚁群算法各自的缺点，把两种算法结合起来，在传统蚁群算法的操作步骤中接入贪心策略，提高算法的局部搜索能力和收敛速度。算法步骤如下：首先进行初始化参数，包括蚁群初始化数量、最迭代次数、启发函数因子、挥发因子、信息素等，其中开始的时候每条边的信息素量都相等。将各只蚂蚁分别放在各个的顶点，禁忌表为对应的顶点。其次选取一只蚂蚁，引入贪心策略修改初始路线。传统的蚁群算法，蚂蚁的初始路线是随机生成的，当遇见带有信息素的路线时，根据概率决绝是否要更改路线。蚁群即使当下时刻选择了走带有信息素的路线，下一时刻也不一定会继续走带有信息素的路线，反而是继续走随机路线。由于随机路线是随机生成的，当参数设置不当时，算法搜索路径的时候会延长，收敛速度极慢，因此引入贪心策略，设置蚁群的初始路线，减少算法迭代的时间。计算一只蚂蚁额的转移概率，选择下一个顶点，更新禁忌表，再计算概率，再选取顶点，循环往复，直至这只蚂蚁遍历了所有顶点。计算当前这只蚂蚁留在各条边上的信息素增量，然后该蚂蚁完成使命死去。所有蚂蚁都重复一样的步骤。直到所有蚂蚁都完成使命。计算各条边的信息素增量 ∆τij和信息素量τij(t+n)。最后，记录本次迭代的路径，更新当前的最优路径，清空禁忌表。判断是否达到预定的迭代步数，若是则输出当前的最优路径，结束程序，若为否，则继续迭代。

2 实验

2.1 参数设置

蚁群作为一种启发式搜索算法，蚁群算法具有良好的鲁棒性，且易于融合其他算法应用到实际问题中[5]。贪心蚁群算法的实验参数设置如下表所示，参数的设置都是在经验值的基础上，结合实验效果进行修改的，具有一定的适用性。

表1 相关参数设置

2.2 实验数据介绍

为了验证算法改进的有效性，使用32个信息节点来模拟一位生鲜配送员的配送情况，并利用Matlab软件编写算法实现。节点的部分信息如下所示。其中节点1表示起点，节点2-32表示顾客，如表2所示。假定生鲜配送员以匀速行驶，没有突发状况发生。

表2 部分节点信息

2.3 结果分析

分别对贪心算法、传统的蚁群算法和改进后的贪心蚁群算法进行10次实验，得到的结果如下表所示。从寻优的结果可以看出，在求解该问题的最优路线时，贪心算法只基于当前节点考虑下一个最优节点，导致前期的路线为最优路线，后期的路线为剩余节点的凑合，路线很长，达不到全局优化的目的。而蚁群算法和贪心蚁群算法从图中可以看出，规划的路线节点之间的长度较均匀合理。但是贪心蚁群算法所求得的路径的距离是三种中最短的、算法运行的时间也较传统的蚁群算法少得多。如图可知，贪心蚁群最优解的配送路线为：1-15-9-8-4-25-21-32-16-6-12-22-11-10-13-19-5-7-14-27-2-23-28-17- 29-24-3-18-31-30-20-26，计算得到总距离约114.9294km。

表3 算法运行结果

图3 贪心算法路径规划图

图4 蚁群算法路径规划图

图5 贪心蚁群路径规划图

蚂蚁种群算法和贪心蚁群算法的最佳距离和算法迭代次数如下图所示，通过贪心算法改善局部搜索能力后，可以用较少的迭代次数找到最佳路径，算法的改进具有良好的效果。

图6 蚁群算法适应度曲线

图7 贪心蚁群算法适应度曲线

3 结论

本文基于生鲜配送问题，使用贪心算法、蚁群算法和改进后的贪心蚁群算法进行求解，通过对比实验可知，贪心蚁群算法能加快算法的收敛，并进行路径的优化。