Article ID: | iaor20052693 |
Volume: | 30 |
Issue: | 3 |
Start Page Number: | 377 |
End Page Number: | 387 |
Publication Date: | Mar 2004 |
Journal: | Parallel Computing |
Authors: | Laporte Gilbert, Ghiani Gianpaolo, Cordeau Jean-Franois, Attanasio Andrea |
Keywords: | heuristics, vehicle routing & scheduling |
In the Dial-a-Ride problem (DARP) users specify transportation requests between origins and destinations to be served by vehicles. In the dynamic DARP, requests are received throughout the day and the primary objective is to accept as many requests as possible while satisfying operational constraints. This article describes and compares a number of parallel implementations of a Tabu search heuristic previously developed for the static DARP, i.e., the variant of the problem where all requests are known in advance. Computational results show that the proposed algorithms are able to satisfy a high percentage of user requests.