language: en

Route Guidance Support in Intelligent Transportation Systems: An Encoded Path View Approach

University of Michigan Technical Report 1995.
Yun-Wu Huangy, Ning Jingz, and Elke A. Rundensteinery
e-mail: [ywh j jning j rundenst] @eecs.umich.edu
Department of Electrical Engineering and Computer Science University of Michigan,
Ann Arbor, MI 48109
Department of Electrical Engineering Changsha Institute of Technology,
Changsha, Hunan, P.R. China

Abstract Efficient path computation necessary for route guidance has been identified as one of the key requirements for Intelligent Transportation Systems (ITS) applications. While the current ITS literature has focused on the application of search algorithms (typically, heuristic A* algorithms) to provide for compute-on-demand path finding, we propose an encoded path view approach that precomputes optimal paths. Advantages of our approach include (1) route search is efficient and less dependent on system load, (2) alternative paths are materialized in addition to the optimal paths, simplifying the process of global optimization, (3) the storage overhead is manageable and less than for the full enumeration of all possible paths. In this paper, we present algorithms for incrementally updating the encoded path view structure in response to weight changes on the traffic links of the underlying network. Despite non-optimal paths also being materialized, our algorithms are designed to operate on cyclic planar graphs | given that ITS maps typically correspond to highly interconnected grid structures. In this paper, we show that while our approach does not encode all paths, it omits some non-optimal paths to resolve cycle ambivalence and will recover them once they become optimal. Proofs of correctness and of complexity are also given. We demonstrate the potential of our approach by presenting experimental results of evaluating our approach both on randomly generated as well as on real city map data. Our experiments furthermore compare the proposed approach against more conventional path searching algorithms, which correspond to the state-of-the-art for route guidance in ITS.

Index Terms | View Materialization, Encoded Path Structure, Route Guidance, Path Retrieval, Map Databases, Cycle Detection.

[This work was supported in part by the University of Michigan ITS Center of Excellence grant (DTFH61-93-X-00017-Sub) sponsored by the U.S. Department of Transportation and by the Michigan Department of Transportation. Ning Jing, on leave from the Changsha Institute of Technology, is currently visiting the University of Michigan and likes to thank the State Education Commission of P.R. China.]