Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Engineering a Lightweight and Efficient Local Search SAT Solver Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Route Planning in Transportation Networks

verfasst von : Hannah Bast, Daniel Delling, Andrew Goldberg, Matthias Müller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, Renato F. Werneck

Erschienen in: Algorithm Engineering

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Engineering a Lightweight and Efficient Local Search SAT Solver
Nächstes Kapitel Theoretical Analysis of the k-Means Algorithm – A Survey
Fußnoten
1
The reader is referred to Sommer [238] for a similar plot (which inspired ours) relating query times to preprocessing space.
 
Literatur
1.
Abraham, I., Delling, D., Fiat, A., Goldberg, A.V., Werneck, R.F.: VC-dimension and shortest path algorithms. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011. LNCS, vol. 6755, pp. 690–699. Springer, Heidelberg (2011). doi:10.​1007/​978-3-642-22006-7_​58 CrossRef
2.
Abraham, I., Delling, D., Fiat, A., Goldberg, A.V., Werneck, R.F.: HLDB: Location-based services in databases. In: Proceedings of the 20th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems (GIS 2012), pp. 339–348. ACM Press 2012. Best Paper Award
3.
Abraham, I., Delling, D., Fiat, A., Goldberg, A.V., Werneck, R.F.: Highway dimension and provably efficient shortest path algorithms. Technical report MSR-TR-2013-91, Microsoft Research (2013)
4.
Abraham, I., Delling, D., Goldberg, A.V., Werneck, R.F.: A hub-based labeling algorithm for shortest paths in road networks. In: Pardalos, P.M., Rebennack, S. (eds.) SEA 2011. LNCS, vol. 6630, pp. 230–241. Springer, Heidelberg (2011). doi:10.​1007/​978-3-642-20662-7_​20 CrossRef
5.
Abraham, I., Delling, D., Goldberg, A.V., Werneck, R.F.: Hierarchical hub labelings for shortest paths. In: Epstein, L., Ferragina, P. (eds.) ESA 2012. LNCS, vol. 7501, pp. 24–35. Springer, Heidelberg (2012). doi:10.​1007/​978-3-642-33090-2_​4 CrossRef
6.
Abraham, I., Delling, D., Goldberg, A.V., Werneck, R.F.: Alternative routes in road networks. ACM J. Exp. Algorithm. 18(1), 1–17 (2013)MathSciNetMATH
7.
Abraham, I., Fiat, A., Goldberg, A.V., Werneck, R.F.: Highway dimension, shortest paths, and provably efficient algorithms. In: Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), pp. 782–793. SIAM (2010)
8.
Ahuja, R.K., Mehlhorn, K., Orlin, J.B., Tarjan, R.: Faster algorithms for the shortest path problem. J. ACM 37(2), 213–223 (1990)MathSciNetMATHCrossRef
9.
Ahuja, R.K., Orlin, J.B., Pallottino, S., Scutellà, M.G.: Dynamic shortest paths minimizing travel times and costs. Networks 41(4), 197–205 (2003)MathSciNetMATHCrossRef
10.
Aifadopoulou, G., Ziliaskopoulos, A., Chrisohoou, E.: Multiobjective optimum path algorithm for passenger pretrip planning in multimodal transportation networks. J. Transp. Res. Board 2032(1), 26–34 (2007). doi:10.​3141/​2032-04 CrossRef
11.
Akiba, T., Iwata, Y., Kawarabayashi, K., Kawata, Y.: Fast shortest-path distance queries on road networks by pruned highway labeling. In: Proceedings of the 16th Meeting on Algorithm Engineering and Experiments (ALENEX 2014), pp. 147–154. SIAM (2014)
12.
Akiba, T., Iwata, Y., Yoshida,Y.: Fast exact shortest-path distance queries on large networks by pruned landmark labeling. In: Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data (SIGMOD 2013), pp. 349–360. ACM Press (2013)
13.
Allulli, L., Italiano, G.F., Santaroni, F.: Exploiting GPS data in public transport journey planners. In: Gudmundsson, J., Katajainen, J. (eds.) SEA 2014. LNCS, vol. 8504, pp. 295–306. Springer, Heidelberg (2014). doi:10.​1007/​978-3-319-07959-2_​25
14.
Antsfeld, L., Walsh, T.: Finding multi-criteria optimal paths in multi-modal public transportation networks using the transit algorithm. In: Proceedings of the 19th ITS World Congress (2012)
15.
Arz, J., Luxen, D., Sanders, P.: Transit node routing reconsidered. In: Bonifaci, V., Demetrescu, C., Marchetti-Spaccamela, A. (eds.) SEA 2013. LNCS, vol. 7933, pp. 55–66. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-38527-8_​7 CrossRef
16.
Babenko, M., Goldberg, A.V., Gupta, A., Nagarajan, V.: Algorithms for hub label optimization. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013. LNCS, vol. 7965, pp. 69–80. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-39206-1_​7
17.
Bader, R., Dees, J., Geisberger, R., Sanders, P.: Alternative route graphs in road networks. In: Marchetti-Spaccamela, A., Segal, M. (eds.) TAPAS 2011. LNCS, vol. 6595, pp. 21–32. Springer, Heidelberg (2011). doi:10.​1007/​978-3-642-19754-3_​5 CrossRef
18.
Barrett, C., Bisset, K., Holzer, M., Konjevod, G., Marathe, M., Wagner, D.: Engineering label-constrained shortest-path algorithms. In: Fleischer, R., Xu, J. (eds.) AAIM 2008. LNCS, vol. 5034, pp. 27–37. Springer, Heidelberg (2008). doi:10.​1007/​978-3-540-68880-8_​5 CrossRef
19.
Barrett, C., Bisset, K., Holzer, M., Konjevod, G., Marathe, M.V., Wagner, D.: Engineering label-constrained shortest-path algorithms. In: The Shortest Path Problem: Ninth DIMACS Implementation Challenge, DIMACS Book, vol. 74, pp. 309–319. American Mathematical Society (2009)
20.
Barrett, C., Bisset, K., Jacob, R., Konjevod, G., Marathe, M.: Classical and contemporary shortest path problems in road networks: implementation and experimental analysis of the TRANSIMS router. In: Möhring, R., Raman, R. (eds.) ESA 2002. LNCS, vol. 2461, pp. 126–138. Springer, Heidelberg (2002). doi:10.​1007/​3-540-45749-6_​15 CrossRef
21.
22.
23.
Bast, H., Brodesser, M., Storandt, S.: Result diversity for multi-modal route planning. In: Proceedings of the 13th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS 2013), OpenAccess Series in Informatics (OASIcs), pp. 123–136 (2013)
24.
Bast, H., Carlsson, E., Eigenwillig, A., Geisberger, R., Harrelson, C., Raychev, V., Viger, F.: Fast routing in very large public transportation networks using transfer patterns. In: Berg, M., Meyer, U. (eds.) ESA 2010. LNCS, vol. 6346, pp. 290–301. Springer, Heidelberg (2010). doi:10.​1007/​978-3-642-15775-2_​25 CrossRef
25.
Bast, H., Sternisko, J., Storandt, S.: Delay-robustness of transfer patterns in public transportation route planning. In: Proceedings of the 13th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS 2013), OpenAccess Series in Informatics (OASIcs), pp. 42–54 (2013)
26.
Bast, H., Storandt, S.: Flow-based guidebook routing. In: Proceedings of the 16th Meeting on Algorithm Engineering and Experiments (ALENEX 2014), pp. 155–165. SIAM (2014)
27.
Bast, H., Storandt, S.: Frequency-based search for public transit. In: Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp. 13–22. ACM Press, November 2014
28.
Bast, H., Funke, S., Matijevic, D.: Ultrafast shortest-path queries via transit nodes. In: The Shortest Path Problem: Ninth DIMACS Implementation Challenge, DIMACS Book, vol. 74, pp. 175–192. American Mathematical Society (2009)
29.
Bast, H., Funke, S., Matijevic, D., Sanders, P., Schultes, D.: In transit to constant shortest-path queries in road networks. In: Proceedings of the 9th Workshop on Algorithm Engineering and Experiments (ALENEX 2007), pp. 46–59. SIAM (2007)
30.
Bast, H., Funke, S., Sanders, P., Schultes, D.: Fast routing in road networks with transit nodes. Science 316(5824), 566 (2007)MathSciNetMATHCrossRef
31.
Batz, G.V., Geisberger, R., Luxen, D., Sanders, P., Zubkov, R.: Efficient route compression for hybrid route planning. In: Even, G., Rawitz, D. (eds.) MedAlg 2012. LNCS, vol. 7659, pp. 93–107. Springer, Heidelberg (2012). doi:10.​1007/​978-3-642-34862-4_​7 CrossRef
32.
Batz, G.V., Geisberger, R., Sanders, P., Vetter, C.: Minimum time-dependent travel times with contraction hierarchies. ACM J. Exp. Algorithm. 18(1.4), 1–43 (2013)MathSciNetMATH
33.
Batz, G.V., Sanders, P.: Time-dependent route planning with generalized objective functions. In: Epstein, L., Ferragina, P. (eds.) ESA 2012. LNCS, vol. 7501, pp. 169–180. Springer, Heidelberg (2012). doi:10.​1007/​978-3-642-33090-2_​16 CrossRef
34.
Bauer, A.: Multimodal profile queries. Bachelor thesis, Karlsruhe Institute of Technology, May 2012
35.
Bauer, R., Baum, M., Rutter, I., Wagner, D.: On the complexity of partitioning graphs for arc-flags. J. Graph Algorithms Appl. 17(3), 265–299 (2013)MathSciNetMATHCrossRef
36.
Bauer, R., Columbus, T., Katz, B., Krug, M., Wagner, D.: Preprocessing speed-up techniques is hard. In: Calamoneri, T., Diaz, J. (eds.) CIAC 2010. LNCS, vol. 6078, pp. 359–370. Springer, Heidelberg (2010). doi:10.​1007/​978-3-642-13073-1_​32 CrossRef
37.
Bauer, R., Columbus, T., Rutter, I., Wagner, D.: Search-space size in contraction hierarchies. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013. LNCS, vol. 7965, pp. 93–104. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-39206-1_​9
38.
Bauer, R., D’Angelo, G., Delling, D., Schumm, A., Wagner, D.: The shortcut problem - complexity and algorithms. J. Graph Algorithms Appl. 16(2), 447–481 (2012)MathSciNetMATHCrossRef
39.
Bauer, R., Delling, D.: SHARC: Fast and robust unidirectional routing. ACM J. Exp. Algorithm. 14(2.4), 1–29 (2009). Special Section on Selected Papers from ALENEX 2008MathSciNetMATH
40.
Bauer, R., Delling, D., Sanders, P., Schieferdecker, D., Schultes, D., Wagner, D.: Combining hierarchical, goal-directed speed-up techniques for Dijkstra’s algorithm. ACM J. Exp. Algorithm. 15(2.3), 1–31 (2010). Special Section devoted to WEA 2008MathSciNetMATHCrossRef
41.
Bauer, R., Delling, D., Wagner, D.: Experimental study on speed-up techniques for timetable information systems. Networks 57(1), 38–52 (2011)MathSciNetCrossRef
42.
43.
Baum, M., Dibbelt, J., Hübschle-Schneider, L., Pajor, T., Wagner, D.: Speed-consumption tradeoff for electric vehicle route planning. In: Proceedings of the 14th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS 2014), OpenAccess Series in Informatics (OASIcs), pp. 138–151 (2014)
44.
Baum, M., Dibbelt, J., Pajor, T., Wagner, D.: Energy-optimal routes for electric vehicles. In: Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp. 54–63. ACM Press (2013)
45.
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)
46.
Bellman, R.: On a routing problem. Q. Appl. Math. 16, 87–90 (1958)MATH
47.
Berger, A., Delling, D., Gebhardt, A., Müller-Hannemann, M.: Accelerating time-dependent multi-criteria timetable information is harder than expected. In: Proceedings of the 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS 2009), OpenAccess Series in Informatics (OASIcs) (2009)
48.
Berger, A., Gebhardt, A., Müller-Hannemann, M., Ostrowski, M.: Stochastic delay prediction in large train networks. In: Proceedings of the 11th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS 2011), OpenAccess Series in Informatics (OASIcs), vol. 20, pp. 100–111 (2011)
49.
Berger, A., Grimmer, M., Müller-Hannemann, M.: Fully dynamic speed-up techniques for multi-criteria shortest path searches in time-dependent networks. In: Festa, P. (ed.) SEA 2010. LNCS, vol. 6049, pp. 35–46. Springer, Heidelberg (2010). doi:10.​1007/​978-3-642-13193-6_​4 CrossRef
50.
Bielli, M., Boulmakoul, A., Mouncif, H.: Object modeling and path computation for multimodal travel systems. Eur. J. Oper. Res. 175(3), 1705–1730 (2006)MATHCrossRef
51.
Böhmová, K., Mihalák, M., Pröger, T., Šrámek, R., Widmayer, P.: Robust routing in urban public transportation: how to find reliable journeys based on past observations. In: Proceedings of the 13th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS 2013), OpenAccess Series in Informatics (OASIcs), pp. 27–41 (2013)
52.
Botea, A.: Ultra-fast optimal pathfinding without runtime search. In: Proceedings of the Seventh AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE 2011), pp. 122–127. AAAI Press (2011)
53.
Botea, A., Harabor, D.: Path planning with compressed all-pairs shortest paths data. In: Proceedings of the 23rd International Conference on Automated Planning and Scheduling, AAAI Press (2013)
54.
Brandes, U., Erlebach, T.: Network Analysis: Methodological Foundations. Theoretical Computer Science and General Issues, vol. 3418. Springer, Heidelberg (2005)MATH
55.
Brandes, U., Schulz, F., Wagner, D., Willhalm, T.: Travel planning with self-made maps. In: Buchsbaum, A.L., Snoeyink, J. (eds.) ALENEX 2001. LNCS, vol. 2153, pp. 132–144. Springer, Heidelberg (2001). doi:10.​1007/​3-540-44808-X_​10 CrossRef
56.
Brodal, G., Jacob, R.: Time-dependent networks as models to achieve fast exact time-table queries. In: Proceedings of the 3rd Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS 2003), Electronic Notes in Theoretical Computer Science, vol. 92, pp. 3–15 (2004)
57.
Bruera, F., Cicerone, S., D’Angelo, G., Di Stefano, G., Frigioni, D.: Dynamic multi-level overlay graphs for shortest paths. Math. Comput. Sci. 1(4), 709–736 (2008)MathSciNetMATHCrossRef
58.
59.
60.
61.
Cherkassky, B.V., Goldberg, A.V., Radzik, T.: Shortest paths algorithms. Math. Programm. Ser. A 73, 129–174 (1996)MathSciNetMATH
62.
Cherkassky, B.V., Goldberg, A.V., Silverstein, C.: Buckets, heaps, lists, and monotone priority queues. In: Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1997), pp. 83–92. IEEE Computer Society Press (1997)
63.
Cionini, A., D’Angelo, G., D’Emidio, M., Frigioni, D., Giannakopoulou, K., Paraskevopoulos, A.: 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 2014), OpenAccess Series in Informatics (OASIcs), pp. 46–61 (2014)
64.
Cohen, E., Halperin, E., Kaplan, H., Zwick, U.: Reachability and distance queries via 2-hop labels. SIAM J. Comput. 32(5), 1338–1355 (2003)MathSciNetMATHCrossRef
65.
Cooke, K., Halsey, E.: The shortest route through a network with time-dependent intermodal transit times. J. Math. Anal. Appl. 14(3), 493–498 (1966)MathSciNetMATHCrossRef
66.
D’Angelo, G., D’Emidio, M., Frigioni, D., Vitale, C.: Fully dynamic maintenance of arc-flags in road networks. In: Klasing, R. (ed.) SEA 2012. LNCS, vol. 7276, pp. 135–147. Springer, Heidelberg (2012). doi:10.​1007/​978-3-642-30850-5_​13 CrossRef
67.
George, B.D.: Linear Programming and Extensions. Princeton University Press, Princeton (1962)
68.
Dean, B.C.: Continuous-time dynamic shortest path algorithms. Master’s thesis, Massachusetts Institute of Technology (1999)
69.
Dean, B.C.: Algorithms for minimum-cost paths in time-dependent networks with waiting policies. Networks 44(1), 41–46 (2004)MathSciNetMATHCrossRef
70.
Dean, B.C.: Shortest paths in FIFO time-dependent networks: theory and algorithms. Technical report, Massachusetts Institute Of Technology (2004)
71.
72.
73.
Delling, D., Dibbelt, J., Pajor, T., Wagner, D., Werneck, R.F.: Computing multimodal journeys in practice. In: Bonifaci, V., Demetrescu, C., Marchetti-Spaccamela, A. (eds.) SEA 2013. LNCS, vol. 7933, pp. 260–271. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-38527-8_​24 CrossRef
74.
Delling, D., Giannakopoulou, K., Wagner, D., Zaroliagis, C.: Timetable information updating in case of delays: modeling issues. Technical report 133, Arrival Technical report (2008)
75.
Delling, D., Goldberg, A.V., Nowatzyk, A., Werneck, R.F.: PHAST: Hardware-accelerated shortest path trees. J. Parallel Distrib. Comput. 73(7), 940–952 (2013)CrossRef
76.
Delling, D., Goldberg, A.V., Pajor, T., Werneck, R.F.: Customizable route planning. In: Pardalos, P.M., Rebennack, S. (eds.) SEA 2011. LNCS, vol. 6630, pp. 376–387. Springer, Heidelberg (2011). doi:10.​1007/​978-3-642-20662-7_​32 CrossRef
77.
Delling, D., Goldberg, A.V., Pajor, T., Werneck, R.F.: Robust distance queries on massive networks. In: Schulz, A.S., Wagner, D. (eds.) ESA 2014. LNCS, vol. 8737, pp. 321–333. Springer, Heidelberg (2014). doi:10.​1007/​978-3-662-44777-2_​27
78.
Delling, D., Goldberg, A.V., Pajor, T., Werneck, R.F.: Customizable route planning in road networks. Transp. Sci. (2015)
79.
Delling, D., Goldberg, A.V., Razenshteyn, I., Werneck, R.F.: Graph partitioning with natural cuts. In: 25th International Parallel and Distributed Processing Symposium (IPDPS 2011), pp. 1135–1146. IEEE Computer Society (2011)
80.
Delling, D., Goldberg, A.V., Savchenko, R., Werneck, R.F.: Hub labels: theory and practice. In: Gudmundsson, J., Katajainen, J. (eds.) SEA 2014. LNCS, vol. 8504, pp. 259–270. Springer, Heidelberg (2014). doi:10.​1007/​978-3-319-07959-2_​22
81.
Delling, D., Goldberg, A.V., Werneck, R.F.: Faster batched shortest paths in road networks. In: Proceedings of the 11th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS 2011), OpenAccess Series in Informatics (OASIcs), vol. 20, pp. 52–63 (2011)
82.
Delling, D., Goldberg, A.V., Werneck, R.F.: Hub label compression. In: Bonifaci, V., Demetrescu, C., Marchetti-Spaccamela, A. (eds.) SEA 2013. LNCS, vol. 7933, pp. 18–29. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-38527-8_​4 CrossRef
83.
Delling, D., Holzer, M., Müller, K., Schulz, F., Wagner, D., High-performance multi-level routing. In: The Shortest Path Problem: Ninth DIMACS Implementation Challenge, DIMACS Book, vol. 74, pp. 73–92. American Mathematical Society (2009)
84.
Delling, D., Italiano, G.F., Pajor, T., Santaroni, F.: Better transit routing by exploiting vehicle GPS data. In: Proceedings of the 7th ACM SIGSPATIAL International Workshop on Computational Transportation Science. ACM Press, November 2014
85.
Delling, D., Katz, B., Pajor, T.: Parallel computation of best connections in public transportation networks. ACM J. Exp. Algorithm. 17(4), 4. 1–4. 26 (2012)MathSciNetMATH
86.
Delling, D., Kobitzsch, M., Luxen, D., Werneck, R.F.: Robust mobile route planning with limited connectivity. In: Proceedings of the 14th Meeting on Algorithm Engineering and Experiments (ALENEX 2012), pp. 150–159. SIAM (2012)
87.
Delling, D., Kobitzsch, M., Werneck, R.F.: Customizing driving directions with GPUs. In: Silva, F., Dutra, I., Santos Costa, V. (eds.) Euro-Par 2014. LNCS, vol. 8632, pp. 728–739. Springer, Heidelberg (2014). doi:10.​1007/​978-3-319-09873-9_​61
88.
89.
Delling, D., Pajor, T., Wagner, D.: Accelerating multi-modal route planning by access-nodes. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol. 5757, pp. 587–598. Springer, Heidelberg (2009). doi:10.​1007/​978-3-642-04128-0_​53 CrossRef
90.
Delling, D., Pajor, T., Wagner, D.: Engineering time-expanded graphs for faster timetable information. In: Ahuja, R.K., Möhring, R.H., Zaroliagis, C.D. (eds.) Robust and Online Large-Scale Optimization. LNCS, vol. 5868, pp. 182–206. Springer, Heidelberg (2009). doi:10.​1007/​978-3-642-05465-5_​7 CrossRef
91.
Delling, D., Pajor, T., Wagner, D., Zaroliagis, C.: Efficient route planning in flight networks. In: Proceedings of the 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS 2009), OpenAccess Series in Informatics (OASIcs) (2009)
92.
Delling, D., Pajor, T., Werneck, R.F.: Round-based public transit routing. In: Proceedings of the 14th Meeting on Algorithm Engineering and Experiments (ALENEX 2012), pp. 130–140. SIAM (2012)
93.
Delling, D., Pajor, T., Werneck, R.F.: Round-based public transit routing. Transp. Sci. 49, 591–604 (2014)CrossRef
94.
Delling, D., Sanders, P., Schultes, D., Wagner, D.: Engineering route planning algorithms. In: Lerner, J., Wagner, D., Zweig, K.A. (eds.) Algorithmics of Large and Complex Networks. LNCS, vol. 5515, pp. 117–139. Springer, Heidelberg (2009). doi:10.​1007/​978-3-642-02094-0_​7 CrossRef
95.
Delling, D., Sanders, P., Schultes, D., Wagner, D.: Highway hierarchies star. In: The Shortest Path Problem: Ninth DIMACS Implementation Challenge, DIMACS Book, vol. 74, pp. 141–174. American Mathematical Society (2009)
96.
97.
98.
Delling, D., Wagner, D.: Time-dependent route planning. In: Ahuja, R.K., Möhring, R.H., Zaroliagis, C.D. (eds.) Robust and Online Large-Scale Optimization. LNCS, vol. 5868, pp. 207–230. Springer, Heidelberg (2009). doi:10.​1007/​978-3-642-05465-5_​8 CrossRef
99.
Delling, D., Werneck, R.F.: Customizable point-of-interest queries in road networks. In: Proceedings of the 21st ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems (GIS 2013), pp. 490–493. ACM Press (2013)
100.
Delling, D., Werneck, R.F.: Faster customization of road networks. In: Bonifaci, V., Demetrescu, C., Marchetti-Spaccamela, A. (eds.) SEA 2013. LNCS, vol. 7933, pp. 30–42. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-38527-8_​5 CrossRef
101.
Demetrescu, C., Goldberg, A.V., Johnson, D.S. (eds.): The Shortest Path Problem: Ninth DIMACS Implementation Challenge, DIMACS Book, vol. 74. American Mathematical Society, Providence (2009)MATH
102.
Demiryurek, U., Banaei-Kashani, F., Shahabi, C.: A case for time-dependent shortest path computation in spatial networks. In: Proceedings of the 18th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS 2010), pp. 474–477 (2010)
103.
104.
Dial, R.B.: Algorithm 360: shortest-path forest with topological ordering [H]. Commun. ACM 12(11), 632–633 (1969)CrossRef
105.
Dibbelt, J., Pajor, T., Strasser, B., Wagner, D.: Intriguingly simple and fast transit routing. In: Bonifaci, V., Demetrescu, C., Marchetti-Spaccamela, A. (eds.) SEA 2013. LNCS, vol. 7933, pp. 43–54. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-38527-8_​6 CrossRef
106.
Dibbelt, J., Pajor, T., Wagner, D.: User-constrained multi-modal route planning. In: Proceedings of the 14th Meeting on Algorithm Engineering and Experiments (ALENEX 2012), pp. 118–129. SIAM (2012)
107.
Dibbelt, J., Strasser, B., Wagner, D.: Customizable contraction hierarchies. In: Gudmundsson, J., Katajainen, J. (eds.) SEA 2014. LNCS, vol. 8504, pp. 271–282. Springer, Heidelberg (2014). doi:10.​1007/​978-3-319-07959-2_​23
108.
109.
Disser, Y., Müller–Hannemann, M., Schnee, M.: Multi-criteria shortest paths in time-dependent train networks. In: McGeoch, C.C. (ed.) WEA 2008. LNCS, vol. 5038, pp. 347–361. Springer, Heidelberg (2008). doi:10.​1007/​978-3-540-68552-4_​26 CrossRef
110.
Drews, F., Luxen, D.: Multi-hop ride sharing. In: Proceedings of the 5th International Symposium on Combinatorial Search (SoCS 2012), pp. 71–79. AAAI Press (2013)
111.
Dreyfus, S.E.: An appraisal of some shortest-path algorithms. Oper. Res. 17(3), 395–412 (1969)MATHCrossRef
112.
Efentakis, A., Pfoser, D.: Optimizing landmark-based routing and preprocessing. In: Proceedings of the 6th ACM SIGSPATIAL International Workshop on Computational Transportation Science, pp. 25:25–25:30. ACM Press, November 2013
113.
Efentakis, A., Pfoser, D.: GRASP. Extending graph separators for the single-source shortest-path problem. In: Schulz, A.S., Wagner, D. (eds.) ESA 2014. LNCS, vol. 8737, pp. 358–370. Springer, Heidelberg (2014). doi:10.​1007/​978-3-662-44777-2_​30
114.
Efentakis, A., Pfoser, D., Vassiliou., Y.: SALT: a unified framework for all shortest-path query variants on road networks. CoRR, abs/1411.0257 (2014)
115.
Efentakis, A., Pfoser, D., Voisard, A.: Efficient data management in support of shortest-path computation. In: Proceedings of the 4th ACM SIGSPATIAL International Workshop on Computational Transportation Science, pp. 28–33. ACM Press (2011)
116.
Efentakis, A., Theodorakis, D., Pfoser,D.: Crowdsourcing computing resources for shortest-path computation. In: Proceedings of the 20th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems (GIS 2012), pp. 434–437. ACM Press (2012)
117.
Ehrgott, M., Gandibleux, X.: Multiple Criteria Optimization: State of the Art Annotated Bibliographic Surveys. Kluwer Academic Publishers Group, New York (2002)MATH
118.
Eisenstat, D.: Random road networks: the quadtree model. In: Proceedings of the Eighth Workshop on Analytic Algorithmics and Combinatorics (ANALCO 2011), pp. 76–84. SIAM, January 2011
119.
Eisner, J., Funke, S.: Sequenced route queries: getting things done on the way back home. In: Proceedings of the 20th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems (GIS 2012), pp. 502–505. ACM Press (2012)
120.
Eisner, J., Funke, S.: Transit nodes - lower bounds and refined construction. In: Proceedings of the 14th Meeting on Algorithm Engineering and Experiments (ALENEX 2012), pp. 141–149. SIAM (2012)
121.
Eisner, J., Funke, S., Herbst, A., Spillner, A., Storandt, S.: Algorithms for matching and predicting trajectories. In: Proceedings of the 13th Workshop on Algorithm Engineering and Experiments (ALENEX 2011), pp. 84–95. SIAM (2011)
122.
Eisner, J., Funke, S., Storandt, S.: Optimal route planning for electric vehicles in large network. In: Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence. AAAI Press, August 2011
123.
Eppstein, D., Goodrich, M.T.: Studying (non-planar) road networks through an algorithmic lens. In: Proceedings of the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS 2008), pp. 1–10. ACM Press (2008)
124.
Erb, S., Kobitzsch, M., Sanders, P.: Parallel bi-objective shortest paths using weight-balanced B-trees with bulk updates. In: Gudmundsson, J., Katajainen, J. (eds.) SEA 2014. LNCS, vol. 8504, pp. 111–122. Springer, Heidelberg (2014). doi:10.​1007/​978-3-319-07959-2_​10
125.
Firmani, D., Italiano, G.F., Laura, L., Santaroni, F.: Is timetabling routing always reliable for public transport? In: Proceedings of the 13th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS 2013), OpenAccess Series in Informatics (OASIcs), pp. 15–26 (2013)
126.
Floyd, R.W.: Algorithm 97: shortest path. Commun. ACM 5(6), 345 (1962)CrossRef
127.
Ford, Jr., L.R.: Network flow theory. Technical report P-923, Rand Corporation, Santa Monica, California (1956)
128.
Foschini, L., Hershberger, J., Suri, S.: On the complexity of time-dependent shortest paths. Algorithmica 68(4), 1075–1097 (2014)MathSciNetMATHCrossRef
129.
Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34(3), 596–615 (1987)MathSciNetCrossRef
130.
Fu, L., Sun, D., Rilett, L.R.: Heuristic shortest path algorithms for transportation applications: state of the art. Comput. Oper. Res. 33(11), 3324–3343 (2006)MATHCrossRef
131.
Funke, S., Nusser, A., Storandt, S.: On k-path covers and their applications. In: Proceedings of the 40th International Conference on Very Large Databases (VLDB 2014), pp. 893–902 (2014)
132.
Funke, S., Nusser, A., Storandt, S.: Placement of loading stations for electric vehicles: no detours necessary! In: Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence. AAAI Press (2014)
133.
Funke, S., Storandt, S.: Polynomial-time construction of contraction hierarchies for multi-criteria objectives. In: Proceedings of the 15th Meeting on Algorithm Engineering and Experiments (ALENEX 2013), pp. 31–54. SIAM (2013)
134.
Gavoille, C., Peleg, D.: Compact and localized distributed data structures. Distrib. Comput. 16(2–3), 111–120 (2003)CrossRef
135.
136.
137.
Geisberger, R.: Advanced route planning in transportation networks. Ph.D. thesis, Karlsruhe Institute of Technology, February 2011
138.
Geisberger, R., Kobitzsch, M., Sanders, P.: Route planning with flexible objective functions. In: Proceedings of the 12th Workshop on Algorithm Engineering and Experiments (ALENEX 2010), pp. 124–137. SIAM (2010)
139.
Geisberger, R., Luxen, D., Sanders, P., Neubauer, S., Volker, L.: Fast detour computation for ride sharing. In: Proceedings of the 10th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS 2010), OpenAccess Series in Informatics (OASIcs), vol. 14, pp. 88–99 (2010)
140.
Geisberger, R., Rice, M., Sanders, P., Tsotras, V.: Route planning with flexible edge restrictions. ACM J. Exp. Algorithm. 17(1), 1–20 (2012)MathSciNetMATH
141.
Geisberger, R., Sanders, P.: Engineering time-dependent many-to-many shortest paths computation. In: Proceedings of the 10th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS 2010), OpenAccess Series in Informatics (OASIcs), vol. 14 (2010)
142.
Geisberger, R., Sanders, P., Schultes, D., Vetter, C.: Exact routing in large road networks using contraction hierarchies. Transp. Sci. 46(3), 388–404 (2012)CrossRef
143.
Geisberger, R., Schieferdecker, D.: Heuristic contraction hierarchies with approximation guarantee. In: Proceedings of the 3rd International Symposium on Combinatorial Search (SoCS 2010). AAAI Press (2010)
144.
Geisberger, R., Vetter, C.: Efficient routing in road networks with turn costs. In: Pardalos, P.M., Rebennack, S. (eds.) SEA 2011. LNCS, vol. 6630, pp. 100–111. Springer, Heidelberg (2011). doi:10.​1007/​978-3-642-20662-7_​9 CrossRef
145.
Goerigk, M., Heße, S., Müller-Hannemann, M., Schmidt, M.: Recoverable robust timetable information. In: Proceedings of the 13th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS 2013), OpenAccess Series in Informatics (OASIcs), pp. 1–14 (2013)
146.
Goerigk, M., Knoth, M., Müller-Hannemann, M., Schmidt, M., Schöbel, A.: The price of strict and light robustness in timetable information. Transp. Sci. 48, 225–242 (2014)MATHCrossRef
147.
148.
Goldberg, A.V., Harrelson, C.: Computing the shortest path: A* search meets graph theory. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), pp. 156–165. SIAM (2005)
149.
Goldberg, A.V., Kaplan, H., Werneck, R.F.: Reach for A*: shortest path algorithms with preprocessing. In: The Shortest Path Problem: Ninth DIMACS Implementation Challenge, DIMACS Book, vol. 74, pp. 93–139. American Mathematical Society (2009)
150.
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)
151.
Goldman, R., Shivakumar, N.R., Venkatasubramanian, S., Garcia-Molina, H.: Proximity search in databases. In: Proceedings of the 24th International Conference on Very Large Databases (VLDB 1998), pp. 26–37. Morgan Kaufmann, August 1998
152.
Goodrich, M.T., Pszona, P.: Two-phase bicriterion search for finding fast and efficient electric vehicle routes. In: Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. ACM Press, November 2014
153.
154.
Gutman, R.J., Reach-based routing: a new approach to shortest path algorithms optimized for road networks. In: Proceedings of the 6th Workshop on Algorithm Engineering and Experiments (ALENEX 2004), pp. 100–111. SIAM (2004)
155.
Hansen, P.: Bricriteria path problems. In: Fandel, G., Gal, T. (eds.) Multiple Criteria Decision Making - Theory and Application. LNEMS, vol. 177, pp. 109–127. Springer, Heidelberg (1979). doi:10.​1007/​978-3-642-48782-8_​9 CrossRef
156.
Hart, P.E., Nilsson, N., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern. 4, 100–107 (1968)CrossRef
157.
Hilger, M., Köhler, E., Möhring, R.H., Schilling, H., Fast point-to-point shortest path computations with arc-flags. In: The Shortest Path Problem: Ninth DIMACS Implementation Challenge, DIMACS Book, vol. 74, pp. 41–72. American Mathematical Society (2009)
158.
159.
Holzer, M.: Engineering planar-separator and shortest-path algorithms. Ph.D. thesis, Karlsruhe Institute of Technology (KIT) - Department of Informatics (2008)
160.
Holzer, M., Schulz, F., Wagner, D.: Engineering multilevel overlay graphs for shortest-path queries. ACM J. Exp. Algorithm. 13(2.5), 1–26 (2008)MathSciNetMATH
161.
Holzer, M., Schulz, F., Wagner, D., Willhalm, T.: Combining speed-up techniques for shortest-path computations. ACM J. Exp. Algorithm. 10(2.5), 1–18 (2006)MathSciNetMATH
162.
Horvitz, E., Krumm, J.: Some help on the way: opportunistic routing under uncertainty. In: Proceedings of the 2012 ACM Conference on Ubiquitous Computing (Ubicomp 2012), pp. 371–380. ACM Press (2012)
163.
Ikeda, T., Hsu, M.-Y., Imai, H., Nishimura, S., Shimoura, H., Hashimoto, T., Tenmoku, K., Mitoh, K.: A fast algorithm for finding better routes by AI search techniques. In: Proceedings of the Vehicle Navigation and Information Systems Conference (VNSI 1994), pp. 291–296. ACM Press (1994)
164.
Jing, N., Huang, Y.-W., Rundensteiner, E.A.: Hierarchical encoded path views for path query processing: an optimal model and its performance evaluation. IEEE Trans. Knowl. Data Eng. 10(3), 409–432 (1998)CrossRef
165.
Jung, S., Pramanik, S.: An efficient path computation model for hierarchically structured topographical road maps. IEEE Trans. Knowl. Data Eng. 14(5), 1029–1046 (2002)CrossRef
166.
Kaindl, H., Kainz, G.: Bidirectional heuristic search reconsidered. J. Artif. Intell. Res. 7, 283–317 (1997)MathSciNetMATH
167.
Kaufmann, H.: Towards mobile time-dependent route planning. Bachelor thesis, Karlsruhe Institute of Technology (2013)
168.
Kieritz, T., Luxen, D., Sanders, P., Vetter, C.: Distributed time-dependent contraction hierarchies. In: Festa, P. (ed.) SEA 2010. LNCS, vol. 6049, pp. 83–93. Springer, Heidelberg (2010). doi:10.​1007/​978-3-642-13193-6_​8 CrossRef
169.
Kirchler, D., Liberti, L., Wolfler Calvo, R.: A label correcting algorithm for the shortest path problem on a multi-modal route network. In: Klasing, R. (ed.) SEA 2012. LNCS, vol. 7276, pp. 236–247. Springer, Heidelberg (2012). doi:10.​1007/​978-3-642-30850-5_​21 CrossRef
170.
Kirchler, D., Liberti, L., Pajor, T., Calvo, R.W.: UniALT for regular language constraint shortest paths on a multi-modal transportation network. In: Proceedings of the 11th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS 2011), OpenAccess Series in Informatics (OASIcs), vol. 20, pp. 64–75 (2011)
171.
Kleinberg, J.M., Slivkins, A., Wexler, T.: Triangulation and embedding using small sets of beacons. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2004), pp. 444–453. IEEE Computer Society Press (2004)
172.
Knopp, S., Sanders, P., Schultes, D., Schulz, F., Wagner, D.: Computing many-to-many shortest paths using highway hierarchies. In: Proceedings of the 9th Workshop on Algorithm Engineering and Experiments (ALENEX 2007), pp. 36–45. SIAM (2007)
173.
174.
Kobitzsch, M., Radermacher, M., Schieferdecker, D.: Evolution and evaluation of the penalty method for alternative graphs. In: Proceedings of the 13th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS 2013), OpenAccess Series in Informatics (OASIcs), pp. 94–107 (2013)
175.
Kontogiannis, S., Zaroliagis, C.: Distance oracles for time-dependent networks. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8572, pp. 713–725. Springer, Heidelberg (2014). doi:10.​1007/​978-3-662-43948-7_​59
176.
Krumm, J., Gruen, R., Delling, D.: From destination prediction to route prediction. J. Locat. Based Serv. 7(2), 98–120 (2013)CrossRef
177.
Krumm, J., Horvitz, E.: Predestination: where do you want to go today? IEEE Comput. 40(4), 105–107 (2007)CrossRef
178.
Lauther, U.: An experimental evaluation of point-to-point shortest path calculation on roadnetworks with precalculated edge-flags. In: The Shortest Path Problem: Ninth DIMACS Implementation Challenge, vol. 74, DIMACS Book, pp. 19–40. American Mathematical Society (2009)
179.
Ken, C.K., Lee, J.L., Zheng, B., Tian, Y.: ROAD: a new spatial object search framework for road networks. IEEE Trans. Knowl. Data Eng. 24(3), 547–560 (2012)CrossRef
180.
181.
182.
183.
Luxen, D., Sanders, P.: Hierarchy decomposition for faster user equilibria on road networks. In: Pardalos, P.M., Rebennack, S. (eds.) SEA 2011. LNCS, vol. 6630, pp. 242–253. Springer, Heidelberg (2011). doi:10.​1007/​978-3-642-20662-7_​21 CrossRef
184.
185.
Luxen, D., Vetter, C.: Real-time routing with OpenStreetMap data. In: Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. ACM Press (2011)
186.
Madduri, K., Bader, D.A., Berry, J.W., Crobak, J.R., Parallel shortest path algorithms for solving large-scale instances. In: The Shortest Path Problem: Ninth DIMACS Implementation Challenge, DIMACS Book, vol. 74, pp. 249–290. American Mathematical Society (2009)
187.
188.
Maue, J., Sanders, P., Matijevic, D.: Goal-directed shortest-path queries using precomputed cluster distances. ACM J. Exp. Algorithm. 14, 3.2:1–3.2:27 (2009)MathSciNetMATH
189.
Mehlhorn, K.: A faster approximation algorithm for the Steiner problem in graphs. Inf. Process. Lett. 27(3), 125–128 (1988)MathSciNetMATHCrossRef
190.
Mehlhorn, K., Sanders, P., Algorithms, D.S.: The Basic Toolbox. Springer, Heidelberg (2008)MATH
191.
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)
192.
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)
193.
Meyer, U., Sanders, P.: \(\delta \)-stepping: a parallelizable shortest path algorithm. J. Algorithms 49(1), 114–152 (2003)MathSciNetMATHCrossRef
194.
Milosavljević, N.: On optimal preprocessing for contraction hierarchies. In: Proceedings of the 5th ACM SIGSPATIAL International Workshop on Computational Transportation Science, pp. 33–38. ACM Press (2012)
195.
Modesti, P., Sciomachen, A.: A utility measure for finding multiobjective shortest paths in urban multimodal transportation networks. Eur. J. Oper. Res. 111(3), 495–508 (1998)MATHCrossRef
196.
Möhring, R.H.: Verteilte Verbindungssuche im öffentlichen Personenverkehr - Graphentheoretische Modelle und Algorithmen. In: Angewandte Mathematik insbesondere Informatik, Beispiele erfolgreicher Wege zwischen Mathematik und Informatik, pp. 192–220. Vieweg (1999)
197.
Möhring, R.H., Schilling, H., Schütz, B., Wagner, D., Willhalm, T.: Partitioning graphs to speedup Dijkstra’s algorithm. ACM J. Exp. Algorithm. 11(28), 1–29 (2006)MATH
198.
Moore, E.F.: The shortest path through a maze. In: Proceedings of the International Symposium on the Theory of Switching, pp. 285–292. Harvard University Press (1959)
199.
Müller-Hannemann, M., Schnee, M.: Paying less for train connections with MOTIS. In: Proceedings of the 5th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS 2005), OpenAccess Series in Informatics (OASIcs), p. 657 (2006)
200.
Müller-Hannemann, M., Schnee, M.: Finding all attractive train connections by multi-criteria pareto search. In: Geraets, F., Kroon, L., Schoebel, A., Wagner, D., Zaroliagis, C.D. (eds.) Algorithmic Methods for Railway Optimization. LNCS, vol. 4359, pp. 246–263. Springer, Heidelberg (2007). doi:10.​1007/​978-3-540-74247-0_​13 CrossRef
201.
Müller-Hannemann, M., Schnee, M.: Efficient timetable information in the presence of delays. In: Ahuja, R.K., Möhring, R.H., Zaroliagis, C.D. (eds.) Robust and Online Large-Scale Optimization. LNCS, vol. 5868, pp. 249–272. Springer, Heidelberg (2009). doi:10.​1007/​978-3-642-05465-5_​10 CrossRef
202.
Müller-Hannemann, M., Schnee, M., Weihe, K.: Getting train timetables into the main storage. Electron. Notes Theoret. Comput. Sci. 66(6), 8–17 (2002)CrossRef
203.
Müller-Hannemann, M., Schulz, F., Wagner, D., Zaroliagis, C.: Timetable information: models and algorithms. In: Geraets, F., Kroon, L., Schoebel, A., Wagner, D., Zaroliagis, C.D. (eds.) Algorithmic Methods for Railway Optimization. LNCS, vol. 4359, pp. 67–90. Springer, Heidelberg (2007). doi:10.​1007/​978-3-540-74247-0_​3 CrossRef
204.
Müller-Hannemann, M., Weihe, K.: Pareto shortest paths is often feasible in practice. In: Brodal, G.S., Frigioni, D., Marchetti-Spaccamela, A. (eds.) WAE 2001. LNCS, vol. 2141, pp. 185–197. Springer, Heidelberg (2001). doi:10.​1007/​3-540-44688-5_​15 CrossRef
205.
Muller, L.F., Zachariasen, M.: Fast and compact oracles for approximate distances in planar graphs. In: Arge, L., Hoffmann, M., Welzl, E. (eds.) ESA 2007. LNCS, vol. 4698, pp. 657–668. Springer, Heidelberg (2007). doi:10.​1007/​978-3-540-75520-3_​58 CrossRef
206.
Nachtigall, K.: Time depending shortest-path problems with applications to railway networks. Eur. J. Oper. Res. 83(1), 154–166 (1995)MATHCrossRef
207.
Nannicini, G., Delling, D., Liberti, L., Schultes, D.: Bidirectional A* search on time-dependent road networks. Networks 59, 240–251 (2012). Best Paper AwardMathSciNetMATHCrossRef
208.
Orda, A., Rom, R.: Shortest-path and minimum delay algorithms in networks with time-dependent edge-length. J. ACM 37(3), 607–625 (1990)MathSciNetMATHCrossRef
209.
210.
Pajor, T.: Multi-modal route planning. Master’s thesis, Universität Karlsruhe (TH), March 2009
211.
Pallottino, S., Scutellà, M.G.: Shortest path algorithms in transportation models: Classical and innovative aspects. In: Equilibrium and Advanced Transportation Modelling, pp. 245–281. Kluwer Academic Publishers Group (1998)
212.
Papadimitriou, C.H., Yannakakis, M.: On the approximability of trade-offs and optimal access of web sources. In: Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2000), pp. 86–92 (2000)
213.
Paraskevopoulos, A., Zaroliagis, C.: Improved alternative route planning. In: Proceedings of the 13th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS 2013), OpenAccess Series in Informatics (OASIcs), pp. 108–122 (2013)
214.
215.
216.
Pohl, I.: Bi-directional and heuristic search in path problems. Technical report SLAC-104, Stanford Linear Accelerator Center, Stanford, California (1969)
217.
Pohl, I.: Bi-directional search. In: Proceedings of the Sixth Annual Machine Intelligence Workshop, vol. 6, pp. 124–140. Edinburgh University Press (1971)
218.
Pyrga, E., Schulz, F., Wagner, D., Zaroliagis, C.: Experimental comparison of shortest path approaches for timetable information. In: Proceedings of the 6th Workshop on Algorithm Engineering and Experiments (ALENEX 2004), pp. 88–99. SIAM (2004)
219.
Pyrga, E., Schulz, F., Wagner, D., Zaroliagis, C.: Efficient models for timetable information in public transportation systems. ACM J. Exp. Algorithm. 12(24), 1–39 (2008)MathSciNetMATHCrossRef
220.
Rice, M., Tsotras, V.: Bidirectional A* search with additive approximation bounds. In: Proceedings of the 5th International Symposium on Combinatorial Search (SoCS 2012), AAAI Press (2012)
221.
Rice, M.N., Tsotras, V.J.: Exact graph search algorithms for generalized traveling salesman path problems. In: Klasing, R. (ed.) SEA 2012. LNCS, vol. 7276, pp. 344–355. Springer, Heidelberg (2012). doi:10.​1007/​978-3-642-30850-5_​30 CrossRef
222.
Sanders, P., Mandow, L.: Parallel label-setting multi-objective shortest path search. In: 27th International Parallel and Distributed Processing Symposium (IPDPS 2013), pp. 215–224. IEEE Computer Society (2013)
223.
Sanders, P., Schultes, D.: Highway hierarchies hasten exact shortest path queries. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol. 3669, pp. 568–579. Springer, Heidelberg (2005). doi:10.​1007/​11561071_​51 CrossRef
224.
Sanders, P., Schultes, D.: Robust, almost constant time shortest-path queries in road networks. In: The Shortest Path Problem: Ninth DIMACS Implementation Challenge, DIMACS Book, vol. 74, pp. 193–218. American Mathematical Society (2009)
225.
Sanders, P., Schultes, D.: Engineering highway hierarchies. ACM J. Exp. Algorithm. 17(1), 1–40 (2012)MathSciNetMATH
226.
227.
Sanders, P., Schulz, C.: Distributed evolutionary graph partitioning. In: Proceedings of the 14th Meeting on Algorithm Engineering and Experiments (ALENEX 2012), pp. 16–29. SIAM (2012)
228.
Sankaranarayanan, J., Alborzi, H., Samet, H.: Efficient query processing on spatial networks. In: Proceedings of the 13th Annual ACM International Workshop on Geographic Information Systems (GIS 2005), pp. 200–209 (2005)
229.
Sankaranarayanan, J., Samet, H.: Query processing using distance oracles for spatial networks. IEEE Trans. Knowl. Data Eng. 22(8), 1158–1175 (2010)CrossRef
230.
Sankaranarayanan, J., Samet, H.: Roads belong in databases. IEEE Data Eng. Bull. 33(2), 4–11 (2010)
231.
Schilling, H.: TomTom navigation - How mathematics help getting through traffic faster (2012). Talk given at ISMP
232.
233.
Schultes, D.: Route planning in road networks. Ph.D. thesis, Universität Karlsruhe (TH), February 2008
234.
235.
Schulz, F., Wagner, D., Weihe, K.: Dijkstra’s algorithm on-line: an empirical case study from public railroad transport. ACM J. Exp. Algorithm. 5(12), 1–23 (2000)MathSciNetMATH
236.
Schulz, F., Wagner, D., Zaroliagis, C.: Using multi-level graphs for timetable information in railway systems. In: Mount, D.M., Stein, C. (eds.) ALENEX 2002. LNCS, vol. 2409, pp. 43–59. Springer, Heidelberg (2002). doi:10.​1007/​3-540-45643-0_​4 CrossRef
237.
238.
Sommer, C.: Shortest-path queries in static networks. ACM Comput. Surv. 46(4), 1–31 (2014)MATHCrossRef
239.
Storandt, S.: Route planning for bicycles - exact constrained shortest paths made practical via contraction hierarchy. In: Proceedings of the Twenty-Second International Conference on Automated Planning and Scheduling, pp. 234–242 (2012)
240.
Storandt, S., Funke, S.: Cruising with a battery-powered vehicle and not getting stranded. In: Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence. AAAI Press (2012)
241.
Storandt, S., Funke, S.: Enabling e-mobility: facility location for battery loading stations. In: Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence. AAAI Press (2013)
242.
Strasser, B., Wagner, D.: Connection scan accelerated. In: Proceedings of the 16th Meeting on Algorithm Engineering and Experiments (ALENEX 2014), pp. 125–137. SIAM (2014)
243.
Theune, D.: Robuste und effiziente Methoden zur Lösung von Wegproblemen. Ph.D. thesis, Universität Paderborn (1995)
244.
Thorup, M.: Integer priority queues with decrease key in constant time and the single source shortest paths problem. In: 35th ACM Symposium on Theory of Computing, pp. 149–158. ACM, New York (2003)
245.
246.
Tsaggouris, G., Zaroliagis, C.: Multiobjective optimization: improved FPTAS for shortest paths and non-linear objectives with applications. Theory Comput. Syst. 45(1), 162–186 (2009)MathSciNetMATHCrossRef
247.
Tulp, E., Siklóssy, L.: TRAINS, an active time-table searcher. ECAI 88, 170–175 (1988)
248.
Tulp, E., Siklóssy, L.: Searching time-table networks. Artif. Intell. Eng. Des. Anal. Manuf. 5(3), 189–198 (1991)CrossRef
249.
van Vliet, D.: Improved shortest path algorithms for transport networks. Transp. Res. Part B: Methodol. 12(1), 7–20 (1978)
250.
Wagner, D., Willhalm, T.: Drawing graphs to speed up shortest-path computations. In: Proceedings of the 7th Workshop on Algorithm Engineering and Experiments (ALENEX 2005), pp. 15–24. SIAM (2005)
251.
Wagner, D., Willhalm, T., Zaroliagis, C.: Geometric containers for efficient shortest-path computation. ACM J. Exp. Algorithm. 10(1.3), 1–30 (2005)MathSciNetMATH
252.
Weller, M.: Optimal hub labeling is NP-complete. CoRR, abs/1407.8373 (2014)
253.
254.
Williams, J.W.J.: Algorithm 232: heapsort. J. ACM 7(6), 347–348 (1964)
255.
Winter, S.: Modeling costs of turns in route planning. GeoInformatica 6(4), 345–361 (2002)MATHCrossRef
256.
257.
Lingkun, W., Xiao, X., Deng, D., Cong, G., Zhu, A.D., Zhou, S.: Shortest path and distance queries on road networks: an experimental evaluation. Proc. VLDB Endow. 5(5), 406–417 (2012)CrossRef
258.
Yu, H., Lu, F.: Advanced multi-modal routing approach for pedestrians. In: 2nd International Conference on Consumer Electronics, Communications and Networks, pp. 2349–2352 (2012)
259.
260.
Zhong, R., Li, G., Tan, K.-L., Zhou, L.: G-tree: an efficient index for KNN search on road networks. In: Proceedings of the 22nd International Conference on Information and Knowledge Management, pp. 39–48. ACM Press (2013)
261.
Zhu, A.D., Ma, H., Xiao, X., Luo, S., Tang, Y., Zhou, S.: Shortest path, distance queries on road networks: towards bridging theory and practice. In: Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data (SIGMOD 2013), pp. 857–868. ACM Press (2013)
262.
Metadaten
Titel
Route Planning in Transportation Networks
verfasst von
Hannah Bast
Daniel Delling
Andrew Goldberg
Matthias Müller-Hannemann
Thomas Pajor
Peter Sanders
Dorothea Wagner
Renato F. Werneck
Copyright-Jahr
2016
Buch
Algorithm Engineering

Print ISBN: 978-3-319-49486-9

Electronic ISBN: 978-3-319-49487-6

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-319-49487-6_2