城市轨道交通网络时变路径搜索算法

引用本文

周玮腾, 韩宝明. 城市轨道交通网络时变路径搜索算法[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.
Doi:10.11860/j.issn.1673-0291.2017.04.017 复制到剪切板

Permissions

北京交通大学学报编辑部所有

城市轨道交通网络时变路径搜索算法

周玮腾, 韩宝明

北京交通大学交通运输学院,北京 100044

通信作者:韩宝明(1963—),男,山西太原人,教授,博士,博士生导师. email:bmhan@bjtu.edu.cn

第一作者:周玮腾(1988—),男,湖南郴州人,讲师,博士. 研究方向为城市轨道交通运输规划与管理.email:zhouwt@bjtu.edu.cn

收稿日期: 2016-09-05

基金: 北京市自然科学基金(8162033); 北京交通大学实验室研究课题(16010206)

摘要

为求解时变路径搜索问题,设计并实现了城市轨道交通大规模网络条件下的时变 k短路径搜索算法.算法可分为两部分:首先基于深度优先的边删除法搜索网络的静态 k短路径,然后将静态 k短路径按照列车到发时刻进行扩展并排序获得时变 k短路径.将算法应用于北京地铁网络路径搜索实例中,通过与既有算法对比,证明本文算法具有较优的效率,并能够获取基于列车时刻表的有效的时变 k短路径集,为城市轨道交通网络路径搜索和管理提供辅助技术支持.

关键词: 城市轨道交通; 路径搜索; k短路径; 时变路径; 时刻表; 扩展

中图分类号:U293

Temporal path searching algorithm of urban rail transit network

ZHOU Weiteng, HAN Baoming

School of Traffic and Transportation, Beijing Jiaotong University, Beijing 100044,China

Fund:Foundation item:Beijing Municipal Natural Science Foundation(8162033); Beijing Jiaotong University Laboratory Research Project(16010206)

Abstract

A new method on searching the dynamic and temporal k-shortest paths in the urban rail transit network is put forward in this paper, which can be used to solved the dynamic path searching problem in huge scale network. The algorithm can be divided into two part: firstly, the static k-shortest path of the network can be searched based on depth-first deletion algorithm; then the temporal path can be obtained and sorted by the train arrival and departure time expanding in the schedule. The effectiveness of the algorithm proposed in this paper is verified in comparison with the existing algorithm through the case study in Beijing subway network, and the temporal k-shortest path in the network based on the train schedule can be obtained accurately, which demonstrates that it could provide decision support for the operation and travel guidance of path management in urban rail transit network.

Keyword: urban rail transit; path searching; k-shortest path; temporal path; schedule; expand

文章图片

我国部分大城市已经进入大规模的城市轨道交通网络化运营时期^[1].在网络化运营时期, 一些原本在单线运营条件下较为明确和简单的问题逐渐显得模糊和复杂化, 如OD车站间的有效路径搜索问题.随着城市轨道交通网络规模增大和网络化程度提高, 该问题的求解复杂程度也相应增加.对于轨道交通出行服务而言, 网络中的OD车站间的有效路径是进行乘客出行路径诱导的前提; 对于轨道交通运营管理而言, 轨道交通网络的客流动态预测和清分结算是以每个OD对间的有效路径为基础计算清分比例^[2].因此, 通过网络路径搜索获取不同OD车站之间的有效路径具有重要的理论和现实意义.

网络路径搜索是获取网络中有效路径的基本方法, 属于图论研究范畴, 一直是国内外广泛研究的方向.在最初应用于大规模交通网络的最短路径搜索算法中, 分别形成了Dijkstra^[3]和Floyd^[4]等常用算法.Dijkstra算法用于解决非负权网络中单源顶点到其他顶点的最短路径问题, 是目前应用最为广泛的搜索算法, 并分别形成了DKA(Dijkstra’ s algorithm implemented with approximate buckets)和DKD(Dijkstra’ s algorithm implemented with double buckets)等改进的D算法^[5].然而在网络路径搜索中, 往往不仅需要获得最短路径, 而且需得到次短路径、k短路径等路径或路径集, 进而衍生了k短路径搜索问题.k短路径搜索问题和算法最早是由Hoffman等^[6]提出, 实际上最短路径问题是k短路径搜索的特殊情况(k=1), 而k≥ 2条件下的k短路径搜索问题受到更多学者的研究和关注.在最短路径搜索算法的基础上, Yen^[7]提出了利用边删除算法获得最小支撑树的子图, 通过求解子图最短路径获得图中无环k短路径问题, 这也是迄今为止影响最深的k短路径搜索算法.经过多年的发展, 在边删除法的基础上, 分别形成了更多的优化和改进算法^{[8, 9]}.在城市轨道交通网络的路径搜索方面, 徐瑞华等^[10]在保证路径完备性的基础上, 通过删除法获得轨道交通网络上任意两点不重复的k条路径; 四兵锋等^[11]提出了基于深度优先的遍历算法以获取有效路径搜索.这两类算法因其高效的运算能力, 成为目前比较常用的轨道交通网络k短路径搜索算法.但是, 算法仅考虑了静态路网拓扑结构下的路径搜索问题, 缺乏网络中列车动态运行对于路径的可达时间依赖约束.在实时客流分配时需设计更为高效的方法以获取轨道交通网络中的动态路径, 目前对于轨道交通网络的动态k短路径搜索研究较少, 在既有的研究中多以改进的公交网络的动态时变路径搜索算法为主, 并将该类路径搜索问题归纳为时间依赖网络(time-dependent network)的路径搜索问题^[12], 如Xu等^[13]提出的基于时刻表的公交网络k短路径搜索方法, 采用车辆到达时间列表排序进行路径遍历, 以保证搜索的网络时空路径的动态有效性.

针对当前城市轨道交通网络路径搜索算法以静态为主, 未考虑列车运行时刻表和换乘时间对网络动态时变路径的约束这一问题, 本文作者面向城市轨道交通网络客流动态路径诱导和客流分布管理的实际应用需求, 研究并提出任意时刻标度下的基于列车时刻表约束的城市轨道交通时变k短路径搜索问题和解决策略.结合列车运行图扩展时空网络, 通过双层拓扑子图的深度优先的分支边删除算法, 采用时刻表扩展策略, 设计实现有效而实用的城市轨道交通网络下的k短时变路径的搜索算法.

1 时变路径搜索问题建模

时变路径搜索的前提在于进行时变网络建模.考虑到城市轨道交通网络是由物理拓扑网络和列车运行网络嵌套的复合网络, 因此结合给定列车时刻表构建城市轨道交通时变网络拓扑G(N, A, L, T), 其中N={n₁, n₂, n₃, ...}为网络上的节点, 表示路网上的车站; A={a₁, a₂, a₃, …}为网络上所有连接的边和弧, 边表示路网上连接车站的区间, 弧表示连接换乘站的通道; L={l₁, l₂, l₃, …}为网络上运营的轨道交通线路; T={t₁, t₂, t₃, …}表示网络上列车的到发时刻集合.该网络拓扑结构包括以下两方面的定义.

1)物理网络建模层面:将城市轨道交通网络拓扑描述为加权有向连接图, 如图1所示, A站和B站依据所在的线路建模为2个具有方向特征的“ 虚拟节点” , I线、II线和III线路的同方向轨道区间建模为节点间相互连接的边, 对于A和B换乘站, 节点间的相互换乘关系则通过换乘弧进行连接, 如图中连接虚线所示.在物理拓扑网络上OD对间的静态路径是由相邻节点构成的连接边序列.

	Figure Option View Download New Window
	图1 城市轨道交通物理网络建模Fig.1 Modelling of urban rail transit physical network

