Optimized Customizable Route Planning in Large Road Networks with Batch Processing

Abstract

Abstract

Modern route planners such as Google Maps and Apple Maps serve millions of users worldwide, optimizing routes in large-scale road networks where fast responses are required for diverse cost metrics including travel time, fuel consumption, and toll costs. Classical algorithms like Dijkstra or A* are too slow at this scale, and while index-based techniques achieve fast queries, they are often tied to fixed metrics, making them unsuitable for dynamic conditions or user-specific metrics. Customizable approaches address this limitation by separating metric-independent preprocessing and metric-dependent customization, but they remain limited by slower query performance. We recently introduced Customizable Tree Labeling (CTL) as a framework that combines tree labelings with shortcut graphs. The shortcut graph enables efficient customization to different cost metrics, while tree labeling, supported by path arrays, provides fast query answering. Although CTL enables optimizing routes with different cost metrics, it still faces challenges in storing and reconstructing path information efficiently, which hinders its scalability for answering millions of queries. In this article, we build on the CTL framework by developing several algorithmic variants that differ in the information retained within shortcut graphs and path arrays, offering a spectrum of trade-offs between memory usage and query performance. To further enhance scalability, we propose a batch processing strategy that shares path information across queries to eliminate redundant computation. We empirically evaluated the performance of our algorithms on 13 real-world road networks. The results show that they significantly outperform state-of-the-art methods, achieving speedups of up to factor 15 for route computation while maintaining practical memory requirements.