Student or educator? Sign up with your school email and get 6 months of Pro free.
CoChat

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 access
Bast, Hannah, Delling, Daniel, Goldberg, Andrew, Müller-Hannemann, Matthias, Pajor, Thomas, Sanders, Peter, Wagner, Dorothea, Werneck, Renato F. · 2015 · arXiv

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

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

DataCite · 10.48550/arxiv.1504.05140

Cites

238 of 238 references verified0 citation errors · 0 not checkable

Statistics

Nothing to recompute.

Verification

Claims the paper makes

0 Valid · 20 Not valid · 130 Not checked · 115 Own results and interpretations

103 more claims

Create a free account to see all 265 claims and every source verdict.

See all claims — free account
  • Probably not a substantial claim. 100
  • It may state two separate claims as one. 79

Create a free account to see these claims.

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.

1 of 1

Citations

Cites

Show all 238 references

Research works printed but not linked: 20

  1. Andreas Bauer. Multimodal profile queries. Bachelor thesis, Karlsruhe Institute of Technology, May 2012.
  2. Cambridge Vehicle Information Technology Ltd. Choice routing, 2005. Available at http: //www.camvit.com.
  3. 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.
  4. Brian C. Dean. Continuous-time dynamic shortest path algorithms. Master's thesis, Mas- sachusetts Institute of Technology, 1999.
  5. 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.
  6. 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.
  7. 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.
  8. 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.
  9. Morgan Kaufmann, August 1998.
  10. Pierre Hansen. Bricriteria path problems. In Multiple Criteria Decision Making -Theory and Application -, pages 109-127. Springer, 1979.
  11. 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.
  12. Kurt Mehlhorn and Peter Sanders. Algorithms and Data Structures: The Basic Toolbox. Springer, 2008.
  13. 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.
  14. 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.
  15. Thomas Pajor. Multi-modal route planning. Master's thesis, Universität Karlsruhe (TH), March 2009.
  16. Ira Pohl. Bi-directional search. In Proceedings of the Sixth Annual Machine Intelligence Workshop, volume 6, pages 124-140. Edinburgh University Press, 1971.
  17. 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.
  18. 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.
  19. Mathias Weller. Optimal hub labeling is np-complete. CoRR, abs/1407.8373, 2014. · arXiv
  20. Lotfi A. Zadeh. Fuzzy logic. IEEE Computer, 21(4):83-93, 1988.

Cited by

See all 189

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)
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
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.