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 HighWire Citing Articles via Google Scholar Google Scholar Articles by Campbell, A. M. Articles by Thomas, B. W. Search for Related Content

Probabilistic Traveling Salesman Problem with Deadlines

Department of Management Sciences, University of Iowa, Iowa City, Iowa 52242
Department of Management Sciences, University of Iowa, Iowa City, Iowa 52242
ann-campbell{at}uiowa.edu
barrett-thomas{at}uiowa.edu

Time-constrained deliveries are one of the fastest growing segments of the delivery business, and yet there is surprisingly little literature that addresses time constraints in the context of stochastic customer presence. We begin to fill that void by introducing the probabilistic traveling salesman problem with deadlines (PTSPD). The PTSPD is an extension of the well-known probabilistic traveling salesman problem (PTSP) in which, in addition to stochastic presence, customers must also be visited before a known deadline. We present two recourse models and a chance constrained model for the PTSPD. Special cases are discussed for each model, and computational experiments are used to illustrate under what conditions stochastic and deterministic models lead to different solutions.

Key Words: vehicle routing; traveling salesman problem; probabilistic; deadlines
History: Received: April 2005; revised: January 2007; accepted: April 2007.

This article has been cited by other articles:

				C. Groer, B. Golden, and E. Wasil The Consistent Vehicle Routing Problem MSOM, October 1, 2009; 11(4): 630 - 643. [Abstract] [PDF]

				S. Chen, B. Golden, R. Wong, and H. Zhong Arc-Routing Models for Small-Package Local Routing Transportation Science, February 1, 2009; 43(1): 43 - 55. [Abstract] [PDF]