Research On Optimal Path Algorithm In GPS Vehicle Navigation System

In recent years, with the rapid development of traffic and transportation industry, the vehicle navigation system has become an important research subject in the current transportation application field. The vehicle navigation system provides users with the best route layouts based on real-time traffic information, which can shorten the retention time of the vehicles on the road, reduce the amount of the vehicle emissions, and alleviate fog and haze to improve the environment,In addition, it can save a lot of time for users, and make the road resources fully utilized. Therefore, the route layouts of users become particularly important.Being the core of the vehicle navigation system, the route layout requires the system to help drivers from the starting place to the destination plan an optimal route according to the stored electronic map topology information and certain route layout algorithm. Therefore, the route layout algorithm research of the vehicle navigation system is of great significance. The common route layout algorithms in vehicle navigation systems mainly are Dijkstra algorithm and A* algorithm, but the existing algorithms work inefficiently, are not suitable to be used in vehicle navigation systems directly, and need to be improved and optimized.The thesis mainly talks about how to improve the efficiency of the algorithm through improving the data structure of the algorithm and A* algorithm evaluation function. Due to the mature technology in the traffic detection, suppose the road traffic situation is known, the thesis assesses a variety of classic layout algorithms and makes improvements based on the original algorithms. First, Dijkstra algorithm is studied and its realization is described, as Dijkstra algorithm aims to calculate the shortest route by traversing all nodes of the network. The algorithm is inefficient, occupies a lot of storage space, and is not suitable for vehicle-mounted systems. Then, A* algorithm is studied and its realization is described. Comparing Dijkstra algorithm with A* algorithm, the thesis focuses on the research of the heuristic search algorithm A* algorithm. In data structure optimization, binary heap is used to sort all nodes. In the process of repeating storage, it saves plenty of time and promotes the algorithm’s efficiency as well, In the improvement of evaluation function, direction judgement is added in searching routes and the nearest nodes that are in the same direction with the destination are chosen. By the way, the efficiency is realized. In conclusion, final experimental data show that, in terms of the distance and the efficiency, the improved algorithm is superior to the original algorithm. In real applications, all kinds of factors that influence the driving time should be considered, such as traffic jams and other factors. In the thesis, the factors of the distance and section speed are proposed and considered, different weightings are assigned based on the distance and road speed, the fast speed section which is close to the end is laid out. Thus, the optimal route with minimum time is laid out.Finally, in the thesis, with the two softwares of Microsoft company---Microsoft Visual Studio 2010 and MapInfo, a different number of nodes and routes are respectively generated, and the route layout is operated on the road network nodes and routes. Suppose that the number of road network nodes is 200, by using the original algorithm and the improved algorithm, the distances of the route layout are 15.7 kilometers and 13.2 kilometers respectively. Compared with each other, there are 2.5 kilometers reduced. In the aspect of time, it is 53 milliseconds based on the original algorithm while it is 20 milliseconds based on the improved algorithm. Compared with each other, there are 33 milliseconds shortened. Suppose that the number of road network nodes is 1000, by using the original algorithm and the improved algorithm, the distances of the route layout are 76.1 kilometers and 64.7 kilometers respectively. Compared with each other, there are 11.4 kilometers reduced. In the aspect of time, it is 164 milliseconds based on the original algorithm while it is 67 milliseconds based on the improved algorithm. Compared with each other, there are 97 milliseconds shortened. The experiment proves that the improved algorithm is superior to the original algorithm on the distances of the route layout and the execution efficiency.