Route Planning in Transportation Networks

Understand

We survey recent advances in algorithms for route planning in transportation networks.

• For road networks, we show that one can compute driving directions in milliseconds or less even at continental scale.
• A variety of techniques provide different trade-offs between preprocessing effort, space requirements, and query time.
• Some algorithms can answer queries in a fraction of a microsecond, while others can deal efficiently with real-time traffic.