Simulated annealing metaheuristics for the vehicle routing problem with time windows

被引:186
作者
Chiang, WC [1 ]
Russell, RA [1 ]
机构
[1] UNIV TULSA,DEPT QUANTITAT METHODS,TULSA,OK 74014
关键词
metaheuristics; simulated annealing; vehicle routing problems with time windows; TRAVELING SALESMAN PROBLEM; SCHEDULING PROBLEMS; ASSIGNMENT PROBLEMS; TABU SEARCH; OPTIMIZATION; CONSTRAINTS; ALGORITHM;
D O I
10.1007/BF02601637
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
This paper develops simulated annealing metaheuristics for the vehicle routing and scheduling problem with time window constraints. Two different neighborhood structures, the ii-interchange mechanism of Osman and the k-node interchange process of Christofides and Beasley, are implemented. The enhancement of the annealing process with a short-term memory function via a tabu list is examined as a basis for improving the metaheuristic approach. Computational results on test problems from the literature as well as large-scale real-world problems are reported. The metaheuristics achieve solutions that compare favorably with previously reported results.
引用
收藏
页码:3 / 27
页数:25
相关论文
共 40 条
[1]  
Baker E. K., 1986, American Journal of Mathematical and Management Sciences, V6, P261
[2]   THE ASYMPTOTIC-BEHAVIOR OF QUADRATIC SUM ASSIGNMENT PROBLEMS - A STATISTICAL-MECHANICS APPROACH [J].
BONOMI, E ;
LUTTON, JL .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1986, 26 (02) :295-300
[4]   THE PERIOD ROUTING PROBLEM [J].
CHRISTOFIDES, N ;
BEASLEY, JE .
NETWORKS, 1984, 14 (02) :237-256
[5]   AN IMPROVED ANNEALING SCHEME FOR THE QAP [J].
CONNOLLY, DT .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1990, 46 (01) :93-100
[6]   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
[7]  
DESROCHERS M., 1988, VEHICLE ROUTING: METHOD AND STUDIES. STUDIES IN MANAGEMENT SCIENCE AND SYSTEMS, P65
[8]  
FISHER M, 1991, 4C1991 IMSOR TU DENM
[9]   A GENERALIZED ASSIGNMENT HEURISTIC FOR VEHICLE-ROUTING [J].
FISHER, ML ;
JAIKUMAR, R .
NETWORKS, 1981, 11 (02) :109-124
[10]   A SIMULATED ANNEALING APPROACH TO THE NETWORK DESIGN PROBLEM WITH VARIATIONAL INEQUALITY CONSTRAINTS [J].
FRIESZ, TL ;
CHO, HJ ;
MEHTA, NJ ;
TOBIN, RL ;
ANANDALINGAM, G .
TRANSPORTATION SCIENCE, 1992, 26 (01) :18-26