Adaptive large neighborhood search for the time-dependent profitable dial-a-ride problem

This paper is motivated by a non-emergency ambulance transportation service provider that picks up and drops off patients while considering both the time window for medical appointments and the maximum ride-time constraint for each patient. Varying travel times based on departure times further complicates the feasibility evaluation of a given route under both constraints. This problem aims to maximize the net profit which is calculated as the collected reward of serving the selected requests minus the total travel cost of the designed route. The problem is modeled as a time-dependent profitable dial-a-ride problem (TD-PDARP) with a single-vehicle using a mixed-integer linear programming (MILP) model. We propose a tailored feasibility evaluation procedure to handle the complicated maximum ride-time constraint under the time-dependent travel time model, which is then embedded in a hybrid algorithm to solve the proposed problem. This hybrid algorithm leverages an adaptive large neighborhood search (ALNS) for large-scale exploration together with local search (LS) techniques to exploit local regions comprehensively. We evaluate the performance of the proposed algorithm on newly generated TD-PDARP instances. The experiments show that our ALNS-LS algorithm can solve large instances that cannot be solved by commercial solvers in a reasonable time. Furthermore, for all instances that can be solved by the solver within 12 h, our proposed heuristic algorithm is able to obtain the optimal solutions and takes only 1.03% of the average run time required by the solver.