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

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

（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 对之间一条有效路径，接着利用回溯的方法再次进行深度优先遍历，直至找出所有有效路径。这两种方法虽然能够保证搜索路径的完整性，但是复杂程度明显增大，而且在搜索过程中并未对路径进行简化处理，在构建轨道交通路网模型进行客流实时仿真时，可能存在搜索效率不高的问题。周玮腾等[9]对路径做了简化，构建了只包含换乘车站的拓扑网络，利用深度优先的搜索策略搜索出所有有效路径，最后通过对比还原的方法找出完整网络下OD 对之间的有效路径，但是该方法增加了匹配的难度并且没有对搜索深度进行限制，同样会产生一定的无效搜索。本文在简化搜索路径的基础上，利用深度优先的搜索思想并结合轨道交通路网的拓扑特征，提出一种更加高效的有效路径搜索算法。

2 路径搜索算法

2.1 路网模型

本文所建立的轨道交通路网拓扑结构可表示为G=｛L(s)｝，G表示所构建的轨道交通路网，L表示轨道交通路网中的线路。其中：

L=｛l1,l2,…,lm｝，m为路网中所包含的线路数量；

li=｛si1,si2,…,sin｝，n为线路i上的车站数，sin表示线路li上的第n个车站。

车站sin又包含车站名、所属线路编号、车站编号和是否为换乘站点4 个属性。其中，车站所属线路编号为该车站所在所有线路的集合；车站编号由车站在线路上的相对位置确定，按从下行到上行依次递增。换乘站在不同的线路中分别设置不同的编号以示区分。

轨道交通网络由不同的线路组成，各线路间通过换乘车站衔接。本文提出的搜索算法以换乘站为核心节点进行搜索，故需在构建路网模型时，依据车站与线路的逻辑关系，实现如下两个基本方法。

1）寻找与非换乘站最近的换乘站

对于一个非换乘车站，找出其所在的线路上的所有换乘车站，并选择与其间隔车站数最少的换乘站作为其最近换乘站。若同时存在两个或两个以上最近换乘站，则随机选择一个作为其最近换乘站。

2）寻找与换乘站相邻的换乘站

换乘车站是多条线路的交汇点，为保证路径搜索的完整性，需要找出与之相邻的所有换乘车站。对于一个换乘站点，遍历其所在的线路，找出每条线路上与之相邻的换乘车站，形成换乘车站集合，作为与该换乘站相邻的换乘车站。

2.2 限制搜索深度的搜索算法

对于国内大多数轨道交通路网而言，从任意一点出发，最多经过3 次换乘，可以到达路网中任意一个节点。故本文将一个行程分为5 个部分，如图1所示。对于不同的OD 对，换乘站的数目可能有所差别，需要根据实际情况进行调整。在路径搜索的过程中，只考虑由起终点及换乘站组成的简化路网，从给定的起点站开始，通过逐层搜索中间换乘站点的方式，找到与终点站属于同一线路的换乘站以完成路径搜索。同时，为了提高搜索效率，算法限制了搜索深度，搜索到第3 层换乘车站后，如果其不与终点站在同一线路，则放弃该条路径的搜索，这样选择性的放弃了一些明显不合理的路径，节约了搜索时间但不会遗漏合理路径。

图1 出行行程划分Fig.1 Typical travel partition

2.3 算法流程

步骤1:从自动售检票系统（AFC）记录的交易数据中提取乘客出行的起讫点。

步骤2:构建3 个换乘站列表，换乘站列表1、换乘站列表2、换乘站列表3，分别对应如图1 所示的3 个换乘节点。列表为一维列表，用于存放车站(sin)信息，在记录路径时分别称从换乘站列表1、换乘站列表2、换乘站列表3 中提取出的站点为换乘站1、换乘站2、换乘站3。

步骤3:判断起终点是否在同一条线路上，如果是，则记录路径[起点站，终点站]，如果不是，则找出与起点站相邻的换乘车站（如果起点站为非换乘车站，找到与之最近的换乘车站，如果起点站为换乘车站，找到与之相邻的所有换乘车站），添加到换乘站列表1 中。

步骤4:遍历换乘站列表1 中的车站，判断其是否与终点站在同一线路上。如果是，则记录路径[起点站，换乘站1，终点站]，继续遍历，直至换乘站列表1 中的车站全部被遍历，执行步骤7；如果不是，则中断遍历，找出与之相邻的换乘站，添加到换乘站列表2 中，执行步骤5。

