作　　者： ;

机构地区： 华南理工大学

出　　处： 《西南交通大学学报》 2011年第4期 645-650,共6页

摘　　要： 为解决路网规模过大导致的路径规划算法计算效率低的问题,通过引入路网分层预处理的思想,采用方向诱导搜索策略、双向搜索策略和数据结构改进策略,提出了一种新的路径规划算法——分层A＊算法,并在广东省大规模路网上进行了实验.实验结果表明：与A＊算法和Highway Hierarchical算法相比,A＊算法的计算效率分别平均提高11.7倍和2.4倍,搜索空间分别平均缩小5.7倍和2.8倍,且新算法的计算效率和搜索空间都更为稳定. 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 the computational efficiency by averages of 11.7 and 2.4 times respectively,reduces the search space by averages of 5.7 and 2.8 times,respectively,and has a stable search space and computational efficiency.

关 键 词： 分层路网 最短路 A＊算法 预处理 路径规划

分 类 号： [U495]

领　　域： []