KIT | KIT-Bibliothek | Impressum | Datenschutz

Fast, Exact and Scalable Dynamic Ridesharing

Buchhold, Valentin; Sanders, Peter; Wagner, Dorothea


We study the problem of servicing a set of ride requests by dispatching a set of shared vehicles, which is faced by ridesharing companies such as Uber and Lyft. Solving this problem at a large scale might be crucial in the future for effectively using large fleets of autonomous vehicles. Since finding a solution for the entire set of requests that minimizes the total driving time is NP-complete, most practical approaches process the requests one by one. Each request is inserted into any vehicle's route such that the increase in driving time is minimized. Although this variant is solvable in polynomial time, it still takes considerable time in current implementations, even when inexact filtering heuristics are used. In this work, we present a novel algorithm for finding best insertions, based on (customizable) contraction hierarchies with local buckets. Our algorithm finds provably exact solutions, is still 30 times faster than a state-of-the-art algorithm currently used in industry and academia, and scales much better. When used within iterative transport simulations, our algorithm decreases the simulation time for largescale scenarios with many requests from days to hours.

Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Forschungsbericht/Preprint
Publikationsdatum 05.11.2020
Sprache Englisch
Identifikator KITopen-ID: 1000133464
Nachgewiesen in arXiv
Relationen in KITopen
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page