进一步分析物理网络模型, 由于城市轨道交通网络中的大部分节点连接度为2, 在路径搜索时遍历多个节点会降低搜索效率.因此本文引入仅具有换乘站节点的拓扑子网络.通过保留原拓扑中换乘车站节点, 隐去其他普通车站节点, 根据其连接关系通过有向边重连形成新的网络.图2表示某城市轨道交通网络拓扑简化前后的情况.简化后的换乘节点拓扑子网络变为了由圆圈组成的非完全二分图, 大部分节点的连接度大于2, 适用于深度优先的前向边删除法进行k短路径搜索.在静态路径搜索时, 可先搜索拓扑子网络的k短路径, 再利用普通车站节点与换乘站节点的连接关系, 采用节点比较的方式获得全路网的k短路径.

	Figure Option View Download New Window
	图2 某地铁拓扑网络和拓扑子网络Fig.2 Topological network and sub-network of one subway

2)时刻表扩展网络^[14]建模:在建立物理网络的基础上, 为了表征时变路径, 可根据列车时刻表列车的到发时间, 将拓扑网络的空间线路和节点进行关联和扩展.通过列车的运行径路及其到发时间将静态网络的节点进行关联, 形成时变连接弧, 并按照列车到发车次形成时刻表扩展网络.

在时刻表扩展网络中, 任意一对OD站点之间的时变连接弧在时间维度的连接序列表示OD车站间的时变路径, 必须满足线路节点之间的连通关系, 同时满足时刻表上列车的接续关系.图3表示车站a₁至b₃在早7:30— 8:00之间的时变扩展路径的扩展弧连接关系.

	Figure Option View Download New Window
	图3 时刻表扩展网络Fig.3 Schedule-expanded network

根据城市轨道交通时变网络拓扑G(N, A, L, T), 建立时变k短路径搜索模型的目的是求解从起始车站节点s到目标车站节点t的路径集 $R_{s, t}^{Tar}$ { $l_{s, t}^{Tar, 1}$ , $l_{s, t}^{Tar, 2}$ , …, $l_{s, t}^{Tar, k}$ }, 使该路径集中的所有路径对于任意时刻Tar, 在列车按图行车的条件下, 费用权值C( $l_{s, t}^{Tar, k}$ )为节点s与t间所有路径的前k小时间费用.

模型表示如下.

C( $l_{s, t}^{Tar, k}$ )=min_k $\{\sum_{(n_{i}, n_{j}) \in G (N, A, L, T)} C (n_{i}, n_{j})\}$ (1)

式中:C(n_i, n_j)表示时变路径 $l_{s, t}^{Tar, k}$ 连接边(n_i, n_j)的时间费用; i, j表示路径上的节点序列号; min_k表示前k小时间费用排序.

2 时变k短路径搜索算法

由于拓扑网络的静态k短路径实际上是时变k短路径的特殊情况, 即对于任意时刻Tar, 静态k短路径忽略了不同线路之间的列车接续关系和换乘走行时间约束, 但标定了时变k短路径的节点序列关系.因此本文在进行时变k短路径搜索算法设计时考虑将完整的搜索过程分割为两部分, 一部分为求取拓扑网络节点间的静态k短路径; 另一部分以此为基础, 利用时刻表扩展网络对列车车次遍历计算时变的换乘弧权值, 从而获取时刻表扩展网络中任意时刻的时变k短路径.定义算法中所使用的符号, 如表1所示.

