Path Searching Strategies Research

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.