步骤5:遍历换乘站列表2 中的站点，判断其是否与起点站位于同一条线路上。如果是，则将其添加到换乘站列表1 中；如果不是，判断其是否与终点站在同一条线路上，如果是，则记录路径[起点站，换乘站1，换乘站2，终点站]，继续遍历换乘站列表2 中的站点，直至换乘站列表2 中的站点均被遍历，清空换乘站列表2、换乘站列表3，返回步骤4 继续遍历下一个车站，如果不是，则中断遍历，继续寻找与之相邻的换乘站并添加到换乘站列表3 中，执行步骤6。

步骤6:遍历换乘站列表3 中的站点，如果其与换乘站1 在同一条线路上，则将此站点添入换乘站列表2，如果其与起点站在同一线路上，则将该站点添入换乘站列表1；否则，判断该站点是否与终点站在同一线路上，如果是，则记录路径[起点站，换乘站1，换乘站2，换乘站3，终点站]，继续遍历换乘站3 中的站点，直至列表3 中的换乘站点均被遍历，清空换乘站列表3，返回步骤5 继续遍历下一个车站。

步骤7:输出所有记录的路径。

注1：在步骤4、步骤5 向换乘站列表中添加站点时，如果该站点已经存在于列表中，则不再继续添加。若找到的换乘车站为起点站，同样无需将起点站加入换乘站列表中。

注2：在搜索步骤4、步骤5 中，之所以会往换乘站列表1、换乘站列表2 中回添站点，是为了避免同一线路上出现多个换乘站，导致经过3个换乘站后无法由起点到达终点，即路径中的换乘站指乘客实际发生换乘的车站，而非简单的物理换乘站。

2.4 有效路径筛选

经过上述方法搜索后，某一OD 对之间可能会搜索到多条可达路径，但在实际环境中，乘客在进行路径选择时，不会考虑所有的可达路径，而会从有效路径中进行选择。通常情况下，采用3 条以内渐短路径作为有效路径。故找到可达路径后，还需从中筛选出有效路径，本文考虑设置如下3 条筛选原则。

1）找出搜索结果中经过换乘站数目最少的路径，删除比最少换乘路径多两个及以上换乘站的路径。

2）找出搜索结果中经过车站数目最少的路径，删除路径中经过车站数比最少经过车站数多n个以上车站的路径(n可根据实际调查设定)。

3）如果经1）、2）两条原则筛选过后，剩余路径的条数仍多于3 条，则优先考虑换乘站数较少的路径，换乘站数相同的情况下，保留经过站点数较少或舒适度较高的路径。

3 应用实例

3.1 路网结构设计

以天津地铁为例，首先构建轨道交通路网模型。目前天津地铁包含6 条运营线路，143 个车站及15个换乘车站，在轨道交通路网模型中为每个站点设置包括所属线路、站点编号、是否为换乘站点等3个属性。其中，站点编号由站点在线路上的相对位置确定，从下行到上行依次递增，换乘站在不同的线路中分别设置不同的编号以示区分。

3.2 结果与讨论

以咸阳路站为起始站，以营口道站为终点站，采用本文的搜索方法，共搜索到8 条路径，如表1所示。

表1 咸阳路站至营口道站路径搜索结果Tab.1 Search results of the paths between Xianyang Road Station and Yingkou Road Station

可以看到，此11 条路径均可由咸阳路车站到达营口道车站，但各条路径所经过的站点数及换乘车站的数目不同。根据上述有效路径筛选原则进行筛选，7、9、10、11 号路径为从咸阳路站到营口道站的有效路径，经验证，乘客在出行路径选择时很少会考虑其他路径出行。

评价路径搜索算法优劣主要从准确性与搜索效率两个角度进行考虑，本文使用天津地铁线网客流数据，按上述介绍的算法，寻找全线网20 306 个OD 对之间的有效路径。从准确性角度讲，本文的搜索不会漏掉任何换乘次数≤3 的路径，对有效路径的筛选也满足人们日常出行的行为习惯，算法的准确性可以得到保障。从效率角度讲，本文提出的搜索算法完成全部OD 对的搜索共耗时127 s，找到有效路径210 001 条。相比于基于线路组合的路径搜索算法[10]，本文的方法在搜索时间上有明显优势。两种算法的搜索效率对比如表2 所示，可以看到，在路网复杂度明显增大的情况下，本文所实现的方法在搜索时间上仍有明显优势。

表2 两种搜索算法效率对比Tab.2 Efficiency comparison of two search algorithms

4 结语

本文基于轨道交通线网拓扑特点，利用深度优先的搜索思想，提出了一种高效的路径搜索算法，相比于传统深度优先算法，该算法在搜索之前，首先进行路径简化，减少了搜索节点，同时在搜索过程中，限制了搜索深度，避免无效搜索，大幅提高了搜索效率。此外，本文提出的基于3 层换乘的搜索算法具有良好的可移植性，对城市轨道交通路网模型的建立具有一定的参考价值。