This Article Full Text (PDF) e-companion Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Google Scholar Articles by Secomandi, N. Articles by Margot, F.

Reoptimization Approaches for the Vehicle-Routing Problem with Stochastic Demands

Tepper School of Business, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213
Tepper School of Business, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213
ns7{at}andrew.cmu.edu
fmargot{at}andrew.cmu.edu

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.

Subject classifications: dynamic programming; application; heuristics; network/graphs; stochastic model; transportation; vehicle-routing problem; stochastic demands.
History: Received December 2005; revision received September 2007; accepted October 2007.