Research And Realization Of The Shortest Path Algorithm Within Typical Urban Road Network

With the accelerating of modern life pace and the rapid growth of cars’ number, transportation problems have become more prominent, therefore many countries in the world have launched the Intelligent Transportation System study. As an important subsystem of ITS, Urban Traffic Guidance System has always been a hot and difficult problem for industry experts and scholars and is also one of the most effective way to solve existing traffic problems.The core problem of route guidance is the shortest path algorithm in graph theory. For sparse networks, since the heap data structure can make the Dijkstra algorithm time complexity dropped to N log N (N indicates the number of nodes in the network), Dijkstra algorithm is widely used to solve single-source shortest path problem of the urban road networks.However, while solving the two-node shortest path problem, especially for large-scale urban road networks, Dijkstra algorithm still has a larger redundancy and the shortest path query is difficult to meet requirements of instantaneity and reliability. Study on restricting searching area shortest path algorithm becomes the most direct and effective method to improve the shortest path algorithm and reduce the path query time within urban road networks.The content of this study is the theoretical study and experimental verification of the improved ellipse restricted searching area algorithm in the typical urban road networks. The purpose of this study is minimizing the shortest path query time on condition that the query results are reliable. The research approach is to reduce the redundancy and complexity of the shortest path algorithm though fully studying and using the characteristic parameters of the urban road networks. Algorithm performance is estimated with double evaluation criteria by software simulation predictions and measured data statistics.The research content mainly includes the following aspects:(1) Typical characteristics study of feature extraction of the urban road networks. Including study on road length value, study on ratio (section number to site number) value and study on the shortest path ratio value.(2) Multi-scale ellipse shortest path algorithm and its performance analysis. Including study on value of split point between different scale ellipses, and study on shortest path query time as well as searching area of multi-scale algorithm.(3) Two-tree ellipse shortest path algorithm and its performance analysis. Including study on termination condition of the two tree algorithm and study on shortest path query time as well as searching area of two-tree algorithm.Simulation projections and experimental results show that:compared with the ellipse algorithm, while the starting station and destination station is distant, multi-scale algorithm can effectively reduce the shortest path query time by18%and the shortest path found by multi-scale algorithm is absolutely reliable; compared with the single-source algorithm, two-tree algorithm can reduce the shortest path query time by approximately40%, and with the increasing of the Euclidean distance between the starting station and destination station, the effectiveness improvement of the two-three algorithm is much greater, so the two-tree algorithm is especially suitable for the shortest path optimization of large-scale urban road networks.