基于改进最短路径法的城市轨道交通有效路径集生成建模*

蔡昌俊 叶 茂 马灵玲 何建涛 殷世松

(1.广州地铁集团有限公司，510330，广州；2.南京理工大学交通工程系，210094，南京；3.交通信息融合与系统控制工业和信息化部重点实验室，210094，南京∥第一作者，正高级工程师)

随着城市轨道交通线网越来越发达，乘客的出行路径更加多样化。有效路径的确定是轨道交通客流合理分配的基础和断面客流估算的前提，是轨道交通票务清分重要的一部分[1-2]。同一OD(起讫点)对之间通常有很多条不同路径，乘客最初的出行都是基于最短路径的。随着城市轨道交通线网的扩大，存在多条费用差别不大的路径可供乘客选择。乘客出行的路径选择行为受到多种因素的影响，包括乘客类别[3]、列车拥挤度[4]和旅行时间等。因此，在某一OD对之间，存在一条或几条路径费用相近的可选路径，乘客若总是选择这一条或几条路径出行，这样的路径称为有效路径。

目前，国内外关于网络路径搜索算法的研究已经较为成熟，其中，最短路径法已经形成了非常经典的算法并被广泛采用[5-6]。与最短路径法相关的还有K最短路算法。文献[7]建立了突发事件下的网络受影响客流重分布预测算法，基于突发事件下乘客出行行为特征变化的分析,提出一种受影响客流的界定算法。文献[8]在K最短路算法的基础上，提出基于轨道网络特点的K最短路算法，将轨道站点之间K最短路径搜索转化为不同出行点对之间的换乘线路组合搜索，极大地缩小了搜索空间，同时将该算法与基于最短路径点分支变化的向外搜索算法进行路径搜索对比，证明该算法的高效性。除了基于遗传算法、蚁群算法、深度优先算法、广度优先算法和Dail算法等的路径生成算法，还有学者从另一种角度设计了有效路径生成算法。文献[9]基于轨道交通旅客出行所能承受的换乘次数是有上限的这一事实，设计出基于换乘次数的有效路径集生成算法，并用算例将该算法与全路径搜索算法对比，证明了该算法的高效性。

以往的研究往往追求OD对间有效路径的搜索效率，并没有考虑到路径集生成后后续使用的便利性，如缺乏对换乘关系的描述，客流预测就无法从路径集中直接生成换乘站在各个方向的换乘量。本文在不涉及轨道交通共线、共轨、并线运行的条件下，提出乘客出行有效路径应满足的基本假设。对路网中的线路和站点进行编号，将线路分割成连续的单位区间；基于路径选择影响因素分析，在最短路径法基础上改进并构建有效路径搜索模型；以2015年广州地铁网络为例进行应用分析，证明了所提有效路径搜索方法的有效性，为城市后续的轨道交通线网客流分配、断面客流估算及清分提供了较好的路径结构基础和方法支撑。

1 路径选择影响因素分析

在网络化条件下，某一OD对之间通常有多条路径，一般而言乘客总是选择出行费用较小的路径。而影响出行费用的因素不止一个，本文将这些影响因素归为客观因素与主观因素两种情况。

1.1 客观因素

客观因素主要为轨道交通线网结构与乘客出行的起始站和终点站位置，此类因素不受乘客自身感受的影响，主要分为无换乘出行和有换乘出行两种情况。无换乘出行情况是指城市中只存在一条轨道交通线路或乘客在一条没有换乘站的线路上出行时，只存在一条有效路径。有换乘出行情况是指当乘客出行的起始站和终点站不在同一条线上时，乘客出行时必须通过换乘才能到达，此时可能有多条路径可供选择。

单方式和多方式路径换乘示意图如图1所示。单方式换乘是指乘客出行的起始站和终点站之间只有一种换乘方式。例如，乘客想从站点A到站点C，只能在站点B进行换乘，此时有效路径只有一条。多方式换乘是指当网络中存在多个换乘站，乘客可按自己需求选择合适的换乘站路径到达目的地。如乘客由站点A上车至目的地站点D，可以通过站点B或站点C进行换乘。

图1 路径换乘示意图Fig.1 Diagram of path interchange

1.2 主观因素

主观因素为出行过程中使乘客具有自我感受、自我判断和自我选择的因素。当多数起、终点站之间有多条可达路径，在主观因素的影响下，大多数乘客只会把其中几条作为有效路径，主观因素有以下几种：

