A Stochastic and Dynamic Vehicle Routing Problem in the Euclidean Plane

Dimitris J. Bertsimas and Garrett van Ryzin
Additional contact information
Dimitris J. Bertsimas: Massachusetts Institute of Technology, Cambridge, Massachusetts
Garrett van Ryzin: Massachusetts Institute of Technology, Cambridge, Massachusetts

Operations Research, 1991, vol. 39, issue 4, 601-615

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.

Keywords: networks/graphs: stochastic; traveling salesman; probability; stochastic model; transportation: vehicle routing (search for similar items in EconPapers)
Date: 1991
References: Add references at CitEc
Citations: View citations in EconPapers (60)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.39.4.601 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:39:y:1991:i:4:p:601-615

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().