Application Research On Path Planning In Vehicle Navigation System

Intelligent Transportation System helps to reduce traffic congestion and achieves a reasonable distribution of traffic flow. It can promote the traffic network to be effective and provide a complete solution for the increasingly serious traffic problems. Vehicle Navigation System is an important part of Intelligent Transportation System. With the rapid development of positioning, communication and geographic information technology, Vehicle Navigation System becomes a hot research topic gradually.Path planning requires vehicle navigation equipment can help the driver to adopt a strategy to calculate an optimal path from the origin to the destination rapidly based on the topology information in the electronic map. Path planning is one of the core technologies in Vehicle Navigation System, and it is also the basis to achieve accurate and real-time vehicle navigation. Path planning plays an extremely important role in the study and realization of vehicle navigation system.This paper mainly research on path planning in Vehicle Navigation System. First of all, the concept of path planning, its current development and basic principles are introduced based on a comprehensive analysis of Vehicle Navigation System modules. And then transport network structure which can affect the efficiency of path planning algorithm and electronic maps are described in detail through combining with the theory of graph. Second, principles, implementation methods and time complexity of common path planning algorithms are analyzed in detail. Heuristic search algorithm is considered to have the advantages of efficiency and convenient and is fully suitable for vehicle navigation system applications.In this paper, A* algorithm is selected to be the basic algorithm on which an improved algorithm is based. Basic principles and realization steps of the A* algorithm are fully analyzed and discussed in detail. After A* algorithm is deeply understood, it is optimized using the method of the least heap ranking to node. Then an improved algorithm, bidirectional and hierarchical search A* algorithm based on least heap, is proposed combined with bidirectional and hierarchical search strategy. In the algorithm into which bidirectional search strategy is introduced, stop conditions of bidirectional search and switching criteria is discussed. After comparing several common methods of GIS development, an integrated secondary development approach is used in the design of this article. Mapinfo MapX5.0 controls and Visual C++ are selected to be the visualization tools and development platform for the application development. The improved path planning algorithm is implemented on Lingtu electronic map of version 4.3 and experimental results are obtained.Finally, results of four algorithms, that is traditional A* algorithm, bidirectional search A* algorithm, bidirectional search A* algorithm based on least heap, bidirectional and hierarchical search A* algorithm based on least heap, are analyzed and compared at the criterion of path length that the algorithm searches out and running time of the algorithm, an conclusion that speed of path search of the improved algorithm is significantly improved is reached. So, the improved algorithm in this article is tested to be feasible and rational.