1) 候车时间：乘客采用轨道交通出行时，购票、安检和等车过程中有出行时耗。

2) 乘车时间：主要包括列车在各区段的运行时间和在各站点的停站时间。

3) 换乘时间：在轨道交通网络中，当某一OD对之间不能直达时，需通过换乘站进行换乘，且不同换乘站的换乘过程所消耗的换乘时间也不相同。

4) 换乘次数：当乘客对轨道交通网络不熟悉或是两种路径所花费的旅行时间相差不大时，通常乘客更偏向于选择换乘次数少的路径。

2 有效路径建模前提

2.1 有效路径的假设前提

基于地铁线网的实际情况和乘客的出行习惯，将有效路径搜索模型的假设定义如下：

假设1：若起始站和终点站属于同一条线路，则仅存在一条有效路径，即乘客只在该条线路上出行；

假设2：线网中不存在较大的弧线，即在假设1成立的条件下，乘客在一条线路上出行时不存在绕行情况；

假设3：线网中不存在环线情况；

假设4：在假设1成立的条件下，当起始站和终点站同为换乘站，且为同两条线路的换乘站时，需特殊考虑，即可能存在两条有效路径。

2.2 轨道交通线网的抽象表示

1) 站点编号原则。对线网中的每一个车站进行编号。编号的基本原则为：每个站的编号共4位，前2位为该站所在的线路编号，后2位为该站在所在线路中的排序。广州地铁5号线部分车站编号情况如图2所示。

图2 广州地铁站点的编号情况示意图Fig.2 Diagram of the numbering of Guangzhou metro stations

一般车站只位于一条线路上，映射在图中的结点是唯一的，所以一般站只需要一个车站编号便可唯一确定。而线网中的换乘站至少在两条线路上，只用一个车站编号不能完全记录换乘车站的全部信息，则其编号原则为：将换乘站的编号个数定为所在线路个数，在不同线路上采用不同编号，每个编号仍根据一般站的编号。如广州地铁线网中的坦尾站、广州火车站站、区庄站这3个换乘站的编号(见图2)，在这种情况下，便可看成线网中各条线之间只能通过换乘站相互衔接，减少了线路间的相互干扰。

2) 线网单位区间定义原则。本文提出单位区间的概念，即线网中的各条线路可以分割成相邻站点的最小区间，或乘客发生换乘行为的换乘站内的换乘虚拟区间，如图3所示。其中：不同线条表示不同线路，实线段表示相邻车站间的单位区间；虚线段表示乘客在换乘站发生换乘行为的换乘虚拟区间。

图3 线网单位区间示意图Fig.3 Diagram of line network unit interval

3 有效路径建模

3.1 构建线网拓扑图

构建全网拓扑图，用线段表示线路，用节点表示车站。在城市轨道交通中，各线路是双向开行的，因此拓扑图中的线段都表示双向线段。换乘站的节点数等于该换乘站所在的线路个数。对拓扑图中的所有节点进行排序，使得不同节点之间可以用序号进行区分，这样简化了城市轨道交通网络的表达形式，以便于编程的实现。

用G={V,E,T}来描述轨道交通网络模型，G为轨道交通网络模型，V为车站集合，E为站间单位区间集合，T为换乘虚拟区间集合，则有：

vi∈V，ei,j∈E， (ti,j，tmi′,nj′)∈T

(1)

式中：

vi——拓扑图中序号为i的车站；

ei,j——拓扑图中序号为i的车站到序号为j的车站单位区间；

ti,j——拓扑图中序号为i的车站到序号为j的车站虚拟区间；

tmi′,nj′——乘客从线路m的车站i′换乘到线路n的车站j′的虚拟区间。

ei,j、ti,j的出行费用单位区间个数(xei,j、xti,j)以及单位区间运行时间(yei,j、yti,j)可以表示为：

(2)

式中：

α、β——取值为0或1的系数，当α=1时，β=0；当β=1时，α=0。

3.2 基于改进最短路径法的有效路径生成

基于对路径选择影响因素的分析，构造两个关于全网出行费用的邻接矩阵，运用最短路径法搜索每个邻接矩阵下的最短路径，并以此为基准设置乘客忍受阈值，构建有效路径搜索模型。

1) 对网络拓扑结构构造关于线网出行费用的邻接矩阵，则有：

(3)

