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

肖 晨，何跃齐，赵嘉伟，张 宁

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

1 概述

城市轨道交通具有运量大、速度快、时间准、污染少和安全舒适等特点，在缓解大城市交通拥堵方面具有独特优越性，已成为城市公共交通系统中的重要组成部分。截至2019 年底，中国大陆地区共40 个城市开通城市轨道交通服务，19 个城市进入网络化运营阶段。在网络化运营阶段，客流量急剧增大且乘客出行路径选择增多，需要运营管理者从宏观角度把握客流特征，安排运营组织。构建合理的轨道交通路网模型，能够为运营组织者提供决策依据，而路网模型的关键在于路径选择算法。

以图的方式描述路网已成为交通研究中广泛使用的方法，如何从路网中提取有效路径一直以来都受到广泛关注，相关学者先后提出了Dijkstra 算法[1]、FLOYD 算法[2]、A*算法[3]等一系列最短路径求解方法。然而在网络化运营的轨道交通路网中，起讫点（OD 对）之间可能会存在多条有效路径，如果仅按最短路径进行客流量的分配，会与实际情况有较大出入，故需要求解OD 对间的K 短路径。K短路径搜索问题最早由Hoffman 等[4]提出，并得到不断完善。在轨道交通方面，在找到K 短路径之后，一般情况下，需进一步寻找有效路径进行客流量的分配[5-6]。徐瑞华等[7]通过删除法获得轨道交通网络上任意两点不重复的K 条路径，四兵锋等[8]先利用深度优先的搜索算法，搜索出OD 对之间一条有效路径，接着利用回溯的方法再次进行深度优先遍历，直至找出所有有效路径。……