基于改进蚁群算法在粮食物流配送路径优化的应用研究

何小虎

（渭南师范学院 数学与信息科学学院，陕西 渭南　714000）

基于改进蚁群算法在粮食物流配送路径优化的应用研究

何小虎

（渭南师范学院 数学与信息科学学院，陕西 渭南714000）

为了有效地降低粮食的运输成本，提出了一种改进的蚁群算法对粮食物流配送路径进行优化。该算法通过改进蚂蚁的转移规则、初始化信息素和全局信息素以及增加各条路径信息量调整的局部更新规则。仿真实验结果表明，改进的蚁群算法比基本蚁群算法可以更好地解决粮食物流配送路径优化问题，路径长度明显缩短，从而使有限的资源发挥更大的作用。

蚁群算法；粮食物流；路径优化；信息素

在粮食价格的构成中，生产成本所占比重最大，其次就是粮食流通成本。但流通费用越来越成为影响农产品价格和竞争力的一个较为重要的因素。我国是粮食的生产大国，也是粮食的消费大国，因此，研究如何有效地降低粮食的运输成本，提高运输效益，将有十分重要的现实意义。

降低粮食的运输成本，就是要设计合理的车辆运输路线方案，尽量减少配送里程数和配送时间，有效地减少车辆的空驶率和增加车辆的利用率，降低运输成本，节约运输时间［1］。解决这类问题的方法较多，包括遗传算法、模拟退火算法、禁忌搜索算法和蚁群算法等。其中，蚁群算法是一种新型的智能优化算法，已经成为解决配送路径选择问题的有效方法。因此，文中对基本蚁群算法进行改进，建立数学模型，进而对粮食物流配送车辆路径问题进行了实验仿真。结果表明，改进后的蚁群算法提高了全局寻优能力与收敛速度，取得了较好的效果。

1　蚁群算法

蚁群算法是意大利学者Marco Dorigo等人于1991年受自然界蚂蚁觅食过程启发而提出的一种新型智能搜索优化算法。随后将蚁群算法成功地应用于旅行商问题求解上，并取得了非常好的实验结果。受其影响，蚁群算法受到许多研究者者的关注，并不断应用于实际问题求解，蚁群算法已经被广泛地应用到各个领域解决复杂组合优化问题。蚁群算法具有鲁棒性、并行性、分布性、全局寻优、易于与其他优化算法相结合等优点，能够在较短时间内发现问题的最优解，使这种仿生优化算法展现出广阔的应用前景。

1.1蚁群算法的原理

蚂蚁在觅食的时候，经过一定的时间，就可以找到一条从巢穴到食物源二者的最短路径，通过生物学家研究发现，蚂蚁视觉系统发育不全甚至没有，蚂蚁协助完成觅食是依靠一种叫信息素的化学物质来完成。蚂蚁在爬行过的路径上会遗留下信息素。同时蚂蚁会根据信息素的浓度来选择走一条路径，当那条路径上的信息素浓度越浓时，蚂蚁选择该路径的概率越大，这样就会有更多的蚂蚁选择该条路径。相反，在信息素浓度越少的路径上，蚂蚁选择的概率越小，该路径随着时间的推移信息素逐渐挥发，而导致以后蚂蚁选择的可能性更小。最终信息素浓度最高的路径就是蚂蚁找出的最优路径。蚁群算法就是通过这种正反馈机制来寻找优解的执行过程。

1.2蚁群算法的基本模型

蚁群算法可以表述如下：初始时刻，各条路径上的信息素量相等，设τij（0）=C（C为常数），蚂蚁k（k=1，2，3，…，m）在运动过程中根据各条路径上的信息量决定转移方向。蚂蚁系统所使用的转移规则被称为随机比例规则，在时刻 t，蚂蚁k从城市i选择城市j的转移概率Pkij（t）为：

