The Research Of Dynamic Path Planning And Application System Design For Internet

Route planning is a classical problem in network optimization, which is widely used in logistics transportation, traffic navigation, communication engineering, computer engineering and other fields. The essence of route planning in road networks is the shortest path problem in graph theory, and Dijkstra algorithm is recognized as the most classical algorithm to solve this problem.But with the development of transportation, the complexity of the road network increased and the scale of network expanded such as Dijkstra algorithm would be far too slow in large road networks. Thus, many speedup strategies are proposed, such as heuristic strategy, bidirectional searching strategy, hierarchical compression strategy and so on. During which, the highway hierarchical algorithm based on hierarchical compression strategy has the advantage and which is widely studied, for the algorithm preprocess road network according to a certain percentage of compression, and which improves the compute efficiency by reducing the search space and search volume. Meanwhile, with the development of dynamic traffic information collection technology such as floating cars technique, the availability of dynamic traffic information has been improved, the dynamic route planning has become a study hotspot in recent years. As the demand of planning path rising in logistics and transport systems and public transportation information service, how to build effective and rational dynamic path planning system in the Internet environment becomes a focus of the study. In this context, this thesis studies the route planning algorithm and system based on the―2008 Guangdong Province modern information service development‖project. The main works of this thesis are as follows:Firstly, through the analysis of the Highway Hierarchical algorithm based on road network compression strategy, find that the algorithm has problems such as compression into the ring in road network, the storage of pretreatment data problem and the calculate of the shortest path problem. Improve and implement the algorithm with no-ring compression strategy, tiered storage strategy and local shortest path storage strategy. Secondly, design and implement the path planning system in the internet environment. After analyzing the data transmission problem and multi-user concurrency of the request problem of system, use WCF technology and build up a distributed system, to achieve a reasonable and efficient path planning system.Thirdly, with the availability of dynamic traffic information being improved, this thesis builds dynamic road networks based on the available dynamic traffic data, and the dynamic route planning based on highway hierarchical algorithm is proposed. Dynamic route planning based on large-scale road networks is carried out.A large scale experiment is taken in the road networks of Guangdong Province. The experiment results show that the improved highway hierarchical also is more efficient in the large-scale road network. It ensures the efficiency of path planning system in the internet. The application in the logistics transportation and public travel service also proved that the system has good practical value.