The DOI matches its DataCite record; 240 of the 240 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
Computing the shortest path: A search meets graph theory
Goldberg, A. V., & Harrelson, C. (2005) · doi:10.5555/1070432.1070455 · Cited by 719
Self-citationLipton, R. J., Rose, D. J., & Tarjan, R. E. (1979) · SIAM Journal on Numerical Analysis · doi:10.1137/0716027 · Cited by 560
Faster algorithms for the shortest path problem
Ahuja, R. K., Mehlhorn, K., Orlin, J., & Tarjan, R. E. (1990) · Journal of the ACM · doi:10.1145/77600.77615 · Cited by 554
Williams, J. W. J. (1964) · Communications of the ACM · doi:10.1145/512274.3734138 · Cited by 527
Hansen, P. (1980) · Lecture Notes in Economics and Mathematical Systems · doi:10.1007/978-3-642-48782-8_9 · Cited by 525
Reachability and Distance Queries via 2-Hop Labels
Cohen, E., Halperin, E., Kaplan, H., & Zwick, U. (2003) · SIAM Journal on Computing · doi:10.1137/s0097539702403098 · Cited by 518
Network Analysis: Methodological Foundations (Lecture Notes in Computer Science)
Brandes, U., & Erlebach, T. (2005) · Springer eBooks · Cited by 514
Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length
Orda, A., & Rom, R. (1990) · Journal of the ACM · doi:10.1145/79147.214078 · Cited by 483
Real-time routing with OpenStreetMap data
Luxen, D., & Vetter, C. (2011) · Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems · doi:10.1145/2093973.2094062 · Cited by 478
On the approximability of trade-offs and optimal access of Web sources
Papadimitriou, C. H., & Yannakakis, M. (2002) · Proceedings 41st Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2000.892068 · Cited by 458
Engineering Route Planning Algorithms
Delling, D., Sanders, P., Schultes, D., & Wagner, D. (2009) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-02094-0_7 · Cited by 454
Self-citationOn a multicriteria shortest path problem
Martins, E. Q. V. (1984) · European Journal of Operational Research · doi:10.1016/0377-2217(84)90077-8 · Cited by 450
A faster approximation algorithm for the Steiner problem in graphs
Mehlhorn, K. (1988) · Information Processing Letters · doi:10.1016/0020-0190(88)90066-x · Cited by 420
The shortest route through a network with time-dependent internodal transit times
Cooke, K. L., & Halsey, E. (1966) · Journal of Mathematical Analysis and Applications · doi:10.1016/0022-247x(66)90009-6 · Cited by 412
Fast exact shortest-path distance queries on large networks by pruned landmark labeling
Akiba, T., Iwata, Y., & Yoshida, Y. (2013) · Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data · doi:10.1145/2463676.2465315 · Cited by 400
Algorithm 360: shortest-path forest with topological ordering [H]
Dial, R. B. (1969) · Communications of the ACM · doi:10.1145/363269.363610 · Cited by 369
Heuristic shortest path algorithms for transportation applications: State of the art
Fu, L., Sun, D., & Rilett, L. R. (2006) · Computers & Operations Research · doi:10.1016/j.cor.2005.03.027 · Cited by 341
Highway Hierarchies Hasten Exact Shortest Path Queries
Sanders, P., & Schultes, D. (2005) · Lecture Notes in Computer Science · doi:10.1007/11561071_51 · Cited by 327
Self-citationExact Routing in Large Road Networks Using Contraction Hierarchies
Geisberger, R., Sanders, P., Schultes, D., & Vetter, C. (2012) · Transportation Science · doi:10.1287/trsc.1110.0401 · Cited by 323
Self-citation?-solutions in vector minimization problems
Loridan, P. (1984) · Journal of Optimization Theory and Applications · doi:10.1007/bf00936165 · Cited by 313
Δ-stepping: a parallelizable shortest path algorithm
Meyer, U., & Sanders, P. (2003) · Journal of Algorithms · doi:10.1016/s0196-6774(03)00076-2 · Cited by 309
Self-citationReach-Based Routing: A New Approach to Shortest Path Algorithms Optimized for Road Networks.
Gutmann, R. J. (2004) · Cited by 292
The Use of Linear Graphs in Gauss Elimination
Parter, S. (1961) · SIAM Review · doi:10.1137/1003021 · Cited by 290
Shortest Path Algorithms In Transportation Models: Classical and Innovative Aspects
Pallottino, S., & Scutellà, M. G. (1998) · Equilibrium and Advanced Transportation Modelling · doi:10.1007/978-1-4615-5757-9_11 · Cited by 267
Compact oracles for reachability and approximate distances in planar digraphs
Thorup, M. (2004) · Journal of the ACM · doi:10.1145/1039488.1039493 · Cited by 257
A Hub-Based Labeling Algorithm for Shortest Paths in Road Networks
Abraham, I., Delling, D., Goldberg, A. V., & Werneck, R. F. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-20662-7_20 · Cited by 254
Self-citationShortest-path queries in static networks
Sommer, C. (2014) · ACM Computing Surveys · doi:10.1145/2530531 · Cited by 247
An efficient path computation model for hierarchically structured topographical road maps
Jung, S., & Pramanik, S. (2002) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2002.1033772 · Cited by 229
Fast Routing in Road Networks with Transit Nodes
Bast, H., Funke, S., Sanders, P., & Schultes, D. (2007) · Science · doi:10.1126/science.1137521 · Cited by 228
Self-citationGavoille, C., Peleg, D., Pérennes, S., & Raz, R. (2004) · Journal of Algorithms · doi:10.1016/j.jalgor.2004.05.002 · Cited by 224
Hierarchical Hub Labelings for Shortest Paths
Abraham, I., Delling, D., Goldberg, A. V., & Werneck, R. F. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-33090-2_4 · Cited by 218
Self-citationGoldman, R., Shivakumar, N., Venkatasubramanian, S., & García-Molina, H. (1998) · Very Large Data Bases · Cited by 217
Efficient models for timetable information in public transportation systems
Pyrga, E., Schulz, F., Wagner, D., & Zaroliagis, C. (2008) · ACM Journal of Experimental Algorithmics · doi:10.1145/1227161.1227166 · Cited by 211
Self-citationDemetrescu, C., Goldberg, A. V., & Johnson, D. S. (2009) · DIMACS series in discrete mathematics and theoretical computer science · doi:10.1090/dimacs/074 · Cited by 210
Self-citationA New Implementation of Sparse Gaussian Elimination
Schreiber, R. (1982) · ACM Transactions on Mathematical Software · doi:10.1145/356004.356006 · Cited by 199
Jing, N., Huang, Y.-W., & Rundensteiner, E. A. (1998) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/69.687976 · Cited by 199
Shortest-Route Methods: 1. Reaching, Pruning, and Buckets
Denardo, E. V., & Fox, B. L. (1979) · Operations Research · doi:10.1287/opre.27.1.161 · Cited by 198
In Transit to Constant Time Shortest-Path Queries in Road Networks
Bast, H., Funke, S., Matijevic, D., Sanders, P., & Schultes, D. (2007) · 2007 Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments (ALENEX) · doi:10.1137/1.9781611972870.5 · Cited by 191
Self-citationCombining hierarchical and goal-directed speed-up techniques for dijkstra's algorithm
Bauer, R., Delling, D., Sanders, P., Schieferdecker, D., Schultes, D., & Wagner, D. (2010) · ACM Journal of Experimental Algorithmics · doi:10.1145/1671970.1671976 · Cited by 190
Self-citationOptimal Route Planning for Electric Vehicles in Large Networks
Eisner, J., Funke, S., & Storandt, S. (2011) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v25i1.7991 · Cited by 184
Fast point-to-point shortest path computations with arc-flags
Hilger, M., Köhler, E., Möhring, R. H., & Schilling, H. (2009) · DIMACS series in discrete mathematics and theoretical computer science · doi:10.1090/dimacs/074/03 · Cited by 184
Minimum weight paths in time‐dependent networks
Orda, A., & Rom, R. (1991) · Networks · doi:10.1002/net.3230210304 · Cited by 182
Formal-Language-Constrained Path Problems
Barrett, C., Jacob, R., & Marathe, M. (2000) · SIAM Journal on Computing · doi:10.1137/s0097539798337716 · Cited by 181
Fast Routing in Very Large Public Transportation Networks Using Transfer Patterns
Bast, H., Carlsson, E., Eigenwillig, A., Geisberger, R., Harrelson, C., Raychev, V., & Viger, F. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-15775-2_25 · Cited by 179
Self-citationSchultes, D., & Sanders, P. (2007) · Springer eBooks · doi:10.1007/978-3-540-72845-0_6 · Cited by 179
Self-citationExact and Approximate Distances in Graphs — A Survey
Zwick, U. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-44676-1_3 · Cited by 176
Modeling Costs of Turns in Route Planning
Winter, S. (2002) · GeoInformatica · doi:10.1023/a:1020853410145 · Cited by 172
Modesti, P., & Sciomachen, A. (1998) · European Journal of Operational Research · doi:10.1016/s0377-2217(97)00376-7 · Cited by 171
Shortest path and distance queries on road networks: an experimental evaluation
Wu, L., Xiao, X., Deng, D., Cong, G., Zhu, A. D., & Zhou, S. (2012) · Proceedings of the VLDB Endowment · doi:10.14778/2140436.2140438 · Cited by 170
Dijkstra's algorithm on-line: an empirical case study from public railroad transport
Schulz, F., Wagner, D., & Weihe, K. (2000) · ACM Journal of Experimental Algorithmics · doi:10.1145/351827.384254 · Cited by 170
Self-citationDelling, D., Goldberg, A. V., Pajor, T., & Werneck, R. F. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-20662-7_32 · Cited by 168
Self-citationRound-Based Public Transit Routing
Delling, D., Pajor, T., & Werneck, R. F. (2015) · Transportation Science · doi:10.1287/trsc.2014.0534 · Cited by 168
Self-citationBidirectional Heuristic Search Reconsidered
Kaindl, H., & Kainz, G. (1997) · Journal of Artificial Intelligence Research · doi:10.1613/jair.460 · Cited by 165
Partitioning graphs to speedup Dijkstra's algorithm
Möhring, R. H., Schilling, H., Schütz, B., Wagner, D., & Willhalm, T. (2007) · ACM Journal of Experimental Algorithmics · doi:10.1145/1187436.1216585 · Cited by 158
Self-citationSHARC: Fast and robust unidirectional routing
Bauer, R., & Delling, D. (2009) · ACM Journal of Experimental Algorithmics · doi:10.1145/1498698.1537599 · Cited by 156
Self-citationDelling, D., & Wagner, D. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-05465-5_8 · Cited by 149
Self-citationIntriguingly Simple and Fast Transit Routing
Dibbelt, J., Pajor, T., Strasser, B., & Wagner, D. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-38527-8_6 · Cited by 148
Self-citationShortest paths in euclidean graphs
Sedgewick, R., & Vitter, J. S. (1986) · Algorithmica · doi:10.1007/bf01840435 · Cited by 148
Compact and localized distributed data structures
Gavoille, C., & Peleg, D. (2003) · Distributed Computing · doi:10.1007/s00446-002-0073-5 · Cited by 147
Multi-criteria Shortest Paths in Time-Dependent Train Networks
Disser, Y., Müller‐Hannemann, M., & Schnee, M. (2008) · Springer eBooks · doi:10.1007/978-3-540-68552-4_26 · Cited by 146
Self-citationWhite, D. J. (1986) · Journal of Optimization Theory and Applications · doi:10.1007/bf00940762 · Cited by 146
Using Multi-level Graphs for Timetable Information in Railway Systems
Schulz, F., Wagner, D., & Zaroliagis, C. (2002) · Lecture notes in computer science · doi:10.1007/3-540-45643-0_4 · Cited by 145
Self-citationAlternative routes in road networks
Abraham, I., Delling, D., Goldberg, A. V., & Werneck, R. F. (2013) · ACM Journal of Experimental Algorithmics · doi:10.1145/2444016.2444019 · Cited by 141
Self-citationPHAST: Hardware-accelerated shortest path trees
Delling, D., Goldberg, A. V., Nowatzyk, A. G., & Werneck, R. F. (2012) · Journal of Parallel and Distributed Computing · doi:10.1016/j.jpdc.2012.02.007 · Cited by 140
Self-citationShortest path and distance queries on road networks: towards bridging theory and practice
Zhu, A. D., Ma, H., Xiao, X., Luo, S., Tang, Y., & Zhou, S. (2013) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/2463676.2465277 · Cited by 137
Time-dependent Networks as Models to Achieve Fast Exact Time-table Queries
Brodal, G. S., & Jacob, R. (2004) · Electronic Notes in Theoretical Computer Science · doi:10.1016/j.entcs.2003.12.019 · Cited by 137
Route Planning in Road Networks
Schultes, D. (2008) · Repository KITopen (Karlsruhe Institute of Technology) · doi:10.5445/ir/1000007755 · Cited by 135
Computing Many-to-Many Shortest Paths Using Highway Hierarchies
Knopp, S., Sanders, P., Schultes, D., Schulz, F., & Wagner, D. (2007) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611972870.4 · Cited by 132
Self-citationLandmark-Based Routing in Dynamic Graphs
Delling, D., & Wagner, D. (2007) · Springer eBooks · doi:10.1007/978-3-540-72845-0_5 · Cited by 129
Self-citationBidirectionalA* search on time‐dependent road networks
Nannicini, G., Delling, D., Schultes, D., & Liberti, L. (2011) · Networks · doi:10.1002/net.20438 · Cited by 129
Self-citationTriangulation and Embedding Using Small Sets of Beacons
Kleinberg, J. M., Slivkins, A., & Wexler, T. (2004) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2004.70 · Cited by 129
Timetable Information: Models and Algorithms
Müller‐Hannemann, M., Schulz, F., Wagner, D., & Zaroliagis, C. (2007) · Springer eBooks · doi:10.1007/978-3-540-74247-0_3 · Cited by 128
Self-citationDistributed Evolutionary Graph Partitioning
Sanders, P., & Schulz, C. (2012) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611972924.2 · Cited by 128
Self-citationGraph Partitioning with Natural Cuts
Delling, D., Goldberg, A. V., Razenshteyn, I., & Werneck, R. F. (2011) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2011.108 · Cited by 127
Self-citationFast Shortest-path Distance Queries on Road Networks by Pruned Highway Labeling
Akiba, T., Iwata, Y., Kawarabayashi, K., & Kawata, Y. (2013) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611973198.14 · Cited by 127
On finding minimum routes in a network with turn penalties
Caldwell, T. (1961) · Communications of the ACM · doi:10.1145/366105.366184 · Cited by 126
Proximity-preserving labeling schemes
Peleg, D. (2000) · Journal of Graph Theory · doi:10.1002/(sici)1097-0118(200003)33:3<167::aid-jgt7>3.0.co;2-5 · Cited by 125
Efficient query processing on spatial networks
Sankaranarayanan, J., Alborzi, H., & Samet, H. (2005) · ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL GIS) · doi:10.1145/1097064.1097093 · Cited by 125
Object modeling and path computation for multimodal travel systems
Bielli, M., Boulmakoul, A., & Mouncif, H. (2005) · European Journal of Operational Research · doi:10.1016/j.ejor.2005.02.036 · Cited by 121
ROAD: A New Spatial Object Search Framework for Road Networks
Lee, K. C. K., Lee, W.-C., Zheng, B., & Tian, Y. (2010) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2010.243 · Cited by 120
Stochastic Delay Prediction in Large Train Networks
Berger, A., Gebhardt, A., Müller‐Hannemann, M., & Ostrowski, M. (2011) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/oasics.atmos.2011.100 · Cited by 120
Self-citationHighway Dimension, Shortest Paths, and Provably Efficient Algorithms
Abraham, I., Fiat, A., Goldberg, A. V., & Werneck, R. F. (2010) · ACM-SIAM Symposium on Discrete Algorithms (SODA) · doi:10.1137/1.9781611973075.64 · Cited by 119
Self-citationTsaggouris, G., & Zaroliagis, C. (2007) · Theory of Computing Systems · doi:10.1007/s00224-007-9096-4 · Cited by 118
G-tree: an efficient index for KNN search on road networks
Zhong, R., Li, G., Tan, K., & Zhou, L. (2013) · ACM International Conference on Information and Knowledge Management (CIKM) · doi:10.1145/2505515.2505749 · Cited by 118
On the Complexity of Time-Dependent Shortest Paths
Foschini, L., Hershberger, J. E., & Suri, S. (2012) · Algorithmica · doi:10.1007/s00453-012-9714-7 · Cited by 118
Engineering multilevel overlay graphs for shortest-path queries
Holzer, M., Schulz, F., & Wagner, D. (2008) · ACM Journal of Experimental Algorithmics · doi:10.1145/1412228.1412239 · Cited by 117
Self-citationA fast algorithm for finding better routes by AI search techniques
Ikeda, T., Hsu, M.-Y., Imai, H., Nishimura, S., SHIMOURA, H., Hashimoto, T., TENMOKU, K., & Mitoh, K. (2002) · Vehicle Navigation and Information Systems Conference (VNIS) · doi:10.1109/vnis.1994.396824 · Cited by 117
Studying (non-planar) road networks through an algorithmic lens
Eppstein, D., & Goodrich, M. T. (2008) · ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL GIS) · doi:10.1145/1463434.1463455 · Cited by 116
Delling, D. (2009) · Algorithmica · doi:10.1007/s00453-009-9341-0 · Cited by 106
Self-citationThorup, M. (2003) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/780542.780566 · Cited by 105
Geometric containers for efficient shortest-path computation
Wagner, D., Willhalm, T., & Zaroliagis, C. (2005) · ACM Journal of Experimental Algorithmics · doi:10.1145/1064546.1103378 · Cited by 105
Self-citationDynamic shortest paths minimizing travel times and costs
Ahuja, R. K., Orlin, J. B., Pallottino, S., & Scutellà, M. G. (2003) · Networks · doi:10.1002/net.10072 · Cited by 104
Minimum time-dependent travel times with contraction hierarchies
Batz, G. V., Geisberger, R., Sanders, P., & Vetter, C. (2013) · ACM Journal of Experimental Algorithmics · doi:10.1145/2444016.2444020 · Cited by 99
Self-citationPredestination: Where Do You Want to Go Today?
Krumm, J. C., & Horvitz, E. (2007) · Computer · doi:10.1109/mc.2007.141 · Cited by 96
Delling, D., & Wagner, D. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-02011-7_13 · Cited by 95
Self-citationEnergy-optimal routes for electric vehicles
Baum, M., Dibbelt, J., Pajor, T., & Wagner, D. (2013) · ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL GIS) · doi:10.1145/2525314.2525361 · Cited by 95
Self-citationTime depending shortest-path problems with applications to railway networks
Nachtigall, K. (1995) · European Journal of Operational Research · doi:10.1016/0377-2217(94)e0349-g · Cited by 94
Computing Multimodal Journeys in Practice
Delling, D., Dibbelt, J., Pajor, T., Wagner, D., & Werneck, R. F. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-38527-8_24 · Cited by 93
Self-citationAlternative Route Graphs in Road Networks
Bader, R., Dees, J., Geisberger, R., & Sanders, P. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-19754-3_5 · Cited by 91
Self-citationImproved shortest path algorithms for transport networks
Vliet, D. V. (1978) · Transportation Research · doi:10.1016/0041-1647(78)90102-8 · Cited by 91
Algorithms for minimum‐cost paths in time‐dependent networks with waiting policies
Dean, B. C. (2004) · Networks · doi:10.1002/net.20013 · Cited by 91
Round-Based Public Transit Routing
Delling, D., Pajor, T., & Werneck, R. F. (2012) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611972924.13 · Cited by 90
Self-citationSingle-Source Shortest-Paths on Arbitrary Directed Graphs in Linear Average-Case Time
Meyer, U. (2001) · Max Planck Institute for Plasma Physics · doi:10.5555/365411.365784 · Cited by 80
Accelerating Multi-modal Route Planning by Access-Nodes
Delling, D., Pajor, T., & Wagner, D. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-04128-0_53 · Cited by 79
Self-citationPareto Shortest Paths is Often Feasible in Practice
Müller‐Hannemann, M., & Weihe, K. (2001) · Lecture notes in computer science · doi:10.1007/3-540-44688-5_15 · Cited by 79
Self-citationExperimental study of speed up techniques for timetable information systems
Bauer, R., Delling, D., & Wagner, D. (2010) · Networks · doi:10.1002/net.20382 · Cited by 77
Self-citationTransit Node Routing Reconsidered
Arz, J., Luxen, D., & Sanders, P. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-38527-8_7 · Cited by 76
Self-citationGoal-directed shortest-path queries using precomputed cluster distances
Maue, J., Sanders, P., & Matijević, D. (2009) · ACM Journal of Experimental Algorithmics · doi:10.1145/1498698.1564502 · Cited by 76
Self-citationCherkasskyBoris, V., GoldbergAndrew, V., & RadzikTomasz (1996) · Mathematical Programming · doi:10.5555/3226663.3227073 · Cited by 76
Query Processing Using Distance Oracles for Spatial Networks
Sankaranarayanan, J., & Samet, H. (2010) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2010.75 · Cited by 75
Reach for A*: shortest path algorithms with preprocessing
Goldberg, A. V., Kaplan, H. Y., & Werneck, R. F. (2009) · DIMACS series in discrete mathematics and theoretical computer science · doi:10.1090/dimacs/074/05 · Cited by 75
Self-citationVC-Dimension and Shortest Path Algorithms
Abraham, I., Delling, D., Fiat, A., Goldberg, A. V., & Werneck, R. F. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-22006-7_58 · Cited by 73
Self-citationCar or Public Transport—Two Worlds
Bast, H. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-03456-5_24 · Cited by 73
Self-citationFast Detour Computation for Ride Sharing
Geisberger, R., Luxen, D., Neubauer, S., Sanders, P., & Völker, L. (2010) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/oasics.atmos.2010.88 · Cited by 72
Self-citationRobust Distance Queries on Massive Networks
Delling, D., Goldberg, A. V., Pajor, T., & Werneck, R. F. (2014) · Lecture notes in computer science · doi:10.1007/978-3-662-44777-2_27 · Cited by 69
Self-citationEngineering Label-Constrained Shortest-Path Algorithms
Barrett, C., Bisset, K. R., Holzer, M., Konjevod, G., MARATHE, M. V., & Wagner, D. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-68880-8_5 · Cited by 66
Self-citationUltrafast shortest-path queries via transit nodes
Bast, H., Funke, S., & Matijević, D. (2009) · DIMACS series in discrete mathematics and theoretical computer science · doi:10.1090/dimacs/074/07 · Cited by 66
Self-citationCore Routing on Dynamic Time-Dependent Road Networks
Delling, D., & Nannicini, G. (2011) · INFORMS journal on computing · doi:10.1287/ijoc.1110.0448 · Cited by 65
Self-citationFinding All Attractive Train Connections by Multi-criteria Pareto Search
Müller‐Hannemann, M., & Schnee, M. (2007) · Springer eBooks · doi:10.1007/978-3-540-74247-0_13 · Cited by 64
Self-citationRoute Planning with Flexible Objective Functions
Geisberger, R., Kobitzsch, M., & Sanders, P. (2010) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611972900.12 · Cited by 62
Self-citationEfficient Routing in Road Networks with Turn Costs
Geisberger, R., & Vetter, C. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-20662-7_9 · Cited by 62
Ultra-Fast Optimal Pathfinding without Runtime Search
Botea, A. (2011) · Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment · doi:10.1609/aiide.v7i1.12443 · Cited by 61
Efficient Timetable Information in the Presence of Delays
Müller‐Hannemann, M., & Schnee, M. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-05465-5_10 · Cited by 60
Self-citationBarrett, C., Bisset, K. R., Jacob, R., Konjevod, G., & MARATHE, M. V. (2002) · Lecture notes in computer science · doi:10.1007/3-540-45749-6_15 · Cited by 59
Distributed Time-Dependent Contraction Hierarchies
Kieritz, T., Luxen, D., Sanders, P., & Vetter, C. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-13193-6_8 · Cited by 59
Self-citationA case for time-dependent shortest path computation in spatial networks
Demiryurek, U., Banaei‐Kashani, F., & Shahabi, C. (2010) · ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL GIS) · doi:10.1145/1869790.1869865 · Cited by 58
A Practical Shortest Path Algorithm with Linear Expected Time
Goldberg, A. V. (2008) · SIAM Journal on Computing · doi:10.1137/070698774 · Cited by 56
Self-citationShortest Paths in Time-Dependent FIFO Networks
Dehne, F., Omran, M. T., & Sack, J.-R. (2010) · Algorithmica · doi:10.1007/s00453-010-9461-6 · Cited by 56
Hub Labels: Theory and Practice
Delling, D., Goldberg, A. V., Savchenko, R., & Werneck, R. F. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-07959-2_22 · Cited by 56
Self-citationSome help on the way: opportunistic routing under uncertainty
Horvitz, E., & Krumm, J. C. (2012) · ACM International Joint Conference on Pervasive and Ubiquitous Computing (UbiComp) · doi:10.1145/2370216.2370273 · Cited by 55
Faster Customization of Road Networks
Delling, D., & Werneck, R. F. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-38527-8_5 · Cited by 54
Self-citationSanders, P., Schultes, D., & Vetter, C. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-87744-8_61 · Cited by 54
Self-citationOn k-path covers and their applications
Funke, S., Nusser, A., & Storandt, S. (2014) · Proceedings of the VLDB Endowment · doi:10.14778/2732951.2732963 · Cited by 54
The Price of Strict and Light Robustness in Timetable Information
Goerigk, M., Schmidt, M., Schöbel, A., Knoth, M., & Müller‐Hannemann, M. (2013) · Transportation Science · doi:10.1287/trsc.2013.0470 · Cited by 53
Self-citationCandidate Sets for Alternative Routes in Road Networks
Luxen, D., & Schieferdecker, D. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-30850-5_23 · Cited by 53
Parallel Label-Setting Multi-objective Shortest Path Search
Sanders, P., & Mandow, L. (2013) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2013.89 · Cited by 52
Self-citationEngineering Time-Expanded Graphs for Faster Timetable Information
Delling, D., Pajor, T., & Wagner, D. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-05465-5_7 · Cited by 51
Self-citationPreprocessing Speed-Up Techniques Is Hard
Bauer, R., Columbus, T., Katz, B., Krug, M., & Wagner, D. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-13073-1_32 · Cited by 51
Self-citationEngineering highway hierarchies
Sanders, P., & Schultes, D. (2012) · ACM Journal of Experimental Algorithmics · doi:10.1145/2133803.2330080 · Cited by 51
Self-citationStorandt, S. (2012) · Proceedings of the International Conference on Automated Planning and Scheduling · doi:10.1609/icaps.v22i1.13495 · Cited by 51
Drews, F., & Luxen, D. (2021) · Proceedings of the International Symposium on Combinatorial Search · doi:10.1609/socs.v4i1.18279 · Cited by 49
Contraction of Timetable Networks with Realistic Transfers
Geisberger, R. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-13193-6_7 · Cited by 49
Parallel shortest path algorithms for solving large-scale instances
Madduri, K., Bader, D. A., Berry, J. W., & Crobak, J. R. (2009) · DIMACS series in discrete mathematics and theoretical computer science · doi:10.1090/dimacs/074/10 · Cited by 49
Experimental Comparison of Shortest Path Approaches for Timetable Information.
Pyrga, E., Schulz, F., Wagner, D., & Zaroliagis, C. (2004) · Cited by 48
Self-citationUser-Constrained Multi-Modal Route Planning
Dibbelt, J., Pajor, T., & Wagner, D. (2012) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611972924.12 · Cited by 48
Self-citationFrom destination prediction to route prediction
Krumm, J. C., Gruen, R., & Delling, D. (2013) · Journal of Location Based Services · doi:10.1080/17489725.2013.788228 · Cited by 48
Self-citationParallel Bi-objective Shortest Paths Using Weight-Balanced B-trees with Bulk Updates
Erb, S., Kobitzsch, M., & Sanders, P. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-07959-2_10 · Cited by 44
Self-citationSpeed-Consumption Tradeoff for Electric Vehicle Route Planning
Baum, M., Dibbelt, J., Hübschle-Schneider, L., Pajor, T., & Wagner, D. (2014) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/oasics.atmos.2014.138 · Cited by 44
Self-citationHigh-performance multi-level routing
Delling, D., Holzer, M., Müller, K., Schulz, F., & Wagner, D. (2009) · DIMACS series in discrete mathematics and theoretical computer science · doi:10.1090/dimacs/074/04 · Cited by 44
Self-citationAifadopoulou, G., Ziliaskopoulos, A. K., & Chrisohoou, E. (2007) · Transportation Research Record Journal of the Transportation Research Board · doi:10.3141/2032-04 · Cited by 43
HLDB: location-based services in databases
Abraham, I., Delling, D., Fiat, A., Goldberg, A. V., & Werneck, R. F. (2012) · ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL GIS) · doi:10.1145/2424321.2424365 · Cited by 43
Self-citationAlgorithms for Matching and Predicting Trajectories
Eisner, J., Funke, S., Herbst, A., Spillner, A., & Storandt, S. (2011) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611972917.9 · Cited by 43
Delling, D., Goldberg, A. V., & Werneck, R. F. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-38527-8_4 · Cited by 43
Self-citationParallel computation of best connections in public transportation networks
Delling, D., Katz, B., & Pajor, T. (2012) · ACM Journal of Experimental Algorithmics · doi:10.1145/2133803.2345678 · Cited by 42
Self-citationLauther, U. (2009) · DIMACS series in discrete mathematics and theoretical computer science · doi:10.1090/dimacs/074/02 · Cited by 42
Customizable Contraction Hierarchies
Dibbelt, J., Strasser, B., & Wagner, D. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-07959-2_23 · Cited by 42
Self-citationAdvanced Route Planning in Transportation Networks
Geisberger, R. (2011) · Repository KITopen (Karlsruhe Institute of Technology) · doi:10.5445/ir/1000021997 · Cited by 42
Improved Alternative Route Planning
Paraskevopoulos, A., & Zaroliagis, C. (2013) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/oasics.atmos.2013.108 · Cited by 40
Optimizing Landmark-Based Routing and Preprocessing
Efentakis, A., & Pfoser, D. (2013) · ACM SIGSPATIAL International Workshop on Computational Transportation Science (IWCTS) · doi:10.1145/2533828.2533838 · Cited by 40
Frequency-based search for public transit
Bast, H., & Storandt, S. (2014) · ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL GIS) · doi:10.1145/2666310.2666405 · Cited by 39
Self-citationBerger, A., Grimmer, M., & Müller‐Hannemann, M. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-13193-6_4 · Cited by 38
Self-citationAccelerating Time-Dependent Multi-Criteria Timetable Information is Harder Than Expected
Berger, A., Delling, D., Gebhardt, A., & Müller‐Hannemann, M. (2009) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/oasics.atmos.2009.2148 · Cited by 37
Self-citationResult Diversity for Multi-Modal Route Planning
Bast, H., Brodesser, M., & Storandt, S. (2013) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/oasics.atmos.2013.123 · Cited by 37
Self-citationCruising with a Battery-Powered Vehicle and Not Getting Stranded
Storandt, S., & Funke, S. (2021) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v26i1.8326 · Cited by 35 · cited 1×
“Minimizing the energy consumption of electric vehicles [43,44,122,152,240,241] is another nontrivial application, since batteries are recharged when the car is going downhill.”
BackgroundSearch-Space Size in Contraction Hierarchies
Bauer, R., Columbus, T., Rutter, I., & Wagner, D. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-39206-1_9 · Cited by 34
Self-citationDelay-Robustness of Transfer Patterns in Public Transportation Route Planning
Bast, H., Sternisko, J., & Storandt, S. (2013) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/oasics.atmos.2013.42 · Cited by 34
Self-citationPolynomial-time Construction of Contraction Hierarchies for Multi-criteria Objectives
Funke, S., & Storandt, S. (2013) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611972931.4 · Cited by 34
Bi-Directional and Heuristic Search in Path Problems [Thesis]
Pohl, I., US Atomic Energy Commission (AEC), & USDOE Office of Science (SC) (1969) · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · doi:10.2172/1453875 · Cited by 34
Buckets, heaps, lists, and monotone priority queues
Cherkassky, B. V., Goldberg, A. V., & Silverstein, C. D. (1997) · Symposium on Discrete Algorithms · doi:10.5555/314161.314187 · Cited by 32
Self-citationAntsfeld, L., & Walsh, T. (2012) · 19th ITS World CongressERTICO - ITS EuropeEuropean CommissionITS AmericaITS Asia-Pacific · Cited by 30
An Alternative Approach to Alternative Routes: HiDAR
Kobitzsch, M. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-40450-4_52 · Cited by 29
Evolution and Evaluation of the Penalty Method for Alternative Graphs
Kobitzsch, M., Radermacher, M., & Schieferdecker, D. (2013) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/oasics.atmos.2013.94 · Cited by 28
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
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
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 23
Self-citationDynamic 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
Two-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-citationSankaranarayanan, J., & Samet, H. (n.d.) · Cited by 21
Exact 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
Research works printed but not linked: 20
- Ittai Abraham, Amos Fiat, Andrew V. Goldberg, and Renato F. Werneck. Highway dimension, shortest paths, and provably efficient algorithms. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'10), pages 782-793. SIAM, 2010.
- 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.
- 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
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.