轨道交通网络有效路径搜索算法的改进及实现

,,

(苏州大学轨道交通学院， 江苏 苏州 215131)

随着我国城市轨道交通的不断建设和发展，许多城市的轨道交通逐渐由单线运营向网络化运营转变。因此，城市轨道交通网络中的每一对起讫站点之间可能存在多条合理的出行路径。在无缝换乘模式下，通过AFC刷卡数据可以得到乘客具体的上下车站和时间信息，但却无法直接获得乘客在网络中的具体走行路径。把握乘客在轨道交通网络中的出行路径对于分析网络客流规律和多家运营商背景下的票务清分来说具有重大的意义。

目前，在城市道路网络中出行者选择行为和路径搜索算法方面，国内外专家学者取得了丰富的成果，提出了许多路径搜索理论和算法[1-4]。Dial[1]认为当一条路径所包含的所有路段都使出行者离起始节点越来越远，离终点节点越来越近，则这条路径是“有效”的，并提出一种有效路径求解算法。Hoffman等[2]最早提出了K短路径的算法，用以求出起终点间最短、次短和第K短路径。Christopher和Brace[3]研究了K短路径长度、不经过重复节点的K短路径和带单边约束的最短路径等问题。

但是与城市道路网络相比，城市轨道交通网络在节点性质、网络构成、阻抗计算方法、影响因素等方面都具有不同的特性[5-7]。轨道交通网络节点处存在节点阻抗(停车时间、换乘时间)，因此在实际应用中往往需要进行特殊的处理。林湛等[8]根据最短路径费用定义OD之间的有效路径集合，钱堃等[9]重点研究了换乘时间对乘客路径选择行为的影响，但都没有对轨道交通网络节点的具体处理方式进行阐述。四兵锋等[10]在客流分配模型中将网络节点阻抗合并到区间阻抗中，这样处理虽然简化了问题，但是可能造成搜索过程中路径阻抗的计算偏差。周薇[11]在改进的Dial算法中将一个轨道交通车站表示成两个节点，郭彦云[12]在对轨道交通网络拓扑关系建模中同样分拆了网络节点，这样处理有效地体现了节点阻抗，但是这种处理方式导致的有效路径中可能存在冗余路段的问题却没有被提及。

基于上述分析，结合城市轨道交通自身特性，给出有效路径中冗余路段的定义并提出增加冗余路段判定步骤的改进的有效路径搜索算法，期望以此为基础建立一个完整的轨道交通网络客流路径分析系统。

1 网络节点及有效路径定义

1.1 网络节点处理

城市轨道交通网络主要由区间和车站两个部分组成，除了轨道交通区间有运行时间阻抗，轨道交通车站也存在停车时间阻抗，因此轨道交通网络每个节点都存在节点阻抗。为了表示车站的停站时间，将每个轨道交通普通车站分拆表示为停车节点和出发节点，其间增加停车弧表示停车时间。

除固定的区间运行时间、停车时间之外，换乘步行时间和换乘等待时间也是轨道交通网络阻抗的重要组成部分。对于轨道交通换乘站而言，节点阻抗存在两种情况：一方面，如果乘客在换乘站不需要换乘，则只经历停车时间，可看作普通车站，通过停车弧对其进行表示；另一方面，如果乘客在换乘站进行了换乘，则存在换乘时间，需要引入换乘弧对其进行描述。处理后的整个城市轨道交通网络可以用“带权有向图”来描述。图1和图2分别表示普通车站和换乘车站的网络节点示意图。

图1 普通车站停车弧示意图

图2 换乘车站换乘弧示意图

1.2 有效路径判定规则

在一次出行中，轨道交通乘客总是希望选择出行费用(时间、票价等)最少的路径，当起讫站点间有多条路径可选时，乘客不会考虑全部的路径，而是将其中几条作为备选方案，那些被大多数乘客所考虑的费用相近的路径便称为“有效路径”。

常用的有效路径判定规则采用“相对值”法[13-15]，同时考虑到换乘次数的增加也会降低乘客的舒适性，因此在有效路径的判定规则中增加换乘次数的限制。

定义1 当OD对(r,s)间的路径k满足以下3个条件，则称其为有效路径。

1)路径k中不存在环路，即不重复经过同一个节点。

2)路径k的阻抗小于等于最短路径阻抗的1+Hrs倍，即：

(1)

3)路径k的换乘次数小于等于网络最大换乘次数限制，即

Tk≤Tmax

(2)

式中：Tk为路径k的换乘次数；Tmax为网络最大换乘次数限制。

2 冗余路段定义及判定

2.1 路径冗余路段定义

由于轨道交通车站节点的特殊处理，在实际操作过程中，通过未改进的有效路径算法搜索到的仅仅满足1.2中有效路径判定规则的部分路径中还包含了不符合换乘逻辑的路段。为了说明上述路段的特征，图3为某个换乘车站网络节点的示意图，虚线框线内的节点归属于同一个车站，其中节点18、19、74、75为换乘车站节点，其余为普通车站节点。

图3 换乘车站网络节点示意图

假如某位乘客从车站A上车，在车站B下车，其间经过了两段区间运行时间和一段换乘时间，可以看出，符合该乘客正确换乘逻辑的路径应该是17-18-75-76。通过未改进的算法搜索到的相同起终点的路径有17-18-74-75-76、17-18-19-75-76和17-18-74-19-75-76。这些路径中均包含了不符合逻辑的停车时间和换乘时间，相应的18-74-75、18-19-75、18-74-19-75均可判定为冗余路段。结合以上分析，给出冗余路段的定义。

