The DOI matches its Crossref record; 258 of the 263 references it cites were found in a registry or an index.
Route Planning in Transportation Networks
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.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“Graph-based local planners use the same techniques as graph-based global planners such as Dijkstra [254] and A* [249], which output discrete paths rather than continuous ones.This can lead to jerky trajectories [19].”
From A Survey of Autonomous Driving: Common Practices and Emerging Technologies (2020) · cites this paper as [249]
In the citing paper
“A* search [249] is a standard goal-directed path planning algorithm and used extensively in various fields for almost 50 years.”
From A Survey of Autonomous Driving: Common Practices and Emerging Technologies (2020) · cites this paper as [249]
Citations
Cites
A note on two problems in connexion with graphs
Dijkstra, E. W. (1959) · Numerische Mathematik · doi:10.1007/bf01386390 · Cited by 29,065
A Formal Basis for the Heuristic Determination of Minimum Cost Paths
Hart, P., Nilsson, N., & Raphael, B. (1968) · IEEE Transactions on Systems Science and Cybernetics · doi:10.1109/tssc.1968.300136 · Cited by 12,738
Linear Programming and Extensions
Dantzig, G. (1963) · RAND Corporation eBooks · doi:10.7249/r366 · Cited by 5,755
Floyd, R. W. (1962) · Communications of the ACM · doi:10.1145/367766.368168 · Cited by 3,998
Fibonacci heaps and their uses in improved network optimization algorithms
Fredman, M. L., & Tarjan, R. E. (1987) · Journal of the ACM · doi:10.1145/28869.28874 · Cited by 3,132
Bellman, R. (1958) · Quarterly of Applied Mathematics · doi:10.1090/qam/102435 · Cited by 2,758
Zadeh, L. A. (1988) · Computer · doi:10.1109/2.53 · Cited by 1,824
A Separator Theorem for Planar Graphs
Lipton, R. J., & Tarjan, R. E. (1979) · SIAM Journal on Applied Mathematics · doi:10.1137/0136016 · Cited by 1,359
The shortest path through a maze
Moore, E. (1959) · Medical Entomology and Zoology · Cited by 1,236
An Appraisal of Some Shortest-Path Algorithms
Dreyfus, S. E. (1969) · Operations Research · doi:10.1287/opre.17.3.395 · Cited by 1,002
Research works printed but not linked: 13
- Bauer, A.: Multimodal profile queries. Bachelor thesis, Karlsruhe Institute of Technology, May 2012
- Baumann, N., Schmidt, R.: Buxtehude-Garmisch in 6 Sekunden. die elektronische Fahrplanauskunft (EFA) der Deutschen Bundesbahn. Zeitschrift für aktuelle Verkehrsfragen 10, 929–931 (1988)
- Cambridge Vehicle Information Technology Ltd. Choice routing (2005). http://www.camvit.com
- Geisberger, R.: Advanced route planning in transportation networks. Ph.D. thesis, Karlsruhe Institute of Technology, February 2011
- Goldberg, A.V., Werneck, R.F.: Computing point-to-point shortest paths from external memory. In: Proceedings of the 7th Workshop on Algorithm Engineering and Experiments (ALENEX 2005), pp. 26–40. SIAM (2005)
- Kaufmann, H.: Towards mobile time-dependent route planning. Bachelor thesis, Karlsruhe Institute of Technology (2013)
- Mehlhorn, K., Sanders, P., Algorithms, D.S.: The Basic Toolbox. Springer, Heidelberg (2008)
- Mellouli, T., Suhl, L.: Passenger online routing in dynamic networks. In: Mattfeld, D.C., Suhl, L. (eds.) Informations probleme in Transport und Verkehr, vol. 4, pp. 17–30. DS&OR Lab, Universität Paderborn (2006)
- Meyer, U.: Single-source shortest-paths on arbitrary directed graphs in linear average-case time. In: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2001), pp. 797–806 (2001)
- Pajor, T.: Multi-modal route planning. Master’s thesis, Universität Karlsruhe (TH), March 2009
- Pohl, I.: Bi-directional search. In: Proceedings of the Sixth Annual Machine Intelligence Workshop, vol. 6, pp. 124–140. Edinburgh University Press (1971)
- Sankaranarayanan, J., Samet, H.: Roads belong in databases. IEEE Data Eng. Bull. 33(2), 4–11 (2010)
- Theune, D.: Robuste und effiziente Methoden zur Lösung von Wegproblemen. Ph.D. thesis, Universität Paderborn (1995)
Cited by
A Survey of Motion Planning and Control Techniques for Self-Driving Urban Vehicles
Paden, B., Cap, M., Yong, S. Z., Yershov, D., & Frazzoli, E. (2016) · IEEE Transactions on Intelligent Vehicles · doi:10.1109/tiv.2016.2578706 · Cited by 2,585
A Survey of Autonomous Driving: Common Practices and Emerging Technologies
Yurtsever, E., Lambert, J., Carballo, A., & Takeda, K. (2020) · IEEE Access · doi:10.1109/access.2020.2983149 · Cited by 1,889
“HL is the fastest query time algorithm for route planning [244], in the expense of high storage usage.”
BackgroundMethodPerception, Planning, Control, and Coordination for Autonomous Vehicles
Pendleton, S., Andersen, H., Du, X., Shen, X., Meghjani, M., Eng, Y., Rus, D., & Ang, M. (2017) · Machines · doi:10.3390/machines5010006 · Cited by 657
Survey of Deep Reinforcement Learning for Motion Planning of Autonomous Vehicles
Aradi, S. (2022) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2020.3024655 · Cited by 639
Computing Systems for Autonomous Driving: State of the Art and Challenges
Liu, L., Lu, S., Zhong, R., Wu, B., Yao, Y., Zhang, Q., & Shi, W. (2021) · IEEE Internet of Things Journal · doi:10.1109/jiot.2020.3043716 · Cited by 450
Metadata
- Authors
- Bast, H., Delling, D., Goldberg, A., Müller-Hannemann, M., Pajor, T., Sanders, P., Wagner, D., & Werneck, R. F.
- Affiliations
- University of Freiburg (DE)
- Apple (United States) (US)
- Amazon (United States) (US)
- Microsoft (United States) (US)
- Karlsruhe Institute of Technology (DE)
- Corresponding author
- Pajor, Thomas
- Venue
- Lecture Notes in Computer Science
- Publisher
- Springer International Publishing
- Published
- 2016
- Pages
- 19-80
- ISSN
- 0302-9743 (ISSN-L)
- 1611-3349
- OpenAlex
- W2104317982
- Semantic Scholar
- 0bf0554b1dcf9619aa6d6048b1512c21efb5fc49
- Cited by
- 610
- References
- 263
- Citations by year
- 2026: 30 · 2025: 32 · 2024: 47 · 2023: 40 · 2022: 50 · 2021: 88 · 2020: 69 · 2019: 83 · 2018: 50 · 2017: 53 · 2016: 31
- FWCI
- 106.82
- Type
- conference paper
- Language
- en
- Open access
- closed
- Locations
- Lecture notes in computer science (publishedVersion)
- Topics
- Social Sciences › Transportation › Transportation Planning and Optimization
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Physical Sciences › Computer Science › Information Systems › Data Management and Algorithms
- Keywords
- route planning, transportation networks, road network, driving directions, real-time traffic, public transport, journey planning, multimodal route planning, approximate algorithms
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Route Planning in Transportation Networks. https://app.cochat.ai/papers/10.1007/978-3-319-49487-6_2
- The paper
- Bast, H., Delling, D., Goldberg, A., Müller-Hannemann, M., Pajor, T., Sanders, P., Wagner, D., & Werneck, R. F. (2016). Route Planning in Transportation Networks. Lecture Notes in Computer Science. https://doi.org/10.1007/978-3-319-49487-6_2
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.