G. Veit Batz
Abstract
Time-dependent road networks are represented as weighted graphs, where the weight of an edge depends on the time one passes through that edge. This way, we can model periodic congestions during rush hour and similar effects. In this work we deal with the special case where edge weights are time-dependent travel times. Namely, we consider two problems in this setting: Earliest arrival queries ask for a minimum travel time route for a start and a destination depending on a given departure time. Travel time profile queries ask for the travel time profile for a start, a destination, and an interval of possible departure times. For an instance representing the German road network, for example, we can answer earliest arrival queries in less than 1.5ms. For travel time profile queries, which are much harder to answer, we need less than 40ms if the interval of possible departure times has a width of 24 hours. For inexact travel time profiles with an allowed error of about 1% this even reduces to 3.2ms. The underlying hierarchical representations of the road network, which are variants of a time-dependent contraction hierarchy (TCH), need less than 1GiB of space and can be generated in about 30 minutes. As far as we know, TCHs are currently the only method being able to answer travel time profile queries efficiently. Altogether, with TCHs, web servers with massive request traffic are able to provide fast time-dependent earliest arrival route planning and computation of travel time profiles.
- Batz, G. V., Delling, D., Sanders, P., and Vetter, C. 2009. Time-dependent contraction hierarchies. In Proceedings of the 11th Workshop on Algorithm Engineering and Experiments (ALENEX'09). SIAM, 97--105.Google Scholar
- Batz, G. V., Geisberger, R., Neubauer, S., and Sanders, P. 2010. Time-dependent contraction hierarchies and approximation. See Festa {2010}, 166--177. http://www.springerlink.com/content/u787292691813526/. Google ScholarDigital Library
- Batz, G. V., Geisberger, R., and Sanders, P. 2008. Time dependent contraction hierarchies—basic algorithmic ideas. Tech. rep. ITI Sanders, Faculty of Informatics, Universität Karlsruhe (TH).Google Scholar
- Batz, G. V. and Sanders, P. 2012. Time-dependent route planning with generalized objective functions. In Proceedings of the 20th Annual European Symposium on Algorithms (ESA'12). Springer. Google ScholarDigital Library
- Bauer, R., Delling, D., Sanders, P., Schieferdecker, D., Schultes, D., and Wagner, D. 2010. Combining hierarchical and goal-directed speed-up techniques for Dijkstra's algorithm. ACM J. Exp. Algor. 15, 2.3 (January 2010), 1--31. Google ScholarDigital Library
- Brunel, E., Delling, D., Gemsa, A., and Wagner, D. 2010. Space-efficient SHARC-routing. In Proceedings of the 9th International Symposium on Experimental Algorithms (SEA'10). Springer, 47--58. Google ScholarDigital Library
- Dantzig, G. B. 1962. Linear Programming and Extensions. Princeton University Press.Google Scholar
- Dean, B. C. 2004. Shortest paths in FIFO time-dependent networks: theory and algorithms. Tech. rep., Massachusetts Institute of Technology.Google Scholar
- Delling, D. 2009. Engineering and augmenting route planning algorithms. Ph.d. Dissertation, Universität Karlsruhe, Fakultät für Informatik. http://i11www.ira.uka.de/extra/publications/d-earpa-09. pdf.Google Scholar
- Delling, D. 2011. Time-dependent SHARC-routing. Algorithmica 60, 1, 60--94.Google ScholarDigital Library
- Delling, D. and Nannicini, G. 2008. Bidirectional core-based routing in dynamic time-dependent road networks. In Proceedings of the 19th International Symposium on Algorithms and Computation (ISAAC'08), Springer, 813--824. Google ScholarDigital Library
- Delling, D., Sanders, P., Schultes, D., and Wagner, D. 2009. Engineering route planning algorithms. In Algorithmics of Large and Complex Networks, Jürgen Lerner, Dorothea Wagner, and Katharina A. Zweig, Eds., Springer, 117--139. Google ScholarDigital Library
- Dijkstra, E. W. 1959. A note on two problems in connexion with graphs. Numer. Math. 1, 269--271.Google ScholarDigital Library
- Dreyfus, S. E. 1969. An appraisal of some shortest-path algorithms. Oper. Res. 17, 3, 395--412.Google ScholarDigital Library
- Festa, P. (Ed.). 2010. Proceedings of the 9th International Symposium on Experimental Algorithms (SEA'10). Springer. Google ScholarDigital Library
- Geisberger, R. and Sanders, P. 2010. 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'10).Google Scholar
- Geisberger, R., Sanders, P., Schultes, D., and Delling, D. 2008. Contraction hierarchies: Faster and simpler hierarchical routing in road networks. In Proceedings of the 7th Workshop on Experimental Algorithms (WEA'08). Springer, 319--333. Google ScholarDigital Library
- Geisberger, R., Sanders, P., Schultes, D., and Vetter, C. 2012. Exact routing in large road networks using contraction hierarchies. Trans. Sci. 46, 3, 388--404. Google ScholarDigital Library
- Goldberg, A. V. and Harrelson, C. 2005. Computing the shortest path: A* search meets graph theory. In Proceedings of the 16th Annual ACM--SIAM Symposium on Discrete Algorithms (SODA'05). SIAM, 156--165. Google ScholarDigital Library
- Holzer, M., Schulz, F., and Wagner, D. 2008. Engineering multilevel overlay graphs for shortest-path queries. ACM J. Exp. Algor. 13, 2.5, 1--26. Google ScholarDigital Library
- Imai, H. and Iri, M. 1987. An optimal algorithm for approximating a piecewise linear function. J. Info. Proces. 9, 3, 159--162.Google Scholar
- Kieritz, T., Luxen, D., Sanders, P., and Vetter, C. 2010. Distributed time-dependent contraction hierarchies. In Proceedings of the 9th International Symposium on Experimental Algorithms (SEA'10). Springer, 83--93. Google ScholarDigital Library
- Mehlhorn, K. and Sanders, P. 2008. Algorithms and Data Structures: The Basic Toolbox. Springer. Google ScholarDigital Library
- Nannicini, G., Delling, D., Liberti, L., and Schultes, D. 2008. Bidirectional A* search for time-dependent fast paths. In Proceedings of the 7th Workshop on Experimental Algorithms (WEA'08). Springer, 334--346. Google ScholarDigital Library
- Neubauer, S. 2009. Space efficient approximation of piecewise linear functions. Studienarbeit, Universität Karlsruhe, Fakultät für Informatik. http://algo2.iti.kit.edu/download/neubauer_sa.pdf.Google Scholar
- Orda, A. and Rom, R. 1990. Shortest-path and minimum delay algorithms in networks with time-dependent edge-length. J. ACM 37, 3, 607--625. Google ScholarDigital Library
- Sanders, P. and Schultes, D. 2005. Highway hierarchies hasten exact shortest path queries. In Proceedings of the 13th Annual European Symposium on Algorithms (ESA'05). Springer, 568--579. Google ScholarDigital Library
- Schultes, D. and Sanders, P. 2007. Dynamic highway-node routing. In Proceedings of the 6th Workshop on Experimental Algorithms (WEA'07). Springer, 66--79. Google ScholarDigital Library
Index Terms
- Minimum time-dependent travel times with contraction hierarchies
Recommendations
Engineering highway hierarchies
Highway hierarchies exploit hierarchical properties inherent in real-world road networks to allow fast and exact point-to-point shortest-path queries. A fast preprocessing routine iteratively performs two steps: First, it removes edges that only appear ...
Processing time-dependent shortest path queries without pre-computed speed information on road networks
Shortest path (or least travel time path) identification has been actively studied for direct application to road networks. In addition, the processing of time-dependent shortest-path queries, which use past traffic data to compute the speed variations ...
Go slow to go fast: minimal on-road time route scheduling with parking facilities using historical trajectory
For thousands of years, people have been innovating new technologies to make their travel faster, the latest of which is GPS technology that is used by millions of drivers every day. The routes recommended by a GPS device are computed by path planning ...
Comments