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

Time-Dependent SHARC-Routing

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

In recent years, many speed-up techniques for Dijkstra’s algorithm have been developed that make the computation of shortest paths in static road networks a matter of microseconds. However, only few of those techniques work in time-dependent networks which, unfortunately, appear quite frequently in reality: Roads are predictably congested by traffic jams, and efficient timetable information systems rely on time-dependent networks. Hence, a fast technique for routing in such networks is needed.

In this work, we present an efficient time-dependent route planning algorithm. It is based on our recently introduced SHARC algorithm, which we adapt by augmenting its basic ingredients such that correctness can still be guaranteed in a time-dependent scenario. As a result, we are able to efficiently compute exact shortest paths in time-dependent continental-sized transportation networks, both of roads and of railways. It should be noted that time-dependent SHARC was the first efficient algorithm for time-dependent route planning.

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

Access this article

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

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Batz, V., Delling, D., Sanders, P., Vetter, C.: Time-dependent contraction hierarchies. In: Proceedings of the 11th Workshop on Algorithm Engineering and Experiments (ALENEX’09), pp. 97–105. SIAM, New York (2009)

    Google Scholar 

  2. Bauer, R., Delling, D.: SHARC: fast and robust unidirectional routing. In: Munro, I., Wagner, D. (eds.) Proceedings of the 10th Workshop on Algorithm Engineering and Experiments (ALENEX’08), pp. 13–26. SIAM, New York (2008)

    Google Scholar 

  3. Bauer, R., Delling, D.: SHARC: fast and robust unidirectional routing. ACM J. Exp. Algorithmics 14, 2.4–2.29 (2009). Special Section on Selected Papers from ALENEX 2008

    Article  Google Scholar 

  4. Brodal, G., Jacob, R.: Time-dependent networks as models to achieve fast exact time-table queries. In: Proceedings of ATMOS Workshop 2003, pp. 3–15 (2004)

  5. Cooke, K., Halsey, E.: The shortest route through a network with time-dependent intermodal transit times. J. Math. Anal. Appl. 14, 493–498 (1966)

    Article  MathSciNet  MATH  Google Scholar 

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

  7. Delling, D.: Time-dependent SHARC-routing. In: Proceedings of the 16th Annual European Symposium on Algorithms (ESA’08). Lecture Notes in Computer Science, vol. 5193, pp. 332–343. Springer, Berlin (2008). Best Student Paper Award—ESA Track B

    Google Scholar 

  8. Delling, D., Nannicini, G.: Bidirectional core-based routing in dynamic time-dependent road networks. In: Hong, S.-H., Nagamochi, H., Fukunaga, T. (eds.) Proceedings of the 19th International Symposium on Algorithms and Computation (ISAAC’08). Lecture Notes in Computer Science, vol. 5369, pp. 813–824. Springer, Berlin (2008)

    Google Scholar 

  9. Delling, D., Wagner, D.: Landmark-based routing in dynamic graphs. In: Demetrescu, C. (ed.) Proceedings of the 6th Workshop on Experimental Algorithms (WEA’07). Lecture Notes in Computer Science, vol. 4525, pp. 52–65. Springer, Berlin (2007)

    Google Scholar 

  10. 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. Lecture Notes in Computer Science, vol. 5515, pp. 117–139. Springer, Berlin (2009)

    Chapter  Google Scholar 

  11. Delling, D., Sanders, P., Schultes, D., Wagner, D., Highway hierarchies star. In: Demetrescu, C., Goldberg, A.V., Johnson, D.S. (eds.) Shortest Path Computations: Ninth DIMACS Challenge. DIMACS Book. American Mathematical Society (2009, in press)

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

    Article  MathSciNet  MATH  Google Scholar 

  13. Disser, Y., Müller-Hannemann, M., Schnee, M.: Multi-criteria shortest paths in time-dependent train networks. In: McGeoch, C.C. (ed.) Proceedings of the 7th Workshop on Experimental Algorithms (WEA’08). Lecture Notes in Computer Science, vol. 5038, pp. 347–361. Springer, Berlin (2008)

    Google Scholar 

  14. Flinsenberg, I.C.: Route Planning Algorithms for Car Navigation. PhD thesis, Technische Universiteit Eindhoven (2004)

  15. Geisberger, R., Sanders, P., Schultes, D., Delling, D.: Contraction hierarchies: faster and simpler hierarchical routing in road networks. In: McGeoch, C.C. (ed.) Proceedings of the 7th Workshop on Experimental Algorithms (WEA’08). Lecture Notes in Computer Science, vol. 5038, pp. 319–333. Springer, Berlin (2008)

    Google Scholar 

  16. 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’05), pp. 156–165 (2005)

  17. 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’05), pp. 26–40. SIAM, New York (2005)

    Google Scholar 

  18. Goldberg, A.V., Kaplan, H., Werneck, R.F.: Reach for A*: efficient point-to-point shortest path algorithms. In: Proceedings of the 8th Workshop on Algorithm Engineering and Experiments (ALENEX’06), pp. 129–143. SIAM, New York (2006)

    Google Scholar 

  19. Goldberg, A.V., Kaplan, H., Werneck, R.F.: Better landmarks within reach. In: Demetrescu, C. (ed.) Proceedings of the 6th Workshop on Experimental Algorithms (WEA’07). Lecture Notes in Computer Science, vol. 4525, pp. 38–51. Springer, Berlin (2007)

    Google Scholar 

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

  21. Hilger, M., Köhler, E., Möhring, R.H., Schilling, H.: Fast point-to-point shortest path computations with arc-flags. In: Demetrescu, C., Goldberg, A.V., Johnson, D.S. (eds.) Shortest Paths: Ninth DIMACS Implementation Challenge. DIMACS Book. American Mathematical Society (2009). To appear

  22. Kaufman, D.E.: Smith, R.L.: Fastest paths in time-dependent networks for intelligent vehicle-highway systems application. J. Intell. Transp. Syst. 1(1), 1–11 (1993)

    Article  Google Scholar 

  23. Köhler, E., Möhring, R.H., Schilling, H.: Acceleration of shortest path and constrained shortest path computation. In: Proceedings of the 4th Workshop on Experimental Algorithms (WEA’05). Lecture Notes in Computer Science, pp. 126–138. Springer, Berlin (2005)

    Google Scholar 

  24. Lauther, U.: An extremely fast, exact algorithm for finding shortest paths in static networks with geographical background. In: Geoinformation und Mobilität—von der Forschung zur praktischen Anwendung, vol. 22, pp. 219–230. IfGI prints (2004)

  25. Lauther, U.: An experimental evaluation of point-to-point shortest path calculation on roadnetworks with precalculated edge-flags. In: Demetrescu, C., Goldberg, A.V., Johnson, D.S. (eds.) Shortest Paths: Ninth DIMACS Implementation Challenge. DIMACS Book. American Mathematical Society (2009). To appear

  26. Möhring, R.H., Schilling, H., Schütz, B., Wagner, D., Willhalm, T.: Partitioning graphs to speed up Dijkstra’s algorithm. In: Proceedings of the 4th Workshop on Experimental Algorithms (WEA’05). Lecture Notes in Computer Science, pp. 189–202. Springer, Berlin (2005)

    Google Scholar 

  27. Möhring, R.H., Schilling, H., Schütz, B., Wagner, D., Willhalm, T.: Partitioning graphs to speedup Dijkstra’s algorithm. ACM J. Exp. Algorithmics 11(2.8) (2006)

  28. Nannicini, G., Delling, D., Liberti, L., Schultes, D.: Bidirectional A* search for time-dependent fast paths. In: McGeoch, C.C. (ed.) Proceedings of the 7th Workshop on Experimental Algorithms (WEA’08). Lecture Notes in Computer Science, vol. 5038, pp. 334–346. Springer, Berlin (2008)

    Google Scholar 

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

  30. Pellegrini, F.: SCOTCH: static mapping, graph, mesh and hypergraph partitioning, and parallel and sequential sparse matrix ordering package (2007)

  31. Pyrga, E., Schulz, F., Wagner, D., Zaroliagis, C.: Towards realistic modeling of time-table information through the time-dependent approach. In: Proceedings of ATMOS Workshop 2003, pp. 85–103 (2004)

  32. Pyrga, E., Schulz, F., Wagner, D., Zaroliagis, C.: Efficient models for timetable information in public transportation systems. ACM J. Exp. Algorithmics 12(2.4) (2007)

  33. R Development Core Team. R: A language and environment for statistical computing (2004)

  34. Sanders, P., Schultes, D.: Highway hierarchies hasten exact shortest path queries. In: Proceedings of the 13th Annual European Symposium on Algorithms (ESA’05). Lecture Notes in Computer Science, vol. 3669, pp. 568–579. Springer, Berlin (2005)

    Google Scholar 

  35. Sanders, P., Schultes, D.: Engineering highway hierarchies. In: Proceedings of the 14th Annual European Symposium on Algorithms (ESA’06). Lecture Notes in Computer Science, vol. 4168, pp. 804–816. Springer, Berlin (2006)

    Google Scholar 

  36. Schultes, D.: Route planning in road networks. PhD thesis, Universität Karlsruhe (TH), Fakultät für Informatik, February (2008)

  37. Schultes, D., Sanders, P.: Dynamic highway-node routing. In: Demetrescu, C. (ed.) Proceedings of the 6th Workshop on Experimental Algorithms (WEA’07). Lecture Notes in Computer Science, vol. 4525, pp. 66–79. Springer, Berlin (2007)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Universität Karlsruhe (TH), 76128, Karlsruhe, Germany

    Daniel Delling

Authors
  1. Daniel Delling
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Daniel Delling.

Additional information

Partially supported by the Future and Emerging Technologies Unit of EC (IST priority–6th FP), under contract no. FP6-021235-2 (project ARRIVAL) and the DFG (project WA 654/16-1).

Rights and permissions

Reprints and permissions

About this article

Cite this article

Delling, D. Time-Dependent SHARC-Routing. Algorithmica 60, 60–94 (2011). https://doi.org/10.1007/s00453-009-9341-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-009-9341-0

Keywords

Search

Navigation