基于改进蚁群算法的车辆路径优化

宋志飞 张俊峰

摘要：对基本蚁群算法做了分析的基础上，针对车辆交通路径的特点，本文提出适用于求解车辆路径规划问题的改进算法。在基本蚁群算法的基础上引入启发式因子，提高了算法前期的收敛速度.分析了参数对算法结果准确性与蚁群算法求解速度的影响，提出了自适应调整参数的策略，以提高解的质量.结合仿真实验的数据，将改进蚁群算法与基本蚁群算法进行了比较，实验验证了改进算法的可行性.

关键词：蚁群算法；车辆路径优化；最优路径

中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2018）23-0225-02

随着相关学者及专家对车辆路径在优化问题的分析中，提出了许多算法，如启发式算法、遗传算法和禁忌搜索算法[1].随着经济与社会的发展，交通拥挤已成为制约城市和区域发展的瓶颈之一.寻找高效、合理的车辆交通路线已成为交通网络系统急需解决的难题.城市交通网络诱导系统采用定位系统、电子地图、通信技术和当前交通状况给驾驶者提供最优的路线[2].

1 基本蚁群算法

基本蚁群算法是从自然界中真实蚂蚁集体觅食行为提出的，蚂蚁群体在寻找食物时将一种叫作信息素的物质会从它们走过的路径中散发出来，其他通过该路径的蚂蚁会根据留在该段路径的信息素的多少来判别要不要走该段路径，最终会找到一段从最短路径.

2 改进的蚁群算法

2.1 TSP与车辆路径优化的区别

（1） 在TSP问题中，开始点与目的点是随机的，开始点与目的点一般是同一点的，蚂蚁可以随机出现在任何城市.在路径优化问题中，起点和终点是确定好的[4].在TSP问题中，起始点一般与目标点相同.而一般在交通问题中，开始点与目的点不是同一点；

（2） 城市车辆交通网络中，节点较大，计算城市之间的距离需要花费大量时间，并且由于城市交通网络的复杂性和不稳定性，距离矩阵通常是稀疏矩阵 [5]；

（3） 而在TSP问题中，城市间的构成的距离矩阵一般都是对称矩阵，即[dij=dji]，而在交通网络中，则不一定就是，即[dij≠dji]；

（4） 城市交通网络中仍然存在一个节点只发散一个边，相当于設置了一个陷阱，这使得搜索蚂蚁失去了前进的能力，但是在TSP问题中没有这样的问题.

2.2 交通网络蚁群算法

当基本蚁群算法用于解决交通问题时，很容易陷入局部最优解.基本蚁群算法一开始就没有有效的启发因素，搜索的盲目性.提出了以下改进方法.

2.2.1 启发式因子

通过一开始就增加对目标节点的引导，改进算法在开始时获得较好的起始值，提高蚁群在目标节点附近的速度，加快收敛速度，在短时间内找到最优值，并减少资源消费。

4 结束语

仿真结果表明，改进蚁群算法的收敛速度明显提高.同时，为了减少算法进入局部最优解的可能性，提高了算法的自适应能力.仿真实验结果表明，改进后的算法与基本蚁群算法相比，可以加快算法的速度.收敛速度进一步提高了蚁群算法的有效性，为车辆路径优化问题提供了一种优化的途径.

参考文献：

[1] MitsuoGen，Run Wei Cheng，Ding Wei Wang.Genetic Algorithms for Solving Shortest Path Problems[J].IEEE.2002，10（1）：121-135.

[2] 赵家俊，于宝琴.现代物流配送管理[M].北京：北京大学出版社，2004.

[3] 胡小兵，黄席樾.蚁群优化算法及其应用[J].计算机仿真，2004，21（5）：81-85.

[4] 温惠英，徐建闽.基于改进型蚁群算法的车辆导航路径规划研究[J].公路交通科技，2009，1（26）：125-129.

[5] 雷登云，赵炜.基于改进蚁群算法的车辆路径优化模型[J].电子科技，2010，23（1）：8-14.

[6] 靳凯文，李春葆，秦前清.基于蚁群算法的最短路径搜索方法研究[J].公路交通科技，2006，23（3）：128-134.

[7] 范红平，陈丽娟，杨国军，等.GAAA算法在直线步进电机控制中的应用[J].电子科技，2006（10）：51-54.58.

【通联编辑：唐一东】