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

来源：计算机工程杂志2019年第1期北京时间：

作者：唐继孟,孙全欣,杜鹏,陈志杰

单位：北京交通大学 a.城市交通复杂系统理论与技术教育部重点实验室; b.交通运输学院,北京 100044

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

关键词：城市轨道交通,K最短路径,标记边,路径搜索,无环路径

基金资助：国家自然科学基金重大项目(71390332);国家自然科学基金青年基金(71001006)