A Hierarchical Path View Model for Path Finding in Intelligent Transportation Systems

Abstract

Effective path finding has been identified as an important requirement for dynamic route guidance in Intelligent Transportation Systems (ITS). Path finding is most efficient if the all-pair (shortest) paths are precomputed because path search requires only simple lookups of the precomputed path views. Such an approach however incurs path view maintenance (computation and update) and storage costs which can be unrealistically high for large ITS networks. To lower these costs, we propose a Hierarchical Path View Model (HPVM) that partitions an ITS road map, and then creates a hierarchical structure based on the road type classification. HPVM includes a map partition algorithm for creating the hierarchy, path view maintenance algorithms, and a heuristic hierarchical path finding algorithm that searches paths by traversing the hierarchy. HPVM captures the dynamicity of traffic change patterns better than the ITS path finding systems that use the hierarchical A * approach because: (1) during path search, HPVM traverses the hierarchy by dynamically selecting the connection points between two levels based on up-to-date traffic, and (2) HPVM can reroute the high-speed road traffic through local streets if needed. In this paper, we also present experimental results used to benchmark HPVM and to compare HPVM with alternative ITS path finding approaches, using both synthetic and real ITS maps that include a large Detroit map (> 28,000 nodes). The results show that the HPVM incurs much lower costs in path view maintenance and storage than the non-hierarchical path precomputation approach, and is more efficient in path search than the traditional ITS path finding using A * or hierarchical A * algorithms.