Waiting Strategies for Dynamic Vehicle Routing
Authors:
- 1 August 2005
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Transportation Science
- Vol. 39 (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
This publication has 21 references indexed in Scilit:
- Diversion Issues in Real-Time Vehicle DispatchingTransportation Science, 2000
- Anticipation in Dynamic Optimization: The Scheduling CaseLecture Notes in Computer Science, 2000
- Parallel Tabu Search for Real-Time Vehicle Routing and DispatchingTransportation Science, 1999
- Dynamic Vehicle Routing and Dispatching1998
- A New Generation of Vehicle Routing Research: Robust Algorithms, Addressing UncertaintyOperations Research, 1996
- Genetic Algorithms + Data Structures = Evolution Programs1996
- Stochastic and Dynamic Vehicle Routing in the Euclidean Plane with Multiple Capacitated VehiclesOperations Research, 1993
- A Stochastic and Dynamic Vehicle Routing Problem in the Euclidean PlaneOperations Research, 1991
- OR-Library: Distributing Test Problems by Electronic MailJournal of the Operational Research Society, 1990
- Planar Formulae and Their UsesSIAM Journal on Computing, 1982