A tabu search algorithm for the vehicle routing problem

被引:116
作者
Barbarosoglu, G [1 ]
Ozgur, D [1 ]
机构
[1] Bogazici Univ Bebek, Dept Ind Engn, Istanbul, Turkey
关键词
metaheuristics; tabu search; distribution; vehicle routing problem;
D O I
10.1016/S0305-0548(98)00047-1
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
The purpose of this study is to develop a new tabu search heuristic to solve-the single-depot vehicle routing problem of a distribution company carrying goods from a depot to a set of dedicated dealers. The heuristic proposes a new neighbourhood generation procedure which considers the scattering pattern iii the locations of the dealers. A set of neighbours are generated by first executing a procedure which ignores the clustering of the vertices and then executing a second procedure which takes into account the relative locations of the dealers; then the feasible non-tabu move among these with the best objective function value is implemented. During neighbourhood construction, a combination of traditional improvement techniques are used simultaneously in order to achieve the exchange of vertices. The intensification efforts, on the other hand, are focused upon the hill-climbing behaviour of the search, and the diversification step which is standard in all previous tabu search approaches is not included in this heuristic. Numerical results on well-known benchmark problems indicate that the performance of the algorithm developed in this study is compatible with the other best-known algorithms in the literature. (C) 1998 Elsevier Science Ltd. All rights reserved.
引用
收藏
页码:255 / 270
页数:16
相关论文
共 24 条
[1]   PARALLEL SAVINGS BASED HEURISTICS FOR THE DELIVERY PROBLEM [J].
ALTINKEMER, K ;
GAVISH, B .
OPERATIONS RESEARCH, 1991, 39 (03) :456-469
[2]   On the effectiveness of set covering formulations for the vehicle routing problem with time windows [J].
Bramel, J ;
SimchiLevi, D .
OPERATIONS RESEARCH, 1997, 45 (02) :295-301
[3]  
Christofides N., 1979, Combinatorial optimization, P315
[4]  
CHRISTOFIDES N, 1993, NEW EXACT ALGORITHM
[5]   SCHEDULING OF VEHICLES FROM CENTRAL DEPOT TO NUMBER OF DELIVERY POINTS [J].
CLARKE, G ;
WRIGHT, JW .
OPERATIONS RESEARCH, 1964, 12 (04) :568-&
[6]  
DESROCHERS M, 1989, G8904 EC HAUT ET COM
[7]   Vehicle routing with time windows: Two optimization algorithms [J].
Fisher, ML ;
Jornsten, KO ;
Madsen, OBG .
OPERATIONS RESEARCH, 1997, 45 (03) :488-492
[8]  
FISHER ML, 1989, 891213 WHART SCH DEC
[9]   A TABU SEARCH HEURISTIC FOR THE VEHICLE-ROUTING PROBLEM [J].
GENDREAU, M ;
HERTZ, A ;
LAPORTE, G .
MANAGEMENT SCIENCE, 1994, 40 (10) :1276-1290
[10]   HEURISTIC ALGORITHM FOR VEHICLE-DISPATCH PROBLEM [J].
GILLETT, BE ;
MILLER, LR .
OPERATIONS RESEARCH, 1974, 22 (02) :340-349