Change In Gis Theory And Algorithm Of The Shortest Path

Shortest path problem is always a research focus of geographical information system (GIS), communications, logistics management and other areas, there has been producing a large number of research results.Most of these studies are based on a static network, the weights of the network arc are fixed. But in real life there are many problems such as traffic areas, the weights of the network arcs change over time, while the static shortest path algorithm can not meet the requirements of these problems. Paper based on the city road network, analyzed and studied the time-dependent shortest path (TDSP) theory and divided the time shortest path of three common problems. Then we analyzed improving algorithm from search strategy and distribution of road network to increase efficiency.Main contributions of the dissertation include:1) Use GIS technology to extract information on the road network in Beijing area, and build its static road network topology.2) Analyze the statistical properties of urban traffic flow, and establish a time-dependent road network model. According to the daily travel needs, time-dependent shortest path problem is divided into three types of applications and algorithms:given departure time, given the departure time domain and given arrival time.3) To against the blindness of D_TDSP algorithm (given departure time circumstances) in the search process, use heuristic search strategy and put forward A_TDSP algorithm with heuristic factor, to accelerate the convergence speed.4) To against the process of the A_TDSP algorithm sometimes appears lack of heuristic information, according to characteristics of the road network to improve the algorithm. Based on statistical characteristics of network-based data, proposing algorithm of restricted search area:R_TDSP algorithm.5) Based on the constructed area of Beijing platform for time-dependent road network, we simulated and compared each time-dependent algorithm presented above. Experiment results showed:all of the above mentioned algorithms are correct and effective. Moreover, A_TDSP algorithm, R_TDSP algorithm has obvious advantages than D_TDSP algorithm.