Journal club on fast route planning algorithms

June 20, 2016 @ 11.00 – 12.00
Lecture room AS3, TUAS
Presenter: Rainer Kujala

Approximate outline of the talk:
1. Graph search basics and terminology
2. (Traditional) Speed-up techniques for static graphs
3. Modern techniques for routing in road (=static networks)
4. Time-dependent road network routing (traffic jams, changing road conditions…)
5. Routing in public transport networks

Based mostly on the article:

Route Planning in Transportation Networks

Authors: Hannah Bast, Daniel Delling, Andrew Goldberg, Matthias Müller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, Renato F. Werneck

Abstract: 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. Journey planning on public transportation systems, although conceptually similar, is a significantly harder problem due to its inherent time-dependent and multicriteria nature. Although exact algorithms are fast enough for interactive queries on metropolitan transit systems, dealing with continent-sized instances requires simplifications or heavy preprocessing. The multimodal route planning problem, which seeks journeys combining schedule-based transportation (buses, trains) with unrestricted modes (walking, driving), is even harder, relying on approximate solutions even for metropolitan inputs.

Download the article here