A Stochastic and Dynamic Vehicle Routing Problem in the Euclidean Plane

Abstract

We propose and analyze a generic mathematical model for dynamic, stochastic vehicle routing problems, the dynamic traveling repairman problem (DTRP). The model is motivated by applications in which the objective is to minimize the wait for service in a stochastic and dynamically changing environment. This is a departure from classical vehicle routing problems where one seeks to minimize total travel time in a static, deterministic environment. Potential areas of application include repair, inventory, emergency service and scheduling problems. The DTRP is defined as follows: Demands for service arrive in time according to a Poisson process, are independent and uniformly distributed in a Euclidean service region, and require an independent and identically distributed amount of on-site service by a vehicle. The problem is to find a policy for routing the service vehicle that minimizes the average time demands spent in the system. We propose and analyze several policies for the DTRP. We find a provably optimal policy in light traffic and several policies with system times within a constant factor of the optimal policy in heavy traffic. We also show that the waiting time grows much faster than in traditional queues as the traffic intensity increases, yet the stability condition does not depend on the system geometry.