Google Focused Research Award on Next-Generation Route Planning
The goal of this project was to bring the state of the art on route planning on road and transit networks to the next level. We identified three critical dimensions: scalability, result diversity, and real-time updates. We achieved major improvements along all three of these. Perhaps most notably are our scalability improvements by several orders of magnitude and the incorporation of real-time updates for the state-of-the-art algorithms for both road and transit networks.
We here provide a brief account encompassing the whole project (2012 - 2015): a short history of the developments that led to the project, a list of all the people involved, a succinct summary of the main achievements, and a list of publications directly related to the project, each with a one-sentence summary.
History prior to the project
The three principal investigators were critically involved in the state of the art on route planning systems already prior to the start of the project. Hannah Bast (University of Freiburg) developed Transfer Patterns, the method at work behind Google's transit direction service, during a one-year stay at Google as visiting resarcher. The group of Peter Sanders (Karlsruhe Institute of Technology = KIT) has developed Contraction Hierarchies, state of the art and widely used for routing on road networks. The group of Dorothea Wagner (also KIT) has pioneered fundamental graph models and speedup techniques in both road and transit networks for over a decade.
Contributors and interaction with Google
Google supported this project with a three-year Focused Research Award. The following three (post-)doctoral students were paid by the funding from this award: Sabine Storandt (postdoc in Hannah Bast's group), Ben Strasser (doctoral student in Dorothea Wagner's group), Sascha Witt (doctoral student in Peter Sanders' group).
 |  | |
| Prof. Dr. Hannah Bast University of Freiburg | Prof. Dr. Peter Sanders Karlsruhe Institute of Technology | Prof. Dr. Dorothea Wagner, Karlsruhe Institute of Technology |
 |  |  |
| Dr. Sabine Storandt University of Freiburg | Sascha Witt, Karlsruhe Institute of Technology | Ben Strasser, Karlsruhe Institute of Technology |
In addition, several other (mostly doctoral) students from the three groups contributed to the project, and appear as co-authors on the various publications: Thomas Pajor, Jonas Sternisko, Mirko Brodesser, Julian Dibbelt, Moritz Baum, Andreas Gemsa, Moritz Kobitzsch, Dennis Schieferdecker, Dennis Luxen, Patrick Brosi, Julian Arz, Stephan Erb, Tobias Zündorf, Matthias Hertel, Valentin Buchhold.
The project was accompanied by a fruitful interaction with Google. We continuously informed each other about recent developments and plans. Four large, joint meetings were held: a kick-off meeting in Karlsruhe (September 2012), two progress meetings in Freiburg (January 2013 and February 2014), and a final meeting in Zürich (September 2015). In addition, several meetings in smaller circles, focusing on particular sub-tasks, took place in Karlsruhe, Freiburg, and Zürich.
Achievements: Scalability
A central goal of the project was scalability. At the beginning of the project, the state of the art on routing on road networks was already very advanced. In particular, there were algorithms with fast query times (milliseconds), small precomputation times (minutes) and moderate space requirement (< 1 GB) for continent-scale networks. Transit routing was lagging behind considerably in all three aspects. Over the course of the project, we successfully addressed all three of them.
An important building block were new algorithms for vastly improved one-to-one and one-to-all searches on transit networks [24, 8, 39, 40, 19]. These are interesting in their own right and they alone improve the (very resource-critical) precomputation of the original Transfer Patterns algorithm by a factor of 60. Eventually, we also solved the long-standing open problem of making proper use of "hierarchy" in transit networks, using Transfer Patterns [9]. All the advances combined result in an over 1000 times faster precomputation, over 10 times less space consumption, and 100% exact results, as compared to the original implementation .
We also pushed the boundary in routing on road networks. We reconquered the record for the currently fastest algorithm [1] and made progress on the inherently hard parallelization of the query processing [35, 26]. Our graph partitioners [36, 17, 29] yield best or near best quality in many benchmarks including road networks. This helps accelerating many speed-up techniques for route planning including distributed memory contraction hierarchies.
Achievements: Diversity and Multi-Modality
Users want diverse results, both for road networks (alternate routes) and transit networks (at different times, minimal number of transfers, minimal travel time, etc.). For alternate routes, we developed several new schemes and analyses based on the widely used Contraction Hierarchies [31, 30].
Users also want multi-modal results = routes for the various modes of transportation (car, transit, walking, bicycle, flights) not only in isolation, but also in combination wherever meaningful. However, the number of potentially relevant solutions then quickly reaches into the hundreds or even thousands. Our research has shown an unexpected negative result: that there is no canonical model to select a representative sample, but a strong dependence on personal preference. Instead, we developed several pragmatic approaches [3, 18, 25].
We also developed guidebook routing [7], a time-independent result summary over a larger time span, for example: take Tram 8 to Zürich HB, from there take the Tram 13, from 8am - 10pm, every 8 minutes. Google Maps has launched its version of guidebook routing in May 2013.
Real-time updates
Users want results that take the current traffic situation into account (traffic jams, train delays or cancelations, road or railway closures). We investigated both Contraction Hierarchies and Transfer Patterens in this respect.
We showed that the precomputation for Contraction Hierarchies can be turned into a two-phased (so-called "customizable") scheme that is ideal for real-time updates [20]. In the first phase, a metric-independent overlay graph is constructed. In the second phase, the resulting graph gets "coated" with a metric (e.g. travel times). This precomputation enables query times of a few milliseconds, and if the travel times change, only the second phase has to be redone, which is matter of seconds. This result was inspired by the theoretical study from [15] described below.
We showed a similar result for Transfer Patterns [6]. The precomputation has two phases by design: the precomputation of all transfer patterns between all pairs of stations and the precomputation of all direct connections. We showed that even for large and wide-spread delays, a re-computation of the direct connections (which can be done in a matter of seconds) preserves over 99% of all optimal connections. We also investigated the related task of finding journeys that are robust against typical delays in the first place [22].
Theoretical results
Most of the work done in this project is practically directly relevant. We also worked on various theoretical problems that informed some of these practical results or provided additional insights. Most notably, we proved bounds on the search space size of Contraction Hierarchies using nested dissection [15]; this enabled the customized scheme described above. We also showed how to adapt Contraction Hierarchies for multiple objectives [27]. Concerning the limits of known approaches, we proved the NP-hardness of: time-dependent routing for anything more general than travel-time [13], graph partitioning for arc flags [14], minimizing the size of a space-efficient oracle to very quickly identify the first arc on a shortest path [16].
Publications
[1] J. Arz, D. Luxen, and P. Sanders. Transit node routing reconsidered. In SEA, pages 55-66, 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.
[2] S. Andreev, J. Dibbelt, M. Nöllenburg, T. Pajor, D. Wagner. Towards realistic pedestrian route planning. In ATMOS, pages 1-15, 2015.
Integrating special requirements for pedestrian routing.
[3] H. Bast, M. Brodesser, and S. Storandt. Result diversity for multi-modal route planning. In ATMOS, 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.
[4] H. Bast, P. Brosi, and S. 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.
[5] H. Bast, D. Delling, A. V. Goldberg, M. Müller-Hannemann, T. Pajor, P. Sanders, D. Wagner, and R. 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.
[6] H. Bast, J. Sternisko, and S. Storandt. Delay-robustness of transfer patterns in public transportation route planning. In ATMOS, 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.
[7] H. Bast and S. Storandt. Flow-based guidebook routing. In ALENEX, pages 155-165, 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).
[8] H. Bast and S. 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.
[9] H. Bast, M. Hertel and S. Storandt. Scalable Transfer Patterns. In ALENEX, to appear, 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.
[10] G. Batz, R. Geisberger, D. Luxen, P. Sanders, and R. Zubkov. Efficient route compression for hybrid route planning. In MedAlg, pages 93-107, 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.
[11] 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.
[12] G. Batz, R. Geisberger, P. Sanders, and C. Vetter. Minimum time-dependent travel times with contraction hierarchies. In JEA, 18, 2013.
Journal paper on time-dependent contraction hierarchies.
[13] G. Batz and P. Sanders. Time-Dependent Route Planning with Generalized Objective Functions. In ESA, pages 169-180, 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.
[14] R. Bauer, M. Baum, I. Rutter, and D. Wagner. On the complexity of partitioning graphs for arc-flags. In JGAA, 17(3):265-299, 2013.
Theoretical proof that Arc-Flags preprocessing is (NP-)hard.
[15] R. Bauer, T. Columbus, I. Rutter, and D. Wagner. Search-space size in contraction hierarchies. In ICALP, pages 93-104, 2013.
Theoretical analysis of contraction hierarchies based on nested dissection.
[16] A. Botea, B. Strasser, D. Harabor. Complexity results for compressing optimal paths. In AAAI, pages 1100-1106, 2015.
Hardness proof for [37] and decomposition result for articulation points.
[17] 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.
[18] D. Delling, J. Dibbelt, T. Pajor, D. Wagner, and R. F. Werneck. Computing multimodal journeys in practice. In SEA, pages 260-271, 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.
[19] D. Delling, J. Dibbelt, T. Pajor, R. Werneck. Public transit labeling. In SEA, pages 273-285, 2015.
Hub-Labeling combined with public transit routing.
[20] J. Dibbelt, B. Strasser, and D. Wagner. Customizable contraction hierarchies. In SEA, pages 271-282, 2014.
Conference version and subset of the following paper.
[21] J. Dibbelt, B. Strasser, D. Wagner. Customizable contraction hierarchies. In JEA, 2015.
Engineering contraction hierarchies using a nested-dissection based order.
[22] J. Dibbelt, B. Strasser, D. Wagner. Delay-robust journeys in timetable networks with minimum expected arrival time. In ATMOS, pages 1-14, 2014.
Efficiently computing routes in public transit with backup routes. For a demo, see http://meatdemo.iti.kit.edu .
[23] J. Dibbelt, B. Strasser, D. Wagner. Fast exact shortest path and distance queries on road networks with parametrized costs. In SIGSPATIAL , 2015.
Reasonably fast routing with very flexible arc costs.
[24] J. Dibbelt, T. Pajor, B. Strasser, and D. Wagner. Intriguingly simple and fast transit routing. In SEA, pages 43-54, 2013.
Fast algorithm to compute routes in public transit networks.
[25] J. Dibbelt, T. Pajor, D. Wagner. User-constrained multi-modal route planning. In JEA 19, 2015.
Routing in a multimodal setting with restricted transfer possibilities between modes.
[26] S. Erb, M. Kobitzsch, P. Sanders. Parallel Bi-Objective Shortest Paths using Weight-Balanced B-Trees with Bulk Updates. In SEA, 2014.
Shows that the parallel bicriteria shortest path algorithm from Sanders and Mandow (see below) can be implemented in time comparable to that of a sequential single-criteria implementation.
[27] S. Funke and S. 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.
[28] R. Geisberger, P. Sanders, D. Schultes, and C. Vetter. Exact routing in large road networks using contraction hierarchies.Transportation Science, 46(3):388-404, 2012.
Journal paper on (dynamic) contraction hierarchies.
[29] M. Hamann, B. Strasser. Graph bisection with pareto-optimization. In ALENEX, 2016.
Separating a graph into two pieces along a small separator. Very effective for separator based speed-up techniques.
[30] M. Kobitzsch. An alternative approach to alternative routes: HiDAR. In ESA, pages 613-624, 2013.
Shows that unpacking the search space of a contraction hierarchy query allows fast, high quality computation of via-node based alternative routes.
[31] M. Kobitzsch, M. Radermacher, and D. Schieferdecker. Evolution and evaluation of the penalty method for alternative graphs. In ATMOS, pages 94-107, 2013.
Shows that the penalty approach to finding alternative routes can be made fast.
[34] D. Luxen, D. Schieferdecker. Candidate sets for alternative routes in road networks. In JEA, 19, 2015.
General technique for accelerating computation of via-node alternative routes using preprocessing
[35] P. Sanders and L. Mandow. Parallel label-setting multi-objective shortest path search. In IPDPS, pages 215-224, 2013.
Shows that the additional complexity of adding multiple objectives to the shortest path problem can be "parallelized away"; an implementation is provided in Erb et al (see above).
[36] P. Sanders and C. 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.
[37] B. Strasser, A. Botea, D. Harabor. Compressing optimal paths with run length encoding. In JAIR, 2015.
Preprocessing-based technique to very efficiently compute the first edge of a shortest path.
[38] B. Strasser, D. Harabor, A. Botea. Fast first-move queries through run-length encoding. In SoCS, 2014.
Subset and conference version of the previous article.
[39] B. Strasser and D. Wagner. Connection scan accelerated. In ALENEX, pages 125-137, 2014.
A multi-level extension of Connection Scan Accelerated (see above) to efficiently compute routes in large public transit networks.
[40] S. Witt. Trip-based public transit routing. In ESA, pages 1025-1036, 2015.
Best student paper award for a new technique to route planning in public transportation networks where trips of a vehicle with multiple stops are treated like a node in a network.