Google Focused Research Award

The goal of this project was the advancement of the state of the art of route planning. While Google already employs sophisticated algorithms for routing on road and public transit networks, they are always looking for ways to improve the service they provide to their users. Hannah Bast, Peter Sanders, and Dorothea Wagner – together with their respective research groups – are some of the leading researchers in the field of route planning. As the title suggests, the focus of this collaboration was on three aspects that are important for modern route planning.

First, routing is inherently multi-modal: A typical route can involve walking, driving, and public transport all together. One of the challenges of multi-modal route planning is dealing with the large number of alternative routes that arise as a result of different modes of traveling. However, not all of these possible routes are reasonable; for example, people rarely drive between taking trains.

This ties in with result diversity: Users have different preferences as to what constitutes a “good” route. This already holds for single-mode routes – e.g., some people might prefer a slower, but more scenic route – but is even more pronounced in multi-modal routing, where some people may prefer public transit over driving or vice versa. The goal is to provide users with a selection of sufficiently diverse routes without overwhelming them with meaningless choices, allowing them to easily pick their preferred option.

A further challenge is the incorporation of real-time data. Often, optimal routes change as traffic jams are formed and resolved or trains are delayed. Therefore, algorithms should be able to use this information to provide the user with alternatives in a timely manner.

• Minimum Expected Arrival Time

• Simeon Danailov Andreev, Julian Dibbelt, Martin Nöllenburg, Thomas Pajor, and Dorothea Wagner. Towards realistic pedestrian route planning. In Proceedings of the 15th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS’15), volume 48 of OpenAccess Series in Informatics (OASIcs), pages 1–15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, September 2015.
  Integrating special requirements for pedestrian routing.
• Julian Arz, Dennis Luxen, and Peter Sanders. Transit node routing reconsidered. In Proceedings of the 12th International Symposium on Experimental Algorithms (SEA’13), volume 7933 of Lecture Notes in Computer Science, pages 55–66. Springer, 2013.
  Integrating contraction hierarchies with transit node routing yields two orders of magnitude faster queries at the cost of less than a factor of two in preprocessing time.
• Hannah Bast, Mirko Brodesser, and Sabine Storandt. Result diversity for multi-modal route planning. In Proceedings of the 13th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS’13), OpenAccess Series in Informatics (OASIcs), pages 123–136, 2013.
  Defining a set of axioms and designing a filter algorithm to efficiently compute small yet representative sets of reasonable paths in a multi-modal scenario.
• Hannah Bast, P. Brosi, and Sabine Storandt. Real-time movement visualization of public transit data. In SIGSPATIAL, pages 331–340, 2014.
  Using GTFS (real-time) data and efficient data structures to interpolate and visualize public transit vehicle positions on large scale.
• Hannah Bast, Daniel Delling, Andrew V. Goldberg, Matthias Müller–Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato F. Werneck. Route planning in transportation networks. Technical Report abs/1504.05140, ArXiv e-prints, 2015.
  Survey covering the state-of-the-art for route planning in road and public transportation networks.
• Hannah Bast, Jonas Sternisko, and Sabine Storandt. Delay-robustness of transfer patterns in public transportation route planning. In Proceedings of the 13th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS’13), OpenAccess Series in Informatics (OASIcs), pages 42–54, 2013.
  Empirical proof that transfer patterns still work well in case of (even large and wide-spread) delays with less than one percent of queries being answered sub-optimally.
• Hannah Bast and Sabine Storandt. Flow-based guidebook routing. In Proceedings of the 16th Meeting on Algorithm Engineering and Experiments (ALENEX’14), pages 155–165. SIAM, 2014.
  Computing a time-independent and concise summary of reasonable route options over a larger time span (e.g., take Tram 8 to Zurich HB, every 8 minutes, from 8am - 6pm).
• Hannah Bast and Sabine Storandt. Frequency-based search for public transit. In SIGSPATIAL, pages 13–22, 2014.
  New frequency-based model which accelerates the transfer-patterns precomputation by a factor of 60, reduces space consumption by a factor of 10, and speeds up query times by a factor of 10.
