Abstract
We study the approximation of minimum travel time paths in time dependent networks. The travel time on each link of the network is a piecewise linear function of the departure time from the start node of the link. The objective is to find the minimum travel time to a destination node d, for all possible departure times at source node s. Dehne et al. proposed an exact output-sensitive algorithm for this problem [6, 7] that improves, in most cases, upon the existing algorithms. They also provide an approximation algorithm. In [10, 11], Foschini et al. show that this problem has super-polynomial complexity and present an ε–approximation algorithm that runs \(O( {\lambda \over \epsilon} \log ({T_{max} \over T_{min}}) \log({L \over \lambda \epsilon T_{min}}))\) shortest path computations, where λ is the total number of linear pieces in travel time functions on links, L is the horizontal span of the travel time function and T min and T max are the minimum and maximum travel time values, respectively.
In this paper, we present two ε–approximation algorithms that improve upon Foschini et al.’s result. Our first algorithm runs \(O({\lambda \over \epsilon}(\log ({T_{max}\over T_{min}})+ \log ({ L\over \lambda T_{min}})))\) shortest path computations at fixed departure times. In our second algorithm, we reduce the dependency on L, by using only \(O(\lambda( {1 \over \epsilon} \log ({T_{max} \over T_{min}})+ \log ({ L \over \lambda \epsilon T_{min}})))\) total shortest path computations.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bertsekas, D.P.: A simple and fast label correcting algorithm for shortest paths. Networks 23(7), 703–709 (1993)
Brodal, G.S., Jacob, R.: Time-dependent networks as models to achieve fast exact time-table queries. Electronic Notes in Theoretical Computer Science 92, 3–15 (2004)
Cooke, K.L., Halsey, E.: The shortest route through a network with time-dependent internodal transit times. Journal of Mathematical Analysis and Applications 14(3), 493–498 (1966)
Daganzo, C.F.: Reversibility of the time-dependent shortest path problem. Transportation Research 36(7), 665–668 (2002)
Dean, B.C.: Shortest paths in FIFO time-dependent networks: Theory and algorithms. Technical report, MIT Department of Computer Science (2004)
Dehne, F., Omran, M.T., Sack, J.-R.: Shortest paths in time-dependent FIFO networks using edge load forecasts. In: Proceedings of the 2nd International Workshop on Computational Transportation Science, pp. 1–6 (2009)
Dehne, F., Omran, M.T., Sack, J.-R.: Shortest paths in time-dependent FIFO networks. Algorithmica 62(1-2), 416–435 (2012)
Dijkstra, E.W.: A note on two problems in connexion with graphs. Numerische Mathematik 1(1), 269–271 (1959)
Ding, B., Yu, J.X., Qin, L.: Finding time-dependent shortest paths over large graphs. In: EDBT 2008, pp. 205–216 (2008)
Foschini, L., Hershberger, J., Suri, S.: On the complexity of time-dependent shortest paths. In: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 327–341 (2011)
Foschini, L., Hershberger, J., Suri, S.: On the complexity of time-dependent shortest paths. Algorithmica, 1–23 (2012)
Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34(3), 596–615 (1987)
Kanoulas, E., Du, Y., Xia, T., Zhang, D.: Finding fastest paths on a road network with speed patterns. In: Proceedings of the 22nd International Conference on Data Engineering, p. 10 (2006)
Kontogiannis, S.C., Zaroliagis, C.D.: Distance oracles for time-dependent networks. CoRR, abs/1309.4973 (2013)
Nachtigall, K.: Time depending shortest-path problems with applications to railway networks. European Journal of Operational Research 83(1), 154–166 (1995)
Orda, A., Rom, R.: Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length. J. ACM 37(3), 607–625 (1990)
Orda, A., Rom, R.: Minimum weight paths in time-dependent networks. Networks 21, 295–319 (1991)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Omran, M., Sack, JR. (2014). Improved Approximation for Time-Dependent Shortest Paths. In: Cai, Z., Zelikovsky, A., Bourgeois, A. (eds) Computing and Combinatorics. COCOON 2014. Lecture Notes in Computer Science, vol 8591. Springer, Cham. https://doi.org/10.1007/978-3-319-08783-2_39
Download citation
DOI: https://doi.org/10.1007/978-3-319-08783-2_39
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-08782-5
Online ISBN: 978-3-319-08783-2
eBook Packages: Computer ScienceComputer Science (R0)