Research Of One-to-One Shortest Path Algorithm And Design Of On-Vehicle Navigation System

Shortest path problems are often found in logistics distribution, on-vehicle navigation, communication network and so on, and many efficient algorithms based on classical Dijkstra algorithm have been developed already. No matter in logistics distribution or in on-vehicle navigation, one-to-one shortest path problem is the most common issue among all kinds of shortest path problems.First, all kinds of often used one-to-one shortest path algorithms are introduced in this paper, including classical algorithms. A*algorithm, Genetic Algorithm and Ant Colony Algorithm. And their advantages and disadvantages are compared with each other in quite detail.Secondly, based upon the increasingly mature multicore and multithread techniques, traditional A*algorithm is improved and an A*algorithm based upon multicore and multithread is developed. Tests show that this multicore and multithread based A*algorithm incorporating directly inserted binary heap data structure improved from standard binary heap can enhance the searching efficiency of one-to-one shortest path to a great extent.Thirdly, aiming at the performance requirement of one-to-one shortest path problem in large size network and the characteristics of one-to-one shortest path model. a series of improvements are made upon Genectic Algorithm, including initializing method of population. selection method, crossover method and mutation method, and the crossover ratio and mutation ratio can be adjusted adaptively. It is proved by tests that this adaptive Genetic Algorithm is high-speed and flexible, can effectively avoid broken roads and loop roads, and can satisfy the requirement of one-to-one shortest path problem in large size network.Finally, by adopting above multicore and multithread based A*algorithm. an on-vehicle navigation system of Android edition is developed on embedded platform using Eclipse. And this on-vehicle navigation system is evaluated on the electronic map of Nanchang city and gets very good results.