• Hannah Bast, M. Hertel and Sabine Storandt. Scalable Transfer Patterns. In ALENEX, 2016.
  New clustering-based preprocessing scheme for transfer patterns that reduces preprocessing times by a factor of 20 and space consumption by a factor of 100.
• Gernot Veit Batz, Robert Geisberger, Dennis Luxen, Peter Sanders, and Roman Zubkov. Efficient route compression for hybrid route planning. In Proceedings of the 1st Mediterranean Conference on Algorithms. Springer, 2012.
  Shows that static contraction hierarchies allow a client to quickly decode routes from a dynamic routing engine on the host which encodes them as via edges.
• G. Batz, R. Geisberger, S. Neubauer, and P. Sanders. Time-dependent contraction hierarchies and approximation. In SEA, pages 166–177, 2010.
  Makes time-dependent contraction hierarchies practical at the price of negligible inaccuracies.
• Gernot Veit Batz, Robert Geisberger, Peter Sanders, and Christian Vetter. Minimum time-dependent travel times with contraction hierarchies. ACM Journal of Experimental Algorithmics, 18(1.4):1–43, April 2013.
  Journal paper on time-dependent contraction hierarchies.
• Gernot Veit Batz and Peter Sanders. Time-dependent route planning with generalized objective functions. In Proceedings of the 20th Annual European Symposium on Algorithms (ESA’12), volume 7501 of Lecture Notes in Computer Science. Springer, 2012.
  Shows that even adding a static offset to a time-dependent travel time objective leads to an NP-hard problem but gives heuristics that work very well in practice
• Reinhard Bauer, Moritz Baum, Ignaz Rutter, and Dorothea Wagner. On the complexity of partitioning graphs for arc-flags. Journal of Graph Algorithms and Applications, 17(3):265–299, 2013.
  Theoretical proof that Arc-Flags preprocessing is (NP-)hard.
• Reinhard Bauer, Tobias Columbus, Ignaz Rutter, and Dorothea Wagner. Search-space size in contraction hierarchies. In Proceedings of the 40th International Colloquium on Automata, Languages, and Programming (ICALP’13), volume 7965 of Lecture Notes in Computer Science, pages 93–104. Springer, 2013.
  Theoretical analysis of contraction hierarchies based on nested dissection.
• Moritz Baum, Julian Dibbelt, Andreas Gemsa, Dorothea Wagner, and Tobias Zündorf. Shortest feasible paths with charging stops for battery electric vehicles. In Proceedings of the 23rd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. ACM Press, 2015.
• Moritz Baum, Julian Dibbelt, Lorenz Hübschle-Schneider, Thomas Pajor, and Dorothea Wagner. Speed-consumption tradeoff for electric vehicle route planning. In Proceedings of the 14th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS’14), volume 42 of OpenAccess Series in Informatics (OASIcs), pages 138–151. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, September 2014.
• Moritz Baum, Julian Dibbelt, Thomas Pajor, and Dorothea Wagner. Energy-optimal routes for electric vehicles. In Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 54–63. ACM Press, 2013.
• Adi Botea, Ben Strasser, and Daniel Harabor. Complexity results for compressing optimal paths. In Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, pages 1100–1106. AAAI Press, 2015.
  Hardness proof for SRC and decomposition result for articulation points.
• A. Buluc, H. Meyerhenke, I. Safro, P. Sanders, and C. Schulz. Recent advances in graph partitioning. In arXiv, preprint arXiv:1311.3144, 2013.
  Survey on state-of-the-art graph partitioning algorithms.
• Daniel Delling, Julian Dibbelt, Thomas Pajor, Dorothea Wagner, and Renato F. Werneck. Computing multimodal journeys in practice. In Proceedings of the 12th International Symposium on Experimental Algorithms (SEA’13), volume 7933 of Lecture Notes in Computer Science, pages 260–271. Springer, 2013.
  Computing Pareto-optimal paths in a multimodal setting using a combination of RAPTOR and CH followed by filtering the Pareto-set to get a small set of “reasonable” routes that can be presented to the user.
