Research On Route Planning Algorithm In Vehicle Navigation System

Several key problems in route planning algorithm in Vehicle Navigation System (VNS) are studied in this dissertation, which include fusion methods of the road properties and traffic information, evaluation methods of the optimal route, and the shortest path searching algorithms, etc. The main and original works are as follows:1. Firstly, the paper presents the key techniques in VNS, analyzes the background and current research of the key problems in route planning in VNS, and points out the main problems to be studied. Then, vital theory and methods are put forward, which are the base of the study of this dissertation.2. The basic problems of the route planning in VNS are presented. The paper discusses the quantification methods for the road properties and traffic information and the effect to the planning; and then explains the two key problems of the route planning in VNS detailedly, which are evaluation methods of the optimal route and the shortest path searching algorithms.3. The applications of the information fusion theory in optimal route planning are studied. The basic theory of the weighted mean method, Bayes's theorem and evidence theory are introduced, then point out the the main problems of the three algorithm respectively and improve them. And using the improved methods to make a fusion about the route property and traffic information, and apply them in the route planning. The three methods are analyzed and compared. The experiments show that the results based on the information fusion theory are better than the usual methods, especially the result based on evidence theory is better than the other two, and that makes some foundations for the shortest route searching.4. The applications of the swarm intelligence for the shortest route searching are studied. The basic theory of the ant colony optimization algorithm, particle swarm optimization algorithm and bee colony optimization algorithm are presented. The paper improves the three algorithms and makes them fit for the route planning in VNS; compare the advantages and disadvantages of the three algorithms, and present some notions about the applications of the swarm intelligent theory in route planning in VNS. In the end, we get a conclusion about the improvement of the swarm intelligent optimization algorithms and the problems to be solved. The experiments show that the particle swarm optimization algorithm is more suitable for the large district searching, but there are few theory for the three algorithm in route planning, they should be studied more.