Abstract
Efficiently computing fast paths in large-scale dynamic road networks (where dynamic traffic information is known over a part of the network) is a practical problem faced by traffic information service providers who wish to offer a realistic fast path computation to GPS terminal enabled vehicles. The heuristic solution method we propose is based on a highway hierarchy-based shortest path algorithm for static large-scale networks; we maintain a static highway hierarchy and perform each query on the dynamically evaluated network, using a simple algorithm to propagate available dynamic traffic information over a larger part of the road network. We provide computational results that show the efficacy of our approach.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Ahuja, R., Orlin, J., Pallottino, S., Scutellà, M.: Dynamic shortest paths minimizing travel times and costs. Networks 41(4), 197–205 (2003)
Buriol, L., Resende, M., Thorup, M.: Speeding up dynamic shortest path algorithms. INFORMS J. Comput. (2008). DOI: 10.1287/ijoc.1070.0231
Chabini, I.: Discrete dynamic shortest path problems in transportation applications: complexity and algorithms with optimal run time. Transp. Res. Rec. 1645, 170–175 (1998)
Chabini, I., Shan, L.: Adaptations of the A * algorithm for the computation of fastest paths in deterministic discrete-time dynamic networks. IEEE Trans. Intell. Transp. Syst. 3(1), 60–74 (2002)
Chan, E., Zhang, N.: Finding shortest paths in large network systems. In: GIS’01: Proceedings of the 9th ACM International Symposium on Advances in Geographic Information Systems, pp. 160–166. Assoc. Comput. Mach., New York (2001)
Cooke, K., Halsey, E.: The shortest route through a network with time-dependent internodal transit times. J. Math. Anal. Appl. 14, 493–498 (1966)
Dean, B.: Shortest paths in FIFO time-dependent networks: theory and algorithms. Technical Report, MIT, Cambridge, MA (2004)
Delling, D., Wagner, D.: Landmark-based routing in dynamic graphs. In: Demetrescu, C. (ed.) WEA 2007—Workshop on Experimental Algorithms. Lecture Notes in Computer Science, vol. 4525. Springer, New York (2007)
Dijkstra, E.: A note on two problems in connexion with graphs. Numer. Math. 1, 269–271 (1959)
Dreyfus, S.: An appraisal of some shortest-path algorithms. Oper. Res. 17(3), 395–412 (1969)
Flatberg, T., Hasle, G., Kloster, O., Nilssen, E., Riise, A.: Dynamic and stochastic aspects in vehicle routing—a literature survey. Technical Report STF90A05413, SINTEF, Oslo, Norway (2005)
Goldberg, A., Kaplan, H., Werneck, R.: Reach for A *: Efficient point-to-point shortest path algorithms. In: Demetrescu, C., Sedgewick, R., Tamassia, R. (eds.) ALENEX 2005. SIAM, Philadelphia (2005)
Holzer, M., Schulz, F., Wagner, D.: Engineering multi-level overlay graphs for shortest-path queries. In: Proceedings of the 8th Workshop on Algorithm Engineering. Lecture Notes in Computer Science, vol. 129, pp. 156–170. SIAM, Philadelphia (2006)
Kerner, B.S.: The Physics of Traffic. Springer, Berlin (2004)
NV, T.: Tele Atlas Multinet ShapeFile 4.3.1 Format Specifications. TeleAtlas NV, May 2005
Sanders, P., Schultes, D.: Highway hierarchies hasten exact shortest path queries. In: Stølting Brodal, G., Leonardi, S. (eds.) ESA. Lecture Notes in Computer Science, vol. 3669, pp. 568–579. Springer, Berlin (2005)
Sanders, P., Schultes, D.: Engineering highway hierarchies. In: ESA 2006. Lecture Notes in Computer Science, vol. 4168, pp. 804–816. Springer, Berlin (2006)
Sanders, P., Schultes, D.: Dynamic highway-node routing. In: Demetrescu, C. (ed.) WEA 2007—Workshop on Experimental Algorithms. Lecture Notes in Computer Science, vol. 4525, pp. 66–79. Springer, New York (2007)
Sanders, P., Schultes, D.: Engineering fast route planning algorithms. In: Demetrescu, C. (ed.) WEA 2007—Workshop on Experimental Algorithms. Lecture Notes in Computer Science, vol. 4525, pp. 23–36. Springer, New York (2007)
Schultes, D.: Fast and exact shortest path queries using highway hierarchies. Master Thesis, Informatik, Universität des Saarlandes, June 2005
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Nannicini, G., Baptiste, P., Barbier, G. et al. Fast paths in large-scale dynamic road networks. Comput Optim Appl 45, 143–158 (2010). https://doi.org/10.1007/s10589-008-9172-y
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10589-008-9172-y