KaRRi - Karlsruhe Rapid Ridesharing

KaRRi is a state-of-the-art dispatcher for the dynamic taxi sharing problem with meeting points. KaRRi utilizes highly engineered many-to-many shortest path queries to compute optimal assignments of riders to vehicles and according meeting points within milliseconds.


What KaRRi - Karlsruhe Rapid Ridesharing can do for you

KaRRi is the fastest and most flexible dispatching algorithm for dynamic taxi sharing with meeting points. KaRRi serves as a first step towards novel, multimodal personal transportation schemes and software-defined public transportation.


  • highly engineered many-to-many queries based on state-of-the-art shortest path speedup techniques like (bucket-based) (customizable) contraction hierarchies
  • novel pruning techniques with a scope beyond taxi sharing
  • SIMD-parallelism using bundled shortest path queries
  • multi-threading for additional speedups (experimental)


  • highly parameterized cost function
  • on-the-fly shortest path queries that can quickly adapt to changes in the road network using (customizable) contraction hierarchies (no pre-computation of shortest paths)
  • run KaRRi on the bundled input instances, on random input data generated for a given urban area using OpenStreetMap data, or on your own input data using the ConvertGraph and TransformLocations utilities

Try it out for yourself by checking out our GitHub page.

Learn more about what makes KaRRi fast:
Moritz Laupichler, and Peter Sanders: Fast Many-to-Many Routing for Dynamic Taxi Sharing with Meeting Points. 2024 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX), 2024.

Participating organisations

Karlsruhe Institute of Technology (KIT)

Reference papers


Moritz Laupichler
Karlsruhe Institute of Technology

Related projects

no image

Core Informatics

A Helmholtz Pilot Program

Updated 8 months ago
In progress