Research On The Shortest Path Algorithm For Large-scale Road Network

Along with the rapid human migration to urban areas,global road network is constantly expanding,making the fast and highly efficient calculation of the shortest path between two nodes in the vast network of roads become a research topic for many researchers and developers in academia and industry.After years of study,scholars presented numerous relevant algorithms such as Dijkstra algorithm,CH algorithm(Construction Hierarchies Algorithm),Arc-Flag algorithm,Highway Hierarchies algorithm as well as some shortest path algorithms combined with intelligent algorithm.But there is still no good solution to reduce the searching time by narrowing down the data searching space,making it remain a problem.In order to solve the problem that finding the shortest path between two nodes in the mass data of large-scale road network is quite time-consuming,this paper puts forward an efficient and feasible solution with good performance on the basis of a node-degree based method for division of large-scale road network presented in this thesis after analyzing the restrictions between actual roads.Major work of the thesis is as follows:(1)A node-degree based algorithm for division of road network is presented to solve the problem in which the area with high node density may be easily divided into multiple subnetworks while partitioning the data of road network.First,the algorithm processes and stores the road network data according to the restrictions between actual roads.Second,upper limit of the node amount in each sub-network is set,road network data are divided using Kd-tree and the maximum node degree of sub-network gets marked.Finally,neighbors of a boundary node will be merged if the boundary node possesses the maximum node-degree of the sub-network and thus is proved to be in an area with high node density.Experiment result demonstrates that the algorithm makes sub-networks more independent to some extent.(2)Efficiency of the division-based shortest path algorithm is optimized to solve the problems that in large-scale road network,the shortest path searching is very space-consuming and the searching efficiency is low when the start node and target node are close to each other.First,road network data are divided according to the characteristics of roads.Second,the number of nodes in sub-network is set as the maximum number of nodes that can be handled by hierarchical shrinking shortest path algorithm.Road network data are divided using nodedegree based road division algorithm.Then,it obtains the set of boundary nodes in subnetworks and establishes the shortest path searching table for those boundary nodes.Finally,it selects different shortest path search strategies according to whether the start node and target node belong to the same sub-network.If it's true,shortest path will be searched bi-directionally according to the importance of the nodes in sub-network.(3)Many experiments have been performed to validate the shortest path algorithm presented in this paper.Experimental results show that the algorithm put forward in this thesis consumes less space and time compared with classical shortest path algorithm based on road network division.(4)This thesis develops DLL(Dynamic Link Library)for shortest path searching,sets up road network database with turning restrictions,implements the division of road network data and encapsulates the function of shortest path searching based on C# and OpenStreetMap.Reliability of the DLL has been proved by sample codes which call the DLL.