Friday, 10.50 - 11.35, HFB|C

Route Planning in Transportation – New Results and Challenges

Nowadays, route planning systems belong to the most frequently used information systems. The algorithmic core problem of such systems, is the classical shortest paths problem that can be solved by Dijkstra's algorithm which, however, is too slow for practical scenarios.

Algorithms for route planning in transportation networks have recently undergone a rapid development, leading to methods that are up to several million times faster than Dijkstra’s algorithm. For example, for continent-sized road networks, newly-developed algorithms can answer queries in a few hundred nanoseconds; others can incorporate current traffic information in under a second on a commodity server; and many new applications can now be dealt with efficiently. Accordingly, route planning has become a showpiece of Algorithm Engineering demonstrating the engineering cycle that consists of design, analysis, implementation and experimental evaluation of practicable algorithms.

Recently, new aspects like multimodal route planning, personalized journey planning with respect to multiple criteria or energy-aware route planning for electric vehicles come up. This talk provides a condensed survey of recent advances in algorithms for route planning in transportation networks.

Dorothea Wagner is a full professor for Informatics at the Karlsruhe Institute of Technology (KIT). Her research interests include design and analysis of algorithms and algorithm engineering, graph algorithms, computational geometry and discrete optimization, particularly applied to transportation systems, energy systems, network analysis, data mining and visualization.

Among other activities she is member of the German Council of Science and Humanities (Wissenschaftsrat). From 2007 to 2014 she was vice president of the DFG (Deutsche Forschungsgemeinschaft - German Research Foundation) and 2004 to 2013 speaker of the scientific advisory board of Dagstuhl - Leibniz Center for Informatics. In 2012 she received a Google Focused Research Award, she is member of Academia Europaea, of acatech - National Academy of Science and Engineering, and Fellow of the GI (Gesellschaft für Informatik).

Dorothea Wagner obtained her diploma and Ph.D. degrees from the RWTH Aachen in 1983 and 1986 respectively; and 1992 the Habilitation degree from the TU Berlin. 1994 - 2003 she was a full professor at the University of Konstanz.