其中，Jk（i）=｛1，2，……，n｝-tabuk表示蚂蚁k下一步允许选择的城市。列表tabuk记录了蚂蚁k在本次迭代中已经走过的城市，不允许该蚂蚁在本次循环中再经过这些城市。当所有n座城市都加入到tabuk中时，蚂蚁k便完成了一次周游，此时蚂蚁k所走过的路径便是TSP问题的一个可行解。式（1）中的ηij是一个启发式因子，被称为能见度因子。在 AS算法中，ηij通常取城市i与城市j之间距离的倒数。α和β分别反映了在蚂蚁的运动过程中已积累的信息和启发信息的相对重要程度。当所有蚂蚁完成一次周游后，各路径上的信息素根据（2）式更新。

其中ρ（0＜ρ＜1）表示路径上信息素的挥发系数，1-ρ表示信息素的持久系数；Δτij表示本次迭代边 （ij）上信息素的增量。Δτkij表示第k只蚂蚁在本次迭代中留在边（ij）上的信息素量。如果蚂蚁 k没有经过边（ij），则Δτkij的值为0。Δτkij表示为：

其中，Q为正常数，Lk表示第k只蚂蚁在本次周游中所走过路径的长度。

2　改进蚁群算法

蚁群算法是模拟自然界中蚂蚁觅食行为的随机搜索算法［2］，具有正反馈作用，通过一群蚂蚁之间的信息交流和传递，最终找到最优解。蚁群算法具有好的鲁棒性、并行性计算能力、正反馈机制。但是也有一些缺点：

1）与其他算法相比，该算法收敛速度慢，搜索需要一段较长的时间［3］。

2）算法容易出现搜索停滞现象，即算法进行到一定程度后，所有妈蚁都集中走同一条路径，不能进行新路径的搜索，不能发现更好的解，算法收敛到局部最优解而非全局最优解［4］。

针对蚁群算法存在的缺点，提出了改进的蚁群算法，初始化信息素浓度时加入了方向引导，在全局信息素更新上引入了sigmiod函数作为动态因子σ，自适应地调节每次迭代最优解对路径的信息素更新的比重。

2.1蚂蚁的转移规则不同

在ACS中蚂蚁选择下一个城市使用的公式。

其中q为区间［0，1］内的随机数，q0为［0，1］内的一个参数。S是根据公式（1）确定的。这种以一定随机概率的形式确定蚂蚁行为的方法为随机概率选择规则。当蚂蚁要选择下一个移动的城市时。算法会产生一个［0，1］范围内的随机数q，并判断随机数与参数q0的关系，最后选择确定蚂蚁移动方向的方法。

2.2初始化信息素的改进

针对上面提到的问题［4］，修改妈蚁的初始化信息素强度，取

其中±deje为节点j与终点e的直线矢量距离，W为系统设定的一个正常数。

由式（2）可以看出deje，deje较小，τij（0）就较高，蚂蚁倾向于选择该条路径作为移动方向，加强了蚂蚁在选择下一个节点时指向终点搜索的方向性，减少了不必要的劣质解，缩小了解空间的搜索范围，提高解空间的质量，从而加快了找到全局最优解的速度。

2.3全局信息素的改进

当m只蚂蚁都完成一次循环，则按照全局更新规则只更新该次迭代最优解路径的信息素浓度，其他不更新［4］。全局更新规则由公式（3）给出。

其中L为目前的局部最优解之和的平均路径长度，为此次迭代局部最优解，为目前为止的全局最短路径长度，//为给定参数。

2.4新增了对各条路径信息量调整的局部更新规则

所有的蚂蚁在完成每一次的转移后，都对所经过路径上的信息素进行局部更新，其公式为

其中，Δτ（r，s）的取值可以为0，也可以为一定值。

2.5蚁群算法主要步骤描述如下［4］：

1）初始化参数Q、C、α，β，W，μ。

2）按照公式（2）初始化信息素，并将结果存放到τij（0），在起点S置于n个蚂蚁。

