A Two-Phase Branch-and-Price-and-Cut for a Dial-a-Ride Problem in Patient Transportation

In this paper, we investigate an extension of the R-DARP recently proposed by [Liu M, Luo Z, Lim A (2015) A branch-and-cut algorithm for a realistic dial-a-ride problem. Transporation Res. Part B: Methodological 81(1):267–288.]. The R-DARP, as a variant of the classic dial-a-ride problem (DARP), consists of determining a set of minimum-distance trips for vehicles to transport a set of clients from their origins to their destinations, subject to side constraints, such as capacity constraints, time window constraints, maximum riding time constraints, and manpower planning constraints. Our problem extends the R-DARP by (1) changing its objective to first maximizing the number of requests satisfied and then minimizing the total travel distance of the vehicles, and (2) generalizing the lunch break constraints of staff members. To solve this problem, we propose a two-phase branch-and-price-and-cut algorithm based on a strong trip-based model. The trip-based model is built on a set of nondominated trips, which are enumerated by an ad hoc label-setting algorithm in the first phase. Then we decompose the trip-based model by Benders decomposition and propose a branch-and-price-and-cut algorithm to solve the decomposed model in the second phase. Our two-phase exact algorithm is tested on the R-DARP benchmark instances and a set of new instances generated according to the same real-world data set as the R-DARP instances. Our algorithm quickly solves all of the R-DARP instances to optimality and outperforms the branch-and-cut proposed by Liu, Luo, and Lim. On the 42 new test instances, our algorithm solves 27 instances to optimality in four hours with the largest instance consisting of 36 requests. The online appendix is available at https://doi.org/10.1287/trsc.2017.0772 .