Neighborhood search heuristics for a dynamic vehicle dispatching problem with pick-ups and deliveries

This paper proposes neighborhood search heuristics to optimize the planned routes of vehicles in a context where new requests, with a pick-up and a delivery location, occur in real-time. Within this framework, new solutions are explored through a neighborhood structure based on ejection chains. Numerical results show the benefits of these procedures in a real-time context. The impact of a master slave parallelization scheme, using an increasing number of processors, is also investigated. (c) 2006 Elsevier Ltd. All rights reserved.