We introduce KaRRi, an improved algorithm for scheduling a fleet of shared vehicles as it is used by services like UberXShare and Lyft Shared. We speed up the basic online algorithm that looks for all possible insertions of a new customer into a set of existing routes, we generalize the objective function, and efficiently support a large number of possible pick-up and drop-off locations. This lays an algorithmic foundation for ridesharing systems with higher vehicle occupancy -- enabling greatly reduced cost and ecological impact at comparable service quality. We find that our algorithm computes assignments between vehicles and riders several times faster than a previous state-of-the-art approach. Further, we observe that allowing meeting points for vehicles and riders can reduce the operating cost of vehicle fleets by up to $15\%$ while also reducing passenger wait and trip times.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    Fast Many-to-Many Routing for Ridesharing with Multiple Pickup and Dropoff Locations


    Beteiligte:

    Erscheinungsdatum :

    2023


    Anmerkungen:

    29 pages, 6 figures, 5 tables Submitted to the European Symposium on Algorithms (ESA) 2023


    Medientyp :

    Preprint


    Format :

    Elektronische Ressource


    Sprache :

    Englisch




    Fast Many-to-Many Routing for Ridesharing with Multiple Pickup and Dropoff Locations

    Laupichler, Moritz / Sanders, Peter | DataCite | 2023

    Freier Zugriff

    Systems and methods for updating pickup and dropoff locations for a vehicle

    FRIEDMAN ERIC / TANPHAICHITR SAKSIRI / KIM DONGHYUN et al. | Europäisches Patentamt | 2024

    Freier Zugriff

    Throughput Capacity Comparison for Airport Pickup and Dropoff Facilities

    Kleywegt, Anton J. / Liu, Xinyu | Transportation Research Record | 2021


    Systems and methods for improved vehicle routing to account for real-time passenger pickup and dropoff

    GARDNER MATHEW D / SMITH TAYLOR G | Europäisches Patentamt | 2021

    Freier Zugriff

    SYSTEMS AND METHODS FOR IMPROVED VEHICLE ROUTING TO ACCOUNT FOR REAL-TIME PASSENGER PICKUP AND DROPOFF

    GARDNER MATHEW D / SMITH TAYLOR G | Europäisches Patentamt | 2020

    Freier Zugriff