The Dial-a-Ride Problem with Limited Pickups per Trip

Boshuai Zhao, Kai Wang, Wenchao Wei and Roel Leus

European Journal of Operational Research, 2025, vol. 327, issue 3, 776-790

Abstract: The Dial-a-Ride Problem (DARP) is an optimization problem that involves determining optimal routes and schedules for several vehicles to pick up and deliver items at minimum cost. Motivated by real-world carpooling and crowdshipping scenarios, we introduce an additional constraint imposing a maximum number on the number of pickups per trip. This results in the Dial-a-Ride Problem with Limited Pickups per Trip (DARP-LPT). We apply a fragment-based method for DARP-LPT, where a fragment is a partial path. Specifically, we extend two formulations from Rist and Forbes (2021): the Fragment Flow Formulation (FFF) and the Pickup-Space Fragment Formulation (PSFF). Furthermore, our results show that PSFF outperforms FFF, which in turn surpasses traditional arc-based formulations in both solution quality and computational efficiency. Additionally, we compare several existing fragment sets that differ in the length of their partial paths and find that the sets with shorter partial paths yield the best solution times when used with PSFF. In addition, we propose a new mixed fragment set, which is useful when the sets with longer partial paths become too large. In such cases, it yields the lowest CPU time.

Keywords: Routing; Dial-a-ride problem; Limited number of pickups per trip; Fragments (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221725004497
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:ejores:v:327:y:2025:i:3:p:776-790

DOI: 10.1016/j.ejor.2025.05.051

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().