{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T06:52:45Z","timestamp":1774680765923,"version":"3.50.1"},"reference-count":34,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2021,3,16]],"date-time":"2021-03-16T00:00:00Z","timestamp":1615852800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>We study the problem of quickly computing point-to-point shortest paths in massive road networks with traffic predictions. Incorporating traffic predictions into routing allows, for example, to avoid commuter traffic congestions. Existing techniques follow a two-phase approach: In a preprocessing step, an index is built. The index depends on the road network and the traffic patterns but not on the path start and end. The latter are the input of the query phase, in which shortest paths are computed. All existing techniques have large index size, slow query running times or may compute suboptimal paths. In this work, we introduce CATCHUp (Customizable Approximated Time-dependent Contraction Hierarchies through Unpacking), the first algorithm that simultaneously achieves all three objectives. The core idea of CATCHUp is to store paths instead of travel times at shortcuts. Shortcut travel times are derived lazily from the stored paths. We perform an experimental study on a set of real world instances and compare our approach with state-of-the-art techniques. Our approach achieves the fastest preprocessing, competitive query running times and up to 38 times smaller indexes than competing approaches.<\/jats:p>","DOI":"10.3390\/a14030090","type":"journal-article","created":{"date-parts":[[2021,3,16]],"date-time":"2021-03-16T12:01:02Z","timestamp":1615896062000},"page":"90","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":16,"title":["Space-Efficient, Fast and Exact Routing in Time-Dependent Road Networks"],"prefix":"10.3390","volume":"14","author":[{"given":"Ben","family":"Strasser","sequence":"first","affiliation":[{"name":"Institute of Theoretical Informatics, Karlsruhe Institute of Technology, Am Fasanengarten 5, 76131 Karlsruhe, Germany"}]},{"given":"Dorothea","family":"Wagner","sequence":"additional","affiliation":[{"name":"Institute of Theoretical Informatics, Karlsruhe Institute of Technology, Am Fasanengarten 5, 76131 Karlsruhe, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4746-3582","authenticated-orcid":false,"given":"Tim","family":"Zeitz","sequence":"additional","affiliation":[{"name":"Institute of Theoretical Informatics, Karlsruhe Institute of Technology, Am Fasanengarten 5, 76131 Karlsruhe, Germany"}]}],"member":"1968","published-online":{"date-parts":[[2021,3,16]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","article-title":"A Note on Two Problems in Connexion with Graphs","volume":"1","author":"Dijkstra","year":"1959","journal-title":"Numer. Math."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/978-3-319-49487-6_2","article-title":"Route Planning in Transportation Networks","volume":"Volume 9220","author":"Kliemann","year":"2016","journal-title":"Algorithm Engineering\u2014Selected Results and Surveys"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1498698.1537599","article-title":"SHARC: Fast and Robust Unidirectional Routing","volume":"14","author":"Bauer","year":"2009","journal-title":"ACM J. Exp. Algorithmics"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1287\/ijoc.1110.0448","article-title":"Core Routing on Dynamic Time-Dependent Road Networks","volume":"24","author":"Delling","year":"2012","journal-title":"Informs J. Comput."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1.5:1","DOI":"10.1145\/2886843","article-title":"Customizable Contraction Hierarchies","volume":"21","author":"Dibbelt","year":"2016","journal-title":"ACM J. Exp. Algorithmics"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"388","DOI":"10.1287\/trsc.1110.0401","article-title":"Exact Routing in Large Road Networks Using Contraction Hierarchies","volume":"46","author":"Geisberger","year":"2012","journal-title":"Transp. Sci."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"566","DOI":"10.1287\/trsc.2014.0579","article-title":"Customizable Route Planning in Road Networks","volume":"51","author":"Delling","year":"2017","journal-title":"Transp. Sci."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2444016.2444020","article-title":"Minimum Time-Dependent Travel Times with Contraction Hierarchies","volume":"18","author":"Batz","year":"2013","journal-title":"ACM J. Exp. Algorithmics"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/978-3-319-38851-9_3","article-title":"Dynamic Time-Dependent Route Planning in Road Networks with User Preferences","volume":"Volume 9685","author":"Baum","year":"2016","journal-title":"Proceedings of the 15th International Symposium on Experimental Algorithms (SEA\u201916)"},{"key":"ref_10","unstructured":"Goldberg, A.V., and Harrelson, C. (2005, January 23\u201325). Computing the Shortest Path: A* Search Meets Graph Theory. Proceedings of the 16th Annual ACM\u2013SIAM Symposium on Discrete Algorithms (SODA\u201905), Vancouver, BC, Canada."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","article-title":"A Formal Basis for the Heuristic Determination of Minimum Cost Paths","volume":"4","author":"Hart","year":"1968","journal-title":"IEEE Trans. Syst. Sci. Cybern."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1002\/net.20438","article-title":"Bidirectional A* Search on Time-Dependent Road Networks","volume":"59","author":"Nannicini","year":"2012","journal-title":"Networks"},{"key":"ref_13","first-page":"219","article-title":"An Extremely Fast, Exact Algorithm for Finding Shortest Paths in Static Networks with Geographical Background","volume":"Volume 22","author":"Lauther","year":"2004","journal-title":"Geoinformation und Mobilit\u00e4t\u2014von der Forschung zur Praktischen Anwendung"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1007\/s00453-009-9341-0","article-title":"Time-Dependent SHARC-Routing","volume":"60","author":"Delling","year":"2011","journal-title":"Algorithmica"},{"key":"ref_15","first-page":"1","article-title":"Engineering Multilevel Overlay Graphs for Shortest-Path Queries","volume":"13","author":"Holzer","year":"2008","journal-title":"ACM J. Exp. Algorithmics"},{"key":"ref_16","unstructured":"Kontogiannis, S., Michalopoulos, G., Papastavrou, G., Paraskevopoulos, A., Wagner, D., and Zaroliagis, C. (2016, January 10). Engineering Oracles for Time-Dependent Road Networks. Proceedings of the 18th Meeting on Algorithm Engineering and Experiments (ALENEX\u201916), Arlington, VA, USA."},{"key":"ref_17","unstructured":"Kontogiannis, S., Papastavrou, G., Paraskevopoulos, A., Wagner, D., and Zaroliagis, C. (2017, January 7\u20138). Improved Oracles for Time-Dependent Road Networks. Proceedings of the 17th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS\u201917), Vienna, Austria."},{"key":"ref_18","unstructured":"Strasser, B. (2017, January 7\u20138). Dynamic Time-Dependent Routing in Road Networks Through Sampling. Proceedings of the 17th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS\u201917), Vienna, Austria."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/j.trb.2016.10.013","article-title":"Time-dependent vehicle routing problem with path flexibility","volume":"95","author":"Huang","year":"2017","journal-title":"Transp. Res. Part B Methodol."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/j.cor.2015.06.001","article-title":"Time-dependent routing problems: A review","volume":"64","author":"Gendreau","year":"2015","journal-title":"Comput. Oper. Res."},{"key":"ref_21","unstructured":"Strasser, B., Wagner, D., and Zeitz, T. (2020, January 7\u20139). Space-efficient, Fast and Exact Routing in Time-dependent Road Networks. Proceedings of the 28th Annual European Symposium on Algorithms (ESA\u201920), Pisa, Italy."},{"key":"ref_22","unstructured":"Orda, A., and Rom, R. (1989). Traveling without Waiting in Time-Dependent Networks Is NP-Hard, Department Electrical Engineering, Technion-Israel Institute of Technology. Technical Report."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1287\/opre.17.3.395","article-title":"An Appraisal of Some Shortest-Path Algorithms","volume":"17","author":"Dreyfus","year":"1969","journal-title":"Oper. Res."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1016\/j.tcs.2016.07.003","article-title":"Search-space size in contraction hierarchies","volume":"645","author":"Bauer","year":"2016","journal-title":"Theor. Comput. Sci."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1137\/0710032","article-title":"Nested Dissection of a Regular Finite Element Mesh","volume":"10","author":"George","year":"1973","journal-title":"SIAM J. Numer. Anal."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Gottesb\u00fcren, L., Hamann, M., Uhl, T.N., and Wagner, D. (2019). Faster and Better Nested Dissection Orders for Customizable Contraction Hierarchies. Algorithms, 12.","DOI":"10.3390\/a12090196"},{"key":"ref_27","unstructured":"Z\u00fcndorf, M. (2019). Customizable Contraction Hierarchies with Turn Costs. [Bachelor\u2019s Thesis, Karlsruhe Institute of Technology]."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"2.4:1","DOI":"10.1145\/3362693","article-title":"Real-time Traffic Assignment Using Engineered Customizable Contraction Hierarchies","volume":"24","author":"Buchhold","year":"2019","journal-title":"ACM J. Exp. Algorithmics"},{"key":"ref_29","first-page":"112","article-title":"Algorithms for the Reduction of the Number of Points Required to Represent a Digitized Line or its Caricature","volume":"10","author":"Douglas","year":"1973","journal-title":"Cartogr. Int. J. Geogr. Inf. Geovis."},{"key":"ref_30","first-page":"159","article-title":"An optimal algorithm for approximating a piecewise linear function","volume":"9","author":"Imai","year":"1987","journal-title":"J. Inf. Process."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Hoefler, T., and Belli, R. (2015, January 15\u201320). Scientific benchmarking of parallel computing systems: Twelve ways to tell the masses when reporting performance results. Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, Austin, TX, USA.","DOI":"10.1145\/2807591.2807644"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Demetrescu, C., Goldberg, A.V., and Johnson, D.S. (2009). The Shortest Path Problem: Ninth DIMACS Implementation Challenge, American Mathematical Society. DIMACS Book.","DOI":"10.1090\/dimacs\/074"},{"key":"ref_33","first-page":"568","article-title":"Highway Hierarchies Hasten Exact Shortest Path Queries","volume":"Volume 3669","author":"Sanders","year":"2005","journal-title":"Proceedings of the 13th Annual European Symposium on Algorithms (ESA\u201905)"},{"key":"ref_34","unstructured":"Dibbelt, J. (2016). Engineering Algorithms for Route Planning in Multimodal Transportation Networks. [Ph.D. Thesis, Karlsruhe Institute of Technology]."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/3\/90\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T05:36:19Z","timestamp":1760160979000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/3\/90"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,16]]},"references-count":34,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2021,3]]}},"alternative-id":["a14030090"],"URL":"https:\/\/doi.org\/10.3390\/a14030090","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,3,16]]}}}