表1 算法中所涉及的符号及释义 Tab.1 Symbols with its meaning involved in the algorithm

符号	符号的含义
(s, t)∈ A(O, D), s≠ t	任意OD车站节点对(s, t)
L'_s_,_t{ $l_{s, t}^{1}$ , $l_{s, t}^{2}$ , …, $l_{s, t}^{k}$ }	拓扑子网络g(n, a, l)的静态k短路径集
l'_s_,_t{ $h_{s, t}^{1}$ , $h_{s, t}^{2}$ , …, $h_{s, t}^{n}$ }	拓扑子网络g(n, a, l)的n短备选路径集
r_s_,_t{ $r_{s, t}^{1}$ , $r_{s, t}^{2}$ , …, $r_{s, t}^{k}$ }	拓扑子网络g(n, a, l)的辅助判断k短路径集
p{v₁, v₂, …, v_m}	当前节点p的前向m个扩展节点集合
n_l(v₁, v₂, …, v_d)	路径l的连接节点序列, v₁表示起始节点, v_d表示终止节点
l_o{ $l_{o_{1}}$ , $l_{o_{2}}$ , …, $l_{o_{n}}$ }	起始节点o与起始关联换乘站节点的连接边
$l_{d_{}}$ { $l_{d_{1}}$ , $l_{d_{2}}$ , …, $l_{d_{m}}$ }	目标节点d与目标关联换乘站节点的连接边
R_o_,_d{ $l_{o, d}^{1}$ , $l_{o, d}^{2}$ , …, $l_{o, d}^{k}$ }	全网络的静态k短路径集
$L_{o_{}}$ { $l_{{o_{1}}_{}}$ , $l_{{o_{2}}_{}}$ , …, $l_{{o_{n}}_{}}$ }	全网络G(N, A, L)中起始点o与换乘站节点的前n条关联边
l_d{ $l_{{d_{1}}_{}}$ , $l_{{d_{2}}_{}}$ , …, $l_{{d_{m}}_{}}$ }	全网络G(N, A, L)中目标点d与换乘站节点的前m条关联边
$R_{s, t}^{Tar}$ { $l_{s, t}^{Tar, 1}$ , $l_{s, t}^{Tar, 2}$ , …, $l_{s, t}^{Tar, k}$ }	全网络G(N, A, L, T)中Tar时刻的时变k短路径集
Ru $n_{l_{s, t}^{k}}$ (Run₁, …, Run_M)	按照 $l_{s, t}^{k}$ 方向遍历时刻表中该线路的经过s点的车次
T $s_{l_{s, t}^{k}}$ (Ts₁, …, Ts_j_-1)	Ru $n_{l_{s, t}^{k}}$ (Run₁, …, Run_M)沿 $l_{s, t}^{k}$ 路径方向的换乘站节点
T $a_{L_{j}, T s_{j}}$ (ta₁, …, ta_M)	沿L_j到达换乘站Ts_j到达时刻, M表示线路L_j绕过的换乘站数量
$r_{s, t, k}^{l, Tar}$	节点对(s, t)的静态路径l在时刻Tar的经k次扩展的时变路径集
$B_{s, t}^{Tar}$ { $b_{s, t}^{Tar, 1}$ , $b_{s, t}^{Tar, 2}$ , …, $b_{s, t}^{Tar, n}$ }	全网络G(N, A, L, T)临时时变k短路径集

表1 算法中所涉及的符号及释义 Tab.1 Symbols with its meaning involved in the algorithm

2.1 静态k短路径搜索(算法1)

静态k短路径搜索算法的思路在于搜索仅具有换乘节点的拓扑子网络的静态k短路径, 然后将全网络中普通节点与换乘节点的连接边时间费用与拓扑子网络的静态k短路径相加进行k短费用排序, 获得全网络的静态k短路径集.由于采用了仅具有换乘节点的拓扑子网络, 因此降低了静态k短路径搜索复杂度.对于所有的节点对(s, t)∈ A(O, D), s≠ t的k短路径搜索算法具体步骤为:

Step 1 在拓扑子网络g(n, a, l)下, 通过Dijkstra算法搜寻 $l_{s, t}^{1}$ , 存储该路径以s为顶点的最小路径树 $T_{i}^{s, t}$ .将 $l_{s, t}^{1}$ 存入l'_s_,_t{ $h_{s, t}^{1}$ , $h_{s, t}^{2}$ , …, $h_{s, t}^{n}$ }.

Step 2 对l'_s_,_t{ $h_{s, t}^{1}$ , $h_{s, t}^{2}$ , …, $h_{s, t}^{n}$ }中每条路径按序号执行下列操作:

①选择当前考察路径 $h_{s, t}^{i}$ , 把路径起始节点s作为当前节点, i表示按路径长短排序的标号, 构建考察路径 $h_{s, t}^{i}$ 的节点序列 $n_{h_{s, t}^{i}}$ (v₁, v₂, …, v_d).

