1、理论算法2022.24410 引言随着经济的发展和社会生活水平的提高，各个城市出现交通拥堵现象，给生鲜产品配送带来挑战。生鲜配送的速度会影响到人们健康生活，然而当前社会在生鲜配送上的发展水平较低，需要提高生鲜配送的技术。对于生鲜配送路径优化问题的研究，许多国内学者进行了大量的研究，并取得一定的成果。文慧君1研究了上层为冷链物流优化总成本，下层为优化客户满意度的双层规划模型，使用遗传算法对双层规划模型进行求解。杨雅琪2在生鲜连锁店配送路径问题的研究中，考虑到各地区交通拥堵的因素，为有效减少生鲜配送成本，并且提高生鲜配送的准时性。因此为 M 生鲜连锁店构建出，由蚁群算法和侵入杂草算法相结合的新混合
2、蚁群算法生鲜连锁店配送促进优化模型。明小菊等3以最小化成本为目标创建了冷链配送优化模型，采用莱维飞行和反向学习优化的粒子群算法对粒子群算法进行优化用于模型求解。王永锋4针对生鲜产品易腐败的特性，提出建立带时间窗的配送车辆路径优化数学模型，选择混沌遗传算法对模型求解，缩短了运输距离，降低了运输成本。我国对生鲜产品配送的需求不断增加，为了降低生鲜产品的配送成本，解决路径优化问题，本文采用蚁群算法寻找最优路径，但该算法收敛速度慢、运行时间长、区域搜索能力差。为了弥补蚁群算法的缺点，引入贪心算法提高了蚁群算法的局部搜索能力。考虑到实际生鲜产品配送需求的特点和相关条件的制约，设计了贪心蚁群算法，实施了全
3、球路径规划，达到了配送路径的最佳目的。1 算法1.1 蚁群算法蚁群算法是模仿蚂蚁觅食的行为，是一种仿生算法。蚂蚁在寻找食物的过程中，产生蚂蚁和蚂蚁之间交换信息的机基于贪心蚁群算法的生鲜配送全局路径规划杨瑞琪，马巧玲，连天娇，郭丹阳，许曙博（广州城市理工学院,广东广州，510800）摘要：人们生活质量的提高，使得生鲜产品的种类和需求增加，而生鲜配送过程中存在的物流成本高、易腐烂变质、车辆载重率低、送达时效性低等问题，因此传统的配送方式已经难以适应生鲜物流的需求。通过研究贪心算法和蚁群算法，将贪心算法引入到蚁群算法中来提高蚁群算法的局部搜索能力，从而来设计出贪心蚁群算法，利用贪心蚁群算法得出优化后
4、的车辆配送路线。通过将贪心蚁群算法、贪心算法和蚁群算法对比后，结果表明贪心蚁群算法能够在原有基础上优化路径，达到生鲜配送路径最短、有效降低成本的目标。关键词：蚁群算法；贪心算法；路径规划；冷链物流；生鲜食品中图分类号：TP242 文献标识码：BGlobalrouteplanningoffreshfooddistributionbasedongreedyantcolonyalgorithmYang Ruiqi,Ma Qiaoling,Lian Tianjiao,Guo Danyang,Xu Shubo(Guangzhou City University of Technology,Guangzh
5、ou Guangdong,510800)Abstract:The improvement of peoples quality of life has increased the variety and demand of fresh products,and the problems of high logistics cost,perishability,low vehicle loading rate,and low delivery timeliness exist in the fresh food distribution process,so the traditional di
6、stribution methods are difficult to adapt to the demand of fresh food logistics.By studying the greedy algorithm and ant colony algorithm,the greedy algorithm is introduced into the ant colony algorithm to improve the local search capability of the ant colony algorithm,so as to design the greedy ant
7、 colony algorithm and use the greedy ant colony algorithm to derive the optimized vehicle delivery route.After comparing the greedy ant colony algorithm,the greedy ant colony algorithm and the ant colony algorithm,the results show that the greedy ant colony algorithm can optimize the route on the ba
8、sis of the original one and achieve the goal of shortest fresh food delivery route and effective cost reduction.Keywords:Ant colony algorithm;Greedy algorithm;Path planning;Cold chain logistics;Fresh foodDOI:10.16520/ki.1000-8519.2022.24.036理论算法2022.2442制，即信息素，从而获得食物和当前位置的最佳路径5。传统的蚁群算法是由 1991 年由 Mar
9、co Dorigo 等提出的。在研究过程中发现，蚂蚁觅食的过程中，会在路上释放信息素，而且信息素会随着时间的流逝而挥发，蚂蚁走过的路线越长，留下的信息素挥发多浓度则低，相反越短的路径上面的信息素发挥的时间越短，导致该路径上的信息素浓度高，更容易引导后来的蚂蚁来走这条最短的路径6。蚁群算法就是模拟自然界蚁群寻找从蚁巢到食物源间最短路径过程的一种随机搜索算法7。但是蚁群算法存在收敛速度慢，容易陷入局部最优解的问题。蚁群算法的执行步骤如图 2 所示。图 1 蚂蚁的觅食过程 图 2 蚁群算法流程蚂蚁在觅食过程中会在路径上留下信息素，其他蚂蚁则倾向于沿着不同路径上信息素浓度较高的路径走，如果距离相同，则
10、倾向于走浓度较高的路径，经过一段时间后，可以以最短的路径到达目的地。蚂蚁 k 从选择下一节点的概率公式如式（1）所示：()()()()0 aijijkaijijijj allowedttjallowedPttjelse=(1)式中：kijP表示蚂蚁k从当前位置i到下一位置j的概率；是信息素启发式因子，代表信息素浓度多转移概率的影响，值越大，蚂蚁则更加倾向于该路径，从而降低搜索全局最优解的概率；aij表示从 i 到 j 的路径上的信息素浓度；ij为距离启发信息，表示从节点 i 到节点 j 的欧式距离 dij的倒数如式（2）所示，为距离启发因子 1ijijnd=(2)每个蚂蚁个体在通过特定路径时释
11、放信息素，通过所有路径节点后，根据信息素的叠加和挥发机制更新路径中的信息素，更新策略如公式（3）所示：()()1ijijijt=+(3)式中：为信息素挥发系数，（1-）为信息素的残留系数，如果值过小，会导致残留的信息素裹多，则会无法区别路径的长短，ij为节点 i 到节点 j 信息素的增量，其计算值如式（4）所示：ijkQl=(4)式中：Q 为蚁群算法的信息素强度系数。1.2 贪心算法贪心算法是一种能够得到某种度量意义下的最优解的分级处理方法，它总是做出在当前看来是最优的选择，也就是说贪心策略并不是从整体上加以考虑它所做出的选择只是在某种意义上的局部最优解算法8。贪心算法在路径规划方面，每次仅会
12、选择离当前节点最近的节点，直到所有的节点都选取完毕，就完成路径规划。由于贪心策略总是采用从全局看来是最优的选择，因此并不从整体上加以考虑，不能保证求得的最后解是最佳的。当贪心算法经常被用于解决优化问题时，为了获得目标函数最优解，将会不断地进行搜索选择。采用循环的动态方式缩小问题、解决问题，不断得出子问题的最优解。例如，在活动选择问题中，我们总是根据一个问题选择结束时间最早的活动，然后根据其余活动选择结束时间最早的活动，直到没有活动以这种方式选择为止。综上所述，将总问题划分成子问题，依次求解子问题的最优解，最后将子问题的最优解整合成总问题的解9。1.3 贪心蚁群算法针对贪心算法和蚁群算法各自的缺
13、点，把两种算法结合起来，在传统蚁群算法的操作步骤中接入贪心策略，提高算法的局部搜索能力和收敛速度。算法步骤如下：首先进行初始化参数，包括蚁群初始化数量、最迭代次数、启发函数因子、挥发因子、信息素等，其中开始的时候每条边的信息素量都相等。将各只蚂蚁分别放在各个的顶点，禁忌表为对应的顶点。其次选取一只蚂蚁，引入贪心策略修改初始路线。传统的蚁群算法，蚂蚁的初始路线是随机生成的，当遇见带有信息素的路线时，根据概率决绝是否要更改路线。蚁群即使当下时刻选择了走带有信息素的路线，下一时刻也不一定会继续走带有信息素的路线，反而是继续走随机路线。由于随机路线是随机生成的，当参数设置不当时，算法搜索路径的时候会延
14、长，收敛速度极慢，因此引入贪心策略，设置蚁群的初始路线，减少算法迭代的时间。计算一只蚂蚁额的转移概率()kijpt，选择下一个顶点，更新禁忌表，再计算概率，再选取顶点，循环往复，直至这只蚂蚁遍历了所有顶点。计算当前这只蚂蚁留在各条边上的信息素增量，然后该蚂蚁完成使命死理论算法2022.2443去。所有蚂蚁都重复一样的步骤。直到所有蚂蚁都完成使命。计算各条边的信息素增量ij和信息素量()ijtn+。最后，记录本次迭代的路径，更新当前的最优路径，清空禁忌表。判断是否达到预定的迭代步数，若是则输出当前的最优路径，结束程序，若为否，则继续迭代。2 实验2.1 参数设置蚁群作为一种启发式搜索算法，蚁群算
15、法具有良好的鲁棒性，且易于融合其他算法应用到实际问题中5。贪心蚁群算法的实验参数设置如下表所示，参数的设置都是在经验值的基础上，结合实验效果进行修改的，具有一定的适用性。表 1 相关参数设置参数数值m 蚂蚁个数50Alpha 信息素重要程度因子1Beta 启发函数重要程度因子5Rho 信息素挥发系数0.1NC_max 最大迭代次数200Q 循环一次释放的信息素总量1002.2 实验数据介绍为了验证算法改进的有效性，使用 32 个信息节点来模拟一位生鲜配送员的配送情况，并利用 Matlab 软件编写算法实现。节点的部分信息如下所示。其中节点 1 表示起点，节点2-32 表示顾客，如表 2 所示。
16、假定生鲜配送员以匀速行驶，没有突发状况发生。表 2 部分节点信息标号经度纬度1117.53008530.6974142117.34634930.8159233117.50427130.89692930117.46971530.76148131117.4444330.77901732117.28747330.7549312.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，计算得到总距离约
