Abstract The Dial-a-Ride Problem (DARP) introduced in the early 1980s is the NP-Hard optimization problem of developing the most cost-efficient vehicle schedules for a number of available vehicles that have to start from a depot, pick up and deliver a set of passengers, and return back to the same depot. DARP has been used in many modern applications, including the scheduling of demand-responsive transit and car pooling. This study departs from the original definition of DARP and it extends it by considering an interchange point where vehicles can exchange their picked-up passengers with other vehicles in order to shorten their delivery routes and reduce their running times. In addition to that, this study introduces the concept of generalized passenger travel times in the DARP formulation which translates the increased in-vehicle crowdedness to increased perceived passenger travel times. This addresses a key issue because the perceived in-vehicle travel times of passengers might increase when the vehicle becomes more crowded (i.e., passengers might feel that their travel time is higher when they are not able to find a seat or they are too close to each other increasing the risk of virus transmission or accidents). Given these considerations, this study introduces the Dial-a-Ride Problem with interchange and perceived travel times (DARPi) and models it as a nonlinear programming problem. DARPi is then reformulated to a MILP with the use of linearizations and its search space is tightened with the addition of valid inequalities that are employed when solving the problem to global optimality with Branch-and-Cut. For large problem instances, this study introduces a tabu search-based metaheuristic and performs experiments in benchmark instances used in past literature demonstrating the computation times and solution stability of our approach. The effect of the perceived passenger travel times to the vehicle running costs is also explored in extensive numerical experiments.

    Highlights Definition and Formulation of the Dial-a-Ride problem with Interchange. Model reformulation to a mixed-integer linear program. Incorporation of perceived passenger travel times to the model. Proof of NP-Hardness and introduction of Valid Inequalities. Development of problem-specific Tabu search-based approach.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    The multi-vehicle dial-a-ride problem with interchange and perceived passenger travel times


    Beteiligte:


    Erscheinungsdatum :

    2023-09-13




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch




    Automated taxis’ dial-a-ride problem with ride-sharing considering congestion-based dynamic travel times

    Liang, Xiao / Correia, Gonçalo Homem de Almeida / An, Kun et al. | Elsevier | 2020




    Minimum Makespan Multi-vehicle Dial-a-Ride

    Gørtz, Inge Li / Nagarajan, Viswanath / Ravi, R. | BASE | 2009

    Freier Zugriff

    Multi-Passenger Ride Vehicle

    OSTERMAN ROSS ALAN / SCHWARTZ JUSTIN MICHAEL | Europäisches Patentamt | 2017

    Freier Zugriff