Reoptimization Approaches for the Vehicle-Routing Problem with Stochastic Demands

Nicola Secomandi () and François Margot ()
Additional contact information
Nicola Secomandi: Tepper School of Business, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213
François Margot: Tepper School of Business, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213

Operations Research, 2009, vol. 57, issue 1, 214-230

Abstract: We consider the vehicle-routing problem with stochastic demands (VRPSD) under reoptimization. We develop and analyze a finite-horizon Markov decision process (MDP) formulation for the single-vehicle case and establish a partial characterization of the optimal policy. We also propose a heuristic solution methodology for our MDP, named partial reoptimization, based on the idea of restricting attention to a subset of all the possible states and computing an optimal policy on this restricted set of states. We discuss two families of computationally efficient partial reoptimization heuristics and illustrate their performance on a set of instances with up to and including 100 customers. Comparisons with an existing heuristic from the literature and a lower bound computed with complete knowledge of customer demands show that our best partial reoptimization heuristics outperform this heuristic and are on average no more than 10%--13% away from this lower bound, depending on the type of instances.

Keywords: dynamic programming; application; heuristics; network/graphs; stochastic model; transportation; vehicle-routing problem; stochastic demands (search for similar items in EconPapers)
Date: 2009
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (43)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1080.0520 (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:57:y:2009:i:1:p:214-230

Access Statistics for this article

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