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

In [9] we 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. In this paper, we extend our analysis of this problem 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/mn2 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. In contrast to the uncapacitated case, we show 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 then proposed. Finally, we discuss extending these results to mixed travel cost and system time objectives