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.
Fast Many-to-Many Routing for Ridesharing with Multiple Pickup and Dropoff Locations
2023
29 pages, 6 figures, 5 tables Submitted to the European Symposium on Algorithms (ESA) 2023
Preprint
Electronic Resource
English
Fast Many-to-Many Routing for Ridesharing with Multiple Pickup and Dropoff Locations
DataCite | 2023
|Systems and methods for updating pickup and dropoff locations for a vehicle
European Patent Office | 2024
|Throughput Capacity Comparison for Airport Pickup and Dropoff Facilities
Transportation Research Record | 2021
|European Patent Office | 2021
|European Patent Office | 2020
|