A Branch-and-Cut algorithm for the dial-a-ride problem with incompatible customer types

Arne Schulz and Christian Pfeiffer

Transportation Research Part E: Logistics and Transportation Review, 2024, vol. 181, issue C

Abstract: Ridepooling is expected to become more and more important in people’s mobility. At the same time, autonomous vehicles are expected to be widely used in such applications in the future. While the driver as a person of trust currently provides security, passengers are alone with strangers in an autonomous ridepooling vehicle. In the paper, we address this aspect by including incompatibilities between customers, meaning that incompatible customers cannot share the vehicle at the same time. Although incompatibilities can be defined in any way by the provider, they can be set, for example, if a customer feels unsafe in sharing the vehicle with customers of a certain type. As other compatible customers can replace the driver as a person of trust, we present a second setting where all customers are allowed to share the vehicle at the same time, but customers are never alone in the vehicle with incompatible customers. We present Branch-and-Cut algorithms for both problem settings including methods to improve the search with respect to the incompatibilities. We show in a computational study that the introduced methods improve the search significantly and evaluate the Branch-and-Cut algorithms on realistic instances with up to 120 customers and 10 vehicles. Moreover, our results suggest that it can be a beneficial option for the provider to allow their customers to participate in the decision process by indicating incompatibilities for types of customers, meaning that they do not want to share a vehicle with a customer of an incompatible type.

Keywords: Dial-a-ride problem; Ridepooling; Mixed-integer programming; Branch-and-Cut; Valid inequalities (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/S1366554523003824
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:transe:v:181:y:2024:i:c:s1366554523003824

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/journaldescription.cws_home/600244/bibliographic
http://www.elsevier. ... 600244/bibliographic

DOI: 10.1016/j.tre.2023.103394

Access Statistics for this article

Transportation Research Part E: Logistics and Transportation Review is currently edited by W. Talley

More articles in Transportation Research Part E: Logistics and Transportation Review from Elsevier
Bibliographic data for series maintained by Catherine Liu ().