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

Schulz, Arne; Pfeiffer, Christian

doi:10.1016/j.tre.2023.103394

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

Publication date

2023-12-21

Document type

Forschungsartikel

Author

Schulz, Arne

Pfeiffer, Christian

Organisational unit

Universität Hamburg, Institute of Operations Management

DOI

10.1016/j.tre.2023.103394

URI

https://openhsu.ub.hsu-hh.de/handle/10.24405/22180

Scopus ID

2-s2.0-85180979335

Publisher

Elsevier

Series or journal

Transportation Research Part E: Logistics and Transportation Review

ISSN

1366-5545

Periodical volume

181

Article ID

103394

Peer-reviewed

✅

Part of the university bibliography

Nein

Language

English

Keyword

Branch-and-Cut

Dial-a-ride problem

Mixed-integer programming

Ridepooling

Valid inequalities

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.

Version

Published version

Access right on openHSU

Metadata only access