Stochastic and dynamic vehicle routing in the Euclidean plane with multiple capacitated vehicles

Stochastic and dynamic vehicle routing in the Euclidean plane with multiple capacitated vehicles

0.00 Avg rating0 Votes
Article ID: iaor1994200
Country: United States
Volume: 41
Issue: 1
Start Page Number: 60
End Page Number: 76
Publication Date: Jan 1993
Journal: Operations Research
Authors: ,
Keywords: stochastic processes, vehicle routing & scheduling
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 the present analysis in several directions. First, the authors 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/m2 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. The authors then consider the case in which each vehicle can serve at most q customers before returning to a depot. They 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, the authors discuss extensions to mixed travel cost and system time objectives.

Reviews

Required fields are marked *. Your email address will not be published.