KIT | KIT-Bibliothek | Impressum | Datenschutz

Customization Meets 2-Hop Labeling: Efficient Routing in Road Networks

Farhan, Muhammad; Koehler, Henning; Wang, Qing; Wang, Jiawen; Laupichler, Moritz ORCID iD icon 1; Sanders, Peter ORCID iD icon 1
1 Institut für Theoretische Informatik (ITI), Karlsruher Institut für Technologie (KIT)

Abstract:

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 Customizable Tree Labeling (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. ... mehr


Verlagsausgabe §
DOI: 10.5445/IR/1000186100
Veröffentlicht am 27.10.2025
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Zeitschriftenaufsatz
Publikationsdatum 04.09.2025
Sprache Englisch
Identifikator ISSN: 2150-8097
KITopen-ID: 1000186100
Erschienen in Proceedings of the VLDB Endowment
Verlag VLDB Endowment
Band 18
Heft 10
Seiten 3326–3338
Nachgewiesen in Scopus
Dimensions
Web of Science
OpenAlex
KIT – Die Universität in der Helmholtz-Gemeinschaft
KITopen Landing Page