Hannah Bast, Daniel Delling, Andrew Goldberg
Matthias Müller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, Renato F. Werneck
2015 · arXiv
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.
Metadata: arXiv. Abstracts retain their original authors’ rights.
Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels
7 selected excerpts · 7 total mentions
The problem of finding the shortest path on a map (a la google maps etc) is often solved with approaches like "hub networks" and "contraction hierarchies" rather than simple spatial networks. Things like dijkstra's algorithm are only efficient if you're input is the raw graph and point and you only want one path once. See just for a start: https://arxiv.org/abs/1504.05140
Those seem a little outdated, there has been a ton of work since then :) A bit more updated reference is https://arxiv.org/pdf/1504.05140.pdf, and http://www.sommer.jp/spq-survey.pdf is great! There are also Prof. Hannah Bast's lectures (https://ad-wiki.informatik.uni-freiburg.de/teaching/Efficien...) and her talk at ICAPS (https://www.youtube.com/watch?v=B3wKfJAVRkg), both excellent :)
There are lots of variants of A* that depend on what you can assume about your graph, whether you can preprocess, how often the graph changes, etc. Contraction hierarchies, subgoals, bidirectional A*, hierarchical search, all-pairs compression, moving obstacles, group movement, coordinated movement, landmarks, labeling algorithms, transit nodes, arc flags, cluster distances, vertex separators, reach, highway hiearchies, etc. Differential heuristics are my favorite for "bang for the buck", as they are fairly low effort (maybe <20 lines of code) for good speedup (3-5X on my game map tests [1]). There's lots of research papers out there, especially for road maps. I tried keeping track of them all and gave up :-( But you might find these two papers useful: * https://arxiv.org/pdf/1504.05140.pdf * https://i11www.iti.kit.edu/extra/publications/dssw-erpa-09.p... [1] https://www.redblobgames.com/pathfinding/heuristics/differen...
There’s a great recent-ish survey paper at https://arxiv.org/pdf/1504.05140.pdf which will give you pointers to papers in all directions :)
Contraction Hierarchy (CH) is also at least 100x faster as A* . CH has nice properties of having good memory efficiency, optimality, any graph etc. And I am very sure JPS is not that generic applicable like CH. Still all 'fast' routing algorithms have their own drawbacks of engineering complexity, pre-processing time and memory requirements, potential lack for time dependent support etc. If you want to have the best summary of routing algorithms currently available then read 'Route Planning in Transportation Networks' (2014) https://arxiv.org/abs/1504.05140 And if you want fast implementations for routing algorithms like Dijkstra, A*, CH and Landmarks check out GraphHopper: https://github.com/graphhopper/graphhopper (note: I'm one of the founders)
I'm one of the OSRM devs. To expand on this comment a bit - OSRM still uses Dijkstra, so if you understand that, you already basically understand what OSRM does. What OSRM does in order to speed things up is optimize the graph structure - we still use Dijkstra, but the search completes in a handful of steps, rather than hundreds of thousands. There are quite a few techniques like this. OSRM implements an approach called Contraction Hierarchies. We scan over the graph, inserting "shortcuts" that skip over nodes. As long as you follow a few basic rules, you can repeatably insert shortcuts all over the graph. This gives you a routing graph that is equivalent, but a Dijkstra…
search will typically complete in a handful of iterations. We hope one day to implement several other speedup techniques - each has advantages/disadvantages, depending on what you want to do. Contraction Hierarchies lead to very fast queries (~5ms for a cross-the-US route), but the pre-processing time is very long (~6hrs on a beefy machine for the OSM planet). Any updates to the graph require complete re-processing (new/removed roads, adjusted road speeds, etc). Other techniques compromise search performance for a bit more flexibility - faster update times, query customization (i.e. "avoid highways"). It's a really fascinating corner of CS theory to work in, I really enjoy it :-) This paper: https://arxiv.org/pdf/1504.05140.pdf "Route Planning in Transportation Networks" gives an excellent overview of current search speedup techniques. It's a bit hefty, but if you're interested in knowing what's the state of the art, this is a good place to start.
There's a _lot_ of work on hierarchical route planning in games. I don't mean to put down the developers or anything, and I'm so glad all of this works, but there are plenty of ideas in the academic-world that I think developers should know more about. Botea, Adi, Martin Müller, and Jonathan Schaeffer. 2004. “Near Optimal Hierarchical Path-Finding.” In Journal of Game Development. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.112..... Rahmani, Vahid, and Nuria Pelechano. 2017. “Improvements to Hierarchical Pathfinding for Navigation Meshes.” In Proceedings of the Tenth International Conference on Motion in Games, 8:1–8:6. MIG ’17. New York, NY, USA: ACM. Toll,…
Wouter van, Roy Triesscheijn, Marcelo Kallmann, Ramon Oliva, Nuria Pelechano, Julien Pettré, and Roland Geraerts. 2016. “A Comparative Study of Navigation Meshes.” In Proceedings of the 9th International Conference on Motion in Games, 91–100. ACM. And route planning in graphs (with static edge weights) has been studied to death. https://arxiv.org/pdf/1504.05140.pdf
More from the same topics.
Tim Kraska, Alex Beutel, Ed H. Chi +2
Indexes are models: a B-Tree-Index can be seen as a model to map a key to the position of a record within a sorted array, a Hash-Index as a model to map a key to a position of a record within an unsorted array, and a BitMap-Index as a model to indicate if a data record exists or not.
Martin Kleppmann
The CAP Theorem is a frequently cited impossibility result in distributed systems, especially among NoSQL distributed databases.
Haoran Xu, Fredrik Kjolstad
Fast compilation is important when compilation occurs at runtime, such as query compilers in modern database systems and WebAssembly virtual machines in modern browsers.
David Manheim, Scott Garrabrant
There are several distinct failure modes for overoptimization of systems on the basis of metrics.