②找到 $n_{h_{s, t}^{i}}$ (v₁, v₂, …, v_d)中当前节点的下一个接续节点p, 令p为当前节点, 将p与该路径上的下一个接续节点q的连接边a(p, q)权值设为∞ , 即移除该连接边进而重构网络.若i=1, 即此时 $h_{s, t}^{1}$ = $l_{s, t}^{1}$ , 则搜索网络下由节点p出发至终点t的最短路径r'_s_,_t, 储存至r_s_,_t{ $r_{s, t}^{1}$ , $r_{s, t}^{2}$ , …, $r_{s, t}^{k}$ }中; 若1< i≤ k, 则转入③.

③判断前i-1备选路径集是否包含节点p与p{v₁, v₂, …, v_m}的连接边a(p, v_i), 若包含则将连接边权值设为∞ , 若不包含则保留其原权值.搜索此时由当前节点p出发至终点t的最短路径r'_p_,_t, 由于保留了以s为节点的最小路径树, 则此时的最短路径r'_s_,_t= $T_{i}^{s, p}$ ∪ r'_p_,_t, 将该路径存入r_s_,_t{ $r_{s, t}^{1}$ , $r_{s, t}^{2}$ , …, $r_{s, t}^{k}$ }中.

④还原当前节点p, 接续节点q和p{v₁, v₂, …, v_m}的连接边, 使q为当前节点.判断t点是否是当前节点, 若是则跳出Step 2, 对r_s_,_t{ $r_{s, t}^{1}$ , $r_{s, t}^{2}$ , …, $r_{s, t}^{k}$ }中路径进行排序, 将该路径集中最短路径存入l'_s_,_t{ $h_{s, t}^{1}$ , $h_{s, t}^{2}$ , …, $h_{s, t}^{n}$ }; 否则转至步骤②.

⑤若i< k, 则i=i+1, 返回步骤①; 当i=k, 则跳至Step 3.

Step 3 对l'_s_,_t{ $h_{s, t}^{1}$ , $h_{s, t}^{2}$ , …, $h_{s, t}^{n}$ }中路径进行k序列排序, 获取L'_s_,_t{ $l_{s, t}^{1}$ , $l_{s, t}^{2}$ , …, $l_{s, t}^{k}$ }.

Step 4 利用换乘站与其他普通站的连接关系, 将g(n, a, l)复化为全网络G(N, A, L), 进行节点与边的转换, 此时拓扑子网络起终点(s, t)将对应网络路径起终点(o, d), 同时利用边的转换存储与节点o关联的换乘站节点集合, 存储与节点d关联的换乘站节点集合.

Step 5 搜索l_o{ $l_{o_{1}}$ , $l_{o_{2}}$ , …, $l_{o_{n}}$ }与l_d{ $l_{d_{1}}$ , $l_{d_{2}}$ , …, $l_{d_{m}}$ }, 并计算其连接边费用.由于节点o和d本身有可能为换乘站节点, 同时约束当o和d本身为换乘站节点时, 其换乘关联节点集合为空集.当换乘关联节点集合为空集时, $l_{o_{n}}$ = $l_{d_{m}}$ =0.则全网络的k短路径集R_o_,_d{ $l_{o, d}^{1}$ , $l_{o, d}^{2}$ , …, $l_{o, d}^{k}$ }可通过拓扑子网络的k短路径集L'_s_,_t{ $l_{s, t}^{1}$ , $l_{s, t}^{2}$ , …, $l_{s, t}^{k}$ }与关联换乘站节点的连接边费用相加, 再进行k序排列获得, 即 $l_{o, d}^{k}$ =min_k{R_o_,_d= $l_{s, t}^{k}$ + $l_{o_{n}}$ + $l_{d_{m}}$ }.

算法1执行的伪代码如下:

算法1:Define G(N, L, A), g(n, l, a)

∀ (s, t)∈ A(O, D), s≠ t

Search $l_{s, t}^{1}$ , $T_{i}^{s, t}$ , $l_{s, t}^{1}$ → l'_s_,_t{ $h_{s, t}^{1}$ , $h_{s, t}^{2}$ , …, $h_{s, t}^{n}$ }in g(n, l, a)

Sort l_s_,_t{ $h_{s, t}^{1}$ , $h_{s, t}^{2}$ , …, $h_{s, t}^{n}$ }

