ROUTE GUIDANCE SUPPORT IN INTELLIGENT TRANSPORTATION SYSTEMS : AN ENCODED PATH VIEW APPROACH
Yun-Wu Huang, Jing Ning, Elke Angelika Rundensteiner · 1994
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 cyc...