关键词: 交通工程, 道路交通, 最短路径算法, 转向延误, Dijkstra

Abstract: It is difficult to reflect the real traffic situation when the shortest path algorithm is applied without considering the turn delay in urban road network, because that travel delays at the intersection of urban road network may be larger than the driving time on road section. The existing shortest path algorithm considering turn delay was analyzed. The extension network method lacked practicability due to the excessive time and space overhead. The other algorithms, including dual network method, node labeling algorithm and arc labeling algorithm, were essentially to solve the shortest path problem including node weight and edge weight, and the final solution was node labeling algorithm. The typical node labeling algorithm — Dijkstra algorithm was improved. The steering discrimination was completed by recording the nodes previous node, the time complexity of the proposed algorithm was optimized from O(n2) to O(nlogn) by smallest heap optimization and the data structure of the proposed algorithm was given. The program coding was completed, and the proposed algorithm was validated through an example. The results show that the shortest path of the urban road network will change after considering turn penalties, meanwhile, the time complexity of the algorithm will decrease after heap optimization.

Key words: transportation engineering, road transportation, shortest path algorithm, turn delay, Dijkstra