A rollout policy for the vehicle routing problem with stochastic demands
成果类型：
Article
署名作者：
Secomandi, N
署名单位：
Cornell University
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.49.5.796.10608
发表日期：
2001
页码：
796-802
关键词：
摘要：
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.