language: en

Hierarchical Path Views: A Model Based on Fragmentation and Transportation Road Types

Yun-Wu Huangy, Ning Jingz, and Elke A. Rundensteinery
e-mail: [ywh | jning | rundenst] @eecs.umich.edu
Dept. of Electrical Engineering and Computer Science, Univ. of Michigan,
Ann Arbor, MI48109
Dept. of Electrical Engineering, Changsha Institute of Technology,
Changsha, Hunan, China

Abstract Efficient path query processing necessary for route guidance has been identified as one of the key requirements for Intelligent Transportation Systems (ITS) applications. While precomputing the view of all shortest paths provides the most efficient path retrieval, the view maintenance and storage costs become unrealistic for large ITS networks. Based on ITS road type classification, we propose a hierarchical path view approach, in which the path view maintenance and storage costs are dramatically reduced at the cost of negligible loss of path optimality. Comparing with the traditional ITS path finding approaches that use A or hierarchical A , our hierarchical approach is superior in three areas: 1) path search is more efficient, 2) the connecting point from the low-level roads to the high-level roads and vice versa are dynamically determined based on the most recent traffic, 3) within one region, the high-level traffic can be dynamically rerouted through the low-level roads. In this paper, we conduct experiments to gain insight into the performance of our proposed algorithms and model, as well as to contrast the difference in computational resource requirements between the hierarchical path view and the A algorithms.

1 INTRODUCTION