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

发布时间：2023-11-11 16:52

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

【文章页数】：6 页

【文章目录】：
0概述
1 城市轨道交通网络KSP问题描述
2 标记边的路径搜索算法
    2.1 标记边的Dijkstra算法
    2.2 标记边的Yen算法
    2.3 算法时间复杂度分析
3 算法应用
4 结束语



本文编号：3862941