A rollout policy for the vehicle routing problem with stochastic demands

被引:127
作者
Secomandi, N [1 ]
机构
[1] Cornell Univ, Sch Civil & Environm Engn, Ithaca, NY 14853 USA
关键词
D O I
10.1287/opre.49.5.796.10608
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
The paper considers the single vehicle routing problem with stochastic demands. While most of the literature has studied the a priori solution approach, this work focuses on computing a reoptimization-type routing policy. This is obtained by sequentially improving a given a priori solution by means of a rollout algorithm. The resulting rollout policy appears to be the first computationally tractable algorithm for approximately solving the problem under the reoptimization approach. After describing the solution strategy and providing properties of the rollout policy, the policy behavior is analyzed by conducting a computational investigation. Depending on the quality of the initial solution, the rollout policy obtains 1% to 4% average improvements on the a priori approach with a reasonable computational effort.
引用
收藏
页码:796 / 802
页数:7
相关论文
共 27 条
[1]  
[Anonymous], TRANSPORTATION PLANN, DOI DOI 10.1080/03081069208717490
[2]   THE STOCHASTIC VEHICLE-ROUTING PROBLEM REVISITED [J].
BASTIAN, C ;
KAN, AHGR .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1992, 56 (03) :407-412
[3]   Rollout Algorithms for Combinatorial Optimization [J].
Bertsekas D.P. ;
Tsitsiklis J.N. ;
Wu C. .
Journal of Heuristics, 1997, 3 (3) :245-262
[4]  
Bertsekas D. P., 1996, Neuro Dynamic Programming, V1st
[5]  
Bertsekas D.P., 1997, P 35 ALL C COMM CONT
[6]   Rollout algorithms for stochastic scheduling problems [J].
Bertsekas, DP ;
Castañon, DA .
JOURNAL OF HEURISTICS, 1999, 5 (01) :89-108
[7]  
Bertsekas DP, 2012, DYNAMIC PROGRAMMING, V2
[8]   Computational approaches to stochastic vehicle routing problems [J].
Bertsimas, D ;
Chervi, P ;
Peterson, M .
TRANSPORTATION SCIENCE, 1995, 29 (04) :342-352
[9]   A PRIORI OPTIMIZATION [J].
BERTSIMAS, DJ ;
JAILLET, P ;
ODONI, AR .
OPERATIONS RESEARCH, 1990, 38 (06) :1019-1033
[10]   A new generation of vehicle routing research: Robust algorithms, addressing uncertainty [J].
Bertsimas, DJ ;
SimchiLevi, D .
OPERATIONS RESEARCH, 1996, 44 (02) :286-304