改进蚁群算法在车辆路径优化问题中应用

代婷婷

(昭通学院数学与统计学院 云南 昭通 657000)

随着全球经济和互联网的飞速发展，物流产业已成为国民经济的重要组成部分。但是我国物流发展存在成本高、效率低的问题。物流配送环节是物流行业的一个重要环节，优化物流配送路径是降低物流运输成本、促进物流发展的关键。因此，在物流配送中如何高效规划物流车辆路径就成为人们关心的焦点问题。合理调配优化物流车辆，可以减少车辆的费用支出，提高物流车辆的运载效率，同时可以增加用户的满意度和企业的经济效益[1]。国内外学者关于车辆路径问题展开大量研究，并提出了多种解决方案，通常情况下这些解决方案分为精确算法和传统启发式算法、智能算法[2]，关注精确算法的学者主要研究路径规划问题，涉及的节点少，规模小的情况，VRP的集分割法是最为突出的一种精准算法，是由Balinski等人提出的，并且通过一些算法的优化设计，建立了简单的VRP模型[3,4]。

随着节点和规模的增大，精确算法不足以解决大规模的路径规划问题。为此，这些年学者们的关注点转移到了启发式算法的应用。因为启发式精确算法不但运行时间和复杂度比之前的算法大大降低，而且应用范围相当广泛。本文将在前人研究的基础上，通过将两种改进蚁群算法[5,6]融合，得到了解决优化路径问题的一种新的改进蚁群算法。并通过具体的数据来试验这种方法的有效性和优势。

1 基本蚁群算法

Marco Dorigo[7-9]于1992年在他的博士论文中首次提出了蚁群算法的相关概念，并且阐述了该算法的灵感来源于蚂蚁在寻找食物过程中发现路径的行为。其实就是通过对自然界中蚂蚁搜索路径的行为进行模拟，得到的一种模拟进化算法。按照此机制，以达到寻找到最短路径的目的，具体的模型如下。

设i为外出觅食蚂蚁的出发点，则其到达觅食终点j的随机行进概率可表为

(1)

τij(t+1)=(1-ρ)τij(t)+Δτij(t)

(2)

(3)

蚁群算法的核心就是利用蚂蚁觅食过程中信息素浓度变化的原理来设计的。因此，该算法不但拥有较强的最短路径计算求解能力[1]，而且在求解过程中还可避免过早收敛。除此之外，利用贪婪搜索能力可以降低寻优路径的时间。

2 改进蚁群算法的提出依据

2.1 改进启发函数

基于基本蚁群算法的原理分析以及结合相关的参考文献，我们发现影响最短路径计算结果的主要原因就是节点之间的概率转移和行走路径上的信息素浓度的更新。一般情况下，取节点i与下一个节点j之间的欧氏距离的倒数作为转移概率中的启发函数。实际上，在最初搜索的时候，行走路径上的蚂蚁数量较少，释放的信息素较少，造成其他蚂蚁偏离正确寻找路径的概率较大，从而形成局部最优解或无效解[12]。因此文献[5]在启发函数中引入了下一节点和目标节点之间的欧氏距离，从而加强当前节点与目标节点的联系，数学表达式为

(4)

其中，dij表示当前节点i与下一个可行节点j之间的欧氏距离，djE是下一可行节点j到目标节点E的欧氏距离,于是搜索路径的方向性被加强，则运行时间也就相应缩短，提高了算法的时间效率。

2.2 更新信息素浓度

信息素浓度的更新方式对蚁群算法的效率也具有较强的影响力[13]。更新信息素浓度的主要原因有以下几方面：第一，信息素浓度与路径的长度有着密切的联系，为了防止积累过多使算法过早局部收敛，信息素浓度进行更新是必不可少的；第二，由于大自然的固有特性，随着时间的推移，因为蒸发使得路径上信息素浓度降低；第三，经过行走路径的所有蚂蚁都会释放信息素，正因为其正反馈性，最短路径上的蚂蚁最多，信息素也最多；要在全部路径中凸显最优路径[14,15]。文献[6]通找到了当次迭代中的最优路径和最差路径，通过加强最优路径上的信息素同时减弱最差路径上的信息素释放量，将信息按照式(5)的方式更新，防止收敛过快而陷入局部最优。

(5)

