摘要
蚁群算法是一种新型的模拟进化算法,具有许多优良的性质,可以很好地解决TSP问题.在分析车辆路径问题(VRP)与TSP区别的基础上,论文将蚁群算法应用于VRP的求解,针对VRP的具体特点,构造了具有自适应功能的混合蚁群算法.该算法对基本规则作了进一步改进,并有机结合了爬山法、节约法等方法,以减少计算时间,避免算法停滞.指出可行解问题是蚁群算法的关键问题,提出了大蚂蚁数、近似解可行化等四个解决策略.计算机仿真结果表明,自适应混合蚁群算法性能优良,能够有效地求解VRP.
Ant Colony Algorithm（ACA） is a novel simulated evolutionary algorithm which shows many promising properties and can solve Traveling Salesman Problem（TSP） efficiently. On the basis of analyzing the difference between VRP and TSP, an Adaptive Hybrid Ant Colony Algorithm（AHACA） is proposed to solve VRP, which is improved from basic ACA by improving the basic rules and integrating 2-opt local search method and C-W algorithm in order to decrease computing time and avoid stagnation behavior of basic ACA. Moreover, the problem of acquiring feasible solution is also discussed, and four resolutions such as Mass Ant, Feasibility Process of Approximate Solutions etc. are also introduced. Simulation results show that the AHACA is feasible and valid for VRP.
出处
《管理科学学报》
CSSCI
北大核心
2007年第3期15-22,共8页
Journal of Management Sciences in China
基金
博士后科学基金资助项目(023209031)
关键词
车辆路径问题
旅行商问题
蚁群算法
爬山法
近似解可行化
vehicle routing problem
traveling salesman problem
ant colony algorithm
2-opt
feasibility process of approximate solutions
