Optimal Path Algorithm Research In Vehicle Navigation System

These years every country applies modern science and technology, such as Intelligent Transportation System(ITS) to solve traffic problem. The study on Vehicle Navigation Systems (VNS) is an important research in the ITS, Which guides the travelers by providing them with optimal route based on real-time traffic information. As a result the travel time should be shorted and the traffic congestion should be avoided. Meanwhile the environmental pollution should be alleviated. Being one of the core technologies of VNS, optimal algorithm is the basis of correct and effective route guidance function.In chapter 1, a brief development history of vehicle navigation system is reviewed and the research status quo is introduced. In chapter 2, we determine to focus on some key technologies that impact the practicability of vehicle navigation system currently. In chapter 3, the solution to the representation of road network aiming at the route planning of vehicle navigation is given. As far as the road network is concerned, the connectivity has two layers of meanings. By means of constructing dual network, the connectivity of road network, including one-way traffic, turn restrictions at intersections, and etc., are completely described. The methodologies of calibrating the road weight measured by travel time based on road impedance function model and signalized intersection delay model are proposed.In chapter 4, the traditional algorithms of current optimal path chosen, which contained Dijkstra algorithm and A* algorithm, are researched.This paper brings forward improved Dijkstra algorithm. It can be more quickly to find the superior solution.Through a experiment of simulation and contrast, it can be known that the improved optimal path algorithm has a little exaltation on the efficiency indeed.