{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T16:40:28Z","timestamp":1777653628778,"version":"3.51.4"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"10","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2025,6]]},"abstract":"<jats:p>\n            Efficient route planning is crucial for modern navigation systems, yet traditional methods face challenges in scenarios with unknown or frequently changing traffic dynamics. This paper introduces a general labeling framework based on the 2-hop cover property, enabling robust, metric-independent preprocessing. Using this framework, we propose\n            <jats:italic toggle=\"yes\">Customizable Tree Labeling<\/jats:italic>\n            (CTL), a tree-based method combining three key components: metric-independent preprocessing with tree hierarchies, metric customization for dynamic updates, and efficient query algorithms for fast route computation. To allow trade-offs between customization time, labeling size, and query performance, we further develop a parameterized customization technique by dynamically combining tree labels and shortcut graphs. Our key contributions include the introduction of a customizable labeling framework, a novel tree hierarchy for compact and scalable representation, and a hybrid query algorithm that integrates labels and shortcuts for fast and accurate route computation. We conduct extensive experiments on ten large-scale real-world road networks and a case study on the traffic assignment problem. Our algorithms achieve query response times significantly faster than the state-of-the-art methods, while maintaining competitive customization times and labeling size, making it well-suited for real-time and dynamic routing applications.\n          <\/jats:p>","DOI":"10.14778\/3748191.3748198","type":"journal-article","created":{"date-parts":[[2025,9,4]],"date-time":"2025-09-04T13:50:16Z","timestamp":1756993816000},"page":"3326-3338","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Customization Meets 2-Hop Labeling: Efficient Routing in Road Networks"],"prefix":"10.14778","volume":"18","author":[{"given":"Muhammad","family":"Farhan","sequence":"first","affiliation":[{"name":"Australian National University, Canberra, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Henning","family":"Koehler","sequence":"additional","affiliation":[{"name":"Massey University, Palmerston North, New Zealand"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qing","family":"Wang","sequence":"additional","affiliation":[{"name":"Australian National University, Canberra, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jiawen","family":"Wang","sequence":"additional","affiliation":[{"name":"Australian National University, Canberra, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Moritz","family":"Laupichler","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology, Karlsruhe, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Sanders","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology, Karlsruhe, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,9,4]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 10th International Conference on Experimental Algorithms. 230\u2013241","author":"Abraham Ittai","unstructured":"Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck. 2011. A Hub-Based Labeling Algorithm for Shortest Paths in Road Networks. In Proceedings of the 10th International Conference on Experimental Algorithms. 230\u2013241."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 20th Annual European Conference on Algorithms. 24\u201335","author":"Abraham Ittai","unstructured":"Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck. 2012. Hierarchical Hub Labelings for Shortest Paths. In Proceedings of the 20th Annual European Conference on Algorithms. 24\u201335."},{"key":"e_1_2_1_3_1","unstructured":"PTV AG. [n.d.]. Western europe dataset. http:\/\/www.ptv.de"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973198.14"},{"key":"e_1_2_1_5_1","volume-title":"Route planning in transportation networks. Algorithm engineering: Selected results and surveys","author":"Bast Hannah","year":"2016","unstructured":"Hannah Bast, Daniel Delling, Andrew Goldberg, Matthias M\u00fcller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato F Werneck. 2016. Route planning in transportation networks. Algorithm engineering: Selected results and surveys (2016), 19\u201380."},{"key":"e_1_2_1_6_1","volume-title":"2007 Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM, 46\u201359","author":"Bast Holger","year":"2007","unstructured":"Holger Bast, Stefan Funke, Domagoj Matijevic, Peter Sanders, and Dominik Schultes. 2007. In transit to constant time shortest-path queries in road networks. In 2007 Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM, 46\u201359."},{"key":"e_1_2_1_7_1","volume-title":"Customizable Contraction Hierarchies-A Survey. arXiv preprint arXiv:2502.10519","author":"Bl\u00e4sius Thomas","year":"2025","unstructured":"Thomas Bl\u00e4sius, Valentin Buchhold, Dorothea Wagner, Tim Zeitz, and Michael Z\u00fcndorf. 2025. Customizable Contraction Hierarchies-A Survey. arXiv preprint arXiv:2502.10519 (2025)."},{"key":"e_1_2_1_8_1","volume-title":"Customizable Hub Labeling: Properties and Algorithms. In International Computing and Combinatorics Conference. Springer, 345\u2013356","author":"Blum Johannes","year":"2022","unstructured":"Johannes Blum and Sabine Storandt. 2022. Customizable Hub Labeling: Properties and Algorithms. In International Computing and Combinatorics Conference. Springer, 345\u2013356."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3362693"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3459245"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403098"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.2014.0579"},{"key":"e_1_2_1_13_1","volume-title":"2011 IEEE International Parallel & Distributed Processing Symposium. IEEE, 1135\u20131146","author":"Delling Daniel","year":"2011","unstructured":"Daniel Delling, Andrew V Goldberg, Ilya Razenshteyn, and Renato F Werneck. 2011. Graph partitioning with natural cuts. In 2011 IEEE International Parallel & Distributed Processing Symposium. IEEE, 1135\u20131146."},{"key":"e_1_2_1_14_1","volume-title":"Algorithmics of large and complex networks: design, analysis, and simulation","author":"Delling Daniel","unstructured":"Daniel Delling, Peter Sanders, Dominik Schultes, and Dorothea Wagner. 2009. Engineering route planning algorithms. In Algorithmics of large and complex networks: design, analysis, and simulation. Springer, 117\u2013139."},{"key":"e_1_2_1_15_1","volume-title":"The shortest path problem: Ninth DIMACS implementation challenge","author":"Demetrescu Camil","unstructured":"Camil Demetrescu, Andrew V Goldberg, and David S Johnson. 2009. The shortest path problem: Ninth DIMACS implementation challenge. Vol. 74. American Mathematical Soc."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2886843"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data.","author":"Farhan Muhammad","year":"2024","unstructured":"Muhammad Farhan, Henning Koehler, Robert Ohms, and Qing Wang. 2024. Hierarchical Cut Labelling-Scaling Up Distance Queries on Road Networks. In Proceedings of the ACM SIGMOD International Conference on Management of Data."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3709685"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0927-0507(05)80110-0"},{"key":"e_1_2_1_20_1","volume-title":"An Algorithm for Quadratic Programming. Naval research logistics quarterly 3, 1\u20132","author":"Frank Marguerite","year":"1956","unstructured":"Marguerite Frank and Philip Wolfe. 1956. An Algorithm for Quadratic Programming. Naval research logistics quarterly 3, 1\u20132 (1956), 95\u2013110."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-68552-4_24"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.1110.0401"},{"key":"e_1_2_1_23_1","series-title":"SIAM journal on numerical analysis 10, 2","volume-title":"Nested dissection of a regular finite element mesh","author":"George Alan","year":"1973","unstructured":"Alan George. 1973. Nested dissection of a regular finite element mesh. SIAM journal on numerical analysis 10, 2 (1973), 345\u2013363."},{"key":"e_1_2_1_24_1","first-page":"156","article-title":"Computing the shortest path: A search meets graph theory","volume":"5","author":"Goldberg Andrew V","year":"2005","unstructured":"Andrew V Goldberg and Chris Harrelson. 2005. Computing the shortest path: A search meets graph theory.. In SODA, Vol. 5. 156\u2013165.","journal-title":"SODA"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3626527"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSSC.1968.300136"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213887"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2002.1033772"},{"key":"e_1_2_1_29_1","volume-title":"Stable Tree Labelling for Accelerating Distance Queries on Dynamic Road Networks. arXiv preprint arXiv:2501.17379","author":"Koehler Henning","year":"2025","unstructured":"Henning Koehler, Muhammad Farhan, and Qing Wang. 2025. Stable Tree Labelling for Accelerating Distance Queries on Dynamic Road Networks. arXiv preprint arXiv:2501.17379 (2025)."},{"key":"e_1_2_1_30_1","volume-title":"Hierarchy Decomposition for Faster User Equilibria on Road Networks","author":"Luxen Dennis","unstructured":"Dennis Luxen and Peter Sanders. 2011. Hierarchy Decomposition for Faster User Equilibria on Road Networks. In Experimental Algorithms, Panos M. Pardalos and Steffen Rebennack (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 242\u2013253."},{"key":"e_1_2_1_31_1","first-page":"3","article-title":"Goal-directed shortest-path queries using precomputed cluster distances","volume":"14","author":"Maue Jens","year":"2010","unstructured":"Jens Maue, Peter Sanders, and Domagoj Matijevic. 2010. Goal-directed shortest-path queries using precomputed cluster distances. Journal of Experimental Algorithmics (JEA) 14 (2010), 3\u20132.","journal-title":"Journal of Experimental Algorithmics (JEA)"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196913"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/3377369.3377371"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2014.08.024"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/3547305.3547315"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561071_51"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561071_51"},{"key":"e_1_2_1_38_1","unstructured":"Christian Schulz. 2013. High Quality Graph Partitioning. Ph.D. Dissertation. Karlsruhe Institute of Technology. http:\/\/digbib.ubka.uni-karlsruhe.de\/volltexte\/1000035713"},{"key":"e_1_2_1_39_1","volume-title":"Urban Transportation Networks","author":"Sheffi Yosef","unstructured":"Yosef Sheffi. 1985. Urban Transportation Networks. Prentice-Hall, Englewood Cliffs, N.J."},{"key":"e_1_2_1_40_1","doi-asserted-by":"crossref","unstructured":"Robert Endre Tarjan. 1983. Data structures and network algorithms. SIAM.","DOI":"10.1137\/1.9781611970265"},{"key":"e_1_2_1_41_1","unstructured":"Zijin Wan Xiaojun Dong Letong Wang Enzuo Zhu Yan Gu and Yihan Sun. 2024. Parallel Contraction Hierarchies Can Be Efficient and Scalable. arXiv:2412.18008 [cs.DS] https:\/\/arxiv.org\/abs\/2412.18008"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1680\/ipeds.1952.11259"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/2140436.2140438"},{"key":"e_1_2_1_44_1","unstructured":"Mengxuan Zhang. 2021. Efficient shortest path query processing in dynamic road networks. Ph.D. Dissertation."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517875"},{"key":"e_1_2_1_46_1","volume-title":"Proceedings of the 12th world conference on transport research (WCTRS)","author":"Zhou Zhong","year":"2010","unstructured":"Zhong Zhou and Matthew Martimo. 2010. Computational Study of Alternative Methods for Static Traffic Equilibrium Assignment. In Proceedings of the 12th world conference on transport research (WCTRS), Lisbon, Portugal. 1\u201315."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3748191.3748198","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,4]],"date-time":"2025-09-04T13:52:32Z","timestamp":1756993952000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3748191.3748198"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6]]},"references-count":46,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["10.14778\/3748191.3748198"],"URL":"https:\/\/doi.org\/10.14778\/3748191.3748198","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2025,6]]},"assertion":[{"value":"2025-09-04","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}