摘要
蚁群算法是一种新型的模拟进化算法,具有许多优良的性质,可以很好地解决旅行商问题(TravelingSalesmanProblem,TSP),但同时也存在计算时间长、易出现停滞等缺陷。在分析车辆路径问题(VehicleRoutingProblem,VRP)与TSP区别的基础上,将蚁群算法应用于VRP的求解,通过引入解均匀度、选择窗口以及吸引力等概念对算法的转移策略和更新策略进行改进,构造了具有自适应功能的蚁群算法。实验仿真结果表明所设计的算法具有很强的搜索能力,计算效率较高,能够有效地解决加速收敛与停滞现象之间的矛盾。
Ant Colony Algorithm (ACA) is a novel simulated evolutionary algorithm which shows many promising characters and has been successfully applied to the Traveling Salesman Problem (TSP), which is the prototype of the NP-hard problems. However, ACA has some typical shortages too, such as long computing time, stagnation behavior. ACA is applied to solve Vehicle Routing Problem in terms of the similarity and difference between VRP and TSP, and an Adaptive Ant Colony Algorithm (AACA) is proposed, which is improved from ACA through modifying the pheromone updating rule and the transition rule by introducing Evenness of Solution, Selection Window, Ant Attraction of Arc into it in order to decrease computing time and avoid stagnation behavior of basic ACA. Simulation results show that the AACA can settle the contradictory between convergence speed and stagnation behavior efficiently and is very suitable for solving VRP.
出处
《系统仿真学报》
EI
CAS
CSCD
北大核心
2005年第5期1079-1083,共5页
Journal of System Simulation
基金
国家863/CIMS主题项目(2001AA414230)
关键词
车辆路径问题
旅行商问题
解均匀度
选择窗口
吸引力
自适应蚁群算法
vehicle routing problem
traveling salesman problem
evenness of solution
selection window
ant attraction of arc
adaptive ant colony algorithm
