基于改进蚁群算法的交通网络最优路径规划方法
来源:用户上传
作者:李生彪 彭建奎
摘要：针对交通网络最优路径规划问题，提出了一种基于蚁群算法的改进方法。尝试通过改进信息素初始值的取法、更新信息素的规则、引入 Max-Min信息素系统等来准确快速地找到最优路径。实验仿真结果表明， 该方法无论在时间效率还是配送成本方面均取得了显著改进，充分验证了该改进算法的有效性和可行性。
关键词：路径规划；蚁群算法；最优路径；信息素
中图分类号：TP301文献标志码：A在交通网络中，最优路径规划是指寻找从起始地到目标地之间总代价最小的目标路径的过程，交通网络最优路径规划方法是智能交通领域研究的重点问题，解决该问题的传统算法主要有广度优先搜索法、Dijkstra算法等。 近些年，随着智能技术的出现，一些学者采用群体仿生理论来解决最优路径规划问题，主要有蚁群算法、遗传算法、神经网络算法以及各算法之间的组合优化算法等。
蚁群算法模拟蚂蚁合作觅食行为的性质，具有较强的全局搜索能力和并行性等优点。但传统蚁群算法有易陷入局部最优解、搜索时间长、有时无法跳出死锁状态等局限性［1］。国内外学者对蚁群算法提出了一些改进思路，如高尚等［2-3］加入混沌理论，赵宝江［4］提出基于自适应路径选择和动态信息素更新的蚁群算法，黄贵玲等[5]加入直线优化启发信息， FUELLERER等[6]加入几种其他启发式算法以提高算法效率，DONATI等[7]则完成了对多个目标的优化等。本研究针对传统经典蚁群算法的局限性，改进信息素浓度更新方式，通过优化信息素总量增强全局搜索能力，以使算法更好地满足于求解交通系统的最优路径问题。
1环境建模
2传统蚁群算法及模型
蚂蚁在巢穴和食物之间的路径上会释放信息素，最开始时不论路径的长短都是等概率地选择下一步可行路径。后来，随着迭代次数的增加，蚂蚁在移动时会选择信息素浓度高的路线，这样就使得较短路线上的蚂蚁数量不断增加，较长路线上蚂蚁数量不断减少。因此，通过这些信息素，蚂蚁可以找到一条巢穴到食物的最短路径。
3基于信息素更新方式改进的蚁群算法
3.1信息素浓度限定原则
3.2信息素局部更新算法的改进
3.3信息素全局更新模型的改进
3.4改进蚁群算法的实现步骤
4实验仿真及结果
4.1问题描述
设有一家连锁店企业，有20家连锁分店，编号为1～20，其货物储存仓库（编号为0，坐标为（10，40））每天都向各个连锁分店进行商品补给，该企业每天可调度的车辆数是4辆。 为了方便测试，将储存仓库及20个连锁分店的位置坐标映射至 XOY 平面上，如图1所示。各连锁分店的位置坐标及每天所需补给量如表1所示。
4.2参数设置
综上所述，本文算法较传统蚁群算法在时间效率和配送成本方面均有明显程度的提升，在交通网络最优路径规划问题上更具高效性。参考文献：
[1]王亚文， 汪西莉， 曹菡． 一种限制搜索区域的多比例尺最优路径规划算法［J］． 计算机应用研究， 2007， 24（12）： 66-71.
［2］ 高尚. 解旅行商问题的混沌蚁群算法[J]. 系y工程理论与实践， 2005（9）： 100-104.
［3］ 孙晓莉， 钟亮， 田淑静， 等． 基于ArcGIS的城市道路网最优路径探讨［J］． 贵州大学学报（自然科学版）， 2019， 36（3）： 27-31.
［4］ 赵宝江. 蚁群聚类算法的T-S模糊模型辨识［J］. 计算机工程及应用， 2012， 47（21）： 153-156.
[5] 黄贵玲， 高西全， 靳松杰． 基于蚁群算法的最短路径问题的研究和应用[J]． 计算机工程与应用， 2007， 43（13）： 233-235．
[6] FUELLERERA G， DOERNERA K F， HARTLA R F. Ant colony optimization for the two-dimensional loading vehicle routing problem[J]. Computers & Operations Research， 2009， 36（3）： 655-673.
[7] DONATI A V， MONTEMANNI R， CASAGRANDE N， et al. Time dependent vehicle routing problem with a multi ant colony system[J]. European Journal of Operational Research， 2008，185（3）： 1174-1191.
［8］ 余必秀， 初秀民， 柳晨光， 等. 基于改进A*算法的无人航道测量船路径规划方法［J］. 武汉大学学报（信息科学版）， 2019， 44（8）： 1258-1264.
［9］ 曹新亮， 王智文， 冯晶， 等. 基于改进蚁群算法的机器人全局路径规划研究［J］. 计算机工程与科学， 2020， 42（3）： 564-570.
［10］ 白建龙， 陈瀚宁， 胡亚宝， 等. 基于负反馈机制的蚁群算法及其在机器人路径规划中的应用［J］. 计算机集成制造系统， 2019， 25（7）： 1767-1774.
［11］ 张瑞姣， 陈崇成， 黄正睿， 等. 改进遗传算法求解文化旅游线路规划问题［J］. 贵州大学学报（自然科学版）， 2022， 39（1）： 57-64.
［12］ 马小陆， 梅宏. 基于改进势场蚁群算法的移动机器人全局路径规划［J］. 机械工程学报， 2021， 57（1）： 19-27.
（责任编辑：曾晶）
Optimal Path Planning for Traffic Network Based
on Improved Ant Colony Algorithm
LI Shengbiao PENG Jiankui
（College of Education， Lanzhou University of Arts and Science， Lanzhou 730000， China）Abstract： Aiming at solving the problem of optimal path planning in traffic network， an improved method based on ant colony algorithm is proposed. This method attempts to find the optimal path accurately and quickly by improving the initial value of pheromone， updating the rules of pheromone and introducing Max-Min pheromone system. The experimental simulation results show that this method has significantly improved the time efficiency and distribution cost， which fully verifies the validity and feasibility of the algorithm.
Key words： path planning; ant colony algorithm; optimal path; pheromone
nlc202211161118
转载注明来源:https://www.xzbu.com/1/view-15442203.htm
