標題: | Hybrid shortest path algorithm for vehicle navigation |
作者: | Cho, Hsun-Jung Lan, Chien-Lun 運輸與物流管理系 註:原交通所+運管所 Department of Transportation and Logistics Management |
關鍵字: | Shortest path algorithm;Heuristics;Hierarchical network |
公開日期: | 1-八月-2009 |
摘要: | 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. |
URI: | http://dx.doi.org/10.1007/s11227-008-0236-7 http://hdl.handle.net/11536/6907 |
ISSN: | 0920-8542 |
DOI: | 10.1007/s11227-008-0236-7 |
期刊: | JOURNAL OF SUPERCOMPUTING |
Volume: | 49 |
Issue: | 2 |
起始頁: | 234 |
結束頁: | 247 |
顯示於類別: | 期刊論文 |