A generalized variable neighborhood search heuristic for the capacitated vehicle routing problem with stochastic service times

被引：42
作者：
Lei, Hongtao [3 ]
Laporte, Gilbert [1 ,2 ]
Guo, Bo [3 ]
机构：
[1] HEC Montreal, Canada Res Chair Distribut Management, Montreal, PQ H3T 2A7, Canada
[2] HEC Montreal, CIRRELT, Montreal, PQ H3T 2A7, Canada
[3] Natl Univ Def Technol, Coll Informat Syst & Management, Changsha 410073, Hunan, Peoples R China
来源：
TOP | 2012年 / 20卷 / 01期
基金：
加拿大自然科学与工程研究理事会;
关键词：
Stochastic vehicle routing; Stochastic service time; Route duration; Generalized variable neighborhood search; TRAVELING SALESMAN PROBLEM; ALGORITHM; WINDOWS; OPTIMIZATION; SOLVE;
D O I：
10.1007/s11750-011-0188-6
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
This paper describes a generalized variable neighborhood search heuristic for the Capacitated Vehicle Routing Problem with Stochastic Service Times, in which the service times at vertices are stochastic. The heuristic is tested on randomly generated instances and compared with two other heuristics and with an alternative solution strategy. Computational results show the superiority and effectiveness of the proposed heuristic.
引用
收藏
页码：99 / 118
页数：20
相关论文
共 23 条
[1]   A reactive variable neighborhood search for the vehicle-routing problem with time windows [J].
Bräysy, O .
INFORMS JOURNAL ON COMPUTING, 2003, 15 (04) :347-368
[2]   GENERALIZED DYNAMIC-PROGRAMMING FOR STOCHASTIC COMBINATORIAL OPTIMIZATION [J].
CARRAWAY, RL ;
MORIN, TL ;
MOSKOWITZ, H .
OPERATIONS RESEARCH, 1989, 37 (05) :819-829
[3]   SCHEDULING OF VEHICLES FROM CENTRAL DEPOT TO NUMBER OF DELIVERY POINTS [J].
CLARKE, G ;
WRIGHT, JW .
OPERATIONS RESEARCH, 1964, 12 (04) :568-&
[4]   NEW OPTIMIZATION HEURISTICS - THE GREAT DELUGE ALGORITHM AND THE RECORD-TO-RECORD TRAVEL [J].
DUECK, G .
JOURNAL OF COMPUTATIONAL PHYSICS, 1993, 104 (01) :86-92
[5]   A variable neighbourhood search algorithm for the open vehicle routing problem [J].
Fleszar, Krzysztof ;
Osman, Ibrahim H. ;
Hindi, Khalil S. .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2009, 195 (03) :803-809
[6]  
Hansen P., 1997, Location Science, V5, P207, DOI 10.1016/S0966-8349(98)00030-8
[7]  
Hansen P., 2005, VARIABLE NEIGHBORHOO, P211, DOI DOI 10.1007/0-387-28356-08
[8]   Variable neighbourhood search: methods and applications [J].
Hansen, Pierre ;
Mladenovic, Nenad ;
Moreno Perez, Jose A. .
ANNALS OF OPERATIONS RESEARCH, 2010, 175 (01) :367-407
[9]   Sequential search and its application to vehicle-routing problems [J].
Irnich, S ;
Funke, B ;
Grünert, T .
COMPUTERS & OPERATIONS RESEARCH, 2006, 33 (08) :2405-2429
[10]   PREFERENCE ORDER DYNAMIC PROGRAM FOR A STOCHASTIC TRAVELING SALESMAN PROBLEM [J].
KAO, EPC .
OPERATIONS RESEARCH, 1978, 26 (06) :1033-1045
123