城市轨道交通路网建模中路径搜索算法的实现

doi:10.3969/j.issn.1673-4440.2021.09.010

铁路通信信号工程技术 ›› 2021, Vol. 18 ›› Issue (9): 49-53.DOI: 10.3969/j.issn.1673-4440.2021.09.010

城市轨道交通路网建模中路径搜索算法的实现

肖晨¹，何跃齐²，赵嘉伟³，张宁³

1．天津轨道交通运营集团有限公司，天津 300392；
2．北京城建设计发展集团股份有限公司，北京 100045；
3．东南大学智能运输系统研究中心轨道交通研究所，南京 210018

收稿日期:2020-07-10 修回日期:2021-07-27 出版日期:2021-09-24 发布日期:2021-10-12
基金资助:
中华人民共和国交通运输部建设科技项目(2015318J33080)；南京地铁“十三五”工程专项科技项目（JS-D6-XY01-0000-1708）

Implementation of Path Search Algorithms in Urban Rail Transit Network Modeling

Xiao Chen¹, He Yueqi², Zhao Jiawei³, Zhang Ning³

1. Tianjin Railway Transit Operation Group Co., Ltd., Tianjin 300392, China；
2. Beijing Urban Construction Design & Development Group Co., Limited, Beijing 100045, China；
3. ITS Rail Transit Research Institute of Southeast University, Nanjing 210018, China

Received:2020-07-10 Revised:2021-07-27 Online:2021-09-24 Published:2021-10-12

摘要/Abstract

摘要： 路径搜索算法是路网模型的基础，高效的搜索算法是实现客流实时仿真的保障，现阶段轨道交通领域路径搜索算法大多以最短路径搜索算法为基础进行改进，搜索效率有待提高。利用深度优先搜索思想，根据轨道交通路网特征简化路网的同时，提出一种限制搜索深度的搜索算法，经验证，该算法在保证搜索准确性的同时，明显提升有效路径的搜索效率，并具有良好的可移植性，能够满足实时客流仿真的要求。

关键词: 轨道交通, 网络化运营, 路网仿真模型, 路径搜索算法

Abstract: The path search algorithm is the basis of the network mode. An efficient search algorithm can guarantee in-time simulation. At present, most of the path search algorithms in the field of rail transit are improved on the basis of the shortest path search algorithm, and the search efficiency needs to be improved. In this paper, a new searching algorithm is proposed based on the characteristics of the rail transit network in Tianjin. Contrasted with other methods, it improves the search efficiency of K short-path obviously, has good portability, and can meet the requirements of real-time simulation

Key words: rail transit, network operation, network simulation model, path search algorithm

中图分类号:

U491.1⁺3

肖晨, 何跃齐, 赵嘉伟, 张宁. 城市轨道交通路网建模中路径搜索算法的实现[J]. 铁路通信信号工程技术, 2021, 18(9): 49-53.

Xiao Chen, He Yueqi, Zhao Jiawei, Zhang Ning. Implementation of Path Search Algorithms in Urban Rail Transit Network Modeling[J]. Railway Signalling & Communication Engineering, 2021, 18(9): 49-53.

图/表 3

参考文献

