Combining multicriteria analysis and tabu search for dial-a-ride problems

Julie Paquette, Jean François Cordeau, Gilbert Laporte, Marta M.B. Pascoal

Research output: Contribution to journalArticlepeer-review

97 Citations (SciVal)

Abstract

In the Dial-a-Ride Problem (DARP) the aim is to design vehicle routes for a set of users who must be transported between given origin and destination pairs, subject to a variety of side constraints. The standard DARP objective is cost minimization. In addition to cost, the objectives considered in this paper include three terms related to quality of service. This gives rise to a multicriteria problem. The problem is solved by means of a flexible and simple metaheuristic which efficiently integrates the reference point method for multicriteria optimization within a tabu search mechanism. Extensive tests were performed on randomly generated data and on real-life data provided by a major transporter in the Montreal area. Results indicate that the algorithm can yield a rich set of non-dominated solutions. It can also be employed to determine good trade-offs between cost and quality of service.

Original languageEnglish
Pages (from-to)1-16
Number of pages16
JournalTransportation Research Part B: Methodological
Volume52
DOIs
Publication statusPublished - Jun 2013

Funding

This work was partly supported by the Canadian Social Sciences and Humanities Research Council, by the Canadian Natural Sciences and Engineering Research Council under Grants 227837-09 and 39682-10 , and by the Portuguese FCT Grant SFRH/BSAB/830/2008 and project POSC/U308/1.3/NRE/04. This support is gratefully acknowledged. The computers were provided by Calcul Québec. We also thank Marc Fredette for his help with the analysis of the results of model 3, and the anonymous referees for their valuable comments.

Keywords

  • Dial-a-ride problem
  • Multicriteria analysis
  • Quality of service
  • Reference point method
  • Tabu search

ASJC Scopus subject areas

  • Civil and Structural Engineering
  • Transportation

Fingerprint

Dive into the research topics of 'Combining multicriteria analysis and tabu search for dial-a-ride problems'. Together they form a unique fingerprint.

Cite this