• Daniel Delling, Julian Dibbelt, Thomas Pajor, and Renato F. Werneck. Public transit labeling. In Proceedings of the 14th International Symposium on Experimental Algorithms (SEA’15), Lecture Notes in Computer Science, pages 273–285. Springer, 2015.
  Hub-Labeling combined with public transit routing.
• Daniel Delling, Moritz Kobitzsch, Dennis Luxen, and Renato F. Werneck. Robust mobile route planning with limited connectivity. In Proceedings of the 14th Meeting on Algorithm Engineering and Experiments (ALENEX’12), pages 150–159. SIAM, 2012.
• Daniel Delling, Thomas Pajor, and Renato F. Werneck. Round-based public transit routing. Transportation Science, 49(3):591–604, 2014.
• Julian Dibbelt, Thomas Pajor, Ben Strasser, and Dorothea Wagner. Intriguingly simple and fast transit routing. In Proceedings of the 12th International Symposium on Experimental Algorithms (SEA’13), volume 7933 of Lecture Notes in Computer Science, pages 43–54. Springer, 2013.
  Fast algorithm to compute routes in public transit networks.
• Julian Dibbelt, Thomas Pajor, and Dorothea Wagner. User-constrained multi-modal route planning. ACM Journal of Experimental Algorithmics, 19:3.2:1.1–3.2:1.19, April 2015.
  Routing in a multimodal setting with restricted transfer possibilities between modes.
• Julian Dibbelt, Ben Strasser, and Dorothea Wagner. Customizable contraction hierarchies. In SEA, pages 271–282, 2014.
  Engineering contraction hierarchies using a nested-dissection based order. Conference version of Customizable Contraction Hierarchies.
• Julian Dibbelt, Ben Strasser, and Dorothea Wagner. Customizable contraction hierarchies. ACM Journal of Experimental Algorithmics, 2016.
  Engineering contraction hierarchies using a nested-dissection based order. Journal version of Customizable Contraction Hierarchies.
• Julian Dibbelt, Ben Strasser, and Dorothea Wagner. Delay-robust journeys in timetable networks with minimum expected arrival time. In Proceedings of the 14th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS’14), volume 42 of OpenAccess Series in Informatics (OASIcs), pages 1–14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, September 2014.
  Efficiently computing routes in public transit with backup routes. See also http://meatdemo.iti.kit.edu
• Julian Dibbelt, Ben Strasser, and Dorothea Wagner. Fast exact shortest path and distance queries on road networks with parametrized costs. In Proceedings of the 23rd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. ACM Press, 2015.
  Reasonably fast routing with very flexible arc costs.
• Stephan Erb, Moritz Kobitzsch, and Peter Sanders. Parallel bi-objective shortest paths using weight-balanced B-trees with bulk updates. In Proceedings of the 13th International Symposium on Experimental Algorithms (SEA’14), volume 8504 of Lecture Notes in Computer Science, pages 111–122. Springer, 2014.
  Shows that the parallel bicriteria shortest path algorithm from Sanders and Mandow can be implemented in time comparable to that of a sequential single-criteria implementation.
• Stefan Funke and Sabine Storandt. Polynomial-time construction of contraction hierarchies for multi-criteria objectives. In ALENEX, pages 41–54, 2013.
  Contraction hierarchy based scheme for efficiently answering queries on multi-dimensional cost vectors.
• Robert Geisberger, Peter Sanders, D. Schultes, and Christian Vetter. Exact routing in large road networks using contraction hierarchies. Transportation Science, 46(3):388–404, 2012.
  Journal paper on (dynamic) contraction hierarchies.
• Michael Hamann and Ben Strasser. Graph bisection with pareto-optimization. In Proceedings of the 18th Meeting on Algorithm Engineering and Experiments (ALENEX’16). SIAM, 2016.
  Separating a graph into two pieces along a small separator. Very effective for separator based speed-up techniques.
