Local search with annealing-like restarts to solve the VRPTW

被引:70
作者
Li, HB [1 ]
Lim, A [1 ]
机构
[1] Natl Univ Singapore, Dept Comp Sci, Singapore 117543, Singapore
关键词
routing; vehicle grouting problem with time windows; local search; diversification; intensification;
D O I
10.1016/S0377-2217(02)00486-1
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
In this paper, we propose a metaheuristic based on annealing-like restarts to diversify and intensify local searches for solving the vehicle routing problem with time windows (VRPTW). Using the Solomon's benchmark instances for the problem, our method obtained seven new best results and equaled 19 other best results. Extensive comparisons indicate that our method is comparable to the best in published literature. This approach is flexible and can be extended to handle other variants of vehicle routing problems and other combinatorial optimization problems. (C) 2002 Elsevier Science B.V.. All rights reserved.
引用
收藏
页码:115 / 127
页数:13
相关论文
共 28 条
[1]   Solving vehicle routing problems using constraint programming and metaheuristics [J].
Backer, BD ;
Furnon, V ;
Shaw, P ;
Kilby, P ;
Prosser, P .
JOURNAL OF HEURISTICS, 2000, 6 (04) :501-523
[2]   Simulated annealing metaheuristics for the vehicle routing problem with time windows [J].
Chiang, WC ;
Russell, RA .
ANNALS OF OPERATIONS RESEARCH, 1996, 63 :3-27
[3]  
CHIANG WC, 1997, INFORMS J COMP, V9, P417
[4]  
Cordeau JF, 2002, SIAM MONOG DISCR MAT, P157
[5]  
CORDEAU JF, 2000, CRT0003
[6]  
DESROCHERS J, 1988, VEHICLE ROUTING TIME
[7]   A NEW OPTIMIZATION ALGORITHM FOR THE VEHICLE-ROUTING PROBLEM WITH TIME WINDOWS [J].
DESROCHERS, M ;
DESROSIERS, J ;
SOLOMON, M .
OPERATIONS RESEARCH, 1992, 40 (02) :342-354
[8]  
DESROSIERS J, 1995, HDB OPERATIONS RES M
[9]   AN OPTIMAL ALGORITHM FOR THE TRAVELING SALESMAN PROBLEM WITH TIME WINDOWS [J].
DUMAS, Y ;
DESROSIERS, J ;
GELINAS, E ;
SOLOMON, MM .
OPERATIONS RESEARCH, 1995, 43 (02) :367-371
[10]   Vehicle routing with time windows: Two optimization algorithms [J].
Fisher, ML ;
Jornsten, KO ;
Madsen, OBG .
OPERATIONS RESEARCH, 1997, 45 (03) :488-492