標題: 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
顯示於類別:期刊論文


文件中的檔案:

  1. 000269060200004.pdf

若為 zip 檔案,請下載檔案解壓縮後,用瀏覽器開啟資料夾中的 index.html 瀏覽全文。