KaRRi - Karlsruhe Rapid Ridesharing

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.

Fast:

• 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)

Flexible:

• 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.