Adaptive large neighborhood search for the time-dependent profitable dial-a-ride problem. (November 2022)

• Record Type: Journal Article
• Authors: Zhao, Jingyi; Poon, Mark; Zhang, Zhenzhen; Gu, Ruixue
• Is Part Of: Computers & operations research. Volume 147(2022)
• Publication Date: 2022-11
• Subjects: Routing -- Time-dependent travel time -- Dial-a-ride problem -- Meta-heuristics -- Mixed integer programming; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2022.105938
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: 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. Highlights: Transportation service problem with maximum ride time constraint under time-dependent travel time. MIP model for the proposed time-dependent profitable dial-a-ride problem (TD-PDARP). Feasibility evaluation method for various complicated constraints under time-dependent conditions. Hybrid meta-heuristic algorithm combining ALNS and local search with tailored operators. New benchmark data and comprehensive computational experiments.