面向车辆路径问题的改进蚁群算法研究

为解决基础蚁群算法在求解车辆路径问题时出现收敛速度慢、易陷入局部最优解等问题,提出了一种改进蚁群算法.首先,引入节约矩阵更新选择概率公式引导蚂蚁搜索;其次,运用分段函数改进挥发因子,调整算法的收敛速度;再次,使用2-opt法,提高算法的局部搜索能力;最后,选取车辆路径问题国际通用数据集进行仿真,运用控制变量法找到信息素...

Research on vehicle routing problem based on improved ant colony algorithm[JP]

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.