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

Download PDF

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. 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.