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

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.