A hybrid tabu search and constraint programming algorithm for the dynamic dial-a-ride problem

Gerardo Berbeglia, Jean François Cordeau, Gilbert Laporte

Research output: Contribution to journalArticlepeer-review

49 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)343-355
Number of pages13
JournalINFORMS Journal on Computing
Volume24
Issue number3
DOIs
Publication statusPublished - Jun 2012

Keywords

  • Constraint programming
  • Dial-a-ride problem
  • Dynamic
  • Scheduling
  • Tabu search

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Computer Science Applications
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'A hybrid tabu search and constraint programming algorithm for the dynamic dial-a-ride problem'. Together they form a unique fingerprint.

Cite this