[1] Dijkstra E W. A Note on Two Problems in Connexion with Graphs[J]. Numerische Mathematik, 1959, 1(1): 269-271.
[2] Flody R W.Shortest Path[J].Communications of the Association for Computing Machinery, 1962, 15(6): 245.
[3] Hart P E, Nilsson N J, Raphael B A. Formal Basis for the Heuristic Determination of Minimum Cost Paths[J]. IEEE Transactions on Systems Science and Cybernetics, 1968, 4(2): 100-107.
[4] Hoffman W, Pavley R. A Method for the Solution of the Nth Best Path Problem[J]. Journal of the ACM, 1959, 6(4): 506-514.
[5]赖树坤，毛保华.轨道交通系统票务清分算法的研究[J].铁道运输与经济，2007，29（6）：42-45.
Lai Shukun, Mao Baohua. Study on Ticket Revenue Clearing Algorithm for Rail Transit System[J]. Railway Transport and Economy, 2007, 29(6): 42-45.
[6]赵峰，张星臣，刘智丽.城市轨道交通系统运费清分方法研究[J].交通运输系统工程与信息，2007，7（6）：85-90.
Zhao Feng, Zhang Xingchen, Liu Zhili. Modeling Income Distribution of the Auto Fare Collection System[J]. Journal of Transportation Systems Engineering and Information Technology, 2007, 7(6): 85-90.
[7]徐瑞华，罗钦，高鹏.基于多路径的城市轨道交通网络客流分布模型及算法研究[J].铁道学报，2009，31（2）：110-114.
Xu Ruihua, Luo Qin, Gao Peng. Passenger Flow Distribution Model and Algorithm for Urban Rail Transit Network Based on Multi-Route Choice[J]. Journal of the China Railway Society, 2009, 31(2): 110-114.
[8]四兵锋，毛保华，刘智丽.无缝换乘条件下城市轨道交通网络客流分配模型及算法[J].铁道学报，2007，29（6）：12-18.
Si Bingfeng, Mao Baohua, Liu Zhili. Passenger Flow Assignment Model and Algorithm for Urban Railway Traffic Network under the Condition of Seamless Transfer[J]. Journal of the China Railway Society, 2007, 29(6): 12-18.
[9]周玮腾，韩宝明.城市轨道交通网络时变路径搜索算法[J].北京交通大学学报，2017，41(4):115-122.
Zhou Weiteng, Han Baoming. Temporal Path Searching Algorithm of Urban Rail Transit Network[J]. Journal of Beijing Jiaotong University, 2017, 41(4): 115-122.
[10]钟璧樯，楼栋，周一威.基于轨道交通网络特点的K最短路算法研究[J].都市快轨交通，2019，32（1）：72-77.
Zhong Biqiang, Lou Dong, Zhou Yiwei. Shortest-Path Algorithm Based on the Characteristics of Rail Transit Network[J]. Urban Rapid Rail Transit, 2019, 32(1): 72-77.

[1]	刘畅. 以二维码为基础的交旅融合票务系统方案研究[J]. 铁路通信信号工程技术, 2021, 18(9): 54-59.
[2]	陆海亭, 张义鑫, 张宁. 城市轨道交通通信信号机房走线方案探讨[J]. 铁路通信信号工程技术, 2021, 18(9): 65-68,103.
[3]	董洪卫, 赵博伦. 全自动运行系统站台门间隙探测与信号系统接口探究[J]. 铁路通信信号工程技术, 2021, 18(9): 69-72.
[4]	刘博, 乐梅, 张军, 李擎. 多制式轨道交通协同应急指挥平台方案研究[J]. 铁路通信信号工程技术, 2021, 18(8): 31-35.
[5]	宋大治, 张浩, 徐钟全, 刘光杰. 基于MPP和Hadoop的城市轨道交通线网指挥平台设计[J]. 铁路通信信号工程技术, 2021, 18(8): 47-53.
[6]	李永, 张学兵. 城市轨道交通行车调度岗位风险分析与思考[J]. 铁路通信信号工程技术, 2021, 18(8): 57-61.
[7]	马龙. 城市轨道交通信号系统DCS有线网络过渡方案研究[J]. 铁路通信信号工程技术, 2021, 18(8): 62-64,89.
[8]	王欣. 基于Cordova的跨平台智慧出行APP设计与实现[J]. 铁路通信信号工程技术, 2021, 18(7): 40-44.
[9]	李波, 张炳森, 张宁. 基于生存分析的AFC终端设备无故障运行时间预测[J]. 铁路通信信号工程技术, 2021, 18(5): 59-65.
[10]	黄璞, 黄海荣. CBTC城市轨道交通工程车ATP应用研究[J]. 铁路通信信号工程技术, 2021, 18(5): 100-104.
[11]	周茂庆, 陈卓, 张宁, 张炳森. 基于层次聚类的城轨设备维修方式决策研究[J]. 铁路通信信号工程技术, 2021, 18(4): 52-58.
[12]	赵野, 付保明, 张宁. 城市轨道交通安检集成系统研究[J]. 铁路通信信号工程技术, 2021, 18(4): 71-76.
[13]	王紫薇, 韩冰. 基于人脸识别和信用登乘的轨道交通乘车方案[J]. 铁路通信信号工程技术, 2021, 18(3): 43-46,53.
[14]	袁永恒. 基于轨道交通的个性化信息推送系统[J]. 铁路通信信号工程技术, 2021, 18(10): 63-65,110.
[15]	江梁智, 廖百睿. 联络线区段计轴故障应对方案[J]. 铁路通信信号工程技术, 2021, 18(10): 101-105.

城市轨道交通路网建模中路径搜索算法的实现

Implementation of Path Search Algorithms in Urban Rail Transit Network Modeling

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 3

参考文献

相关文章 15

编辑推荐

Metrics

本文评价