K Shortest Path Searching for Time-Dependent Road Networks
Jiawei Lu, Xiaoxuan Chen, Qinghui Nie, Rongrong Hong, Jingxin Xia · CICTP 2017 · 2018
As an essential part of dynamic traffic assignment in time-dependent road networks, route choice set generation has been studied extensively in recent decades. The K shortest path searching algorithm has been widely used to generate the choice set with the assumption of bounded rationality. Some improved classical path searching algorithms and heuristic approaches have been proposed for the K shortest path searching, but most of them are time-consuming or in some cases, unable to find the optimal results. In this paper, a K shortest path algorithm was designed as a dual-loop framework for urban network route generation. In the framework, the A-star algorithm was used for shortest path search. Meanwhile, the link elimination approach was used as the strategy when searching for the kth shortest path. In order to improve the efficiency of the proposed model, heuristic function in A-star algorithm was also rebuilt according to the characteristics of urban network. The proposed algorithm was tested using a real urban road network. Empirical analysis shows that the proposed algorithm is computationally appealing and succeeds in finding the global K shortest paths. A genetic algorithm and the traditional Dijskstra algorithm were also conducted for comparison analysis. It is encouraging to find that the proposed algorithm significantly outperforms the genetic algorithm in terms of accuracy and is more efficient than the Dijskstra algorithm.