EVALUATION OF HIERARCHICAL PATH FINDING TECHNIQUES FOR ITS ROUTE GUIDANCE

Abstract

Efficient path finding necessary for route guidance has been identified as one of the key requirements for Intelligent Transportation System (ITS) applications. Precomputing all-pair shortest paths for an ITS network would make retrieval of paths extremely efficient allowing a high throughput of path finding requests, though at the cost of precomputed path maintenance and storage. To overcome these costs, which grow quadratically with the size of the ITS networks, we propose the utilization of a hierarchical structure for encoding paths. The main contributions of this paper are two fold. First, an extensive experimental evaluation of our proposed hierarchical path structure, determining both its benefits and limitations as well as contrasting it with alternative techniques currently employed for ITS route guidance is conducted and analyzed. Secondly, we apply our hierarchical path structure model to the Detroit city and vicinity road maps that are very large in size (30,000 nodes) for which the application of path precomputation techniques was previously considered impractical. Our experiments demonstrate that the maintenance costs of the path structure are dramatically reduced in our hierarchical model. We also demonstrate that 3-level hierarchical path structures have superior maintenance costs over 2-level path structures for large maps, with only a negligible performance penalty for path retrieval. Our hierarchial path structure is more efficient in path retrieval than alternative path finding algorithms, such as A and Hierarchical A. Therefore, our approach offers a feasible solution to path finding for centralized ITS route guidance.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 11 citations exist upstream.