The Vehicle Routing Problem with Stochastic Demand and Duration Constraints

Alan L. Erera (), Juan C. Morales () and Martin Savelsbergh ()
Additional contact information
Alan L. Erera: H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
Juan C. Morales: BNSF Railway, Fort Worth, Texas 76131
Martin Savelsbergh: CSIRO Mathematics, Informatics, and Statistics, North Ryde, NSW 1670 Australia

Transportation Science, 2010, vol. 44, issue 4, 474-492

Abstract: Time considerations have been largely ignored in the study of vehicle routing problems with stochastic demands, even though they are crucial in practice. We show that tour duration limits can effectively and efficiently be incorporated in solution approaches that build fixed, or a priori, tours for such problems. We do so by assuming that each tour must be duration feasible for all demand realizations, and determine the maximum duration of a given delivery tour by solving the optimization problem of an adversary. A computational study demonstrates the approach, and shows that enforcing tour duration limits impacts the structure of nearly-best solutions and may create the need for additional tours. However, for the instances considered, the price paid for robustness is small as the increase in total expected tour duration is modest.

Keywords: vehicle routing; stochastic demand; duration constraints (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (27)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1100.0324 (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:ortrsc:v:44:y:2010:i:4:p:474-492

Access Statistics for this article

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