Ride-sharing is an essential aspect of modern urban mobility. In this paper, we consider a classical problem in ride-sharing - the Multi-Vehicle Dial-a-Ride Problem (Multi-Vehicle DaRP). Given a fleet of vehicles with a fixed capacity stationed at various locations and a set of ride requests specified by origins and destinations, the goal is to serve all requests such that no vehicle is assigned more passengers than its capacity at any point along its trip. We propose an algorithm HRA, which is the first non-trivial approximation algorithm for the Multi-Vehicle DaRP. The main technical contribution is to reduce the Multi-Vehicle DaRP to a certain capacitated partitioning problem, which we solve using a novel hierarchical grouping algorithm. Experimental results show that the vehicle routes produced by our algorithm not only exhibit less total travel distance compared to state-of-the-art baselines, but also enjoy a small in-transit latency, which crucially relates to riders' traveling times. This suggests that HRA enhances rider experience while being energy-efficient.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    A Hierarchical Grouping Algorithm for the Multi-Vehicle Dial-a-Ride Problem


    Beteiligte:
    Luo, Kelin (Autor:in) / Florio, Alexandre M. (Autor:in) / Das, Syamantak (Autor:in) / Guo, Xiangyu (Autor:in)

    Erscheinungsdatum :

    2022



    Medientyp :

    Preprint


    Format :

    Elektronische Ressource


    Sprache :

    Englisch




    Minimum Makespan Multi-vehicle Dial-a-Ride

    Goertz, Inge Li / Nagarajan, Viswanath / Ravi, R. | ArXiv | 2011

    Freier Zugriff

    Dial-A-Ride Vehicle Specification

    J. B. suomala | NTIS | 1971


    ELECTRIC VEHICLE DIAL-A-RIDE SYSTEM

    LIMMER STEFFEN | Europäisches Patentamt | 2024

    Freier Zugriff

    Dial-a-Ride

    Jørgensen, Rene Munk | BASE | 2003

    Freier Zugriff

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

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