The DOI matches its DataCite record; 238 of the 238 references it cites were found in a registry or an index; none of the 176 sources its claims cite is checked for support yet.
Route Planning in Transportation Networks
Open accessAbstract
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
CoChat Summary
TL;DR
This survey reviews practical route-planning algorithms for road networks, schedule-based public transit, and multimodal transportation, emphasizing trade-offs among preprocessing, space, and query time. It reports that continental-scale road queries can be answered in milliseconds or less, while public transit and multimodal planning remain harder because of time-dependence, multicriteria objectives, and weaker preprocessing speedups.
Key findings
- Road networks: on Western Europe (18.0M vertices, 42.5M directed arcs), Table 1 reports average query times from 2,195,080 µs for Dijkstra and 1,205,660 µs for bidirectional Dijkstra down to 110 µs for CH, 5.76 µs for CHASE, 0.56 µs for HL, 0.25 µs for HL-∞, and 0.06 µs for table lookup; no single technique dominates, and all current state-of-the-art algorithms find provably exact solutions.
- Public transit: on London (≈21k stops, 2.2k routes, 133k trips, 46k footpaths, 5.1M elementary connections/day), CSA answers earliest-arrival queries in 2.0 ms and RAPTOR in 5.4 ms; Transfer Patterns on Germany (90.4M connections, 7 days) answers in 0.4 ms. For multicriteria queries, RAPTOR is about an order of magnitude faster than Dijkstra-based LD/MLS and twice as fast as TDD while computing twice as many journeys on average; Transfer Patterns has the fastest queries overall by more than an order of magnitude.
- Multimodal: Access-Node Routing on intercontinental multimodal networks runs queries in milliseconds; SDALT reports speedups close to 30 on Île-de-France; UCCH has query performance comparable to Access-Node Routing with significantly less preprocessing time and space.
- Theory: for graphs with highway dimension h and diameter D, after adding O(h log h log D) shortcuts, Reach and CH run in O((h log h log D)^2), HL in O(h log h log D), and long-range TNR queries in O(h^2).
Methods
- Design: a survey of practical algorithms for route planning in transportation networks, covering static shortest paths, road-network speedup techniques, public-transit journey planning, and multimodal journey planning; it includes experimental comparisons and theoretical results.
- Data/sample: benchmark road network of Western Europe (18.0M vertices, 42.5M directed arcs); London transit network (≈21k stops, 2.2k routes, 133k trips, 46k footpaths, 5.1M elementary connections for one day); Germany transit instances (46.2M and 90.4M connections); long-distance European train network (1.7M connections, periodic).
- Main analysis: compares algorithms by preprocessing time, space, query time, scanned vertices, Dijkstra ranks, and Pareto sets; reports results in tables/figures and discusses exactness, trade-offs, and real-world deployment.
Limitations
- Stated: there is no “best” solution; methods must be evaluated by different measures and trade off query time, preprocessing effort, space usage, and robustness to input changes. Public-transit speedups are several orders of magnitude lower than in road networks, and multimodal planning is significantly harder, relying on approximate solutions even for metropolitan inputs; a worldwide multimodal journey planner has not been reached.
- Stated: experimental comparisons are limited because most studies use the simplified model ignoring turn restrictions/penalties, realistic country-scale benchmark data have not been widely available, and research groups often interpret data differently, making comparisons hard. Some methods were evaluated only on undirected graphs (PHL) or grid graphs (HiTi); a TNR grid-based preprocessing flaw is noted.
- Evident from the text: many reported numbers are scaled across different machines or reproduced from original publications, and some algorithms lack published results for certain query types (e.g., TNR+AF Dijkstra-rank results); CH performance degrades under realistic constraints, HL uses significantly more space, and TNR local queries are slower.
Model-written summary. Check it against the paper before relying on it.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
0 Valid · 20 Not valid · 130 Not checked · 115 Own results and interpretations
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Public transit systems have a time-dependent component, so we must consider multiple criteria for meaningful results, and known preprocessing techniques are not nearly as effective.”
§ Route Planning in Transportation Networks * > 1 Introduction
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Rests on an assumption not shown here.
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“During a query, if the target vertex t is not in L(a), the search can safely be pruned at a.”
§ Route Planning in Transportation Networks * > Geometric Containers.
plainstates a cause- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“In practice, even when minimizing travel distances in road networks, A* with geographical distance bound performs poorly compared to other modern methods.”
§ Route Planning in Transportation Networks * > A* Search.
plainstates a cause- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: unclear — It is unclear whether the paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“as long as the potential function is feasible (i.e., if ℓ(v, w)π(v) + π(w) ≥ 0 for (v, w) ∈ E), an s-t query can stop with the correct answer as soon as it is about to scan the target vertex t.”
§ Route Planning in Transportation Networks * > A* Search.
plainstates a cause- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: unclear — It is unclear whether the paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
In the paper
“While the recent PHAST algorithm [75] has made precomputing all-pairs shortest paths feasible, storing all Θ(|V | 2 ) distances is prohibitive already for medium-sized road networks.”
§ Route Planning in Transportation Networks * > 2.5 Bounded-Hop Techniques
What the sources say
- Not matchedcites [75]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
plainstates a cause- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Not matched
103 more claims
Create a free account to see all 265 claims and every source verdict.
- Probably not a substantial claim. 100
- It may state two separate claims as one. 79
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
Each contradiction between two passages listed here was confirmed by an independent check.
Rated minor: it would not touch a result — a value no result rests on, a p-value that stays on the same side of the significance level, or a conflict that is clerical, resolved elsewhere in the paper, or outside its own findings.
In the paper
§ Route Planning in Transportation Networks * > 4.5 Experiments and Comparison
“Thanks to preprocessing, Transfer Patterns has the fastest Table 3.”
§ Route Planning in Transportation Networks * > 4.5 Experiments and Comparison
“CH [136] Europe (lng) 1.7 p • • • • • < 0.1 < 0.1 n/a 0.3 CSA [105] London 4.9 1 • • • • • -26.6 n/a 2.0 ACSA [242] Germany 46.2 2 • • • • • -n/a n/a 8.7 T. Patterns [27] Germany 90.4 7 • • • • • 541 -1.0 0.4”
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
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
Linear Programming and Extensions
Dantzig, G. (1963) · Princeton University Press eBooks · doi:10.1515/9781400884179 · Cited by 2,713
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: 20
- Andreas Bauer. Multimodal profile queries. Bachelor thesis, Karlsruhe Institute of Technology, May 2012.
- Cambridge Vehicle Information Technology Ltd. Choice routing, 2005. Available at http: //www.camvit.com.
- Alessio Cionini, Gianlorenzo D'Angelo, Mattia D'Emidio, Daniele Frigioni, Kalliopi Gian- nakopoulou, and Andreas Paraskevopoulos. Engineering graph-based models for dynamic timetable information systems. In Proceedings of the 14th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'14), OpenAccess Series in Informatics (OASIcs), pages 46-61, 2014.
- Brian C. Dean. Continuous-time dynamic shortest path algorithms. Master's thesis, Mas- sachusetts Institute of Technology, 1999.
- Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck. Faster batched shortest paths in road networks. In Proceedings of the 11th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'11), volume 20 of OpenAccess Series in Informatics (OASIcs), pages 52-63, 2011.
- Daniel Delling, Peter Sanders, Dominik Schultes, and Dorothea Wagner. Highway hierarchies star. In The Shortest Path Problem: Ninth DIMACS Implementation Challenge, volume 74 of DIMACS Book, pages 141-174. American Mathematical Society, 2009.
- Stefan Funke, André Nusser, and Sabine Storandt. Placement of loading stations for electric vehicles: No detours necessary! In Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence. AAAI Press, 2014.
- Andrew V. Goldberg and Renato F. Werneck. Computing point-to-point shortest paths from external memory. In Proceedings of the 7th Workshop on Algorithm Engineering and Experiments (ALENEX'05), pages 26-40. SIAM, 2005.
- Morgan Kaufmann, August 1998.
- Pierre Hansen. Bricriteria path problems. In Multiple Criteria Decision Making -Theory and Application -, pages 109-127. Springer, 1979.
- Martin Holzer, Frank Schulz, Dorothea Wagner, and Thomas Willhalm. Combining speed- up techniques for shortest-path computations. ACM Journal of Experimental Algorithmics, 10(2.5):1-18, 2006.
- Kurt Mehlhorn and Peter Sanders. Algorithms and Data Structures: The Basic Toolbox. Springer, 2008.
- T. Mellouli and L. Suhl. Passenger online routing in dynamic networks. In D. C. Mattfeld and L. Suhl, editors, Informationsprobleme in Transport und Verkehr, volume 4, pages 17-30. DS&OR Lab, Universität Paderborn, 2006.
- Matthias Müller-Hannemann and Mathias Schnee. Paying less for train connections with MO- TIS. In Proceedings of the 5th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'05), OpenAccess Series in Informatics (OASIcs), page 657, 2006.
- Thomas Pajor. Multi-modal route planning. Master's thesis, Universität Karlsruhe (TH), March 2009.
- Ira Pohl. Bi-directional search. In Proceedings of the Sixth Annual Machine Intelligence Workshop, volume 6, pages 124-140. Edinburgh University Press, 1971.
- Michael Rice and Vassilis Tsotras. Bidirectional A* search with additive approximation bounds. In Proceedings of the 5th International Symposium on Combinatorial Search (SoCS'12). AAAI Press, 2012.
- 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.
- Mathias Weller. Optimal hub labeling is np-complete. CoRR, abs/1407.8373, 2014. · arXiv
- Lotfi A. Zadeh. Fuzzy logic. IEEE Computer, 21(4):83-93, 1988.
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
Badue, C., Guidolini, R., Carneiro, R. V., Azevedo, P., Cardoso, V. B., Forechi, A., Jesus, L., Berriel, R., Paixão, T. M., Mutz, F., et al. (2021) · Expert Systems with Applications · doi:10.1016/j.eswa.2020.113816 · Cited by 1,209
Perception, 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
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
crowddeliver: Planning City-Wide Package Delivery Paths Leveraging the Crowd of Taxis
Chen, C., Zhang, D., Ma, X., Guo, B., Wang, L., Wang, Y., & Sha, E. (2016) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2016.2607458 · Cited by 208
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)
- Microsoft (United States) (US)
- Karlsruhe Institute of Technology (DE)
- Amazon (United States) (US)
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2015
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 1504.05140
- OpenAlex
- W2952476710
- Cited by
- 189
- References
- 238
- Citations by year
- 2026: 8 · 2025: 5 · 2024: 2 · 2023: 7 · 2022: 6 · 2021: 9 · 2020: 23 · 2019: 13 · 2018: 11 · 2017: 24 · 2016: 33 · 2015: 30
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Licence
- Locations
- arXiv (Cornell University) (submittedVersion, other-oa)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- 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, data preprocessing, query response time, real-time traffic, public transport, journey planning, time-dependent networks, 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.
A language model drew the claims from the paper on 2026-11-17, under version 3 of the claim definition (model deepseek-v4.1-flash, prompt extract-v3).
A second model labelled each claim on 2026-11-17 (model jev-1.13-20260917, definition revision gold-guideline-v0.2).
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.48550/arxiv.1504.05140
- The paper
- Bast, H., Delling, D., Goldberg, A., Müller-Hannemann, M., Pajor, T., Sanders, P., Wagner, D., & Werneck, R. F. (2015). Route Planning in Transportation Networks. arXiv. https://doi.org/10.48550/arxiv.1504.05140
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.