定义2 当有效路径的路段两端节点为换乘车站节点，且在路径中体现为冗余停车时间或冗余换乘时间，则称该路段为冗余路段。

2.2 路径冗余路段判定

通过分析可以发现，不包含冗余路段的有效路径中，路径经过某换乘车站或在某换乘车站进行换乘则有且只有两个换乘车站节点。因此，路径中冗余路段的判断逻辑为：如果有效路径中有连续3个或3个以上换乘车站节点，则该路径包含冗余路段。

为了筛选出包含冗余路段的有效路径，设立变量transfer记录网络中某节点是否为换乘车站节点，具体定义为：

(3)

在此基础上，根据每个节点的换乘节点变量transfer，搜索到的每条路径便有1个对应的相同长度的换乘节点序列。遍历路径换乘节点序列的子序列，如果子序列集合中包含“1-1-1”或者“1-1-1-1”的元素，则说明该路径中包含冗余路段，需要剔除。基于上述分析，以从节点17到节点76为例的路径换乘节点序列和冗余路段判定见表1。

表1 路径换乘节点序列和冗余路段判定示例

3 改进的有效路径搜索算法

在充分考虑各种路径搜索算法优缺点的情况下，采用深度优先遍历算法来实现有效路径搜索过程。

深度优先遍历的思想是：假设初始状态图中所有顶点均未被访问，从某个顶点v出发，首先访问该顶点，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到。若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

在上述深度优先遍历搜索算法中增加冗余路段判定步骤(Step 4)后，改进的有效路径搜索算法具体步骤如下：

Step 0：初始化。给相关变量赋初值，输入邻接矩阵，设定参数。

Step 1：利用Dijkstra算法计算最短路径阻抗，设根节点v为当前节点。

Step 2：从当前节点i出发，遍历与节点i相邻的节点，例如节点j，如果从根节点v出发沿着该路径的阻抗小于或等于设定阈值并且满足换乘限制条件，则令节点j为当前点，转下一步，否则转Step 6。

Step 3：判断节点j是否为终节点，如果不是则转入Step 2，否则进行下一步。

Step 4：判断该路径是否包含冗余路段，如果是则忽略该路径并转入Step 2，否则进行下一步。

Step 5：搜索前驱节点序列并输出路径。

Step 6：退回上一层，若未退回到根节点则转入Step 2。

4 案例分析

为了检验改进的有效路径搜索算法的可行性及有效性，利用某市轨道交通网络进行案例分析。该市轨道交通网络由1号线、2号线、3号线和4号线组成，共有5座换乘车站，网络示意图如图4所示。

图4 轨道交通网络示意图

4.1 网络参数取值

网络中停车时间、区间运行时间、换乘步行时间参数均为多次实测数据的平均值，换乘等待时间取各条线路平峰行车间隔的一半，网络最大换乘次数限制取2。

除此之外，定义1中的路径伸展系数是有效路径判定条件中的重要参数。如果路径伸展系数取值过大，路径阻抗过大甚至存在绕行情况的路径就被纳入到有效路径中；相反，如果取值过小，则会遗漏部分有效路径。因此，路径伸展系数的取值应根据具体的网络形式确定，通过式(4)计算网络主要换乘方向起讫点间最大合理路径的伸展系数，具体计算结果见表2。

定义3 当一条路径不经过背离起讫点方向的换乘站进行换乘，且在所有满足条件的路径中阻抗最大，则称该路径为最大合理路径。

如从A站到E站，经过G站换乘的路径则是不合理的路径。

(4)

可以看出，除D—E起讫点外，其他起讫点间最大合理路径的阻抗与最短路径阻抗十分接近。对于该市轨道交通网络来说，路径伸展系数取0.3即可满足要求。

表2 主要起讫点间最大合理路径伸展系数

4.2 有效路径搜索结果

利用Python程序语言编写改进后的搜索算法，并对A站与H站之间的有效路径进行搜索。如果采用未改进的算法，则程序输出结果显示有20条，但是经过人工辨识，其中有18条都包含冗余路段。这正是由于网络节点的特殊处理方式以及多个换乘站间冗余路段的乘积效应导致的有效路径数量与实际数量产生明显偏差。同时，由于冗余路段的存在，输出的路径阻抗也与真实的路径阻抗存在偏差。

现采用改进后的算法对A站与H站之间的有效路径进行搜索，共得到2条有效路径，结果表明改进后的算法能有效剔除包含冗余路段的路径，具体路径信息如表3所示。程序输出的有效路径信息符合乘客实际的换乘行为，并且保证了有效路径信息的正确性。

表3 A站-H站间有效路径信息

5 结束语

基于对轨道交通网络节点处理方式和有效路径搜索算法进行研究，对于在实际操作过程中发现的通过未改进算法搜索有效路径仍可能包含冗余路段的问题，给出了一种解决方法。

归因于轨道交通网络车站节点的特殊处理，通过深度优先算法搜索到的有效路径中可能包含冗余的停车时间或换乘时间。通过实例分析冗余路段的特征并给出冗余路段的定义。在深度优先搜索算法中增加了冗余路段判定步骤，具体为分析路径换乘节点序列的子序列集合中是否存在特定元素，进而改进了算法。实例分析中算法改进前后的搜索结果表明改进后的算法能够正确地筛选出轨道交通网络有效路径，得到完整的有效路径信息。研究成果为建立完整的城市轨道交通网络客流路径分析系统奠定了基础。