A Rollout Policy for the Vehicle Routing Problem with Stochastic Demands

Nicola Secomandi ()
Additional contact information
Nicola Secomandi: School of Civil and Environmental Engineering, Cornell University, Hollister Hall, Ithaca, New York 14853-3501

Operations Research, 2001, vol. 49, issue 5, 796-802

Abstract: 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.

Keywords: Dynamic programming: heuristics; Network/graphs: stochastic model; Transportation; vehicle routing: dynamic and stochastic model (search for similar items in EconPapers)
Date: 2001
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (58)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.49.5.796.10608 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:49:y:2001:i:5:p:796-802

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().