Hybrid shortest path algorithm for vehicle navigation |
| |
Authors: | Hsun-Jung Cho Chien-Lun Lan |
| |
Affiliation: | (1) Department of Transportation, National Chiao Tung University, 1001 Ta-Hsueh Road, Hsinchu, Taiwan |
| |
Abstract: | Vehicle navigation is one of the important applications of the single-source single-target shortest path algorithm. This application
frequently involves large scale networks with limited computing power and memory space. In this study, several heuristic concepts,
including hierarchical, bidirectional, and A*, are combined and used to develop hybrid algorithms that reduce searching space, improve searching speed, and provide the
shortest path that closely resembles the behavior of most road users. The proposed algorithms are demonstrated on a real network
consisting 374,520 nodes and 502,485 links. The network is preprocessed and separated into two connected subnetworks. The
upper layer of network is constructed with high mobility links, while the lower layer comprises high accessibility links.
The proposed hybrid algorithms are implemented on both PC and hand-held platforms. Experiments show a significant acceleration
compared to the Dijkstra and A* algorithm. Memory consumption of the hybrid algorithm is also considerably less than traditional algorithms. Results of this
study showed the hybrid algorithms have an advantage over the traditional algorithm for vehicle navigation systems. |
| |
Keywords: | Shortest path algorithm Heuristics Hierarchical network |
本文献已被 SpringerLink 等数据库收录! |
|