基于标记边的城市轨道交通网络KSP算法

Urban Rail Transit Network KSP Algorithm Based on Labeling Edge

城市轨道交通网络票务清分和客流分配都需要以路径搜索作为基础。由于城市轨道交通网络拓扑结构图不适用标记点的路径搜索算法,如对其拓展将导致路径搜索时间延长。为此,基于标记边的思想,考虑进出站时间对路径选择的影响,提出适用于城市轨道交通网络的K最短路径(KSP)搜索算法,以实现无须拓展网络的KSP搜索。在北京城市轨道交通网络上的应用结果表明,与传统的标记点Yen算法相比,该算法计算效率显著提高,在搜索同一OD对之间的KSP时能够节省至少一半时间。

Path searching is the precondition of the ticket income distribution and the passenger flow assignment of urban rail transit network.Only being extended,the urban rail transit network can find path by using path searching algorithm with labeling node,which prolongs the time of paths searching.Considering the influence of the times of in and out of the station to the path-choice,this paper presents the finding K Shortest Paths(KSP)algorithm that applies to urban rail transit network without expanding the network based on the principle of labeling edge.The application of the two algorithms on urban rail transit network of Beijing shows that,compared with the traditional algorithm with labeling node,the proposed algorithm with labeling edge achieves a good effect in computational efficiency,which can save more than half of the time of finding the KSP of the same OD pair.