Research On Shortest Path Analysis In Road Networks Based On Geographical Entities Attribute Information

The computation of shortest path in a graph is a classical problem in graph theory. One of the most obvious practical applications is path analysis in a road network, for example, finding an optimal route from a start location to a target location. In this study, it assumes that a given road network does not change very often, There are much relatively algorithms to solve path analysis in small-scale networks, but for large road networks, the classical Dijkstra algorithm to compute shortest paths is too slow, therefore the conventional algorithms don’t apply. For large road networks, there have faster algorithms been developed in recent years. These new algorithms have in common that they use preprocessing and store auxiliary data to speedup subsequent shortest-path queries. However, these algorithms often consider only the simplest problem of computing a shortest path between source and target node in a graph with non-negative real edge weights. But real-life problems are often not that simple, therefore, it needs to extend the definition of study problem. Set the time from source point to target point as the edge weight, and taking a full consideration the attributes information of nodes and edges in the network. Although there exists some algorithms based on these, but the algorithms aren’t very effective. Therefore, it is very necessary and important to develop a new algorithm.In this paper, a new accelerated algorithm-HP (Hierarchy Partition) algorithm is presented for the shortest path analysis based on entities attribute information of nodes and edges. HP algorithm includes how to partition hierarchies, and how to build shortcuts, and how to sort the nodes on the same level, and how to sampling the node and how to query the shortest path in the network. The experimental data download from OpenStreetMap mirror site. In Data preprocessing phase, an open source plug-in is used to, the plug-in is called ArcGIS Editor For OSM Data, the functions that plug-in provides are used to process OSM original data. After that, a conversion tool XML2RDF is used to convert OSM data format into RDF data format, in the end, the result of conversion data is stored in a RDF-3X database.Under the inspired between CH and TNR, the road network is partitioned into some hierarchies, and shortcuts are constructed from some nodes of the road network. Some experimental data are obtained via sampling based on combining with the Reach algorithm. The result data nodes from50,000to20million are divided into10data sets respectively for search data in the experiment, HP algorithm is compared with CH and Dijkstra and TNR in the distance and query efficiency. In the end, a detailed analysis of the experiment is induced that the space consumption of HP algorithm takes slightly more than CH’s, but better than the other two algorithms in preprocessing, and the space complexity and time space complexity of the HP algorithm are both better than other three algorithms.