$\{\begin{array}{l} \forall h_{s, t}^{i}, i = 1 : n \\ \forall n_{l} (v_{1}, v_{2}, \dots, v_{d}), j = 1 : d \\ \{\begin{array}{l} Find p, q in n_{l} (v_{1}, v_{2}, \dots, v_{d}) \\ \{\begin{array}{l} if p = = t \\ Sort r_{s, t} {r_{s, t}^{1}, r_{s, t}^{2}, \dots, r_{s, t}^{k}}, r'_{s, t} \to l'_{s, t} {h_{s, t}^{1}, h_{s, t}^{2}, \dots, h_{s, t}^{n}} \\ end j \end{array} \\ \{\begin{array}{l} else p! = t \\ Set a (p, q) = \infty, Rebuild g (n, l, a) \\ Search r'_{s, t} \\ if (i = 1) r'_{s, t} \to r_{s, t} {r_{s, t}^{1}, r_{s, t}^{2}, \dots, r_{s, t}^{k}} \\ else (1 < i \leq k) \\ Find r'_{p, t} whena (p, v) \notin r'_{s, t} \\ Then r'_{s, t} = T_{i}^{s, p} ⋃ r'_{p, t} \\ r_{s, t} \to r_{s, t} {r_{s, t}^{1}, r_{s, t}^{2}, \dots, r_{s, t}^{k}} \\ Recovery p, q, a (p, q) \end{array} \\ end j \end{array} \\ if (i < k) i = i + 1 \end{array}$

else (i=k)

end n

Sort l'_s_,_t{ $h_{s, t}^{1}$ , $h_{s, t}^{2}$ , …, $h_{s, t}^{n}$ }, Find min_k(L'_s_,_t{ $h_{s, t}^{1}$ , $h_{s, t}^{2}$ , …, $h_{s, t}^{k}$ })

Search $l_{o, d}^{k}$ =min_k{R_o_,_d= $l_{s, t}^{k}$ + $l_{o_{n}}$ + $l_{d_{m}}$ }

2.2 时变k短路径搜索(算法2)

时变k短路径搜索算法的思路在于根据时刻表扩展网络的建模形式, 对静态路径按照给定时刻表的列车车次在图定的时间维度进行扩展, 通过扩展后的路径费用排序获得静态k短路径的时变路径.设对于每条线路进行扩展的最大车次数量为M, 则在时刻Tar下, 对于全网络G(N, A, L, T), (s, t)∈ A(O, D), s≠ t, R_s_,_t中任意路径 $l_{s, t}^{k}$ 的扩展M次时变路径方法如下:

1)根据起始点s和 $l_{s, t}^{k}$ 的节点序列, 按照 $l_{s, t}^{k}$ 方向遍历经过的线路 $L_{l_{s, t}^{k}}$ (L₁, …, L_j), j表示经过线路的总数, 同时遍历时刻表中该线路的经过s点的车次Ru $n_{l_{s, t}^{k}}$ (Run₁, …, Run_M), 令Tr(tr₁, …, tr_M)表示其到达时间T_arv大于Tar的前M次列车车次到站时间集合.设沿 $l_{s, t}^{k}$ 中换乘站节点Ts(Ts₁, Ts₂, …, Ts_j_-1)的换乘弧时间费用为d(d₁, d₂, …, d_j_-1).

2)根据时刻表依次遍历Ru $n_{l_{s, t}^{k}}$ (Run₁, …, Run_M)沿L_j到达换乘站Ts_j到达时刻T $a_{L_{j}, T s_{j}}$ (ta₁, …, ta_M), 在列车接续情况下, 若路径有效则换出线路L_j₊₁列车到达时刻需大于tr_M+d_j, 应按照时刻表遍历该线路的前M次到达时刻大于tr_M+d_j的列车车次Run'(Run'₁, …, Run'_M), 记录其发车时间为Tr'(tr'₁, …, tr'_M).

3)根据步骤2)沿路径 $l_{s, t}^{k}$ 逐次向前考察节点, 直至遍历所有的换乘节点.根据最后1个换乘节点的列车到达时刻, 并依据时刻表向前搜索M次列车, 即可获得 $l_{s, t}^{k}$ 的扩展M次时变路径.

在此基础上设计深度优先的算法遍历列车车次获得 $R_{s, t}^{Tar}$ { $l_{s, t}^{Tar, 1}$ , $l_{s, t}^{Tar, 2}$ , …, $l_{s, t}^{Tar, k}$ }, 算法为:

Step 1 令n=1, 根据时变路径扩展方法求出R_s_,_t中每条静态路径 $l_{s, t}^{i}$ 经第n次扩展的时变路径 $r_{s, t, k}^{l, Tar}$ , 将 $r_{s, t, k}^{l, Tar}$ 存入 $B_{s, t}^{Tar}$ .

Step 2 对 $B_{s, t}^{Tar}$ 中的时变扩展路径进行比较, 计算出最小的权值, 将最小权值的路径存入 $R_{s, t}^{Tar}$ 中, 并置为当前路径.

Step 3 令n=n+1.若n< k, 则转Step 4, 否则结束, 输出 $R_{s, t}^{Tar}$ .

Step 4 将当前路径的静态路径进行第n次列车车次扩展, 存入 $B_{s, t}^{Tar}$ 中, 转Step 2.

算法2执行的伪代码如下:

算法2:Define G(N, L, A, T), M, Tar

