Stochastic and Dynamic Vehicle Routing in the Euclidean Plane with Multiple Capacitated Vehicles

Dimitris J. Bertsimas and Garrett van Ryzin
Additional contact information
Dimitris J. Bertsimas: Massachusetts Institute of Technology, Cambridge, Massachusetts
Garrett van Ryzin: Columbia University, New York, New York

Operations Research, 1993, vol. 41, issue 1, 60-76

Abstract: In 1991, D. J. Bertsimas and G. van Ryzin introduced and analyzed a model for stochastic and dynamic vehicle routing in which a single, uncapacitated vehicle traveling at a constant velocity in a Euclidean region must service demands whose time of arrival, location and on-site service are stochastic. The objective is to find a policy to service demands over an infinite horizon that minimizes the expected system time (wait plus service) of the demands. This paper extends our analysis in several directions. First, we analyze the problem of m identical vehicles with unlimited capacity and show that in heavy traffic the system time is reduced by a factor of 1/ m 2 over the single-server case. One of these policies improves by a factor of two on the best known system time for the single-server case. We then consider the case in which each vehicle can serve at most q customers before returning to a depot. We show that the stability condition in this case depends strongly on the geometry of the region. Several policies that have system times within a constant factor of the optimum in heavy traffic are proposed. Finally, we discuss extensions to mixed travel cost and system time objectives.

Keywords: networks: stochastic; traveling salesman; probability: stochastic model; transportation: vehicle routing (search for similar items in EconPapers)
Date: 1993
References: Add references at CitEc
Citations: View citations in EconPapers (42)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.41.1.60 (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:41:y:1993:i:1:p:60-76

Access Statistics for this article

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