The Fast Path Optimization Gis Network Data Structure Design And Algorithm Research

As Geographic Information System (GIS) becomes increasingly widely used in logistics management, finding the shortest path quickly in the GIS large-scale network is urgently needed in many logistics optimization model. This paper studied the node-to-node shortest path problem in a GIS network, which is characteristic of small node degree and highways, and put forward a fast algorithm which is a bi-directional research and can effectively reduce the data computation for optimization path basing on a pre-processing multilayer data structure by rebuilding the GIS road network.The algorithm first constructs a multilayer data structure GIS network in pre-processing part. As a way in pre- processing, the paper uses two phases method in order to sort out all the highways in the GIS network, which makes the highway network. The two phase's method first adopts Dijkstra algorithm for all the nodes and derives part of the shortest-path tree. Then all the edges in the tree, from leaves to root, are examined using a criterion and some of them are sorted out to be highways. All the highways make up the highway network. Then, the contracted network of the highway network is constructed. Then two phases method is again used to this contracted network to get all the highways of it. The process goes on and on and finally a multilevel highway network is constructed. In the meanwhile, this multilevel highway network integrates the characteristic of GIS network that some edges allow limited tonnage so that some of the vehicles whose tonnage is beyond the limit are prohibited from passing those edges.Then, the paper put forward a fast bi-directional algorithm, which is based on the Dijkstra algorithm and includes some criteria. Some of these criteria ensure that the bi-directional Dijkstra algorithm is carried out from lower level of the highway network to higher level and that the search for shortest path on the same level of the highway network is constrained within the neighborhood of the entrance node of the level. And when the abortion criterion is carried out, we get the shortest path for this vehicle to travel from start node to end node in the GIS network and the path is also the optimal path.