Program > By author > Gschwind Timo

In the Dial-a-Ride Problem (DARP), user-specified transportation requests from origin to destination points have to be serviced by a fleet of homogeneous vehicles. The problem variant we consider aims at finding a set of minimum-cost routes satisfying pairing and precedence, capacity, time-window, maximum route-duration, and maximum user ride-time constraints. We propose an adaptive large neighborhood search (ALNS) for its solution. The key novelty of the approach is an exact constant-time algorithm for evaluating the feasibility of request insertions in the repair steps of the ALNS. Computational results indicate that the basic version of our ALNS is competitive to state-of-the-art methods for the DARP regarding both solution quality and computation times. To increase the solution quality, we propose two optional improvement techniques: A local-search based, intra-route improvement of all routes of promising solutions using the Balas-Simonetti neighborhood and the solution of a set-partitioning model including all routes generated during the search. Using these techniques, the proposed algorithm outperforms the state-of-the-art methods in terms of solution quality. New best known solutions are found for several benchmark instances.