Solving the equity-aware dial-a-ride problem using an exact branch-cut-and-price algorithm

Shuocheng Guo, Iman Dayarian, Jian Li and Xinwu Qian

Transportation Research Part B: Methodological, 2025, vol. 192, issue C

Abstract: This paper proposes a Branch-Cut-and-Price (BCP) algorithm to solve an equitable variant of the Dial-a-Ride problem (DARP), namely Equity-Aware DARP (EDARP), a bi-objective optimization problem that simultaneously minimizes the total routing cost and maximizes the Equity-of-Travel (EoT) outcomes for individual passengers. For passengers, EoT is specified as their detour rate, measured by the ratio between total in-vehicle time and door-to-door direct trip time. The EoT objective of EDARP is to minimize the maximum detour rate among all passengers while satisfying the DARP constraints. We model the EDARP using a min–max trip-based formulation, which is solved exactly using a tailored BCP algorithm. The BCP algorithm adopts the Column Generation method by decomposing the problem into a master problem and a subproblem. The subproblem is an Elementary Shortest Path Problem with Resource Constraints and Min–Max EoT (ESPPRC-MME), which is NP-hard. To efficiently solve the ESPPRC-MME, we develop a minimal-ride-time calibration algorithm and establish families of resource extension functions in compliance with equity-related resources. We also extend the applicability of EDARP to the operation of the dial-a-ride service during the pandemic aiming to minimize the maximum exposure risk of individual travelers. The effectiveness of our models and algorithms are comprehensively evaluated using both classic DARP instances as well as EDARP instances generated from real-world paratransit trip datasets. Computational results show that our BCP algorithm can optimally solve 50 out of 54 real-world instances (up to 55 passengers and 13 vehicles covering 110 nodes) within a time limit of one hour. Important practical insights are also discussed by investigating the Pareto front and the Lorenz curves for trip inequity based on the optimal outcomes of real-world instances.

Keywords: Dial-a-ride problem; Branch-cut-and-price; Column generation; Demand-responsive transit; Equity; Pareto front (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S019126152400273X
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:192:y:2025:i:c:s019126152400273x

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.103149

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 ().