HackerPapers

arXiv:1504.05140cs.DS

Route Planning in Transportation Networks

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.

arXiv comments
This is an updated version of the technical report MSR-TR-2014-4, previously published by Microsoft Research. This work was mostly done while the authors Daniel Delling, Andrew Goldberg, and Renato F. Werneck were at Microsoft Research Silicon Valley
Journal reference
DOI
Subjects
cs.DSData Structures and Algorithms

On Hacker News

Linked by 7 identifiable commenters in 8 comments across 7 threads, from Apr 2015 to Mar 2024. Found in 2 HN submissions from Apr 2016 to Oct 2024. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments7 threads

  1. Hexagons and Hilbert curves – The headaches of distributed spatial indices 1 comment

    • 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…

      joe_the_userView on HNParent context

  2. A* tricks for videogame path finding 2 comments

    • 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…

      amitpView on HNParent context

    • 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…

      payasrView on HNParent context

  3. New pathfinding algorithm 1 comment

    • 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…

      payasrView on HNParent context

  4. B-Heap vs. Binary Heap (2010) 1 comment

    • 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 :)

      lorenzhsView on HNParent context

  5. JPS+: Over 100x Faster than A* (2015) [video] 1 comment

    • 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…

      karussellView on HNParent context

  6. Show HN: Dijkstra’s algorithm in the web browser with OpenStreetMap 1 comment

    • 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…

      danpatView on HNParent context

  7. On Dijkstra's Algorithm 1 comment

    • Route Planning in Transportation Networks http://arxiv.org/abs/1504.05140 Shortest-Path Queries in Static Networks http://www.sommer.jp/spq-survey.pdf

      csomView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.