{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T17:16:18Z","timestamp":1770484578632,"version":"3.49.0"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2013,4,19]],"date-time":"2013-04-19T00:00:00Z","timestamp":1366329600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["SA 933\/5-1"],"award-info":[{"award-number":["SA 933\/5-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Concept for the Future of KIT within the framework of the German Excellence Initiative"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2013,12]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/2444016.2444020","type":"journal-article","created":{"date-parts":[[2013,5,7]],"date-time":"2013-05-07T20:51:42Z","timestamp":1367959902000},"source":"Crossref","is-referenced-by-count":28,"title":["Minimum time-dependent travel times with contraction hierarchies"],"prefix":"10.1145","volume":"18","author":[{"given":"G. Veit","family":"Batz","sequence":"first","affiliation":[{"name":"Karlsruhe Institute of Technology (KIT), Karlsruhe, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert","family":"Geisberger","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology (KIT), Karlsruhe, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Sanders","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology (KIT), Karlsruhe, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Vetter","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology (KIT), Karlsruhe, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,4,19]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 11th Workshop on Algorithm Engineering and Experiments (ALENEX'09)","author":"Batz G. V."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13193-6_15"},{"key":"e_1_2_1_3_1","unstructured":"Batz G. V. Geisberger R. and Sanders P. 2008. Time dependent contraction hierarchies\u2014basic algorithmic ideas. Tech. rep. ITI Sanders Faculty of Informatics Universit\u00e4t Karlsruhe (TH).  Batz G. V. Geisberger R. and Sanders P. 2008. Time dependent contraction hierarchies\u2014basic algorithmic ideas. Tech. rep. ITI Sanders Faculty of Informatics Universit\u00e4t Karlsruhe (TH)."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33090-2_16"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1671970.1671976"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13193-6_5"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Dantzig G. B. 1962. Linear Programming and Extensions. Princeton University Press.  Dantzig G. B. 1962. Linear Programming and Extensions. Princeton University Press.","DOI":"10.7249\/R366"},{"key":"e_1_2_1_8_1","unstructured":"Dean B. C. 2004. Shortest paths in FIFO time-dependent networks: theory and algorithms. Tech. rep. Massachusetts Institute of Technology.  Dean B. C. 2004. Shortest paths in FIFO time-dependent networks: theory and algorithms. Tech. rep. Massachusetts Institute of Technology."},{"key":"e_1_2_1_9_1","unstructured":"Delling D. 2009. Engineering and augmenting route planning algorithms. Ph.d. Dissertation Universit\u00e4t Karlsruhe Fakult\u00e4t f\u00fcr Informatik. http:\/\/i11www.ira.uka.de\/extra\/publications\/d-earpa-09. pdf.  Delling D. 2009. Engineering and augmenting route planning algorithms. Ph.d. Dissertation Universit\u00e4t Karlsruhe Fakult\u00e4t f\u00fcr Informatik. http:\/\/i11www.ira.uka.de\/extra\/publications\/d-earpa-09. pdf."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118746.3118920"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92182-0_71"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02094-0_7"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.17.3.395"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 9th International Symposium on Experimental Algorithms (SEA'10)","author":"Festa P.","year":"2010"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 10th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'10)","author":"Geisberger R."},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 7th Workshop on Experimental Algorithms (WEA'08)","author":"Geisberger R."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.1110.0401"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 16th Annual ACM--SIAM Symposium on Discrete Algorithms (SODA'05)","author":"Goldberg A. V."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1412228.1412239"},{"key":"e_1_2_1_21_1","first-page":"159","article-title":"An optimal algorithm for approximating a piecewise linear function","volume":"9","author":"Imai H.","year":"1987","journal-title":"J. Info. Proces."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13193-6_8"},{"key":"e_1_2_1_23_1","unstructured":"Mehlhorn K. and Sanders P. 2008. Algorithms and Data Structures: The Basic Toolbox. Springer.   Mehlhorn K. and Sanders P. 2008. Algorithms and Data Structures: The Basic Toolbox. Springer."},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 7th Workshop on Experimental Algorithms (WEA'08)","author":"Nannicini G."},{"key":"e_1_2_1_25_1","unstructured":"Neubauer S. 2009. Space efficient approximation of piecewise linear functions. Studienarbeit Universit\u00e4t Karlsruhe Fakult\u00e4t f\u00fcr Informatik. http:\/\/algo2.iti.kit.edu\/download\/neubauer_sa.pdf.  Neubauer S. 2009. Space efficient approximation of piecewise linear functions. Studienarbeit Universit\u00e4t Karlsruhe Fakult\u00e4t f\u00fcr Informatik. http:\/\/algo2.iti.kit.edu\/download\/neubauer_sa.pdf."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/79147.214078"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561071_51"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 6th Workshop on Experimental Algorithms (WEA'07)","author":"Schultes D."}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2444016.2444020","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2444016.2444020","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:48:57Z","timestamp":1750236537000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2444016.2444020"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,4,19]]},"references-count":28,"alternative-id":["10.1145\/2444016.2444020"],"URL":"https:\/\/doi.org\/10.1145\/2444016.2444020","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,4,19]]}}}