This Article Full Text (PDF) References 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 Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Thomas, B. W. Search for Related Content

Waiting Strategies for Anticipating Service Requests from Known Customer Locations

Department of Management Sciences, University of Iowa, 108 John Pappajohn Business Building, Iowa City, Iowa 52242-1994
barrett-thomas{at}uiowa.edu

This paper considers a dynamic and stochastic routing problem in which information about customer locations and probabilistic information about future service requests are used to maximize the expected number of customers served by a single uncapacitated vehicle. The problem is modeled as a Markov decision process, and analytical results on the structure of the optimal policy are derived. For the case of a single dynamic customer, we completely characterize the optimal policy. Using the analytical results, we propose a real-time heuristic and demonstrate its effectiveness compared with a series of other intuitively appealing heuristics. We also use computational tests to determine the heuristic value of knowing both customer locations and probabilistic information about future service requests.

Key Words: dynamic vehicle routing; stochastic demand; online strategies; real-time heuristics
History: Received: October 2005; revised: July 2006; accepted: October 2006.