矩阵A用来记录拓扑图中连接相邻节点的所有有向线段在实际线网中的费用值。矩阵A中的行(列)号对应各车站在拓扑图中的节点序号，其取值方式可以表示为：

(4)

根据ei,j和ti,j的取值情况，将所构造的两个全网邻接矩阵，运用改进的最短路径法分别在每一个邻接矩阵中搜索某OD对间的有效路径，在这两种情况下搜索得出的路径均为该OD对的有效路径。

2) 构建最短路径搜索模型，其最短路径的计算方法可以表示为：

(5)

式中：

s——站点总数；

COD i,j——一个OD对间所有可达路径出行费用的集合。

3) 改进最短路径搜索模型，构建有效路径搜索模型。最短路径法只能搜索出某OD对间的最短路径，对其进行改进后，能成功搜索出某OD对间的几条有效路径，并在此基础上生成全网的有效路径集。改进的过程可以表示为：

(6)

式中：

COD有效——一个OD对间所有有效可达路径出行费用的集合；

COD——一个OD对间所有路径出行费用的集合。

4 实例分析

以2015年广州地铁线网为例，基于AFC(自动售检票系统)数据用所提方法搜索全网OD的有效路径集。2015年广州地铁线网的拓扑结构，如图4所示。其中：每条线段表示双向开行的情况；为了简化拓扑图，只将线网中的换乘站节点显示出来，用虚线圈表示，同一虚线圈内的小圈表示同一换乘站在不同线路上的节点。拓扑图中各线路对应的编号如表1所示。8号线上各车站在线网中的编号和拓扑图中的序号如表2所示。其余线路的站点编号与序号与之同理。

图4 2015年广州地铁线网拓扑图Fig.4 Topology of Guangzhou metro line network in 2015

表1 2015年广州地铁线路编号Tab.1 Guangzhou metro line numbers in 2015

表2 8号线站点名称及编号Tab.2 Station names and numbers of Line 8

根据2015年广州地铁线网的运营情况，确定网络中ei,j和ti,j的取值情况，分别取α=1、β=0和β=1、α=0，构造两个关于线网单位区间出行费用的邻接矩阵；用改进的最短路径法，生成全网OD的有效路径集。2015年广州地铁线网OD对拥有不同有效路径条数的比例情况如表3所示。用所提方法搜索得到的(西塱站→体育西路站)、(西塱站→体育中心站)单一有效路径的结果，如图5所示。用所提方法搜索得到的(西塱站→广州南站站)和(西塱站→广州火车站站)OD对间的多条有效路径，如图6所示。

表3 2015年广州地铁线网OD对拥有不同有效路径条数的比例情况

图5 单一有效路径Fig.5 Single valid path

图6 多条有效路径Fig.6 Multiple valid paths

由表3可知，运用所提有效路径集生成方法生成有效路径时，58.29%的OD对只有一条有效路径，86.21%的OD对有效路径条数不超过3条，95%的OD对有效路径条数不超过5条。由此可知，运用本文提出的方法生成的有效路径集符合实际情况。由图5和图6中的4个OD对可以看出，当起终点在同一线路上时，只存在一条有效路径；当起终点不在同一线路上时，能有效运用该方法搜索出该OD对的有效路径。

5 结语

本文根据乘客在城市轨道交通中的实际出行情况，提出乘客出行有效路径应满足的基本假设，构建线网拓扑图，通过对路径选择影响因素的分析，构造两个关于全网出行费用的邻接矩阵，运用最短路径法搜索每个邻接矩阵下的最短路径，并以此为基准设置乘客忍受阈值，构建全网OD对有效路径集搜索模型。以2015年广州地铁线网为例，证明了本文提出的有效路径搜索方法的有效性，为后续研究提供了较好的数据结构基础。本文获得的主要结论为：

1) 对轨道交通线网中的线路和站点进行编号，将线路分割成单位区间，使轨道交通线网次序化。

2) 在最短路径法的基础上进行改进，解决了最短路径法针对一个OD对只能搜索出最短路径的问题。所提方法主要以时间代价为基准，遍历生成的有效路径集，并以线路路径费用最短为条件进行筛选，较好地解决了K最短路算法中生成重复路径的问题。

3) 所提方法最后生成的有效路径集详细记录了路径经过的所有站点以及涉及的换乘关系，便于后续客流分配以及断面客流估算研究。本文从AFC数据中随机选取了100条数据，最低的准确度为81.76%，90%以上的路径准确率高于85%，从而可以论证所提方法的有效性。