Diversified Route Planning in Route Networks

Efficient route planning is essential for managing urban traffic flow and individual commutes. However, existing algorithms often generate highly overlapping paths for similar origin-destination (OD) pairs. This phenomenon limits user choices and contributes to localized congestion by funneling traffic into a limited number of major roads. The Diversified k-Shortest Path (DkSP) problem addresses this challenge by seeking a set of k paths that are both near-optimal in distance and sufficiently distinct. Nevertheless, current search-based algorithms frequently encounter a trade-off between computational efficiency and result quality, leading to prohibitive query times or incomplete result sets in large-scale road networks. To address these limitations, this thesis develops a DkSP algorithm based on edge deviation and path concatenation over a precomputed Shortest Path Tree (SPT). By utilizing SPT inheritance and deviation edges, the method categorizes and assembles path candidates from sub-path segments, bypassing the overhead of repetitive Dijkstra-like traversals. A loop detection mechanism ensures path simplicity, allowing the framework to minimize query latency while preserving comprehensive search space coverage. Furthermore, Chapter 4 extends these concepts by developing a hybrid diversified routing system. This system unifies existing algorithms under a theoretical framework that identifies key performance factors, selects optimal heuristic methods, and introduces a query classification module to determine processing strategies based on estimated complexity. Recognizing that enumerating KSP is a core operation whose computational overhead often bottlenecks downstream tasks like DkSP, Chapter 5 specifically addresses the scalability issues and indexing limitations of traditional KSP solvers. By introducing iKSP, a framework that adapts the H2H index for parameter-independent pathfinding, this work provides an efficient foundation for diversified routing. Evaluations on real-world road networks confirm that iKSP significantly improves query performance over existing baselines.