Research On Restrictive Path Planning Algorithm Based On Urban Road Network

With the rapid development of mobile internet,global positioning systems,geographic information systems and wireless communication technology,path planning provides an important reference route for people.However,the traditional path planning algorithm does not consider the spatial distribution characteristics of the urban road network during the design,so that the path planning algorithm accesses a large number of nodes in which a large number of final path decisions are unrelated during the process of solving the path,affecting the performance of the algorithm.In addition,different users have different preferences for different paths,so recommending the top k shortest paths with high similarity cannot meet the individual needs of users,and it is easy to increase the risk of traffic congestion in a certain road section.In response to the above problems,this paper studies the restrictive path planning algorithm based on the urban road network based on the knowledge of network topology and graph theory.The main research contents are as follows:(1)This paper draws on the cognition and understanding of human beings to urban traffic roads,and established a unidirectional road network model that meets the actual law from the characteristics of urban transportation road network itself.The model is a road network model that uses the road as a basic element,which not only can display the steering information directly in the road network,but also to save the segment attribute information directly on the road.(2)This paper proposes a shortest path algorithm based on virtual boundary in dynamic ellipse restricted search area(SPAVBDERSA).Firstly,this paper studies the shortest path ratio in the road network,and extracts the road network statistical feature parameter function based on shortest path ratio.Secondly,this paper proposes a restricted search area shortest path algorithm based on the Dijkstra algorithm and traditional shortest path algorithm based on ellipse restricted search area under the unidirectional road network models,which can delineate different search areas according to the Euclidean distances of different origin-destination(OD)pairs and ensure the reliability of the algorithm by constructing virtual boundaries at a lower confidence level.Thirdly,this paper studies the impact of the road network statistical feature parameters on the reliability and effectiveness of the algorithm under different levels of confidence.Finally,this paper conducted a detailed experiment on the proposed algorithm with the real road network.As the experiment shows,compared with the existing algorithms,SPAVBDERSA can reduce the path query time of 21%-66% of the algorithm in the preceding algorithm in the premise of ensuring the optimal path of the guarantee.(3)This paper proposes a top-k path planning algorithm with diversity in dynamic restricted search area(KPPADDRSA).Firstly,this paper studies the relationship between the shortest path ratio and minimum punishment coefficient ratio in the road network,and extracts the road network feature parameter function under different penalty coefficients.Secondly,this paper sets a threshold as a maximum similarity of paths,and fitting the road network statistical feature parameter function according to the Euclidean distance and penalty factor of different OD pairs.Thirdly,this paper proposes a top-k path planning algorithm with diversity based on SPAVBDERSA under the unidirectional road network models,which can calculate the appropriate penalty coefficient and elliptic statistical parameters according to the OD pairs,and seek the top-k shortest path with diversity below the threshold.Finally,this paper conducted a detailed experiment on the proposed algorithm with the real road network.As the experiment shows,compared with the existing algorithms,KPPADDRSA can reduce the path query time by up to 64% on the premise that the similarity of the k paths is lower than the threshold.