A stochastic and dynamic vehicle routing problem in the Euclidean plane

A stochastic and dynamic vehicle routing problem in the Euclidean plane

0.00 Avg rating0 Votes
Article ID: iaor19931007
Country: United States
Volume: 39
Issue: 4
Start Page Number: 601
End Page Number: 615
Publication Date: Jul 1991
Journal: Operations Research
Authors: ,
Keywords: stochastic processes
Abstract:

The authors 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. The authors propose and analyze several policies for the DTRP. They 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. The authors 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.

Reviews

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