作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2019, Vol. 45 ›› Issue (1): 292-296,302. doi: 10.19678/j.issn.1000-3428.0049057

• 开发研究与工程应用 • 上一篇    下一篇

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

唐继孟a,b,孙全欣a,b,杜鹏a,b,陈志杰a,b   

  1. 北京交通大学 a.城市交通复杂系统理论与技术教育部重点实验室; b.交通运输学院,北京 100044
  • 收稿日期:2017-10-24 出版日期:2019-01-15 发布日期:2019-01-15
  • 作者简介:唐继孟(1989—),男,博士研究生,主研方向为综合交通运输;孙全欣,教授、博士;杜鹏,副教授、博士;陈志杰,博士研究生。
  • 基金资助:

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

Urban Rail Transit Network KSP Algorithm Based on Labeling Edge

TANG Jimenga,b,SUN Quanxina,b,DU Penga,b,CHEN Zhijiea,b   

  1. a.MOE Key Laboratory for Urban Transportation Complex Systems Theory and Technology; b.School of Traffic and Transportation,Beijing Jiaotong University,Beijing 100044,China
  • Received:2017-10-24 Online:2019-01-15 Published:2019-01-15

摘要:

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

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

Abstract:

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.

Key words: urban rail transit, K Shortest Paths (KSP), labeling edge, path searching, loopless path

中图分类号: