Adaptive Large Neighborhood Search with a Constant-Time Feasibility Test for the Dial-a-Ride Problem

Timo Gschwind () and Michael Drexl ()
Additional contact information
Timo Gschwind: Johannes Gutenberg-University Mainz, Germany
Michael Drexl: Johannes Gutenberg-University Mainz, Germany and Deggendorf Institute of Technology

No 1624, Working Papers from Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz

Abstract: In the dial-a-ride problem (DARP), user-specified transport requests from origin to destination points have to be served by a fleet of homogeneous vehicles. The problem variant we consider aims at finding a set of minimum-cost routes satisfying constraints on vehicle capacity, time windows, maximum route duration, and maximum user ride times. We propose an adaptive large neighborhood search (ALNS) for its solution. The key novelty of the approach is an exact amortized constant-time algorithm for evaluating the feasibility of request insertions in the repair steps of the ALNS. In addition, we use two optional improvement techniques: a local-search based, intra-route improvement of routes of promising solutions using the Balas-Simonetti neighborhood, and the solution of a set-partitioning model over a subset of all routes generated during the search. With these techniques, the proposed algorithm outperforms the state-of-the-art methods in terms of solution quality. New best solutions are found for several benchmark instances.

Keywords: Dial-a-ride problem; Adaptive large neighborhood search; Feasibility testing (search for similar items in EconPapers)
Pages: 37 pages
Date: 2016-12-22
New Economics Papers: this item is included in nep-cmp, nep-tre and nep-ure
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
https://download.uni-mainz.de/RePEc/pdf/Discussion_Paper_1624.pdf First version, 2016 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:jgu:wpaper:1624

Access Statistics for this paper

More papers in Working Papers from Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz Contact information at EDIRC.
Bibliographic data for series maintained by Research Unit IPP ().