A Stochastic and Dynamic Vehicle Routing Problem in the Euclidean Plane

TLDR

Classical vehicle routing problems minimize total travel time in static, deterministic environments, whereas this work departs from that by addressing dynamic, stochastic settings. The authors introduce the dynamic traveling repairman problem (DTRP) to minimize the average waiting time of stochastic, time‑varying service demands. They model demands as Poisson arrivals uniformly distributed in a Euclidean region, requiring independent on‑site service, and propose several routing policies for the DTRP. An optimal policy is proven for light traffic, while in heavy traffic several policies achieve system times within a constant factor of optimal, and waiting time escalates faster than in traditional queues yet remains geometry‑independent for stability.

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.