3）启动蚁群，对每一只蚂蚁根据状态转移规则公式（1）选择下一个节点，并更新它们的禁忌表。

4）经过m个时刻，蚂蚁k遍历完一次路径时，按照公式（4）局部更新规则进行更改路径的信息素浓度，更新该次迭代的当前最好路径。

5）当所有蚂奴都进行一次完整的搜索遍历后即一次迭代后，此时按照式（3）全局更新只更新该次迭代的最优路径信息素浓度，更新找到的最好路径，nc=nc+l。

6）若nc等于系统设定的最大迭代次数，则搜索遍历结束，输出最优路径和长度；否则清空禁忌表，返回3）。

3　改进蚁群算法仿真测试

实验室采用图1所示。模拟21个粮食运输点来进行蚁群算法的分析和研究。

图1　优化线路图

如图1所示，我们要求出一条从节点0到节点21的这样的最短路径问题。运用蚁群算法搜索出存在唯一的最优路径：21-20-17-18-6-19-4-3-10-13-5-2-7-8-11-14-12-16-15-9-1，路径长度为38.201公里。

在参数设置基本相同的情况下，用改进的蚁群算法与ACS算法进行仿真比较，并将两者的结果进行对比，见表1。

通过结果对比，ACS的10次平均长度是：40.522 2公里，ACS的10次平均迭代次数是：113次，而改进后的蚁群算法的10次平均长度是：38.548 6公里，改进后的蚁群算法的10次平均迭代次数是：79次。可以看出改进后的蚁群算法在平均路径长度和迭代次数上要明显优于ACS。

表1　本文算法与ACS在平均路径长度和迭代次数上的对比

4　结束语

实验仿真结果表明，求解粮食物流配送路径优化问题时，使用文中改进后的蚁群算法有如下优点：1）找到最优解的概率更高；2）求解效率和性能都进一步提高．但是蚁群算法是一种先进的仿生智能优化算法，今后对参数的设置和算法的优化需要进一步的研究和完善。

［1］余昌艳.基于蚁群算法的粮食加工企业物流配送路径优化研究［D］.武汉：武汉科技大学，2009.

［2］高尚.蚁群算法理论、应用及其与其他算法的混合［D］.南京：南京理工大学，2005.

［3］汪采萍.蚁群算法的应用研究［D］.合肥：合肥工业大学，2007.

［4］吴虎发.蚁群优化算法在求解最短路径问题中的研究与应用［D］.合肥：安徽大学，2012.

［5］龙汀.基于蚁群算法的车辆路径问题的研究［D］.合肥：合肥工业大学，2009.

［6］陈迎欣.基于改进蚁群算法的车辆路径优化问题研究［J］.计算机应用研究，2012，29（6）：2031-2034．

Application research on quantum ant colony algorithm in grain logistics distribution path optimization

HE Xiao-hu
（College of mathematics and Information Science，Weinan Teachers College，Weinan 714000，China）

A modified ant colony algorithm was proposed to optimize grain logistics distribution path in order to reduce transportation cost effectively.The proposed algorithm adjusted local update rules via the following ways，such as improvement transition rule of the ant，initialization pheromone and global pheromone as well as increase the amount of information of each path.The simulation results showed that the modified algorithm provided a better solution in grain logistics distribution path optimization than the basic ant colony algorithm.It can cut down path length and therefore play a bigger role in utilization of the limited resources.

ant colony algorithm；grain logistics；path optimization；pheromones

TN-9

A

1674－6236（2016）09-0039-03

2015-05-17稿件编号：201505137

陕西自然科学基础研究计划项目（2014JM1026）；陕西教育厅教改项目（13BY91）；渭南师范学院项目（15YKP002）；校级特色学科建设项目资助（14TSXK02）；陕西自然科学研究发展计划项目（2014JM2-1004）

何小虎（1980—），男，陕西渭南人，硕士，讲师。研究方向：智能算法优化及其应用。