An adaptive large neighborhood search heuristic for the share-a-ride problem

• We propose an adaptive large neighborhood search (ALNS) heuristic.
• The performance of our heuristic is benchmarked against an MIP solver and Dial-a-Ride (DARP) test instances.
• The ALNS-based heuristic can solve medium size instances of the Share-a-Ride Problem.

The Share-a-Ride Problem (SARP) aims at maximizing the profit of serving a set of passengers and parcels using a set of homogeneous vehicles. We propose an adaptive large neighborhood search (ALNS) heuristic to address the SARP. Furthermore, we study the problem of determining the time slack in a SARP schedule. Our proposed solution approach is tested on three sets of realistic instances. The performance of our heuristic is benchmarked against a mixed integer programming (MIP) solver and the Dial-a-Ride Problem (DARP) test instances. Compared to the MIP solver, our heuristic is superior in both the solution times and the quality of the obtained solutions if the CPU time is limited. We also report new best results for two out of twenty benchmark DARP instances.