Journal article

A Hybrid Tabu Search and Constraint Programming Algorithm for the Dynamic Dial-a-Ride Problem

Gerardo Berbeglia, Jean-Francois Cordeau, Gilbert Laporte

INFORMS Journal on Computing | INFORMS | Published : 2012


This paper introduces a hybrid algorithm for the dynamic dial-a-ride problem in which service requests arrive in real time. The hybrid algorithm combines an exact constraint programming algorithm and a tabu search heuristic. An important component of the tabu search heuristic consists of three scheduling procedures that are executed sequentially. Experiments show that the constraint programming algorithm is sometimes able to accept or reject incoming requests, and that the hybrid method outperforms each of the two algorithms when they are executed alone.

University of Melbourne Researchers


Awarded by Canadian Natural Sciences and Engineering Research Council

Funding Acknowledgements

This work was supported by the Canadian Natural Sciences and Engineering Research Council under Grants 227837-04 and 39682-05. This support is gratefully acknowledged. Thanks are due to the reviewers for their valuable comments.