Research And Implement Of Route Layout Algorithm In Vehicle Navigation System

Vehicle Navigation System is becoming one of the most popular areas in multi-technologies application with the fast development of Global Positioning System, Geographic Information System, the electronics technology and computer technology. It can prevent the occurrence of traffic jam in maximum, reduce the time of vehicles' stay on the road, and finally realize the traffic flow's optimal allocation in various sections of the road network, so that the road network can be used most reasonably and effectively.The issue of route layout is the hard core of navigation. It is requested to help drivers find the optimal path from starting to destination fleetly and accurately by using some kind of strategy according to the topology information stored in navigation system's internal electronic map. Therefore, route layout algorithm's design and research in Vehicle Navigation System is particularly important.How to achieve efficient route layout is the main contents of this paper. According to the route layout needs, this paper introduces route layout project based on classical Dijkstra algorithm, and gives concrete steps to achieve. However, because this algorithm has shortcomings of long time-consuming and occupying large space, it is not suitable for navigation system's requirement. Therefore the paper mainly researches on heuristic search algorithm - A~* algorithm, which has great improvement in the efficiency of optimal route layout. Based on the in-depth understanding of A~* algorithm, the paper focus on the selected strategy of estimated function, proposes four construction methods of estimated function, and adopts binary heap node sort strategy to optimize A~* algorithm so that the efficiency of algorithm and search speed are improved. Considering the actual traffic conditions, this paper has research on traffic control, crossing delays, as well as starting and destination point problems, and then proposes solutions. Considering the drivers' actual demand, the paper has a related discussion on how to achieve the different route layout standards such as the shortest distance, the optimal time and the least cost. Finally, the paper uses Maplnfo's MapX5.0 control for integrated development with common software development tools VB6.0 as platform for the development. By loading digital map of MapInfo format, the paper achieves the optimal route layout function, confirms the validity and rationality of the improved A~* algorithm, then analyzes and compares Dijkstra algorithm, original A* algorithm with the improved A~* algorithm. The result indicates that after adopting binary heap node sort strategy, the improved A~* algorithm has less average search time than Dijkstra algorithm and original A~* algorithm, and leads to the conclusion that improved A~* algorithm has much improvement in the efficiency of route layout.