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

In the dial-a-ride problem, user-specified transport requests from origin to destination points have to be served by a fleet of homogeneous vehicles. The problem variant the authors 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. The authors 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, the authors use two optional improvement techniques: a local-search-based intraroute improvement of routes of promising solutions using the Balas-Simonetti neighborhood and the solution of a set covering 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.The online appendix is available at

  • Record URL:
  • Availability:
  • Supplemental Notes:
    • Abstracts reprinted with permission of INFORMS (Institute for Operations Research and the Management Sciences,
  • Authors:
    • Gschwind, Timo
    • Drexl, Michael
  • Publication Date: 2019-3


  • English

Media Info

Subject/Index Terms

Filing Info

  • Accession Number: 01703260
  • Record Type: Publication
  • Files: TRIS
  • Created Date: Apr 22 2019 1:57PM