A Zoned Precomputation Framework for Real-Time Routing: The Z-Route Approach

Abstract

Real-time routing on large-scale road networks remains a critical challenge for intelligent transportation systems, particularly under high query loads and increasing graph sizes. While classical shortest path algorithms guarantee exact optimality, their direct application leads to high online computational costs. Conversely, advanced hierarchical and labeling-based methods achieve excellent query performance but rely on heavy preprocessing and complex data structures, which limit their flexibility and system-level integration. This paper proposes Z-Route, a zoned precomputation framework that reconciles exact shortest path computation with architectural modularity and scalability. Z-Route follows a clear offline–online separation. In the offline phase, the road network is spatially decomposed into bounded zones, within which exhaustive shortest paths are precomputed in parallel and stored in a cache. In the online phase, routing queries are resolved by assembling precomputed intra-zone paths with lightweight inter-zone transitions through a compact junction graph, avoiding repeated global graph traversals. By confining online computation to cache lookups and reduced graph operations, Z-Route achieves predictable and stable query times that are largely independent of the global network size, while preserving exact shortest path optimality. Extensive experiments conducted on real-world urban road networks, including medium- and large-scale configurations, demonstrate that Z-Route significantly outperforms global Dijkstra in terms of scalability and query latency as graph size increases. The proposed framework emphasizes modularity, explainability, and ease of integration, making it well suited for system-level routing architectures that combine classical algorithms with higher-level intelligent or adaptive components.