Article ID: | iaor2001881 |
Country: | United States |
Volume: | 33 |
Issue: | 4 |
Start Page Number: | 381 |
End Page Number: | 390 |
Publication Date: | Nov 1999 |
Journal: | Transportation Science |
Authors: | Potvin Jean-Yves, Gendreau Michel, Guertin Franois, Taillard ric |
Keywords: | vehicle routing & scheduling |
An abundant literature about vehicle routing and scheduling problems is available in the scientific community. However, a large fraction of this work deals with static problems where all data are known before the routes are constructed. Recent technological advances now create environments where decisions are taken quickly, using new or updated information about the current routing situation. This paper describes such a dynamic problem, motivated from courier service applications, where customer requests with soft time windows must be dispatched in real time to a fleet of vehicles in movement. A tabu search heuristic, initially designed for the static version of the problem, has been adapted to the dynamic case and implemented on a parallel platform to increase the computational effort. Numerical results are reported using different request arrival rates, and comparisons are established with other heuristic methods.