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

摘要：

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

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

所属期刊栏目：45

分类号：TP29(自动化技术及设备)

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

在线出版日期：2019-07-09（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：292-296,302