Effective Handling of Ride-Time Constraints in Solution Approaches to the Dial-a-Ride Problem

In the dial-a-ride problem (DARP), user-specified transportation 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. The temporal constraints of the DARP impose a complex scheduling problem for the service times at the customer locations which makes the efficient feasibility checking of routes and the development of solution approaches intricate. In this talk, we analyze the nature of the scheduling problem and exploit the knowledge gained to derive both an exact and a heuristic solution algorithm for the DARP. For the exact solution, we propose a branch-price-and-cut algorithm that handles all route constraints in the column-generation subproblem using a newly developed pricing procedure. For the heuristic solution, we propose an adaptive large neighborhood search (ALNS). The key novelty here is an exact amortized constant-time algorithm for evaluating the feasibility of request insertions in the repair steps of the ALNS. Computational results indicate that both approaches outperform the respective state-of-the-art methods.