The Design And Implementation Of Route Programming Algorithm In Large Area Based On Vehicle Navigation

With the rapid development of national economy, transportation system has become more and more important. Intelligent Transportation System (ITS) is the main research direction of transportation and route programming is an important part of intelligent transportation. At present, most route programming algorithms are confined within a certain area. While coming across to long-distance movings, there will be a huge road network data, with an increased calculated amount, in result that it will reduce the computing speed and the search efficiency. In reaction to the phenomenon, this study puts nodes and sections into different grades based on the level of road network maps and designs the road network model. It also classifies route programming algorithm in large area into two parts:Intercity route programming algorithm and Urban route programming algorithm.For the well access on the intercity highway, it does not have traffic jams generally. Therefore, it becomes crucial to accelerate the search speed, while using the static navigation mode in the city navigation. This study analyzes the commonly used route programming algorithms. Designed a new route programming algorithm, and the complexity of the algorithm is reduced to O(n). Search efficiency is greatly improved by the optimal path search strategy, shcu as narrowing search scopes, ignoring nodes at low level, and ignoring the reverse of the nodes.For the urban transportation with requent traffic jams, we always take dynamic navigation, because of its great road network density, high complexity and frequent changes of traffic flow. The study firstly introduces the search method of in-and-out points of city. Secondly, it applies the improved Dijkstra algorithm while the beginning and ending points are presented in the same city, in order to improve the search speed of the route.Finally, route programming algorithm in large area makes an organic integration between intercity route programming algorithm and urban route programming algorithm. It develops a prototype system and verifies the method above. It is proved that the route programming algorithm is effective and feasible in this study.