• Moritz Kobitzsch. HiDAR: An alternative approach to alternative routes. In Proceedings of the 21st Annual European Symposium on Algorithms (ESA’13), volume 8125 of Lecture Notes in Computer Science, pages 613–624. Springer, 2013.
  Shows that unpacking the search space of a contraction hierarchy query allows fast, high quality computation of via-node based alternative routes.
• Moritz Kobitzsch, Marcel Radermacher, and Dennis Schieferdecker. Evolution and evaluation of the penalty method for alternative graphs. In Proceedings of the 13th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS’13), OpenAccess Series in Informatics (OASIcs), pages 94–107, 2013.
  Shows that the penalty approach to finding alternative routes can be made fast.
• S. Kontogiannis, G. Michalopoulos, G. Papastavrou, A. Paraskevopoulos, D. Wagner, and C. Zaroliagis. Engineering oracles for time-dependent road networks. In ALENEX, 2016.
• S. Kontogiannis, G. Michalopoulos, G. Papastavrou, A. Paraskevopoulos, D. Wagner, and C. Zaroliagis. Analysis and experimental evaluation of time-dependent distance oracles. In ALENEX, pages 147–158, 2015.
  Experimental evaluation of distance oracles for efficient time-dependent routing.
• Dennis Luxen and Dennis Schieferdecker. Candidate sets for alternative routes in road networks. ACM Journal of Experimental Algorithmics, 2013.
  General technique for accelerating computation of via-node alternative routes using preprocessing.
• Peter Sanders and Lawrence Mandow. Parallel label-setting multi-objective shortest path search. In 27th International Parallel and Distributed Processing Symposium (IPDPS’13), pages 215–224. IEEE Computer Society, 2013.
  Shows that the additional complexity of adding multiple objectives to the shortest path problem can be ”parallelized away”.
• Peter Sanders and Christian Schulz, High Quality Graph Partitioning. In DIMACS Implementation Challenge – Graph Partitioning and Graph Clustering, 2013.
  Describes our graph partitioning tool KaHiP and gives extensive benchmark results showing that KaHiP yields the best known results for many instances.
• Peter Sanders and Christian Schulz. Think locally, act globally: Highly balanced graph partitioning. In Proceedings of the 12th International Symposium on Experimental Algorithms (SEA’13), volume 7933 of Lecture Notes in Computer Science, pages 164–175. Springer, 2013.
• Niklas Schnelle, Stefan Funke, and Sabine Storandt. DORC: distributed online route computation - higher throughput, more privacy. In 2013 IEEE International Conference on Pervasive Computing and Communications Workshops, pages 344–347, July 2013.
• Sabine Storandt. Contraction hierarchies on grid graphs. In Proceedings of the 36rd Annual German Conference on Advances in Artificial Intelligence, Lecture Notes in Computer Science, pages 236–247. Springer, 2013.
• Ben Strasser, Adi Botea, and Daniel Harabor. Compressing optimal paths with run length encoding. Journal of Artificial Intelligence Research, 2015.
  Preprocessing-based technique to very efficiently compute the first edge of a shortest path.
• Ben Strasser, Daniel Harabor, and Adi Botea. Fast first-move queries through run-length encoding. In Proceedings of the 5th International Symposium on Combinatorial Search (SoCS’14). AAAI Press, July 2014.
• Ben Strasser and Dorothea Wagner. Connection scan accelerated. In Proceedings of the 16th Meeting on Algorithm Engineering and Experiments (ALENEX’14), pages 125–137. SIAM, 2014.
  A multi-level extension of CSA to efficiently compute routes in large public transit networks.
• Nathan Sturtevant, Jason Traish, James Tulip, Tansel Uras, Sven Koenig, Ben Strasser, Adi Botea, Daniel Harabor, and Steve Rabin. The grid-based path planning competition: 2014 entries and results. In Proceedings of the 6th International Symposium on Combinatorial Search (SoCS’15). AAAI Press, June 2015.
• Sascha Witt. Trip-based public transit routing. In ESA, pages 1025–1036, 2015.
  A new technique to plan routes in public transportation networks where trips of a vehicle with multiple stops are treated like a node in a network.

• Google
• Group of Prof. Sanders
• Group of Prof. Bast