Research On Optimal Path Planning Algorithm Based On Urban Road Network

Currently, the shortest path problem as one of the hotspots of geographic information systems and computer science, is a hot issue a large number of domestic and foreign scholars attention. Dijkstra algorithm is commonly used as the shortest path algorithm to solve the problem, generally used to calculate the least-cost path unit, has a wide range of applications. Based on the traditional Dijkstra algorithm research and analysis, several deficiencies at the Dijkstra algorithm, and the algorithm is optimized to improve its storage and computational efficiency. And on this basis, the added traffic factors studied urban road network optimal path planning algorithm.First, this paper introduces the theory of knowledge optimal path planning algorithm Its main contents include the introduction of intelligent transport systems, vehicle navigation system and its components, the optimal path planning and optimal path planning principles vehicle navigation system. It also introduces the related concept map and the shortest path problem description. It also introduces the related concept map and the shortest path problem description, analysis of the correlation between the optimal path planning and shortest path problems.Secondly, the proposed optimization algorithm Dijkstra algorithm, based on the traditional Dijkstra algorithm, storage structures and algorithms from two aspects of the structure of the algorithm has been improved, and space complexity and time complexity were compared, analyzed results optimization algorithm improved efficiency.Again, proposed optimal path planning algorithm based on the urban road network. Analysis of the impact of path planning optimization criteria, proposed three factors that affect transportation route planning, ie urban road speed limits, traffic congestion caused by the delay and whether the one-way street. The algorithm is added to the basic factor of three traffic shortest path algorithm is proposed to consider urban road grades and sections based on the vertex weights.Finally, the optimal path planning algorithm simulation system design and implementation, based on the optimal path planning based on urban road network proposed algorithm, build optimal path planning simulation system simulation to achieve the shortest distance and shortest time path query path query, the proposed provide users with the optimal path solution.