Submitted to Operations Research manuscript OPRE-2007-08-388 Fundamental Performance Limits for Multi-Stage Vehicle Routing Problems

In the stochastic and dynamic multi-stage vehicle routing problem, a set of vehicles collectively transports and services demands which require service at multiple spatially separated locations. Arrival times and service locations of individual demands are not known until the demand’s arrival, and vehicles are assumed to have infinite capacity and to travel with bounded velocity. The objective is to define real-time control policies for the vehicles to service the demands such that average demand time-in-system is minimized. Such problems arise in numerous applications, including courier services, inventory routing, and mobile sensor networks. In this paper, we provide a general lower bound on the delay performance of a class of batching policies for the dynamic multi-stage vehicle routing problem. This requires us to overcome nontrivial technical difficulties presented by the non-work-conserving nature of the system and the service of multiple (possibly infinitely many) jobs simultaneously. The single stage Dynamic Traveling Repairperson Problem was first analyzed by Bertsimas and van Ryzin (1991). We recently examined the two-stage Dynamic Pickup and Delivery Problem in Waisanen et al. (2006). In the current paper, we extend the Dynamic Pickup and Delivery Problem to include a single inter-vehicle relay service between the pickup and delivery stages. For this four-stage problem, we present a policy for which the corresponding multi-stage lower bound is tight as a function of the scaling parameters (up to a constant). We note that our bounds are based on sample path analysis and hence are quite general