| 基于路网分层策略的高效路径规划算法 |
| |
| 引用本文： | 钟慧玲,章梦,石永强,蔡文学.基于路网分层策略的高效路径规划算法[J].西南交通大学学报,2011,46(4):645-650. |
| |
| 作者姓名： | 钟慧玲 章梦 石永强 蔡文学 |
| |
| 作者单位： | 华南理工大学经济与贸易学院,广东广州,510006 |
| |
| 基金项目： | 2008年广东省现代信息服务业发展专项资金资助项目(06120840B0450124/2); 中央高校基本科研业务费专项资金资助项目(2011SM003) |
| |
| 摘 要： | 为解决路网规模过大导致的路径规划算法计算效率低的问题,通过引入路网分层预处理的思想,采用方向诱导搜索策略、双向搜索策略和数据结构改进策略,提出了一种新的路径规划算法——分层A*算法,并在广东省大规模路网上进行了实验.实验结果表明:与A*算法和Highway Hierarchical算法相比,A*算法的计算效率分别平均提高11.7倍和2.4倍,搜索空间分别平均缩小5.7倍和2.8倍,且新算法的计算效率和搜索空间都更为稳定.
|
| 关 键 词： | 分层路网 最短路 A*算法 预处理 路径规划 |
Efficient Route Plan Algorithm Based on Multi-level Road Network Strategy |
| |
| ZHONG Huiling,ZHANG Meng,SHI Yongqiang,CAI Wenxue.Efficient Route Plan Algorithm Based on Multi-level Road Network Strategy[J].Journal of Southwest Jiaotong University,2011,46(4):645-650. |
| |
| Authors: | ZHONG Huiling ZHANG Meng SHI Yongqiang CAI Wenxue |
| |
| Institution: | ZHONG Huiling,ZHANG Meng,SHI Yongqiang,CAI Wenxue(School of Economics and Commerce,South China University of Technology,Guangzhou 510006,China) |
| |
| Abstract: | In order to overcome the shortcoming of route plan algorithms' inefficiency caused by an oversized road network,a new route plan algorithm,hierarchy A* algorithm,was proposed.The hierarchy A* algorithm is characterized by the multi-level road network decomposition pre-processing,the goal-directed strategy,the bidirectional strategy and the improved data structure strategy.The experimental result shows that compared with the A* algorithm and the highway hierarchical algorithm,the proposed algorithm increases... |
| |
| Keywords: | multi-level road network shortest path A*algorithm pre-processing route plan |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
