带运力限制车辆路径问题的简易蚁群算法实现  

A simplified ant colony algorithm for capacity-constrained vehicle routing problem

作　　者：潘志铭[1] 林少聪[1] 李霞[1] 

机构地区：[1]深圳大学信息工程学院,深圳518060

出　　处：《深圳大学学报（理工版）》2005年第3期221-225,共5页Journal of Shenzhen University(Science and Engineering)

基　　金：国家自然科学基金资助项目(60372087)

摘　　要：以求解旅行商问题的蚁群算法为基础,根据带运力限制车辆路径问题的实际应用条件,提出一种较为简易的求解带运力限制车辆路径问题的蚁群算法,并对其中的信息素更新策略进行了分析,对蚁群中的精英蚂蚁(搜索出最优解的蚂蚁个体)所经过路径的信息素进行加强,提高了算法的全局收敛性能和收敛速度,允许蚂蚁在搜索的最初阶段有较大的自由以扩大最优解的寻找空间,提出改进蚁群算法.实验结果表明,该方法能在较短的时间内达到已知最优解的1.5%误差范围.With the ant colony algorithm for solving the traveling salesman problem （TSP） as a prototype, a simplified algorithm was developed which considered a capacity-constrained vehicle routing problem as several independent TSPs with the depot serving as one of the cities in each TSP. Pheromone update was analyzed and it was found in the searching process that, if the current solution is best of all so far, then increase of the pheromone of the path found by the elitist ants further improves the solution and speed up the convergence. Moreover, allowing more degree of freedom at the initial stage results in better solution. Experimental results show that the simplified algorithm can efficiently find a satisfactory solution, with an error of no more than 1.5% of the optimal one.

关 键 词：带运力限制的车辆路径问题 蚁群算法 信息素更新 全局收敛性 收敛速度 

分 类 号：O22[理学—运筹学与控制论]