Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Route Planning in Transportation Networks

  • Chapter
  • First Online:
Algorithm Engineering

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 9220))

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.

This work was mostly done while the authors Daniel Delling, Andrew Goldberg, and Renato F. Werneck were at Microsoft Research Silicon Valley.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

eBook
USD 15.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 15.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    The reader is referred to Sommer [238] for a similar plot (which inspired ours) relating query times to preprocessing space.

  2. 2.

    https://developers.google.com/transit/gtfs/.

  3. 3.

    http://data.london.gov.uk/.

  4. 4.

    http://www.bing.com/blogs/site_blogs/b/maps/archive/2012/01/05/bing-maps-new-routing-engine.aspx.

  5. 5.

    http://www.google.com/transit.

  6. 6.

    http://opentripplanner.com.

  7. 7.

    http://www.rome2rio.com.

References

  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

    Chapter  Google Scholar 

  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

    Google Scholar 

  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)

    Google Scholar 

  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

    Chapter  Google Scholar 

  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

    Chapter  Google Scholar 

  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)

    MathSciNet  MATH  Google Scholar 

  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)

    Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  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

    Article  Google Scholar 

  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)

    Google Scholar 

  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)

    Google Scholar 

  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

    Google Scholar 

  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)

    Google Scholar 

  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

    Chapter  Google Scholar 

  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

    Google Scholar 

  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

    Chapter  Google Scholar 

  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

    Chapter  Google Scholar 

  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)

    Google Scholar 

  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

    Chapter  Google Scholar 

  21. Barrett, C., Jacob, R., Marathe, M.V.: Formal-language-constrained path problems. SIAM J. Comput. 30(3), 809–837 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  22. Bast, H.: Car or public transport—two worlds. In: Albers, S., Alt, H., Näher, S. (eds.) Efficient Algorithms. LNCS, vol. 5760, pp. 355–367. Springer, Heidelberg (2009). doi:10.1007/978-3-642-03456-5_24

    Chapter  Google Scholar 

  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)

    Google Scholar 

  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

    Chapter  Google Scholar 

  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)

    Google Scholar 

  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)

    Google Scholar 

  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

    Google Scholar 

  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)

    Google Scholar 

  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)

    Google Scholar 

  30. Bast, H., Funke, S., Sanders, P., Schultes, D.: Fast routing in road networks with transit nodes. Science 316(5824), 566 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  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

    Chapter  Google Scholar 

  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)

    MathSciNet  MATH  Google Scholar 

  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

    Chapter  Google Scholar 

  34. Bauer, A.: Multimodal profile queries. Bachelor thesis, Karlsruhe Institute of Technology, May 2012

    Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  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

    Chapter  Google Scholar 

  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

    Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  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 2008

    MathSciNet  MATH  Google Scholar 

  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 2008

    Article  MathSciNet  MATH  Google Scholar 

  41. Bauer, R., Delling, D., Wagner, D.: Experimental study on speed-up techniques for timetable information systems. Networks 57(1), 38–52 (2011)

    Article  MathSciNet  Google Scholar 

  42. Bauer, R., Krug, M., Meinert, S., Wagner, D.: Synthetic road networks. In: Chen, B. (ed.) AAIM 2010. LNCS, vol. 6124, pp. 46–57. Springer, Heidelberg (2010). doi:10.1007/978-3-642-14355-7_6

    Chapter  Google Scholar 

  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)

    Google Scholar 

  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)

    Google Scholar 

  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)

    Google Scholar 

  46. Bellman, R.: On a routing problem. Q. Appl. Math. 16, 87–90 (1958)

    MATH  Google Scholar 

  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)

    Google Scholar 

  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)

    Google Scholar 

  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

    Chapter  Google Scholar 

  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)

    Article  MATH  Google Scholar 

  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)

    Google Scholar 

  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)

    Google Scholar 

  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)

    Google Scholar 

  54. Brandes, U., Erlebach, T.: Network Analysis: Methodological Foundations. Theoretical Computer Science and General Issues, vol. 3418. Springer, Heidelberg (2005)

    MATH  Google Scholar 

  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

    Chapter  Google Scholar 

  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)

    Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  58. Brunel, E., Delling, D., Gemsa, A., Wagner, D.: Space-efficient SHARC-routing. In: Festa, P. (ed.) SEA 2010. LNCS, vol. 6049, pp. 47–58. Springer, Heidelberg (2010). doi:10.1007/978-3-642-13193-6_5

    Chapter  Google Scholar 

  59. Caldwell, T.: On finding minimum routes in a network with turn penalties. Commun. ACM 4(2), 107–108 (1961)

    Article  MathSciNet  MATH  Google Scholar 

  60. Cambridge Vehicle Information Technology Ltd. Choice routing (2005). http://www.camvit.com

  61. Cherkassky, B.V., Goldberg, A.V., Radzik, T.: Shortest paths algorithms. Math. Programm. Ser. A 73, 129–174 (1996)

    MathSciNet  MATH  Google Scholar 

  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)

    Google Scholar 

  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)

    Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  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

    Chapter  Google Scholar 

  67. George, B.D.: Linear Programming and Extensions. Princeton University Press, Princeton (1962)

    Google Scholar 

  68. Dean, B.C.: Continuous-time dynamic shortest path algorithms. Master’s thesis, Massachusetts Institute of Technology (1999)

    Google Scholar 

  69. Dean, B.C.: Algorithms for minimum-cost paths in time-dependent networks with waiting policies. Networks 44(1), 41–46 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  70. Dean, B.C.: Shortest paths in FIFO time-dependent networks: theory and algorithms. Technical report, Massachusetts Institute Of Technology (2004)

    Google Scholar 

  71. Dehne, F., Omran, M.T., Sack, J.-R.: Shortest paths in time-dependent FIFO networks. Algorithmica 62, 416–435 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  72. Delling, D.: Time-dependent SHARC-routing. Algorithmica 60(1), 60–94 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  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

    Chapter  Google Scholar 

  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)

    Google Scholar 

  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)

    Article  Google Scholar 

  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

    Chapter  Google Scholar 

  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

    Google Scholar 

  78. Delling, D., Goldberg, A.V., Pajor, T., Werneck, R.F.: Customizable route planning in road networks. Transp. Sci. (2015)

    Google Scholar 

  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)

    Google Scholar 

  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

    Google Scholar 

  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)

    Google Scholar 

  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

    Chapter  Google Scholar 

  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)

    Google Scholar 

  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

    Google Scholar 

  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)

    MathSciNet  MATH  Google Scholar 

  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)

    Google Scholar 

  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

    Google Scholar 

  88. Delling, D., Nannicini, G.: Core routing on dynamic time-dependent road networks. Informs J. Comput. 24(2), 187–201 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  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

    Chapter  Google Scholar 

  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

    Chapter  Google Scholar 

  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)

    Google Scholar 

  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)

    Google Scholar 

  93. Delling, D., Pajor, T., Werneck, R.F.: Round-based public transit routing. Transp. Sci. 49, 591–604 (2014)

    Article  Google Scholar 

  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

    Chapter  Google Scholar 

  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)

    Google Scholar 

  96. Delling, D., Wagner, D.: Landmark-based routing in dynamic graphs. In: Demetrescu, C. (ed.) WEA 2007. LNCS, vol. 4525, pp. 52–65. Springer, Heidelberg (2007). doi:10.1007/978-3-540-72845-0_5

    Chapter  Google Scholar 

  97. Delling, D., Wagner, D.: Pareto paths with SHARC. In: Vahrenhold, J. (ed.) SEA 2009. LNCS, vol. 5526, pp. 125–136. Springer, Heidelberg (2009). doi:10.1007/978-3-642-02011-7_13

    Chapter  Google Scholar 

  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

    Chapter  Google Scholar 

  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)

    Google Scholar 

  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

    Chapter  Google Scholar 

  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  Google Scholar 

  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)

    Google Scholar 

  103. Denardo, E.V., Fox, B.L.: Shortest-route methods: 1. reaching, pruning, and buckets. Oper. Res. 27(1), 161–186 (1979)

    Article  MathSciNet  MATH  Google Scholar 

  104. Dial, R.B.: Algorithm 360: shortest-path forest with topological ordering [H]. Commun. ACM 12(11), 632–633 (1969)

    Article  Google Scholar 

  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

    Chapter  Google Scholar 

  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)

    Google Scholar 

  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

    Google Scholar 

  108. Dijkstra, E.W.: A note on two problems in connexion with graphs. Numer. Math. 1, 269–271 (1959)

    Article  MathSciNet  MATH  Google Scholar 

  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

    Chapter  Google Scholar 

  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)

    Google Scholar 

  111. Dreyfus, S.E.: An appraisal of some shortest-path algorithms. Oper. Res. 17(3), 395–412 (1969)

    Article  MATH  Google Scholar 

  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

    Google Scholar 

  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

    Google Scholar 

  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)

    Google Scholar 

  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)

    Google Scholar 

  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)

    Google Scholar 

  117. Ehrgott, M., Gandibleux, X.: Multiple Criteria Optimization: State of the Art Annotated Bibliographic Surveys. Kluwer Academic Publishers Group, New York (2002)

    MATH  Google Scholar 

  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

    Google Scholar 

  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)

    Google Scholar 

  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)

    Google Scholar 

  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)

    Google Scholar 

  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

    Google Scholar 

  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)

    Google Scholar 

  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

    Google Scholar 

  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)

    Google Scholar 

  126. Floyd, R.W.: Algorithm 97: shortest path. Commun. ACM 5(6), 345 (1962)

    Article  Google Scholar 

  127. Ford, Jr., L.R.: Network flow theory. Technical report P-923, Rand Corporation, Santa Monica, California (1956)

    Google Scholar 

  128. Foschini, L., Hershberger, J., Suri, S.: On the complexity of time-dependent shortest paths. Algorithmica 68(4), 1075–1097 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  129. Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34(3), 596–615 (1987)

    Article  MathSciNet  Google Scholar 

  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)

    Article  MATH  Google Scholar 

  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)

    Google Scholar 

  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)

    Google Scholar 

  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)

    Google Scholar 

  134. Gavoille, C., Peleg, D.: Compact and localized distributed data structures. Distrib. Comput. 16(2–3), 111–120 (2003)

    Article  Google Scholar 

  135. Gavoille, C., Peleg, D., Pérennes, S., Raz, R.: Distance labeling in graphs. J. Algorithms 53, 85–112 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  136. Geisberger, R.: Contraction of timetable networks with realistic transfers. In: Festa, P. (ed.) SEA 2010. LNCS, vol. 6049, pp. 71–82. Springer, Heidelberg (2010). doi:10.1007/978-3-642-13193-6_7

    Chapter  Google Scholar 

  137. Geisberger, R.: Advanced route planning in transportation networks. Ph.D. thesis, Karlsruhe Institute of Technology, February 2011

    Google Scholar 

  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)

    Google Scholar 

  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)

    Google Scholar 

  140. Geisberger, R., Rice, M., Sanders, P., Tsotras, V.: Route planning with flexible edge restrictions. ACM J. Exp. Algorithm. 17(1), 1–20 (2012)

    MathSciNet  MATH  Google Scholar 

  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)

    Google Scholar 

  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)

    Article  Google Scholar 

  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)

    Google Scholar 

  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

    Chapter  Google Scholar 

  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)

    Google Scholar 

  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)

    Article  MATH  Google Scholar 

  147. Goldberg, A.V.: A practical shortest path algorithm with linear expected time. SIAM J. Comput. 37, 1637–1655 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Google Scholar 

  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)

    Google Scholar 

  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)

    Google Scholar 

  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

    Google Scholar 

  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

    Google Scholar 

  153. Gunkel, T., Schnee, M., Müller-Hannemann, M.: How to find good night train connections. Networks 57(1), 19–27 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Google Scholar 

  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

    Chapter  Google Scholar 

  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)

    Article  Google Scholar 

  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)

    Google Scholar 

  158. Hliněný, P., Moriš, O.: Scope-based route planning. In: Demetrescu, C., Halldórsson, M.M. (eds.) ESA 2011. LNCS, vol. 6942, pp. 445–456. Springer, Heidelberg (2011). doi:10.1007/978-3-642-23719-5_38

    Chapter  Google Scholar 

  159. Holzer, M.: Engineering planar-separator and shortest-path algorithms. Ph.D. thesis, Karlsruhe Institute of Technology (KIT) - Department of Informatics (2008)

    Google Scholar 

  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)

    MathSciNet  MATH  Google Scholar 

  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)

    MathSciNet  MATH  Google Scholar 

  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)

    Google Scholar 

  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)

    Google Scholar 

  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)

    Article  Google Scholar 

  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)

    Article  Google Scholar 

  166. Kaindl, H., Kainz, G.: Bidirectional heuristic search reconsidered. J. Artif. Intell. Res. 7, 283–317 (1997)

    MathSciNet  MATH  Google Scholar 

  167. Kaufmann, H.: Towards mobile time-dependent route planning. Bachelor thesis, Karlsruhe Institute of Technology (2013)

    Google Scholar 

  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

    Chapter  Google Scholar 

  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

    Chapter  Google Scholar 

  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)

    Google Scholar 

  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)

    Google Scholar 

  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)

    Google Scholar 

  173. Kobitzsch, M.: HiDAR: an alternative approach to alternative routes. In: Bodlaender, H.L., Italiano, G.F. (eds.) ESA 2013. LNCS, vol. 8125, pp. 613–624. Springer, Heidelberg (2013). doi:10.1007/978-3-642-40450-4_52

    Chapter  Google Scholar 

  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)

    Google Scholar 

  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

    Google Scholar 

  176. Krumm, J., Gruen, R., Delling, D.: From destination prediction to route prediction. J. Locat. Based Serv. 7(2), 98–120 (2013)

    Article  Google Scholar 

  177. Krumm, J., Horvitz, E.: Predestination: where do you want to go today? IEEE Comput. 40(4), 105–107 (2007)

    Article  Google Scholar 

  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)

    Google Scholar 

  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)

    Article  Google Scholar 

  180. Lipton, R.J., Rose, D.J., Tarjan, R.: Generalized nested dissection. SIAM J. Numer. Anal. 16(2), 346–358 (1979)

    Article  MathSciNet  MATH  Google Scholar 

  181. Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Appl. Math. 36(2), 177–189 (1979)

    Article  MathSciNet  MATH  Google Scholar 

  182. Loridan, P.: \(\epsilon \)-solutions in vector minimization problems. J. Optim. Theory Appl. 43(2), 265–276 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  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

    Chapter  Google Scholar 

  184. Luxen, D., Schieferdecker, D.: Candidate sets for alternative routes in road networks. In: Klasing, R. (ed.) SEA 2012. LNCS, vol. 7276, pp. 260–270. Springer, Heidelberg (2012). doi:10.1007/978-3-642-30850-5_23

    Chapter  Google Scholar 

  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)

    Google Scholar 

  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)

    Google Scholar 

  187. Martins, E.Q.: On a multicriteria shortest path problem. Eur. J. Oper. Res. 26(3), 236–245 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    MathSciNet  MATH  Google Scholar 

  189. Mehlhorn, K.: A faster approximation algorithm for the Steiner problem in graphs. Inf. Process. Lett. 27(3), 125–128 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  190. Mehlhorn, K., Sanders, P., Algorithms, D.S.: The Basic Toolbox. Springer, Heidelberg (2008)

    MATH  Google Scholar 

  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)

    Google Scholar 

  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)

    Google Scholar 

  193. Meyer, U., Sanders, P.: \(\delta \)-stepping: a parallelizable shortest path algorithm. J. Algorithms 49(1), 114–152 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Google Scholar 

  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)

    Article  MATH  Google Scholar 

  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)

    Google Scholar 

  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  Google Scholar 

  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)

    Google Scholar 

  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)

    Google Scholar 

  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

    Chapter  Google Scholar 

  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

    Chapter  Google Scholar 

  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)

    Article  Google Scholar 

  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

    Chapter  Google Scholar 

  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

    Chapter  Google Scholar 

  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

    Chapter  Google Scholar 

  206. Nachtigall, K.: Time depending shortest-path problems with applications to railway networks. Eur. J. Oper. Res. 83(1), 154–166 (1995)

    Article  MATH  Google Scholar 

  207. Nannicini, G., Delling, D., Liberti, L., Schultes, D.: Bidirectional A* search on time-dependent road networks. Networks 59, 240–251 (2012). Best Paper Award

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  209. Orda, A., Rom, R.: Minimum weight paths in time-dependent networks. Networks 21, 295–319 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  210. Pajor, T.: Multi-modal route planning. Master’s thesis, Universität Karlsruhe (TH), March 2009

    Google Scholar 

  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)

    Google Scholar 

  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)

    Google Scholar 

  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)

    Google Scholar 

  214. Parter, S.V.: The use of linear graphs in Gauss elimination. SIAM Rev. 3(2), 119–130 (1961)

    Article  MathSciNet  MATH  Google Scholar 

  215. Peleg, D.: Proximity-preserving labeling schemes. J. Graph Theory 33(3), 167–176 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  216. Pohl, I.: Bi-directional and heuristic search in path problems. Technical report SLAC-104, Stanford Linear Accelerator Center, Stanford, California (1969)

    Google Scholar 

  217. Pohl, I.: Bi-directional search. In: Proceedings of the Sixth Annual Machine Intelligence Workshop, vol. 6, pp. 124–140. Edinburgh University Press (1971)

    Google Scholar 

  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)

    Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Google Scholar 

  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

    Chapter  Google Scholar 

  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)

    Google Scholar 

  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

    Chapter  Google Scholar 

  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)

    Google Scholar 

  225. Sanders, P., Schultes, D.: Engineering highway hierarchies. ACM J. Exp. Algorithm. 17(1), 1–40 (2012)

    MathSciNet  MATH  Google Scholar 

  226. Sanders, P., Schultes, D., Vetter, C.: Mobile route planning. In: Halperin, D., Mehlhorn, K. (eds.) ESA 2008. LNCS, vol. 5193, pp. 732–743. Springer, Heidelberg (2008). doi:10.1007/978-3-540-87744-8_61

    Chapter  Google Scholar 

  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)

    Google Scholar 

  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)

    Google Scholar 

  229. Sankaranarayanan, J., Samet, H.: Query processing using distance oracles for spatial networks. IEEE Trans. Knowl. Data Eng. 22(8), 1158–1175 (2010)

    Article  Google Scholar 

  230. Sankaranarayanan, J., Samet, H.: Roads belong in databases. IEEE Data Eng. Bull. 33(2), 4–11 (2010)

    Google Scholar 

  231. Schilling, H.: TomTom navigation - How mathematics help getting through traffic faster (2012). Talk given at ISMP

    Google Scholar 

  232. Schreiber, R.: A new implementation of sparse Gaussian elimination. ACM Trans. Math. Softw. 8(3), 256–276 (1982)

    Article  MathSciNet  MATH  Google Scholar 

  233. Schultes, D.: Route planning in road networks. Ph.D. thesis, Universität Karlsruhe (TH), February 2008

    Google Scholar 

  234. Schultes, D., Sanders, P.: Dynamic highway-node routing. In: Demetrescu, C. (ed.) WEA 2007. LNCS, vol. 4525, pp. 66–79. Springer, Heidelberg (2007). doi:10.1007/978-3-540-72845-0_6

    Chapter  Google Scholar 

  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)

    MathSciNet  MATH  Google Scholar 

  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

    Chapter  Google Scholar 

  237. Sedgewick, R., Vitter, J.S.: Shortest paths in Euclidean graphs. Algorithmica 1(1), 31–48 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  238. Sommer, C.: Shortest-path queries in static networks. ACM Comput. Surv. 46(4), 1–31 (2014)

    Article  MATH  Google Scholar 

  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)

    Google Scholar 

  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)

    Google Scholar 

  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)

    Google Scholar 

  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)

    Google Scholar 

  243. Theune, D.: Robuste und effiziente Methoden zur Lösung von Wegproblemen. Ph.D. thesis, Universität Paderborn (1995)

    Google Scholar 

  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)

    Google Scholar 

  245. Thorup, M.: Compact oracles for reachability and approximate distances in planar digraphs. J. ACM 51(6), 993–1024 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  247. Tulp, E., Siklóssy, L.: TRAINS, an active time-table searcher. ECAI 88, 170–175 (1988)

    Google Scholar 

  248. Tulp, E., Siklóssy, L.: Searching time-table networks. Artif. Intell. Eng. Des. Anal. Manuf. 5(3), 189–198 (1991)

    Article  Google Scholar 

  249. van Vliet, D.: Improved shortest path algorithms for transport networks. Transp. Res. Part B: Methodol. 12(1), 7–20 (1978)

    Google Scholar 

  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)

    Google Scholar 

  251. Wagner, D., Willhalm, T., Zaroliagis, C.: Geometric containers for efficient shortest-path computation. ACM J. Exp. Algorithm. 10(1.3), 1–30 (2005)

    MathSciNet  MATH  Google Scholar 

  252. Weller, M.: Optimal hub labeling is NP-complete. CoRR, abs/1407.8373 (2014)

    Google Scholar 

  253. White, D.J.: Epsilon efficiency. J. Optim. Theory Appl. 49(2), 319–337 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  254. Williams, J.W.J.: Algorithm 232: heapsort. J. ACM 7(6), 347–348 (1964)

    Google Scholar 

  255. Winter, S.: Modeling costs of turns in route planning. GeoInformatica 6(4), 345–361 (2002)

    Article  MATH  Google Scholar 

  256. Witt, S.: Trip-based public transit routing. In: Bansal, N., Finocchi, I. (eds.) ESA 2015. LNCS, vol. 9294, pp. 1025–1036. Springer, Heidelberg (2015). doi:10.1007/978-3-662-48350-3_85

    Chapter  Google Scholar 

  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)

    Article  Google Scholar 

  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)

    Google Scholar 

  259. Zadeh, L.A.: Fuzzy logic. IEEE Comput. 21(4), 83–93 (1988)

    Article  Google Scholar 

  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)

    Google Scholar 

  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)

    Google Scholar 

  262. Zwick, U.: Exact and approximate distances in graphs — a survey. In: Heide, F.M. (ed.) ESA 2001. LNCS, vol. 2161, pp. 33–48. Springer, Heidelberg (2001). doi:10.1007/3-540-44676-1_3

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. University of Freiburg, Freiburg im Breisgau, Germany

    Hannah Bast

  2. Apple Inc., Cupertino, USA

    Daniel Delling

  3. Amazon, Seattle, USA

    Andrew Goldberg & Renato F. Werneck

  4. Martin-Luther-Universität Halle-Wittenberg, Halle, Germany

    Matthias Müller-Hannemann

  5. Microsoft Research, Mountain View, USA

    Thomas Pajor

  6. Karlsruhe Institute of Technology, Karlsruhe, Germany

    Peter Sanders & Dorothea Wagner

Authors
  1. Hannah Bast
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Daniel Delling
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Andrew Goldberg
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Matthias Müller-Hannemann
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Thomas Pajor
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Peter Sanders
    View author publications

    You can also search for this author in PubMed Google Scholar

  7. Dorothea Wagner
    View author publications

    You can also search for this author in PubMed Google Scholar

  8. Renato F. Werneck
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Thomas Pajor .

Editor information

Editors and Affiliations

  1. Kiel University , Kiel, Germany

    Lasse Kliemann

  2. Karlsruhe Institute of Technology , Karlsruhe, Germany

    Peter Sanders

Rights and permissions

Reprints and permissions

Copyright information

© 2016 Springer International Publishing AG

About this chapter

Cite this chapter

Bast, H. et al. (2016). Route Planning in Transportation Networks. In: Kliemann, L., Sanders, P. (eds) Algorithm Engineering. Lecture Notes in Computer Science(), vol 9220. Springer, Cham. https://doi.org/10.1007/978-3-319-49487-6_2

Download citation

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

  • Published:

  • Publisher Name: Springer, Cham

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

  • Online ISBN: 978-3-319-49487-6

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation