摘要
车辆路径问题(VRP)是物流研究领域中一个具有重要理论和现实意义的问题.蚁群算法是一种新型的模拟进化算法,可以很好地解决旅行商问题(TSP).在分析VRP与TSP区别的基础上,构造了求解VRP的自适应蚁群算法.指出可行解问题是蚁群算法的关键问题,并重点对该问题进行了研究,提出了近似解可行化等解决策略.实验结果表明,自适应蚁群算法性能优良,能够有效地求解VRP问题.
On the basis of analyzing the differences between vehicle routing problem (VRP) and traveling salesman problem (TSP), an adaptive ant colony algorithm (AACA) is proposed to solve VRP, which is improved from basic ACA by means of integrating C-W algorithm and introducing the adaptive ant attraction of arc in order to decrease computing time and avoid stagnation behavior. Moreover, how to acquire feasible solution is a key problem in this algorithm, and three relative resolutions such as the feasibility process of approximate solution arc presented. The computational experiments show that the AACA is feasible and valid for VRP.
出处
《控制与决策》
EI
CSCD
北大核心
2005年第5期562-566,共5页
Control and Decision
基金
国家"十五"科技攻关项目(2001BA205A08-04).
关键词
车辆路径问题
旅行商问题
自适应蚁群算法
近似解可行化
吸引力
Adaptive algorithms
Genetic algorithms
Information retrieval
Optimization
Traveling salesman problem
