Waiting Strategies for Dynamic Vehicle Routing

Jürgen Branke (), Martin Middendorf (), Guntram Noeth () and Maged Dessouky ()
Additional contact information
Jürgen Branke: Institute AIFB, University of Karlsruhe, 76128 Karlsruhe, Germany
Martin Middendorf: Department of Computer Science, University of Leipzig, 04109 Leipzig, Germany
Guntram Noeth: McKinsey & Company, Inc., Prinzregentenstr. 22, 80538 Munich, Germany
Maged Dessouky: Department of Industrial and Systems Engineering, University of Southern California, Los Angeles, California 90089

Transportation Science, 2005, vol. 39, issue 3, 298-312

Abstract: Many real-world vehicle routing problems are dynamic optimization problems, with customer requests arriving over time, requiring a repeated reoptimization. In this paper, we consider a dynamic vehicle routing problem where one additional customer arrives at a beforehand unknown location when the vehicles are already under way. Our objective is to maximize the probability that the additional customer can be integrated into one of the otherwise fixed tours without violating time constraints. This is achieved by letting the vehicles wait at suitable locations during their tours, thus influencing the position of the vehicles at the time when the new customer arrives. For the cases of one and two vehicles, we derive theoretical results about the best waiting strategies. The general problem is shown to be NP-complete. Several deterministic waiting strategies and an evolutionary algorithm to optimize the waiting strategy are proposed and compared empirically. It is demonstrated that a proper waiting strategy can significantly increase the probability of being able to service the additional customer, at the same time reducing the average detour to serve that customer.

Keywords: dynamic vehicle routing; waiting strategies; flexible operation (search for similar items in EconPapers)
Date: 2005
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (28)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1040.0095 (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:ortrsc:v:39:y:2005:i:3:p:298-312

Access Statistics for this article

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