A Branch-and-Price algorithm for the electric autonomous Dial-A-Ride Problem

Yue Su, Nicolas Dupin, Sophie N. Parragh and Jakob Puchinger

Transportation Research Part B: Methodological, 2024, vol. 186, issue C

Abstract: The Electric Autonomous Dial-A-Ride Problem (E-ADARP) consists in scheduling a fleet of electric autonomous vehicles to provide ride-sharing services for customers that specify their origins and destinations. The E-ADARP considers the following perspectives: (i) a weighted-sum objective that minimizes both total travel time and total excess user ride time; (ii) the employment of electric autonomous vehicles and a partial recharging policy. This paper presents the first labeling algorithm for a path-based formulation of the DARP/E-ADARP, where the main ingredient includes: (1) fragment-based representation of paths, (2) a novel approach that abstracts fragments to arcs while ensuring excess-user-ride-time optimality, (3) construction of a sparser new graph with the abstracted arcs, which is proven to preserve all feasible routes of the original graph, and (4) strong dominance rules and constant-time feasibility checks to compute the shortest paths efficiently. This labeling algorithm is then integrated into Branch-and-Price (B&P) algorithms to solve the E-ADARP. In the computational experiments, the B&P algorithm achieves optimality in 71 out of 84 instances. Remarkably, among these instances, 50 were solved optimally at the root node without branching. We identify 26 new best solutions, improve 30 previously reported lower bounds, and provide 17 new lower bounds for large-scale instances with up to 8 vehicles and 96 requests. In total 42 new best solutions are generated on previously solved and unsolved instances. In addition, we analyze the impact of incorporating the total excess user ride time within the objectives and allowing unlimited visits to recharging stations. The following managerial insights are provided: (1) solving a weighted-sum objective function can significantly enhance the service quality, while still maintaining operational costs at nearly optimal levels, (2) the relaxation on charging visits allows us to solve all instances feasibly and further reduces the average solution cost.

Keywords: Dial-A-Ride Problem; Electric autonomous vehicles; (Excess-)user-ride-time optimal scheduling; Branch-and-Price; Labeling algorithm (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0191261524001358
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:transb:v:186:y:2024:i:c:s0191261524001358

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.trb.2024.103011

Access Statistics for this article

Transportation Research Part B: Methodological is currently edited by Fred Mannering

More articles in Transportation Research Part B: Methodological from Elsevier
Bibliographic data for series maintained by Catherine Liu ().