摘要
为解决基础蚁群算法在求解车辆路径问题时出现收敛速度慢、易陷入局部最优解等问题,提出了一种改进蚁群算法。首先,引入节约矩阵更新选择概率公式引导蚂蚁搜索;其次,运用分段函数改进挥发因子,调整算法的收敛速度;再次,使用2-opt法,提高算法的局部搜索能力;最后,选取车辆路径问题国际通用数据集进行仿真,运用控制变量法找到信息素因子和启发函数因子的合适取值,以P类数据测试算法的改进效果,并与基础蚁群算法、遗传算法、模拟退火算法和粒子群算法进行对比。结果表明,相较于基础蚁群算法,改进蚁群算法的最优路径总长度平均减少了6.97%;与遗传算法、模拟退火算法和粒子群算法相比,改进蚁群算法的寻优能力更强、收敛速度更快。因此,改进蚁群算法可以有效减少路径长度,跳出局部最优,加快收敛速度,尤其是在单路线允许服务点较多且各点分布较离散的车辆路径情况下,其优势更为明显,可为解决车辆路径问题提供一定的参考。
In order to solve the problems of slow convergence and easiness to fall into local optimal solution in solving vehicle routing problem, an improved ant colony algorithm was proposed.Firstly, the saving matrix updating selection probability formula was introduced to guide ant search;Secondly, the piecewise function was used to improve the volatilization factor and adjust the convergence speed of the algorithm;Thirdly, the 2-opt method was used to improve the local search ability of the algorithm;Finally, the international general data set of vehicle routing problem was selected for simulation, and the control variable method was used to find the appropriate values of pheromone factor and heuristic function factor.The improvement effect of the algorithm was tested with class P data, and compared with basic ant colony algorithm, genetic algorithm, simulated annealing algorithm and particle swarm optimization algorithm.The results show that compared with the basic ant colony algorithm, the total length of the optimal path of the improved ant colony algorithm is reduced by 6.97%;Compared with genetic algorithm, simulated annealing algorithm and particle swarm optimization algorithm, the improved ant colony algorithm has stronger optimization ability and faster convergence speed.Therefore, the improved ant colony algorithm can effectively reduce the path length, jump out of the local optimization and accelerate the convergence speed.Especially in the case of a single route that allows more service points and discrete distribution of points, its advantages are more obvious, which provides a certain reference for solving the vehicle routing problem.
作者
刘紫玉
赵丽霞
薛建越
陈军霞
宋伟
LIU Ziyu;ZHAO Lixia;XUE Jianyue;CHEN Junxia;SONG Wei(School of Economics and Management,Hebei University of Science and Technology,Shijiazhuang,Hebei 050018,China)
出处
《河北科技大学学报》
CAS
北大核心
2022年第1期80-89,共10页
Journal of Hebei University of Science and Technology
基金
河北省社会科学基金(HB20GL011)。
关键词
交通运输工程其他学科
基础蚁群算法
路径规划
挥发因子
2-opt法
other disciplines of transportation engineering
basic ant colony algorithm
route planning
volatile factor
2-opt method
