Optimized Customizable Route Planning in Large Road Networks with Batch Processing DOI: XXXXXXX.XXXXXXX

Muhammad Farhan, Henning Koehler · 2026

Read Optimized Customizable Route Planning in Large Road Networks with Batch Processing DOI: XXXXXXX.XXXXXXX by Muhammad Farhan, Henning Koehler (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-10608.txt.

Introduction

Farhan and Koehler improve customizable route planning for large road networks. Planners must answer millions of queries under changing costs like travel time, fuel, and tolls. Building on Customizable Tree Labeling, they introduce leaner ways to store and rebuild path information. Several variants trade memory against query speed. A batch strategy shares path data across queries to cut repeated work. Tests on 13 real road networks show their methods clearly beat the current state of the art.

Catalog record

CREATORMuhammad Farhan, Henning Koehler
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE97125
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.10608

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Optimized Customizable Route Planning in Large Road Networks with Batch Processing DOI: XXXXXXX.XXXXXXX Muhammad Farhan, Henning Koehler Abstract . Modern route planners such as Google Maps and Apple Maps serve millions of users worldwide, optmizing routes in large-scale road networks where fast responses are required under 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. Notably, Customizable Tree Labeling (CTL) was recently introduced as a promising 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 under 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 Customizable Tree Labeling framework to introduce new optimizations for the storage and reconstruction of path information. We develop 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. Empirically, we have 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. 1. Introduction Finding an optimal route between two locations in a road network is a fundamental task in modern navigation systems. What constitutes an optimal route, however, can vary widely. Some users want the fastest path to minimize travel time, others prefer routes that minimize distance to reduce fuel consumption or aim to avoid tolls, and many applications must balance several factors at once. For example, logistics companies must minimize both delivery time and fuel costs while meeting customer deadlines ( 15 ) , eco-routing systems trade-off between travel time and vehicle energy consumption ( 4 ) , and multi-modal transport planners balance transfer times, ticket costs, and overall travel duration ( 8 ) . This diversity makes route planning more complex than simply finding the shortest path under a single fixed cost metric. To optimize route computation at scale, a plethora of methods have been developed ( 23 ; 26 ; 9 ; 7 ; 30 ; 39 ; 13 ; 34 ; 2 ; 1 ; 19 ; 5 ; 29 ; 27 ; 41 ; 46 ) , most notably Contraction Hierarchies (CH) ( 23 ) , Hub Labeling (HL) ( 1 ; 2 ) , and Transit Node Routing (TNR) ( 9 ; 7 ) . These approaches preprocess the network to build auxiliary data structures that allow queries to be answered in milliseconds or even microseconds. Although highly effective when the cost metric is fixed, supporting multiple metrics would require building separate auxiliary structures, which can quickly becomes infeasible in terms of memory. Moreover, updating these structures when edge weights change, for example due to traffic conditions, is costly. While incremental maintenance techniques exist ( 36 ; 45 ; 21 ; 31 ; 24 ) , they are only efficient when a very small number of changes in the metric occur at a time. To address these challenges, customizable techniques were developed ( 15 ; 18 ; 11 ; 20 ) . Their key idea is to separate preprocessing into two phases. The first phase is independent of the metric and captures only the topological structure of the road network, which rarely changes. The second phase is metric-dependent and adapts this structure to a specific cost metric, which can then be used to answer queries efficiently. This approach makes it possible to efficiently reflect changing cost metrics without recomputing everything from scratch. The most well-known customization techniques are Customizable Route Planning (CRP) ( 15 ) and Customizable Contraction Hierarchies (CCH) ( 18 ) . They achieve very fast customization but still suffer from slower query times compared to classical CH or TNR. Customizable Hub Labeling (CuHL) ( 11 ) extended the customization idea to hub labeling, but this work remained theoretical and did not provide practical algorithms. Figure 1. Framework overview: relationship to existing work; novel contributions highlighted in red. SG \backslash PA n one b asic e xtended b asic CTL bn CTL bb – e xtended CTL en CTL eb CTL ee Figure 2. (left) CTL variants from different storage choices in shortcut graphs (SG) and path arrays (PA). (right) Query time vs. labeling size for these variants on large networks. Very recently, we proposed Customizable Tree Labeling (CTL) in ( 20 ) , which combines ideas from labeling and hierarchical methods. CTL introduces a customizable labeling framework based on the 2-hop cover property. The framework uses a tree hierarchy to capture the topological structure of the road network, a shortcut graph scheme to integrate new metrics, and tree labels to support query answering. CTL also introduces a parameterized customization method, giving flexibility to balance preprocessing effort, customization time, and query speed. While CTL represents an important advance, it also has limitations. In particular, the way CTL handles path information is not fully optimized for efficient route computation. Although CTL allows fast distance queries, reconstructing actual paths can be very slow, making it the main bottleneck. In this article, we leverage CTL by exploring how different choices of precomputed path information affect performance. Our focus is on two components: the shortcut graph (SG) and the path arrays (PA). For SG, we consider basic storage, which only keeps the triangle node needed for path reconstruction, and extended storage, which records richer path information. For PA, we examine three options: no path arrays, basic storage that records only the endpoint of the first shortcut, and extended storage that includes both the endpoint and additional path information. Combining these options yields six variants of CTL, five of which are practical, as shown in Figure 2 (left). Each variant represents a different trade-off between memory requirements and query performance. Variants without path arrays use less memory but are slower at query time. In contrast, variants with extended path storage achieve much faster queries but at the cost of larger label sizes. Our experimental results shown in Figure 2 (right) confirm these trade-offs. In addition, we propose a batch processing approach which further improves query times when doing so is most critical, i.e., during high workloads. Here we find that our 2-hop structure based on a shortcut graph naturally lends itself for identifying common subpaths which can be reused, as illustrated in Figure 1 . Contributions. This article is an extended version of ( 20 ) . The following contributions are novel, as highlighted in Figure 1 . • We propose an effective approach for storing additional path information within shortcuts and path arrays to speed up

Read the complete text