Please use this identifier to cite or link to this item:
https://doi.org/10.1287/trsc.2017.0772
Title: | A Two-Phase Branch-and-Price-and-Cut for a Dial-a-Ride Problem in Patient Transportation | Authors: | Zhixing Luo Mengyang Liu Lim Leong Chye, Andrew |
Keywords: | Dial-a-ride problem Manpower planning Branch-and-price-and-cut Patient Transportation History |
Issue Date: | 1-Aug-2018 | Publisher: | informs | Citation: | Zhixing Luo, Mengyang Liu, Lim Leong Chye, Andrew (2018-08-01). A Two-Phase Branch-and-Price-and-Cut for a Dial-a-Ride Problem in Patient Transportation. Transportation Science 53 (1). ScholarBank@NUS Repository. https://doi.org/10.1287/trsc.2017.0772 | Abstract: | 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. | Source Title: | Transportation Science | URI: | https://scholarbank.nus.edu.sg/handle/10635/167646 | ISSN: | 0041-1655 1526-5447 |
DOI: | 10.1287/trsc.2017.0772 |
Appears in Collections: | Staff Publications Elements |
Show full item record
Files in This Item:
File | Description | Size | Format | Access Settings | Version | |
---|---|---|---|---|---|---|
ER-DARP.pdf | 464.09 kB | Adobe PDF | OPEN | Pre-print | View/Download |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.