路径搜索策略研究

Path Searching Strategies Research

针对城市道路网车辆导航系统中经典Dijkstra最短路径搜索算法中存在的计算效率问题，研究基于启发式策略和双向搜索策略的双向启发式优化搜索算法，并探讨路网的分层搜索策略．采用启发信息减少搜索范围、双向搜索分解搜索空间，从而提高了算法的执行效率．实际路网仿真结果表明：相比经典Dijkstra算法，启发式策略搜索效率可提升70％～80％，双向搜索策略在不损失搜索精度下进一步提高搜索效率5％～10％，而分层搜索策略可以极大提高大规模路网车辆导航长距离下路径搜索效率．

Computational efficiency is widely recognized to be the critical issue in the shortest route searching algorithm on urban road traffic network vehicle navigation system using classic Dijkstra algorithm. Heuristic search strategy and bi-directional search strategy are studied, including the exploration with multi-level road networks search strategy. Heuristic information is utilized to limit the search area and bi-directional search method is proposed to decompose the search space, the efficiency of computing shortest path was improved and acceptable results were given with the algorithms. Comparative simulation results on traffic network indicate 70% - 80% computation efficiency improvement by heuristic strategy against classical Dijkstra algorithm and continual 5 % - 10% efficiency gains without losing accuracy by bi-directional search strategy. Finally, multi-level search strategy indicates promising efficiency boost in long distance vehicle navigation system under real traffic networks.