Research On Navigation Network Data Model For Route Planning

With the expansion of cities and the development of transportation, the road network of urban is getting huger and huger. In order to get the reasonable path quickly and accurately in the amount of network data, the thesis discusses the complexity of road network in natrue, proposes a "divide and rule" strategy, and designs a route planning algorithm based on the layer-block network data model. The concepts of layer-block network and complex layer-block network are defined. Some problems such as the layer-blocks' rules, logical uniformity, topological uniformity are discussed. Based on AHP (Analytic Hierarchy Process), the hierarchy architecture of network weights determination is proposed and the standard function of influencing factors is presented. With the basic principles of geometry, the bidirection A* algorithm considering minimum angle and switch search is proposed. The experimental results show that the algorithm is useful and efficient. The design idea and concrete implementation steps of the layer-block route planning algorithm are discussed in detail. Comparative experiment results prove that the algorithm can give priority to find the nearest main road, reduce the search space, improve computational efficiency, and get the reasonable path efficiently.