An improved ant system algorithm for the vehicle routing problem

被引:736
作者
Bullnheimer, B [1 ]
Hartl, RF [1 ]
Strauss, C [1 ]
机构
[1] Univ Vienna, Dept Management Sci, A-1210 Vienna, Austria
关键词
ant system; adaptive memory; vehicle routing; metaheuristics;
D O I
10.1023/A:1018940026670
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 [运筹学与控制论]; 12 [管理学]; 1201 [管理科学与工程]; 1202 [工商管理学]; 120202 [企业管理];
摘要
The Ant System is a distributed metaheuristic that combines an adaptive memory with a local heuristic function to repeatedly construct solutions of hard combinatorial optimization problems. In this paper, we present an improved ant system algorithm for the Vehicle Routing Problem with one central depot and identical vehicles. Computational results on fourteen benchmark problems from the literature are reported and a comparison with five other metaheuristic approaches for solving Vehicle Routing Problems is given.
引用
收藏
页码:319 / 328
页数:10
相关论文
共 24 条
[1]
[Anonymous], 1991, P EUR C ART LIF
[2]
[Anonymous], 1994, BELGIAN J OPERATIONS
[3]
[Anonymous], 1992, OPTIMIZATION LEARNIN
[4]
[Anonymous], METAHEURISTICS THEOR
[5]
BULLNHEIMER B, 1998, METAHEURISTICS ADV T
[6]
Bullnheimer B., 1998, HIGH PERFORMANCE ALG
[7]
BULLNHEIMER B, 1997, IN PRESS CEJOR
[8]
Christofides N., 1979, COMBINATORIAL OPTIMI
[9]
SCHEDULING OF VEHICLES FROM CENTRAL DEPOT TO NUMBER OF DELIVERY POINTS [J].
CLARKE, G ;
WRIGHT, JW .
OPERATIONS RESEARCH, 1964, 12 (04) :568-&
[10]
Ants can colour graphs [J].
Costa, D ;
Hertz, A .
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 1997, 48 (03) :295-305