Route Planning in Transportation Networks
The DOI matches its Crossref record; 258 of the 263 references it cites were found in a registry or an index.
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
Items 201–258 of 258
Path Planning with Compressed All-Pairs Shortest Paths Data
Botea, A., & Harabor, D. (2013) · Proceedings of the International Conference on Automated Planning and Scheduling · doi:10.1609/icaps.v23i1.13600 · Cited by 27
Strasser, B., & Wagner, D. (2013) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611973198.12 · Cited by 27
Self-citationTrip-Based Public Transit Routing
Witt, S. (2015) · Repository KITopen (Karlsruhe Institute of Technology) · doi:10.5445/ir/1000097658 · Cited by 25
Time-Dependent Route Planning with Generalized Objective Functions
Batz, G. V., & Sanders, P. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-33090-2_16 · Cited by 24
Self-citationEfficient data management in support of shortest-path computation
Efentakis, A., Pfoser, D., & Voisard, A. (2011) · ACM SIGSPATIAL International Workshop on Computational Transportation Science (IWCTS) · doi:10.1145/2068984.2068990 · Cited by 24
On optimal preprocessing for contraction hierarchies
Milosavljević, N. (2012) · ACM SIGSPATIAL International Workshop on Computational Transportation Science (IWCTS) · doi:10.1145/2442942.2442949 · Cited by 24
Dynamic Multi-level Overlay Graphs for Shortest Paths
Bruera, F., Cicerone, S., D’Angelo, G., Stefano, G. D., & Frigioni, D. (2008) · Mathematics in Computer Science · doi:10.1007/s11786-007-0023-5 · Cited by 23
Route planning with flexible edge restrictions
Geisberger, R., Rice, M. N., Sanders, P., & Tsotras, V. J. (2012) · ACM Journal of Experimental Algorithmics · doi:10.1145/2133803.2133805 · Cited by 22
Self-citationTwo-phase bicriterion search for finding fast and efficient electric vehicle routes
Goodrich, M. T., & Pszona, P. (2014) · ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL GIS) · doi:10.1145/2666310.2666382 · Cited by 22
Robust, almost constant time shortest-path queries in road networks
Sanders, P., & Schultes, D. (2009) · DIMACS series in discrete mathematics and theoretical computer science · doi:10.1090/dimacs/074/08 · Cited by 22
Self-citationCrowdsourcing computing resources for shortest-path computation
Efentakis, A., Theodorakis, D., & Pfoser, D. (2012) · ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL GIS) · doi:10.1145/2424321.2424383 · Cited by 21
UniALT for regular language contrained shortest paths on a multi-modal transportation network
Kirchler, D., Liberti, L., Pajor, T., & Calvo, R. W. (2011) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/oasics.atmos.2011.64 · Cited by 21
Self-citationBöhmová, K., Mihaľák, M., Pröger, T., Šrámek, R., & Widmayer, P. (2013) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.3929/ethz-b-000076385 · Cited by 21
Engineering label-constrained shortest-path algorithms
Barrett, C., Bisset, K. R., Holzer, M., Konjevod, G., MARATHE, M. V., & Wagner, D. (2009) · DIMACS series in discrete mathematics and theoretical computer science · doi:10.1090/dimacs/074/12 · Cited by 21
Self-citationExact Graph Search Algorithms for Generalized Traveling Salesman Path Problems
Rice, M. N., & Tsotras, V. J. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-30850-5_30 · Cited by 20
Möhring, R. H. (1999) · Vieweg+Teubner eBooks · doi:10.1007/978-3-322-83092-0_11 · Cited by 20
Advanced multi-modal routing approach for pedestrians
Yu, H., & Lu, F. (2012) · International Conference on Consumer Electronics, Communications and Networks (CECNet) · doi:10.1109/cecnet.2012.6201641 · Cited by 20
Is Timetabling Routing Always Reliable for Public Transport?
Firmani, D., Italiano, G. F., Laura, L., & Santaroni, F. (2013) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/oasics.atmos.2013.15 · Cited by 20
Enabling E-Mobility: Facility Location for Battery Loading Stations
Storandt, S., & Funke, S. (2013) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v27i1.8478 · Cited by 20
Fast and Compact Oracles for Approximate Distances in Planar Graphs
Muller, L. F., & Zachariasen, M. (2007) · Springer eBooks · doi:10.1007/978-3-540-75520-3_58 · Cited by 19
A Label Correcting Algorithm for the Shortest Path Problem on a Multi-modal Route Network
Kirchler, D., Liberti, L., & Calvo, R. W. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-30850-5_21 · Cited by 19
Drawing Graphs to Speed Up Shortest-Path Computations.
Wagner, D., & Willhalm, T. (2005) · Cited by 18
Self-citationTransit Nodes – Lower Bounds and Refined Construction
Eisner, J., & Funke, S. (2012) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611972924.14 · Cited by 18
SALT. A Unified Framework for All Shortest-Path Query Variants on Road Networks
Efentakis, A., Pfoser, D., & Vassiliou, Y. (2015) · Lecture notes in computer science · doi:10.1007/978-3-319-20086-6_23 · Cited by 18
Recoverable Robust Timetable Information
Goerigk, M., Heße, S., Müller‐Hannemann, M., Schmidt, M., & Schöbel, A. (2013) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/oasics.atmos.2013.1 · Cited by 18
Self-citationAlgorithms for Hub Label Optimization
Babenko, M. A., Goldberg, A. V., Gupta, A., & Nagarajan, V. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-39206-1_7 · Cited by 17
Self-citationBrunel, E., Delling, D., Gemsa, A., & Wagner, D. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-13193-6_5 · Cited by 17
Self-citationRandom road networks: the quadtree model
Eisenstat, D. (2011) · Workshop on Analytic Algorithmics and Combinatorics (ANALCO) · doi:10.1137/1.9781611973013.9 · Cited by 17
Fully Dynamic Maintenance of Arc-Flags in Road Networks
D’Angelo, G., D’Emidio, M., Frigioni, D., & Vitale, C. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-30850-5_13 · Cited by 16
Hierarchy Decomposition for Faster User Equilibria on Road Networks
Luxen, D., & Sanders, P. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-20662-7_21 · Cited by 16
Self-citationTRAINS, An Active Time-Table Searcher.
Tulp, E., & Siklóssy, L. (1988) · European Conference on Artificial Intelligence · Cited by 15
Getting Train Timetables into the Main Storage
Müller‐Hannemann, M., Schnee, M., & Weihe, K. (2002) · Electronic Notes in Theoretical Computer Science · doi:10.1016/s1571-0661(04)80525-5 · Cited by 15
Self-citationTravel Planning with Self-Made Maps
Brandes, U., Schulz, F., Wagner, D., & Willhalm, T. (2001) · Lecture notes in computer science · doi:10.1007/3-540-44808-x_10 · Cited by 14
Self-citationSequenced route queries: getting things done on the way back home
Eisner, J., & Funke, S. (2012) · ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL GIS) · doi:10.1145/2424321.2424400 · Cited by 14
The Shortcut Problem - Complexity and Algorithms
Bauer, R., D’Angelo, G., Delling, D., Schumm, A., & Wagner, D. (2012) · Journal of Graph Algorithms and Applications · doi:10.7155/jgaa.00270 · Cited by 14
Self-citationEngineering Graph-Based Models for Dynamic Timetable Information Systems
Cionini, A., D’Angelo, G., D’Emidio, M., Frigioni, D., Giannakopoulou, K., Paraskevopoulos, A., & Zaroliagis, C. (2014) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/oasics.atmos.2014.46 · Cited by 14
Bidirectional A* Search with Additive Approximation Bounds
Rice, M. N., & Tsotras, V. J. (2021) · Proceedings of the International Symposium on Combinatorial Search · doi:10.1609/socs.v3i1.18235 · Cited by 14
Tulp, E., & Siklóssy, L. (1991) · Artificial intelligence for engineering design analysis and manufacturing · doi:10.1017/s0890060400002675 · Cited by 13
Customizing Driving Directions with GPUs
Delling, D., Kobitzsch, M., & Werneck, R. F. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-09873-9_61 · Cited by 12
Self-citationPaying Less for Train Connections with MOTIS
Müller‐Hannemann, M., & Schnee, M. (2006) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/oasics.atmos.2005.657 · Cited by 12
Self-citationCustomizable point-of-interest queries in road networks
Delling, D., & Werneck, R. F. (2013) · ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL GIS) · doi:10.1145/2525314.2525470 · Cited by 12
Self-citationGRASP. Extending Graph Separators for the Single-Source Shortest-Path Problem
Efentakis, A., & Pfoser, D. (2014) · Lecture notes in computer science · doi:10.1007/978-3-662-44777-2_30 · Cited by 12
Robust Mobile Route Planning with Limited Connectivity
Delling, D., Kobitzsch, M., Luxen, D., & Werneck, R. F. (2012) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611972924.15 · Cited by 11
Self-citationEfficient Route Planning in Flight Networks
Delling, D., Pajor, T., Wagner, D., & Zaroliagis, C. (2009) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/oasics.atmos.2009.2145 · Cited by 11
Self-citationHeuristic Contraction Hierarchies with Approximation Guarantee
Geisberger, R., & Schieferdecker, D. (2010) · Proceedings of the International Symposium on Combinatorial Search · doi:10.1609/socs.v1i1.18161 · Cited by 11
Engineering Time-Dependent Many-to-Many Shortest Paths Computation
Geisberger, R., & Sanders, P. (2010) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/oasics.atmos.2010.74 · Cited by 11
Self-citationEngineering Planar-Separator and Shortest-Path Algorithms
Holzer, M. (2008) · Repository KITopen (Karlsruhe Institute of Technology) · doi:10.5445/ir/1000009237 · Cited by 11
Bauer, R., Krug, M., Meinert, S., & Wagner, D. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-14355-7_6 · Cited by 10
Self-citationExploiting GPS Data in Public Transport Journey Planners
Allulli, L., Italiano, G. F., & Santaroni, F. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-07959-2_25 · Cited by 10
Bast, H., & Storandt, S. (2013) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611973198.15 · Cited by 10
Self-citationHliněný, P., & Moriš, O. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-23719-5_38 · Cited by 9
Better transit routing by exploiting vehicle GPS data
Delling, D., Italiano, G. F., Pajor, T., & Santaroni, F. (2014) · ACM SIGSPATIAL International Workshop on Computational Transportation Science (IWCTS) · doi:10.1145/2674918.2674923 · Cited by 9
Self-citationDistance Oracles for Time-Dependent Networks
Kontogiannis, S. C., & Zaroliagis, C. (2014) · Lecture notes in computer science · doi:10.1007/978-3-662-43948-7_59 · Cited by 9
Customizable Route Planning in Road Networks (Extended Abstract)
Delling, D., Goldberg, A. V., Pajor, T., & Werneck, R. F. (2021) · Proceedings of the International Symposium on Combinatorial Search · doi:10.1609/socs.v4i1.18272 · Cited by 6
Self-citationEfficient Route Compression for Hybrid Route Planning
Batz, G. V., Geisberger, R., Luxen, D., Sanders, P., & Zubkov, R. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-34862-4_7 · Cited by 5
Self-citationOn the Complexity of Partitioning Graphs for Arc-Flags
Bauer, R., Baum, M., Rutter, I., & Wagner, D. (2013) · Journal of Graph Algorithms and Applications · doi:10.7155/jgaa.00294 · Cited by 5
Self-citationHow to find good night train connections
Gunkel, T., Schnee, M., & Müller‐Hannemann, M. (2010) · Networks · doi:10.1002/net.20380 · Cited by 4
Self-citationOptimal Hub Labeling is NP-completePreprint
Weller, M. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1407.8373 · Cited by 2
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
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.