[1]潘志铭,林少聪,李霞.带运力限制车辆路径问题的简易蚁群算法实现[J].深圳大学学报理工版,2005,22(3):221-225.
 PAN Zhi-ming,LIN Shao-cong,LI Xia.A simplified ant colony algorithm for capacity-constrained vehicle routing problem[J].Journal of Shenzhen University Science and Engineering,2005,22(3):221-225.
点击复制

带运力限制车辆路径问题的简易蚁群算法实现()
分享到:

《深圳大学学报理工版》[ISSN:1000-2618/CN:44-1401/N]

卷:
第22卷
期数:
2005年3期
页码:
221-225
栏目:
光电与信息工程
出版日期:
2005-07-30

文章信息/Info

Title:
A simplified ant colony algorithm for capacity-constrained vehicle routing problem
文章编号:
1000-2618(2005)03-0221-05
作者:
潘志铭林少聪李霞
深圳大学信息工程学院,深圳518060
Author(s):
PAN Zhi-mingLIN Shao-congLI Xia
College of Information Engineering Shenzhen University Shenzhen 518060 P. R. China
关键词:
带运力限制的车辆路径问题蚁群算法信息素更新全局收敛性收敛速度
Keywords:
capacity-constrained vehicle routing problem(CVRP) ant colony algorithm global convergence converge speed space of best solution
分类号:
O 22
文献标志码:
A
摘要:
以求解旅行商问题的蚁群算法为基础,根据带运力限制车辆路径问题的实际应用条件,提出一种较为简易的求解带运力限制车辆路径问题的蚁群算法,并对其中的信息素更新策略进行了分析,对蚁群中的精英蚂蚁(搜索出最优解的蚂蚁个体)所经过路径的信息素进行加强,提高了算法的全局收敛性能和收敛速度,允许蚂蚁在搜索的最初阶段有较大的自由以扩大最优解的寻找空间,提出改进蚁群算法.实验结果表明,该方法能在较短的时间内达到已知最优解的1. 5%误差范围.
Abstract:
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.
更新日期/Last Update: 2015-10-16