An exact branch-and-price-and-cut algorithm for a practical and large-scale dial-a-ride problem

Mohammad Karimi, Fanny Camiat, Guy Desaulniers and Michel Gendreau

Journal of the Operational Research Society, 2025, vol. 76, issue 6, 1125-1139

Abstract: Vehicle routing problems are encountered in various practical transportation scenarios. One such problem is the dial-a-ride problem (DARP), which involves transporting efficiently passengers from their origin to their destination and whose objective is to design vehicle routes minimizing total costs and accommodating all pickup-and-delivery requests. The solution must also adhere to capacity limitations, time windows, and a maximum ride time for each passenger. This paper proposes an exact branch-price-and-cut algorithm to solve a practical variant of the DARP, where both the passengers and vehicle fleet are heterogeneous, and other practical constraints such as break requirements and maximum route duration are imposed. In this algorithm, column generation which alternates between solving a master problem and subproblems, is used to compute lower bounds in the search tree. We develop a labeling algorithm to efficiently handle these subproblems. The effectiveness of the algorithm is evaluated on a real-world case study involving 849 heterogeneous passengers and more than 70 available vehicles, as well as on 10 smaller instances (with 300 to 820 trips) extracted from another very large real-world dataset. To the best of our knowledge, this 849-trip instance is the largest DARP instance reported to be solved to optimality in the literature.

Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/01605682.2024.2412214 (text/html)
Access to full text is restricted to subscribers.

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:taf:tjorxx:v:76:y:2025:i:6:p:1125-1139

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/tjor20

DOI: 10.1080/01605682.2024.2412214

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald

More articles in Journal of the Operational Research Society from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().