一种求解车辆路径问题的混合多蚁群算法(英文)

被引：14

作者：

刘志硕 ^{[1
]}

申金升 ^{[1
]}

柴跃廷 ^{[2
]}

机构：

[1] 北京交通大学交通运输学院

[2] 清华大学自动化系国家CIMS工程技术研究中心

来源：

系统仿真学报 | 2007年 / 15期

关键词：

组合优化; 车辆路径问题; 蚁群算法; 扫描算法; 多蚁群;

D O I：

10.16182/j.cnki.joss.2007.15.040

中图分类号：

TP301.6 [算法理论];

学科分类号：

摘要：

提出一种新的蚁群算法(Multiple Ant Colonies Algorithm based on Sweep Algorithm, SbMACA)用以求解车辆路径问题(Capacitated Vehicle Routing Problem, CVRP)。该方法同以往蚁群算法的不同之处主要体现在两个方面:第一,首次将扫描算法应用于蚁群算法,通过对蚂蚁所构造的初始解中的不同子回路之间的点进行交换优化,该算法可以有效地改进初始解的质量;第二,提出并采用了一种新的多蚁群技术,各个蚁群分别进行各自的搜索,在各个蚁群均停滞后,对蚁群之间的信息素进行交换与更新,以利于蚁群跳离局部最优值。实验结果表明,SbMACA算法具有很强的搜索能力,求取各CVRP的Benchmark问题所得解的质量同最好解相比较而言,平均仅有 0.28%的差距,是求解车辆路径问题的一种十分有效的方法。

引用

页码：3513 / 3520

页数：8

共 8 条

[1] 基于解均匀度的车辆路径问题的自适应蚁群算法 [J].

刘志硕 ;

申金升 .

系统仿真学报, 2005, (05) :1079-1083

[2] 对一类带聚类特征TSP问题的蚁群算法求解 [J].

胡小兵 ;

黄席樾 .

系统仿真学报, 2004, (12) :2683-2686

[3] Ant colony optimization techniques for the vehicle routing problem [J].

Bell, JE ;

McMullen, PR .

ADVANCED ENGINEERING INFORMATICS, 2004, 18 (01) :41-48

[4]

MAX – MIN Ant System[J] . Thomas Stützle,Holger H. Hoos.Future Generation Computer Systems . 2000 (8)

[5] An improved ant system algorithm for the vehicle routing problem [J].

Bullnheimer, B ;

Hartl, RF ;

Strauss, C .

ANNALS OF OPERATIONS RESEARCH, 1999, 89 (0) :319-328

[6] A TABU SEARCH HEURISTIC FOR THE VEHICLE-ROUTING PROBLEM [J].

GENDREAU, M ;

HERTZ, A ;

LAPORTE, G .

MANAGEMENT SCIENCE, 1994, 40 (10) :1276-1290

[7]

Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem[J] . Ibrahim Hassan Osman.Annals of Operations Research . 1993 (4)

[8]

Vehicle routing using r-optimal tabu search. Willard J A G. The Management School, Imperial College . 1989

← 1 →