Fast Detour Computation for Ride Sharing

Robert Geisberger, Dennis Luxen, Sabine Neubauer, Peter Sanders & Lars Volker
Ride sharing becomes more and more popular not least because internet services help matching offers and request. However, current systems use a rather simple-minded functionality allowing to search for the origin and destination city, sometimes enriched with radial search around the cities. We show that theses services can be substantially improved using innovative route planning algorithms. More concretely, we generalize previous static algorithms for many-to-many routing to a dynamic setting and develop an additional pruning...