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.


    Access

    Download


    Export, share and cite



    Title :

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


    Contributors:

    Publication date :

    2023


    Remarks:

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


    Type of media :

    Preprint


    Type of material :

    Electronic Resource


    Language :

    English




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

    Laupichler, Moritz / Sanders, Peter | DataCite | 2023

    Free access

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

    FRIEDMAN ERIC / TANPHAICHITR SAKSIRI / KIM DONGHYUN et al. | European Patent Office | 2024

    Free access

    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 | European Patent Office | 2021

    Free access

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

    GARDNER MATHEW D / SMITH TAYLOR G | European Patent Office | 2020

    Free access