Abstract
In a recent work [1], we proposed a point-to-point shortest paths algorithm which applies bidirectional search on time-dependent road networks. The algorithm is based on A ∗ and runs a backward search in order to bound the set of nodes that have to be explored by the forward search. In this paper we extend the bidirectional time-dependent search algorithm in order to allow core routing, which is a very effective technique introduced for static graphs that consists in carrying out most of the search on a subset of the original node set. Moreover, we tackle the dynamic scenario where the piecewise linear time-dependent arc cost functions are not fixed, but can have their coefficients updated. We provide extensive computational results to show that our approach is a significant speed-up with respect to the original algorithm, and it is able to deal with the dynamic scenario requiring only a small computational effort to update the cost functions and related data structures.
Partially supported by the DFG (project WA 654/16-1) and the EU under grant ARRIVAL (contract no. FP6-021235-2).
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Nannicini, G., Delling, D., Liberti, L., Schultes, D.: Bidirectional A* search for time-dependent fast paths. In: [22], pp. 334–346
Wagner, D., Willhalm, T.: Speed-up techniques for shortest-path computations. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol. 4393, pp. 23–36. Springer, Heidelberg (2007)
Bauer, R., Delling, D., Sanders, P., Schieferdecker, D., Schultes, D., Wagner, D.: Combining hierarchical and goal-directed speed-up techniques for dijkstra’s algorithm. In: [22], pp. 303–318
Cooke, K., Halsey, E.: The shortest route through a network with time-dependent internodal transit times. J. of Math. Analysis and Applications 14, 493–498 (1966)
Dijkstra, E.: A note on two problems in connexion with graphs. Numerische Mathematik 1, 269–271 (1959)
Dreyfus, S.: An appraisal of some shortest-path algorithms. Operations Research 17(3), 395–412 (1969)
Kaufman, D.E., Smith, R.L.: Fastest paths in time-dependent networks for intelligent vehicle-highway systems application. Journal of Intelligent Transportation Systems 1(1), 1–11 (1993)
Orda, A., Rom, R.: Shortest-path and minimum delay algorithms in networks with time-dependent edge-length. Journal of the ACM 37(3), 607–625 (1990)
Hart, E., Nilsson, N., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems, Science and Cybernetics SSC 4(2), 100–107 (1968)
Goldberg, A., Harrelson, C.: Computing the shortest path: A ∗ meets graph theory. In: Proceedings of SODA 2005, pp. 156–165. SIAM, Philadelphia (2005)
Goldberg, A., Kaplan, H., Werneck, R.: Reach for A ∗ : Efficient point-to-point shortest path algorithms. In: Proceedings of ALENEX 2006. LNCS, pp. 129–143. Springer, Heidelberg (2006)
Delling, D., Wagner, D.: Landmark-based routing in dynamic graphs. In: [21], pp. 52–65
Chabini, I., Lan, S.: Adaptations of the A ∗ algorithm for the computation of fastest paths in deterministic discrete-time dynamic networks. IEEE Transactions on Intelligent Transportation Systems 3(1), 60–74 (2002)
Bauer, R., Delling, D.: SHARC: Fast and Robust Unidirectional Routing. In: Proceedings of the ALENEX 2008, pp. 13–26. SIAM, Philadelphia (2008)
Möhring, R.H., Schilling, H., Schütz, B., Wagner, D., Willhalm, T.: Partitioning graphs to speed up dijkstra’s algorithm. In: Nikoletseas, S.E. (ed.) WEA 2005. LNCS, vol. 3503, pp. 189–202. Springer, Heidelberg (2005)
Delling, D.: Time-Dependent SHARC-Routing. In: Halperin, D., Mehlhorn, K. (eds.) Esa 2008. LNCS, vol. 5193, pp. 332–343. Springer, Heidelberg (2008)
Goldberg, A., Werneck, R.: Computing point-to-point shortest paths from external memory. In: Demetrescu, C., Sedgewick, R., Tamassia, R. (eds.) Proceedings of ALENEX 2005, pp. 26–40. SIAM, Philadelphia (2005)
Geisberger, R., Sanders, P., Schultes, D., Delling, D.: Contraction hierarchies: Faster and simpler hierarchical routing in road networks. In: [22], pp. 319–333
Goldberg, A., Kaplan, H., Werneck, R.: Better landmarks within reach. In: [21], pp. 38–51
Delling, D., Sanders, P., Schultes, D., Wagner, D.: Highway Hierarchies Star. In: Shortest Paths: Ninth DIMACS Implementation Challenge. DIMACS Book. American Mathematical Society (to appear, 2008)
Demetrescu, C. (ed.): WEA 2007. LNCS, vol. 4525. Springer, Heidelberg (2007)
McGeoch, C.C. (ed.): WEA 2008. LNCS, vol. 5038. Springer, Heidelberg (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Delling, D., Nannicini, G. (2008). Bidirectional Core-Based Routing in Dynamic Time-Dependent Road Networks. In: Hong, SH., Nagamochi, H., Fukunaga, T. (eds) Algorithms and Computation. ISAAC 2008. Lecture Notes in Computer Science, vol 5369. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-92182-0_71
Download citation
DOI: https://doi.org/10.1007/978-3-540-92182-0_71
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-92181-3
Online ISBN: 978-3-540-92182-0
eBook Packages: Computer ScienceComputer Science (R0)