Variable Neighborhood Search for the Dial-a-Ride Problem.

Sophie Parragh, Karl Dörner, Richard Hartl

Publications: Contribution to journalArticlePeer Reviewed

Abstract

In dial-a-ride problems passengers have to be transported between pre-specified pickup and delivery locations under user inconvenience considerations. The problem variant considered in this paper aims at minimizing total routing costs while respecting maximum route duration limits, time windows, and maximum user ride time limits. We propose a competitive variable neighborhood search-based heuristic, using three classes of neighborhoods. The first neighborhood class uses simple swap operations tailored to the dial-a-ride problem; the second neighborhood class is based on the ejection chain idea; and the third neighborhood class exploits the existence of arcs where the vehicle load is zero, giving rise to natural sequences of requests. We report new best results for 16 out of 20 benchmark instances.
Original languageEnglish
Pages (from-to)1129-1138
Number of pages10
JournalComputers & Operations Research
Volume37
Issue number6
Publication statusPublished - 2010

Austrian Fields of Science 2012

  • 5020 Economics

Fingerprint

Dive into the research topics of 'Variable Neighborhood Search for the Dial-a-Ride Problem.'. Together they form a unique fingerprint.

Cite this