$\{\begin{array}{l} \forall (s, t) \in A (O, D), s \neq t \\ Set R_{s, t} {l_{s, t}^{1}, l_{s, t}^{2}, \dots, l_{s, t}^{k}} \\ \{\begin{array}{l} \forall k \\ Set L (L_{1}, \dots, L_{j}), d (d_{1}, \dots, d_{j}) \\ \{\begin{array}{l} \forall j \\ Find T r_{l_{s, t}^{k}} (t r_{1}, \dots, t r_{M}), Ru n_{l_{s, t}^{k}} (Ru n_{1}, \dots, Ru n_{M}) \\ when T_{arv} \geq Tar \\ {Tr, Run} \to R_{s, t}^{Tar} {l_{s, t}^{Tar, 1}, l_{s, t}^{Tar, 2}, \dots, l_{s, t}^{Tar, k}} \\ \{\begin{array}{l} \forall M \\ Find T a_{L_{j}, T s_{j}} (t a_{1}, \dots, t a_{M}) \\ Find T_{arv} \geq t a_{M} + d_{j} \\ Find Tr' (tr'_{1}, \dots, tr'_{M}), Run' (Run'_{1}, \dots, Run'_{M}) \\ {Tr', Run'} \to R_{s, t}^{Tar} {l_{s, t}^{Tar, 1}, l_{s, t}^{Tar, 2}, \dots, l_{s, t}^{Tar, M}} \\ end M \end{array} \end{array} \\ end j \end{array} \\ end k \end{array}$

end(s, t)

$\{\begin{array}{l} \forall (s, t) \in A (O, D), s \neq t, l_{s, t}^{k} \in R_{s, t} \\ \{\begin{array}{l} \forall k \\ Cal r_{s, t, k}^{l, Tar} of R_{s, t} (l_{s, t}^{1}, l_{s, t}^{2}, \dots, l_{s, t}^{k}), r_{s, t, k}^{l, Tar} \to B_{s, t}^{Tar} \\ Find l_{s, t}^{Tar, 1} = Min (B_{s, t}^{Tar} {b_{s, t}^{Tar, 1}, b_{s, t}^{Tar, 2}, \dots, b_{s, t}^{Tar, n}}), \\ l_{s, t}^{Tar, 1} \to R_{s, t}^{Tar} \\ Set l_{s, t}^{Tar, 1} \\ end k \end{array} \\ end (s, t) \end{array}$

对算法的复杂度进行分析.算法1中, 设全网络的节点数量为N, 换乘子网络的节点数量为n', 获取换乘子网络上任意节点间的时间复杂度为O(n'²)^[4], 若采用Fibonacci Heap结构^[15], 则复杂度为O $(M' + n'logn')$ , 其中M'为换乘子网络所有边的数量.由于采用删边法进行静态k短路径搜索, 设删除路径有效边的最大数量为L_max, 则算法1的时间复杂度为O(kNL_max $(M' + n'logn')$ ).设算法2中对每个节点按照时刻表扩展H次, H最大值为经过这个节点的列车车次数Tr_max, 设S_max为线路的最大车站数, 则算法2的时间复杂度为O(kn'S_maxTr_max).整个算法的复杂度为O(kNL_max $(M' + n'logn')$ )+O(kn'S_maxTr_max).在实际的城市轨道交通时变k短路径搜索中, 可将算法1计算的k短路进行离线存储, 通过算法2进行动态搜索, 在每个时间标度T下, 需要时间复杂度O(kn'S_maxTr_max).

3 算例研究

以北京地铁网络为研究对象, 验证本文的城市轨道交通网络时变k短路径搜索算法的运算效率和时变合理性.选取2015年12月某日北京地铁网络拓扑图作为路径搜索基础网络, 网络共含有281座车站, 17条运营线路, 41个换乘车站, 602个列车运行区间, 全日运行列车数为7 078列, 其中高峰小时(早7:00-9:00, 晚17:00-19:00)列车运行数为2 028列, 高峰小时最小列车发车间隔为120 s.

1)算法运算效率.

图4表示当k取不同值时, 算法1在高峰小时内任意时刻标度下搜索不同数量网络节点时的平均耗时情况.图中网络节点的数量增加是根据北京地铁开通线路的次序增加的.通过趋势分析可得, k值往上增加1个单位, 算法耗时大约多增加15%; 每增加多1条新线(20个普通站节点, 2个换乘站节点), 算法的搜索时间约平均增加8%; 由于借助拓扑子网络进行辅助搜索, 全局的路径搜索在可以接受的时间范围内, 说明算法能适应于大规模网络路径搜索.图5表示在高峰小时任意时间标度一次全OD车站的时变k(k=10)短路径搜索的平均耗时.通过与算法A^[13]和算法B^[16]对比, 本文算法具有较优的运算效率.

	Figure Option View Download New Window
	图4 不同网络规模时的搜索耗时Fig.4 Path-searching time-consuming comparison with different network scales

	Figure Option View Download New Window
	图5 不同算法的耗时对比Fig.5 Path-searching time-consuming comparison between different algorithms

2)算法时变合理性.

结合列车运行图, 假设该天线路在早7:00-9:00发车间隔不变, 选择7:10和7:30这两个时刻分析OD对动物园-和平门的时变k短路径对比, 取k=3, 西直门站4号线换乘2号线的平均时间为208 s, 宣武门4号线换乘2号线的平均时间为353 s, 列车停站时间平均为30 s.如表2所示.通过对比发现同一OD车站在不同时刻的时变路径具有时变差异性, 如表3所示.由于在实际的列车运行中存在列车大小交路套跑、列车首末班车接续、紧急限流和封站等列车运行图调整的情况, 因此有效的时变k短路径搜索获取不同时刻标度下任意OD车站间的路径对实际轨道交通路径管理将具有重要的实际意义.

表2 关联线路车站出发时间和线路列车间隔 Tab.2 Departure time and train interval of related line and station

表3 动物园-和平门之间在7:10和7:30时刻的时变k短路径搜索结果 Tab.3 Searching results of the temporal path at time 7:10 and 7:30 between Dongwuyuan station and Hepingmen station

4 结论

随着城市轨道交通网络规模的不断扩大, 离散化的单线运营向复合化的网络化运营发展是不可逆转的历史进程.通过科学合理的方法获取网络上任意两个车站之间的多样化有效出行路径对运营服务的提高将具有重要的现实意义.本文设计了时变路径的搜索算法, 实现了网络路径搜索和管理优化, 并将方法应用到北京城市轨道交通网络进行实例验证.实例证明, 新的搜索算法在大规模动态网络环境下的适应性较大, 有效降低了算法复杂度并提高了搜索效率, 并且在考虑列车运行时刻表的基础上搜索出有效的时变k短路径, 也即求解了本文提出的时变k短路径搜索问题.今后将结合乘客出行的微观影响因素和自适应特征, 研究考虑不确定因素下的k短路径有效搜索问题.

The authors have declared that no competing interests exist.

参考文献

文献列表

[1]	中国城市轨道交通年度报告课题组. 2015中国城市轨道交通年度报告[M]. 北京: 北京交通大学出版社, 2016: 1-3. China Urban Mass Transit Annual Report Group. 2015 annual report of China urban mass transit[M]. Beijing: Beijing Jiaotong University Press, 2016: 1-3. (in Chinese) [本文引用:1]
[2]	SHEN J M, SHEN Y S, XU L. Research on urban rail transit resource allocation based on K-shortest paths algorithm[J]. Advanced Materials Research, 2013, 748: 1285-1289. [本文引用:1]
[3]	DIJKSTRA E W. A note on two problems in connexion with graphs[J]. Numerische Mathematik, 1959, 1(1): 269-271. [本文引用:1]
[4]	FLOYD R W. Algorithm 97: shortest path[J]. Communications of the ACM, 1962, 5(6): 345. [本文引用:2]
[5]	李树彬, 高自友, 林勇, 等. 大规模交通网络实时路径搜索算法研究[J]. 交通运输系统工程与信息, 2009, 9(5): 141-147. LI Shubin, GAO Ziyou, LIN Yong, et al. Real-time path searching algorithm for large traffic network[J]. Journal of Transportation Systems Engineering & Information Technology, 2009, 9(5): 141-147. (in Chinese) [本文引用:1]
[6]	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. [本文引用:1]
[7]	YEN J Y. Finding the k shortest loopless paths in a network[J]. Management Science, 1971, 17(11): 712-716. [本文引用:1]
[8]	HERSHBERGER J, MAXEL M, SURI S. Finding the k shortest simple paths: a new algorithm and its implementation[J]. ACM Transactions on Algorithms, 2007, 3(4): 45. [本文引用:1]
[9]	牛新奇, 潘荫荣, 胡幼华. K(≤3)条渐次短路径搜索算法的研究[J]. 计算机工程与应用, 2005, 41(22): 51-53. NIU Xinqi, PAN Yinrong, HU Youhua. Research on the algorithm of K-shortest path under single restriction with multiple weights[J]. Computer Engineering & Applications, 2005, 41(22): 51-53. (in Chinese) [本文引用:1]
[10]	徐瑞华, 罗钦, 高鹏. 基于多路径的城市轨道交通网络客流分布模型及算法研究[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. (in Chinese) [本文引用:1]
[11]	四兵锋, 毛保华, 刘智丽. 无缝换乘条件下城市轨道交通网络客流分配模型及算法[J]. 铁道学报, 2008, 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, 2008, 29(6): 12-18. (in Chinese) [本文引用:1]
[12]	WONG S C, TONG C O. Estimation of time-dependent origin-destination matrices for transit networks[J]. Transportation Research Part B: Methodological, 1998, 32(1): 35-48. [本文引用:1]
[13]	XU W, HE S, SONG R, et al. Finding the k shortest paths in a schedule-based transit network[J]. Computers & Operations Research, 2012, 39(8): 1812-1826. [本文引用:2]
[14]	周玮腾, 韩宝明. 考虑列车容量限制的地铁网络客流分配模型[J]. 华南理工大学学报(自然科学版), 2015, 43(8): 126-134. ZHOU Weiteng, HAN Baoming. Passenger flow assignment model of subway networks under train capacity constraint[J]. Journal of South China University of Technology(Natural Science Edition), 2015, 43(8): 126-134. (in Chinese) [本文引用:1]
[15]	FREDMAN M L, TARJAN R E. Fibonacci heaps and their uses in improved network optimization algorithms[J]. Journal of the ACM, 1987, 34(3): 596-615. [本文引用:1]
[16]	FRIEDRICH M, HOFSÄß I, WEKECK S. Timetable-based transit assignment using branch and bound techniques[J]. Transportation Research Record: Journal of the Transportation Research Board, 2001, 1752: 100-107. [本文引用:1]

2016

0.0

... 我国部分大城市已经进入大规模的城市轨道交通网络化运营时期^[1] ...

2013

0.0

... 对于轨道交通运营管理而言,轨道交通网络的客流动态预测和清分结算是以每个OD对间的有效路径为基础计算清分比例^[2] ...

1959

0.0

... 在最初应用于大规模交通网络的最短路径搜索算法中,分别形成了Dijkstra^[3]和Floyd^[4]等常用算法 ...

1962

0.0

... 在最初应用于大规模交通网络的最短路径搜索算法中,分别形成了Dijkstra^[3]和Floyd^[4]等常用算法 ...

... 算法1中,设全网络的节点数量为N,换乘子网络的节点数量为n',获取换乘子网络上任意节点间的时间复杂度为O(n'²)^[4],若采用Fibonacci Heap结构^[15],则复杂度为OM'+n'logn',其中M'为换乘子网络所有边的数量 ...

2009

0.0

李树彬, 高自友, 林勇, 等. 大规模交通网络实时路径搜索算法研究[J]. 交通运输系统工程与信息, 2009, 9(5): 141-147.

Shubin

, GAO

Ziyou

, LIN

Yong

, et al. Real-time path searching algorithm for large traffic network[J]. Journal of Transportation Systems Engineering & Information Technology, 2009, 9(5): 141-147. (in Chinese)

对在研的DynaCHINA软件中大规模交通网络下的实时路径搜索问题进行了研究.提出了新的设计思想,给出了有效路径的产生算法,并设计了支持海量路径数据的存储及高效检索的数据结构.算法充分利用路径的递归特性,降低问题的规模,实现了较小空间花费下的海量路径随机查询.大大提高了大规模交通网络中实时路径搜索问题的计算速度,节省了计算机存储资源.通过与原有算法比较表明,本算法能够在较小的计算机存储资源下,快速有效地处理大规模交通网络中的实时路径搜索问题,具有广阔的应用前景和现实意义.

... s algorithm implemented with double buckets)等改进的D算法^[5] ...

1959

0.0

... k短路径搜索问题和算法最早是由Hoffman等^[6]提出,实际上最短路径问题是k短路径搜索的特殊情况(k=1),而k#cod#x02265 ...

1971

0.0

... 在最短路径搜索算法的基础上,Yen^[7]提出了利用边删除算法获得最小支撑树的子图,通过求解子图最短路径获得图中无环k短路径问题,这也是迄今为止影响最深的k短路径搜索算法 ...

2007

0.0

... 经过多年的发展,在边删除法的基础上,分别形成了更多的优化和改进算法^[8,9] ...

2005

0.0

... 经过多年的发展,在边删除法的基础上,分别形成了更多的优化和改进算法^[8,9] ...

2009

0.0

徐瑞华, 罗钦, 高鹏. 基于多路径的城市轨道交通网络客流分布模型及算法研究[J]. 铁道学报, 2009, 31(2): 110-114.

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. (in Chinese)

城市轨道交通网络形成之后,为实施"一票换乘"需建立轨道交通自动售检票清算管理中心,进行客流信息统计和票务收入清分,而清分的核心在于解决客流在网络上的分布问题.本文结合城市轨道交通系统的基本特性,提出一种考虑乘客多路径出行选择的客流概率分布模型,并设计基于深度优先的路径搜索算法.该模型既体现了乘客出行阻抗最小化的选择心理,又反映了路径多样化的实际情况,具有较强的实用性.最后通过北京轨道交通网络实际客流数据验证模型和算法的有效性.

... 在城市轨道交通网络的路径搜索方面,徐瑞华等^[10]在保证路径完备性的基础上,通过删除法获得轨道交通网络上任意两点不重复的k条路径 ...

2008

0.0

四兵锋, 毛保华, 刘智丽. 无缝换乘条件下城市轨道交通网络客流分配模型及算法[J]. 铁道学报, 2008, 29(6): 12-18.

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, 2008, 29(6): 12-18. (in Chinese)

结合国内城市轨道交通无缝换乘的运营特点,充分考虑了影响城市轨道交通网络客流分配的主要因素(包括出行时间和换乘次数),以及城市轨道交通网络的特有属性,构造城市轨道交通网络的广义费用函数,并分析乘客在城市轨道交通网络中的路径选择行为.在此基础上,基于随机用户平衡原则提出城市轨道交通网络客流分配问题的数学优化模型,在模型的求解中,分析目前常用的有效路径搜索方法并设计了基于图的深度优先搜索算法,以得出符合现实的有效路径集合,并给出求解配流模型的连续平均算法.最后通过北京市轨道交通网络的数据对模型和算法进行验证.

... 四兵锋等^[11]提出了基于深度优先的遍历算法以获取有效路径搜索 ...

1998

0.0

... 在实时客流分配时需设计更为高效的方法以获取轨道交通网络中的动态路径,目前对于轨道交通网络的动态k短路径搜索研究较少,在既有的研究中多以改进的公交网络的动态时变路径搜索算法为主,并将该类路径搜索问题归纳为时间依赖网络(time-dependent network)的路径搜索问题^[12],如Xu等^[13]提出的基于时刻表的公交网络k短路径搜索方法,采用车辆到达时间列表排序进行路径遍历,以保证搜索的网络时空路径的动态有效性 ...

2012

0.0

... 通过与算法A^[13]和算法B^[16]对比,本文算法具有较优的运算效率 ...

2015

0.0

周玮腾, 韩宝明. 考虑列车容量限制的地铁网络客流分配模型[J]. 华南理工大学学报(自然科学版), 2015, 43(8): 126-134.

ZHOU

Weiteng

, HAN

Baoming

. Passenger flow assignment model of subway networks under train capacity constraint[J]. Journal of South China University of Technology(Natural Science Edition), 2015, 43(8): 126-134. (in Chinese)

城市地铁网络客流分配对于城市轨道交通网络化运营管理具有重要意义.既有研究较少地考虑基于时刻表条件下的列车容量限制对于客流分配的影响.文中通过构建时刻表扩展网络,设计时刻表扩展网络下的k短路径搜索算法,考虑列车容量限制下乘客的拥挤因素和留乘延误因素,构建随机用户均衡条件下的客流动态分配模型,并设计了求解算法.通过北京地铁网络客流分配实例进行模型验证,并分析了参数的敏感性.实例证明,模型具有较高的计算精度(相对误差9.5%~11.2%)和收敛速度,能满足地铁大规模网络客流分布的分析和评估需求.

... 2)时刻表扩展网络^[14]建模:在建立物理网络的基础上,为了表征时变路径,可根据列车时刻表列车的到发时间,将拓扑网络的空间线路和节点进行关联和扩展 ...

1987

0.0

2001

0.0

... 通过与算法A^[13]和算法B^[16]对比,本文算法具有较优的运算效率 ...