Automated vehicles are becoming a reality. Expectations are that AVs will ultimately transform personal mobility from privately owned assets to on-demand services. This transformation will enhance the possibility of sharing trips, leading to shared AVs (SAVs). The preeminent aim of this paper is to lay foundations for fast and efficient algorithms to be used in such new driving conditions. These algorithms must be able to solve Dial-a-Ride problems with transfers (DARPT). Hence, they should efficiently assign passengers to vehicles and routes while also: administering vehicles dispatch, determining convenient parking for idling vehicles and managing vehicle routing in real-time. In this paper, we develop two integer linear programming models (one in continuous time and one in discrete time) and their extensions to solve the DARPT. Our models take into account routing, service times, constraints on maximum route time-span, unserved requests, preferred arrival and departure time, nonconstant travel times, convenient parking while optimizing routing costs and quality of the service. The models are tested on instances based on Google Maps data by solving them with a commercial solver. The results of these tests are the starting point for validating the performance of forthcoming, ad hoc metaheuristics to be used in real-life sized scenarios.


    Access

    Download


    Export, share and cite



    Title :

    MILP models for the Dial-a-ride problem with transfers


    Contributors:


    Publication date :

    2021




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    Unknown




    Dial-a-ride problem with modular platooning and en-route transfers

    Fu, Zhexi / Chow, Joseph Y. J. | ArXiv | 2022

    Free access

    The dial-a-ride problem: models and algorithms

    Cordeau, Jean-François / Laporte, Gilbert | Springer Verlag | 2007


    Dial-a-Ride

    Jørgensen, Rene Munk | BASE | 2003

    Free access

    A dial-a-ride problem with driver preferences

    Ouasaid, Sana / Saddoune, Mohammed | IEEE | 2021