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.

    Highlights A Dial-a-Ride Problem with incompatibilities is investigated. Two types of incompatibilities are considered. Branch-and-Cut algorithms are developed for both types. Zero distance chains where several events occur simultaneously are included.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

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


    Beteiligte:


    Erscheinungsdatum :

    2023-12-13




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch




    A branch-and-cut algorithm for a realistic dial-a-ride problem

    Liu, Mengyang / Luo, Zhixing / Lim, Andrew | Elsevier | 2015


    Dial-a-ride with customer operated dispatching

    Elmberg, Curt M. | Online Contents | 1978


    GPU-Accelerated Tabu Search Algorithm for Dial-A-Ride Problem

    Pandi, Ramesh Ramasamy / Ho, Song Guang / Nagavarapu, Sarat Chandra et al. | IEEE | 2018


    A Granular Tabu Search algorithm for the Dial-a-Ride Problem

    Kirchler, Dominik | Online Contents | 2013


    A Granular Tabu Search algorithm for the Dial-a-Ride Problem

    Kirchler, Dominik / Wolfler Calvo, Roberto | Elsevier | 2013