Dynamic Path Navigation Algorithm Research

With the development of economy and the improvement of people’s living standard,traffic demand has been ever-increasing.However,the speed of traffic infrastructure construction in China is quite slow,which leads to traffic congestion in most cities.Therefore,the concept of the intelligent transportation system has emerged at the right moment.In the intelligent transportation system,the efficient vehicle navigation system can ease the traffic congestion by providing trip schemes.The core technology of the vehicle navigation system is to plan an optimal path or an approximate optimal path in a short time,so as to increase the throughput of the road,which has high requirements for the timeliness and accuracy of the path planning algorithm.Because the traffic network is large,the traditional path planning algorithm cannot achieve effective real-time path planning or the traditional algorithm cannot be directly applied to the navigation.At present,mainstream maps are mainly based on the road level of graphical topology to build a hierarchical road network.However,such a road networkbuilding approach would lower the accuracy of path search and prevent a full use of historical traffic data,thus reducing the efficiency of the path planning algorithm.The path planning algorithm cannot fully use the effective information in the network,so the accuracy and timeliness of the planning would be greatly lowered.In view of limitations of the traditional road network and path planning algorithm,this paper put forward the Virus road network and Virus A * algorithm after an in-depth investigation of existing road network models and path planning algorithms.Virus road network is a dynamic and generalized topological road network which is built by adopting the Virus colony search algorithm for hierarchy,digging historical traffic data and retaining intermediate search information.Virus road network is a generalized network model which can not only show static geographic characteristics of urban transportation,but also reflects dynamic changes of the urban transportation,so it is convenient to make path optimization on this model.The algorithm is implemented and the effectiveness of the road network is verified by an experiment and comparison in the real network.In the road network building,large-scale GPS points would cost too long time to build and update the road network.This paper presented a method for simplifying and improving ST-matching,to greatly reduce the matching time,while lowering the accuracy rate.According to the characteristics of Virus road network and combined with LPA * path planning algorithm,a Virus A * algorithm was proposed in this paper.While largely maintaining the accuracy rate,the Virus A * algorithm greatly improves the real-time performance.This algorithm can help to make path planning based on prediction,thus reducing the loss of re-planning.Moreover,data about maps in Fuzhou was collected to make a simulation experiment,to prove that the Virus network partitioning and hierarchy would have a significant effect on reducing the time of the algorithm’s path planning.The Virus A * path planning algorithm has good real-time performance in the dynamic traffic environment.Lastly,the implementation and demonstration of the Virus road network and the Virus A * path planning algorithm on mobile terminals were introduced.