上式中Lbest表示此次迭代中最优路径长度，Lworst表示此次迭代中的最差路径。

针对以上两种改进的优点，本文将文献[5]的启发函数改进和文献[6]提出的信息素浓度更新的方案结合起来提出了一种新的改进蚁群算法。

2.3 改进蚁群算法的参数设置与步骤

通过对文献的详细阅读，本文将文献[5]和[6]的两种改进算法融合得到了一种新的求解车辆路径优化问题的遗传算法，具体的参数设置如表1。

表1 改进蚁群算法参数设置

融合后得到的改进蚁群算法如下：

Step1:设m为蚂蚁数量，s为起始点，g为目标函数，Nmax为最大的迭代次数，设置α和β的值分别为1和6，将所有的蚂蚁都置于起始点。

Step2:所有蚂蚁都从s点出发，随后将s加入禁忌表。

Step3:依据公式(4)寻找下一个节点，将找到属于可行节点集合的节点作为下一个可行节点，并且将其放入到禁忌表中。

Step4:对当前蚂蚁的行走路径做好标记，判断蚂蚁是否已到终点，如果没有到达终点，返回至Step3；若是蚂蚁到达了终点，接着判断其是否已走完全程，是则执行Step5，否则转至Step2使下一只蚂蚁出发。

Step5:等到全部蚂蚁到达目标节点之后，计算每只蚂蚁的路径长度，找出最优解和最差解，然后按照公式(5)对信息素更新，同时增加迭代次数。

Step6:当达到最大迭代次数的时候，输出最短路径，否则转到Step2。

3 实证分析

本文采用Matlab2019进行仿真实验，以规模为30的车辆调配问题进行算法对比验证，说明本文将两种改进蚁群算法融合后形成新算法的可行性和有效性。在新的改进遗传算法的求解过程中，收敛条件设置为文献[5]和文献[6]中的条件，改进算法求解过程中两条求解最优的路径差值不超过0.01%。

3.1 利用基本蚁群算法求解

在使用此方法求解时，设定基本蚁群算法的参数为m=30,Nmax=120,α=1,β=4,ρ=0.7,Q=100,将此方法使用于求解规模为30的车辆调度问题时，得到的结果如图1所示。

实验结果表明：采用基本蚁群算法求解30车辆的路径优化问题得到的最优路径长度为417.20，运算过程耗时19.23 s。

3.2 利用改进蚁群算法求解

设定改进蚁群算法的参数如表1所示，将此方法使用于求解规模为30的车辆调度问题时，得到的结果如图2所示。

图1 普通蚁群算法求解规模为30车辆优化问题时的最优路径与迭代次数

图2 改进的蚁群算法在求解30车辆得到的最优路径和迭代次数

针对30辆车的优化路径问题，改进遗传算法的求解结果获得的最优路径长度为401.96 m，而时间耗费时长只有12.01 s。

为了更清楚地凸显本文得到的改进蚁群算法在解答规模为30车辆的路径优化问题时具有更好的效果。在表2中将该算法和文献[5,6]的算法以及基本蚁群算法的结果进行了分析比较。

表2 不同算法得到的最优路径和运行时长

根据表2的数据可以得出，本文融合改进的蚁群算法与传统的算法、文献[5,6]的算法相比，在求解最优路径问题中具有较高的运算效率，不管是在最优路径上还是运行耗时上都比传统方法具有明显的优势。

4 结论

蚁群算法作为常用的智能优化算法，除了最早的在旅行商问题上的应用之外，还有很多其他的优化应用，尤其是在处理路径规划问题上，此方法的应用非常的普遍。因此，通过查阅相关的资料文献，本文首先对普通蚁群算法的原理进行了详细介绍分析，然后将文献[5]中改进的启发因子和文献[6]中改进的信息素更新融合在一起，产生了一种新的改进蚁群算法，对形成新的蚁群算法的具体步骤进行了阐述并设置了该算法在实验中的相关参数，为了突出改进遗传算法的优势，本文在选择了节点规模为30的车辆优化路径问题作为实验案例，使用普通的遗传算法和改进的遗传算法对节点规模为30的车辆路径优化问题进行了求解对比，得出改进蚁群算法在求解路径优化问题中的可行性和有效性，且求解出的最优路径和迭代次数收敛曲线，以及运行耗时上都比传统的蚁群算法的优势明显。