1.本发明属于城市轨道交通线网客流仿真领域，特别涉及一种城市轨道交通乘客出行链推断方法及系统。
背景技术：
2.城市轨道交通系统在公共交通中扮演着重要角色，高准点率和大容量的特点使其成为城市居民首选的公共交通出行方式，是大城市解决城市拥堵的有效手段。近年来，许多大城市的城市轨道交通系统已经成网运营，乘客在网络中的出行选择更加多元和复杂。城市轨道交通系统afc交易数据只包含了乘客的出行起讫点站点和进出站时间信息，无法捕捉乘客在网络中的具体路径选择行为。为了确定乘客在网络中的出行选择，需要推断乘客在出行过程中所乘坐的列车，从而得到乘客在不同站台的上下车时间，以补全乘客的完整出行链。
3.关于城市轨道交通系统中乘客出行链的推断，国内外现有技术中利用概率模型推断乘客在网络中的路径选择，大多利用对概率分布参数估计的方法确定乘客的出行选择行为，但这些模型都是对乘客的出行特征假设服从某些特定的分布而完成推导；而利用含有位置信息的数据，由于数据样本的限制无法获取全部乘客的出行轨迹。
技术实现要素：
4.本发明所要解决的技术问题是：提出一种城市轨道交通乘客出行链推断方法，更准确推断城市轨道交通乘客的出行轨迹。
5.本发明采用如下技术方案：
6.一种城市轨道交通乘客出行链推断方法，包括步骤：
7.s1、获取并分析处理输入数据，包括：城市轨道交通网络站点和线路基础数据、自动售检票afc系统记录的乘客进出站交易数据以及列车运营时刻表数据，将输入数据经过数据清洗，得到模型要求的数据格式；
8.s2、构建城市轨道网络时空拓扑模型，采用带约束的广度优先算法搜寻路网最短路径集；
9.s3、构建城市轨道交通网络乘客出行链：计算乘客每个出行子链的出行时间区间与对应路段列车运行时间的相似度，检索出乘客出行子链上时间相似度最高的列车作为乘客登上的列车，定义乘客在城市轨道交通网络中出行上下车的时空位置，重构乘客完整的出行链。
10.具体的，步骤s1中，输入数据包括：
11.s1.1、城市轨道交通网络站点数据，包括：站点编号、站点经度、站点纬度和其所属线路四个属性值，表示为：
12.vs＝{[v1，lon1，lat1，l1]，...，[vi，loni，lati，lj]}
[0013]
其中，vi表示站点编号，loni表示站点经度，lati表示站点纬度，i＝1，2，...，n，n为
站点数量，lj表示路网中站点所属线路，j＝1，2，...，m，m为路网中线路总数。
[0014]
构建城市轨道交通网络空间模型如下：
[0015]
n＝{φ(l，v)}
[0016]
其中，n表示路网，l表示线路集合，v表示站点集合；φ表示路网中线路和站点间非线性逻辑关系；
[0017]
s1.2、afc交易数据，具体为：
[0018]
城市轨道交通自动售检票系统记录的交易数据包含乘客的出行起讫点及进出站时间，乘客x的一次完整出行的afc交易数据表示为：
[0019]
trade
x
＝{id
x
，vo，t.a，vd，t.e}
[0020]
式中，id
x
表示自动售检票系统中记录的乘客x的交易号，vo，vd分别表示乘客在城市轨道交通系统中出行的起讫站点，t.a，t.e分别表示乘客通过进站和出站闸机的时间；
[0021]
s1.3、列车时刻表数据，具体为：
[0022]
列车运营时刻表数据包括了线路上运营车次的到站和离站时间信息，表示为：
[0023]
td(l，tr)
[0024]
式中，l为地铁网络中的线路集合，tr为地铁网络中列车集合表示为：
[0025]
tr＝{tr1，tr2，...，trk，...，trk}，k＝1，2，...，k，
[0026]
其中，k为路网中发车总数；
[0027]
在网络中每条线路上会发出不同车次的运营车辆，线路lj上发出的列车集合表示为：
[0028][0029]
其中，p为线路lj上的发车数量。
[0030]
进一步的，步骤s2包括如下子步骤：
[0031]
s2.1、根据城市轨道交通网络特征，构建城市轨道网络空间拓扑模型；
[0032]
s2.2、在路网空间拓扑模型中加载城市轨道交通列车运营时时间信息，构建城市轨道交通网络时空拓扑模型；
[0033]
s2.3、采用带约束的广度优先算法搜寻路网od对间满足最大换乘次数约束的可行路径集，选出od对间最短路径。
[0034]
其中，步骤s2.1，构建城市轨道网络空间拓扑模型，方法为：
[0035]
基于上述路网、站点、线路间的逻辑关系，构建路网空间有向图，表示如下：
[0036]
g(v,a)
[0037]
其中，v为地铁网络中的站点集合，a为地铁网络中的有向连边，即站点间列车轨行区集合；
[0038]
构建g(v,a)的邻接矩阵mc和距离矩阵md，表示为：
[0039][0040]
式中，c
ij
＝1表示站点i,j之间为直接连通，反之则不直接连通，用0表示；
[0041]dij
表示站点i到站点j的有向连边的距离，若两个站点直接连通，相邻站点之间的连边距离为站点间的距离a
ij
，反之则为 ∞；
[0042]
路网中站点和线路间空间逻辑关系和路网有向图，共同构成城市轨道网络空间拓扑模型，表示如下：
[0043]
o＝{φ(l,v),g(v,a)}
[0044]
其中，o表示城市轨道网络空间拓扑模型，路网空间有向图g(v,a)中以v∈v表示图的节点，以a∈a表示图的连边，相邻站点间的上下行方向均设有连边，在换乘站设置有虚拟站台，以描述换乘站内的乘客换乘行为。
[0045]
步骤s2.2，构建城市轨道网络列车运营时间信息模型如下：
[0046][0047]
所述信息模型中包括不同线路上运行列车的到发站时间信息，从列车时刻表中提取路网时间维度信息，列车运营时刻表中列车到站和驶离的信息表示为：
[0048][0049][0050][0051][0052]
式中，分别表示上下行方向的列车到站时间集合，分别表示上下行方向的列车离站时间集合，分别表示线路lj上第i个站点的第k列车辆的上下行列车到站时间，分别表示线路lj上第i个站点的第k列车辆的上下行列车离站时间，m,n,q分别为路网中线路数量，线路中站点数量，线路列车发车数量。
[0053]
步骤s2.3构建城市轨道网络时空拓扑模型，如下：
[0054]
h＝{o＝{φ(l,v),g(v,a)},t(l,v,tr)}
[0055]
式中，h表示路网时空拓扑模型，o＝{φ(l,v),g(v,a)}表示前述步骤s2.1中构建的城市轨道网络空间拓扑模型，t(l,v,tr)表示前述步骤s2.2中构建的城市轨道网络列车运营时间信息模型；
[0056]
步骤s2.4，采用带约束的广度优先算法，搜寻网络中所有od对间最短路，具体为算法a，基于带约束的广度优先网络od对最短路搜寻算法，步骤包括：
[0057]
s2a.1：初始化，加载步骤s2.1中构建的路网有向图g(v,a)，设置路网乘客出行最大换乘次数x，输入路网od对集合rw；
[0058]
s2a.2：循环rw中的od对w
ij
(vi,vj)，并执行步骤s2a.3至s2a.7生成od对可行路径决策树：
[0059]
s2a.3：创建一个空队列q，以od对起点vi作为根节点，将其放入q中，定义数组c表示路径换乘次数，令c＝0；
[0060]
s2a.4：当队列q不为空时循环进行算法步骤s2a.5-s2a.7；
[0061]
s2a.5：取出q中的节点，判断其是否为出行终点vj，若是，执行算法步骤s2a.7；否
s2b.8；
[0078]
s2b.6：筛选乘客出行起点站发车时间和讫点站到站时间满足条件和的列车集合
[0079]
s2b.7：计算中列车运行时间与乘客出行时间的相似度并选择相似度最高的列车作为乘客登上的列车tr
l
(x)，将列车在第i个出行子链的上车站台的离站时间和下车站台的到达时间记录至数组qv；
[0080]
s2b.8：令i＝i 1；
[0081]
s2b.9：将乘客出行链λ
x
＝{t.b,qv,t.e}存储至数组qv；
[0082]
s2b.10：输出数组qv，得到网络中所有乘客的出行链。
[0083]
本发明还提供了一种城市轨道交通乘客出行链推断系统，采用前述的乘客出行链推断方法构建，系统包括路网数据加载模块、路网时空拓扑模型构建及带约束的广度优先路径搜寻算法模块、乘客出行链重构模块；其中，
[0084]
路网数据加载模块，用于加载地铁网络站点和线路基础信息、afc交易数据和列车运营时刻表数据；
[0085]
路网时空拓扑模型构建及带约束的广度优先路径搜寻算法模块，用于构建城市轨道网络时空拓扑模型，实现路径搜寻；
[0086]
乘客出行链重构模块，用于确定乘客在每个出行子链上乘坐的列车，重构乘客在网络中的完整出行链。
[0087]
本发明采用以上技术方案与现有技术相比，具有以下技术效果：
[0088]
1.本发明能够融合afc交易数据和列车运营时刻表数据，推断准确的乘客出行链。
[0089]
2.本发明为城市轨道交通的线网仿真、时刻表优化、客流运营特性分析、列车载客量估计和票务清分提供依据。
附图说明
[0090]
图1为本发明乘客出行链推断方法流程图；
[0091]
图2为本发明城市轨道交通网络有向图。
具体实施方式
[0092]
为了使本发明的目的、技术方案和优点更加清楚，下面结合附图对申请的技术方案做进一步地详尽阐述，所描述的实施例，也只是本发明所涉及实施例的一部分。本领域其他研究人员在该实施例上的所有非创新型实施例，都属于本发明的保护范围。
[0093]
本发明提供了一种城市轨道交通乘客出行链推断方法，如图1所示，包括步骤：
[0094]
s1、获取并分析处理输入数据，包括：城市轨道交通网络站点和线路基础数据、自动售检票afc系统记录的乘客进出站交易数据以及列车运营时刻表数据，将输入数据经过数据清洗，得到模型要求的数据格式；
[0095]
s2、构建城市轨道网络时空拓扑模型，采用带约束的广度优先算法搜寻路网最短路径集；
[0096]
s3、构建城市轨道交通网络乘客出行链：计算乘客每个出行子链的出行时间区间与对应路段列车运行时间的相似度，检索出乘客出行子链上时间相似度最高的列车作为乘客登上的列车，定义乘客在城市轨道交通网络中出行上下车的时空位置，重构乘客完整的出行链。
[0097]
在本发明的一个优选实施例中，具体的，步骤s1中，输入数据包括：
[0098]
s1.1、城市轨道交通网络站点数据，包括：站点编号、站点经度、站点纬度和其所属线路四个属性值，表示为：
[0099]
vs＝{[v1，lon1，lat1，l1]，...，[vi，loni，lati，lj]}
[0100]
其中，vi表示站点编号，loni表示站点经度，lati表示站点纬度，i＝1，2，...，n，n为站点数量，lj表示路网中站点所属线路，j＝1，2，...，m，m为路网中线路总数。
[0101]
城市轨道交通网络空间上分为三个层级，由高至低为“网、线、站”，网络包含不同的运营线路，路网、站点、线路之间的逻辑关系包括：
[0102]
网络层面上，所有线路构成路网，线路集合表示为：
[0103]
l＝{l1，l2，...，lm}
[0104]
其中，lj为路网中某条线路，j＝1，2，...，m，线路lj包含属性值：线路名、线路轨道交通清分系统acc编号；所述车站acc编号对路网中所有站点进行唯一性编码；
[0105]
(2)线路层面上，多个站点构成一条线路，线路lj的站点集合表示为：
[0106][0107]
其中，表示线路lj中的第i个站点，i＝1，2，...，nj，nj为线路lj中的站点数量；
[0108]
车站包含属性值：车站名、所属线路编号、车站acc编号、车站线路内编号、是否为换乘站；
[0109]
所述车站线路内编号，根据线路上下行方向顺序进行编码，站点编码不唯一；换乘站，在不同线路中的编码不同；根据线路和车站的属性，可以实现网络中站点和线路信息的查询功能；
[0110]
(3)路网中包含了所有站点，路网所有站点集合表示为：
[0111][0112]
基于上述路网、站点、线路之间空间逻辑关系，路网中站点和线路空间逻辑关系表示为：
[0113]
φ(l,v)
[0114]
其中，φ表示线路和站点间非线性关系；
[0115]
构建城市轨道交通网络空间模型如下：
[0116]
n＝{φ(l,v)}
[0117]
其中，n表示路网，l为地铁网络中的线路集合，v表示地铁网络中的站点集合；
[0118]
s1.2、afc交易数据，具体为：
[0119]
城市轨道交通自动售检票系统记录的交易数据包含乘客的出行起讫点及进出站
时间，乘客x的一次完整出行的afc交易数据表示为：
[0120]
trade
x
＝{id
x
,vo,t.a,vd,t.e}
[0121]
式中，id
x
表示自动售检票系统中记录的乘客x的交易号，vo,vd分别表示乘客在城市轨道交通系统中出行的起讫站点，t.a,t.e分别表示乘客通过进站和出站闸机的时间；
[0122]
s1.3、列车时刻表数据，具体为：
[0123]
列车运营时刻表数据包括了线路上运营车次的到站和离站时间信息，表示为：
[0124]
td(l,tr)
[0125]
式中，tr为地铁网络中列车集合表示为：
[0126]
tr＝{tr1,tr2,
…
,trk,
…
,trk},k＝1,2,
…
,k，
[0127]
其中，k为路网中发车总数；
[0128]
在网络中每条线路上会发出不同车次的运营车辆，线路lj上发出的列车集合表示为：
[0129][0130]
其中，p为线路lj上的发车数量。
[0131]
在本发明的另一个优选实施例中，步骤s2包括如下子步骤：
[0132]
s2.1、根据城市轨道交通网络特征，构建城市轨道网络空间拓扑模型；
[0133]
s2.2、在路网空间拓扑模型中加载城市轨道交通列车运营时时间信息，构建城市轨道交通网络时空拓扑模型；
[0134]
s2.3、采用带约束的广度优先算法搜寻路网od对间满足最大换乘次数约束的可行路径集，选出od对间最短路径。
[0135]
具体的，步骤s2.1，构建城市轨道网络空间拓扑模型，方法为：
[0136]
基于上述路网、站点、线路间的逻辑关系，构建路网空间有向图，表示如下：
[0137]
g(v,a)
[0138]
其中，a为地铁网络中的有向连边，即站点间列车轨行区集合；
[0139]
构建g(v,a)的邻接矩阵mc和距离矩阵md，表示为：
[0140][0141]
式中，c
ij
＝1表示站点i,j之间为直接连通，反之则不直接连通，用0表示；
[0142]dij
表示站点i到站点j的有向连边的距离，若两个站点直接连通，相邻站点之间的连边距离为站点间的距离a
ij
，反之则为 ∞；
[0143]
路网中站点和线路间空间逻辑关系和路网有向图，共同构成城市轨道网络空间拓扑模型，表示如下：
[0144]
o＝{φ(l,v),g(v,a)}
[0145]
其中，o表示城市轨道网络空间拓扑模型，路网空间有向图g(v,a)中以v∈v表示图的节点，以a∈a表示图的连边，相邻站点间的上下行方向均设有连边，在换乘站设置有虚拟站台，以描述换乘站内的乘客换乘行为。
[0146]
具体地，如图2所示，线路a和线路b在换乘站v
t
连接，则有向图中将换乘站v
t
描述为在线路a和线路b内设有站台和并与虚拟站台v
t
双向连接，乘客在两条线路之间的换
乘步行时间为乘客从前序服务列车下车站台至虚拟站台v
t
的步行时间加上从虚拟站台v
t
至后续服务列车上车站台的步行时间。
[0147]
同样的，线路a、线路b和线路c在换乘站v
t
连接，则有向图中将换乘站v
t
描述为在线路a、线路b和线路c内设有站台和和并与虚拟站台v
t
连接，乘客在三条线路之间的换乘步行时间为乘客从前序服务列车下车站台至虚拟站台v
t
的步行时间加上从虚拟站台v
t
至后续服务列车上车站台的步行时间。
[0148]
然后，步骤s2.2，构建城市轨道网络列车运营时间信息模型如下：
[0149]
t(l,v,tr)
[0150]
所述信息模型中包括不同线路上运行列车的到发站时间信息，从列车时刻表中提取路网时间维度信息，列车运营时刻表中列车到站和驶离的信息表示为：
[0151][0152][0153][0154][0155]
式中，分别表示上下行方向的列车到站时间集合，分别表示上下行方向的列车离站时间集合，分别表示线路lj上第i个站点的第k列车辆的上下行列车到站时间，分别表示线路lj上第i个站点的第k列车辆的上下行列车离站时间，m,n,q分别为路网中线路数量，线路中站点数量，线路列车发车数量。
[0156]
接着，步骤s2.3构建城市轨道网络时空拓扑模型，如下：
[0157]
h＝{o＝{φ(l,v),g(v,a)},t(l,v,tr)}
[0158]
式中，h表示路网时空拓扑模型，o＝{φ(l,v),g(v,a)}表示前述步骤s2.1中构建的城市轨道网络空间拓扑模型，t(l,v,tr)表示前述步骤s2.2中构建的城市轨道网络列车运营时间信息模型；
[0159]
t(l,v,tr)包含了列车在线路上运行的到站时间和离站时间，具体表示为：
[0160][0161]
s.t.lj∈l
[0162][0163][0164][0165][0166]
式中，约束条件等价于前述步骤s2中路网、站点、线路之间空间逻辑关系和线路上
运行列车与列车集合的所属关系。
[0167]
最后，步骤s2.4，采用带约束的广度优先算法，搜寻网络中所有od对间最短路，具体为算法a，基于带约束的广度优先网络od对最短路搜寻算法，步骤包括：
[0168]
s2a.1：初始化，加载步骤s2.1中构建的路网有向图g(v,a)，设置路网乘客出行最大换乘次数x，输入路网od对集合rw；
[0169]
s2a.2：循环rw中的od对w
ij
(vi,vj)，并执行步骤s2a.3至s2a.7生成od对可行路径决策树：
[0170]
s2a.3：创建一个空队列q，以od对起点vi作为根节点，将其放入q中，定义数组c表示路径换乘次数，令c＝0；
[0171]
s2a.4：当队列q不为空时循环进行算法步骤s2a.5-s2a.7；
[0172]
s2a.5：取出q中的节点，判断其是否为出行终点vj，若是，执行算法步骤s2a.7；否则，执行算法步骤s2a.6；
[0173]
s2a.6：以q中取出的节点为父节点v
p
，搜寻父节点在g(v,a)连通的站点作为其直接子节点，为第s个父节点的第n个子节点，并放入队列q中，其中ns为子节点序号；判断子节点是否为换乘站，若是，则该节点换乘次数加一，否则，不做操作；将父节点站点到子节点站点的距离换乘次数子节点站点编号一并记录于对应子节点中；
[0174]
s2a.7：结束搜寻，判断可行路径决策树叶子节点换乘次数cr,r＝1,2,
…
,x为叶子节点个数，x是否小于等于最大换乘次数，若是则保留该分支，否则进行剪枝操作；
[0175]
s2a.8：读取步骤s2a.2中生成的可行路径决策树，每个叶节点分支对应一条可行路径，计算每条可行路径费用，选择路径费用最少的路径作为od对w
ij
间的最短路存入od对最短路径集pw中，算法结束。
[0176]
在本发明的另一个优选实施例中，步骤s3中，重构乘客出行链，主要包括：输入乘客afc交易数据，根据afc交易数据中记录的出行od对将乘客匹配到城市轨道交通网络时空拓扑模型中的od最短路上；再根据乘客出行链的定义，以时间相似度为指标，计算乘客出行子链上满足约束的所有列车的运行时间相似度，检索出相似度最高的列车作为乘客在出行子链上乘坐的列车；最后从列车运营时刻表中读取乘客在出行子链中上下车站台的上下车时间，从而重构出乘客的完整出行链。具体为：
[0177]
首先，定义乘客出行链，如下式：
[0178][0179]
其中，λ
x
表示乘客出行链，x表示进入城市轨道交通系统的某位乘客，t.a表示乘客通过进站闸机的交易时间，t.e表示乘客通过出站闸机的交易时间；xv(tr)表示乘客x在站点v登上列车tr的时间，tr(xv)表示乘客x乘坐列车tr在站点v的下车时间；
[0180]
式中，乘客出行链包含一个或多个出行子链，构成乘客在城市轨道交通系统内乘坐一次列车的出行子链，无换乘的乘客出行链包含一个出行子链，换乘乘客的出行链则包含多个出行子链；
[0181]
然后，定义路径确定的乘客出行子链时间区间与对应路段上列车运行时间的时间
相似度，公式为：
[0182][0183]
式中，表示在路径p上乘客x出行时间区间与列车tr运行时间区间的相似度，为路径p乘客出行时间区间与列车运行时间区间的交集的时间长度，表示路径p乘客x的出行时间区间长度，表示路径p列车tr运行时间区间长度，γ为正常数。
[0184]
接着，计算搜索乘客每个出行子链时间区间与列车运行时间的相似度，输出结果用于确定乘客出行链中的上下车时空位置，构建乘客出行链重构算法，具体为算法b，基于时间相似度最优的列车无遗检索乘客出行链重构算法，步骤如下：
[0185]
s2b.1：初始化：加载步骤s1中的afc交易数据；加载步骤s2.1中构建的路网有向图g(v,a)，输入路网od对集合rw；
[0186]
s2b.2：定义一个空数组qv＝[]，对每一条afc交易数据执行算法步骤s2b.3-s2b.9；
[0187]
s2b.3：读取乘客进出站时间t.b、t.e和站点vo、vd，读取该od对最短路径rw；
[0188]
s2b.4：判断该最短路径的换乘站数量n(v
t
)，并执行以下操作：
[0189]
s2b.5：令0≤i≤n(v
t
)，i＝0，列车记录数组qv＝[]，并循环执行算法步骤s2b.6-s2b.8；
[0190]
s2b.6：筛选乘客出行起点站发车时间和讫点站到站时间满足条件和的列车集合
[0191]
s2b.7：计算中列车运行时间与乘客出行时间的相似度并选择相似度最高的列车作为乘客登上的列车tr
l
(x)，将列车在第i个出行子链的上车站台的离站时间和下车站台的到达时间记录至数组qv；
[0192]
s2b.8：令i＝i 1；
[0193]
s2b.9：将乘客出行链λ
x
＝{t.b,qv,t.e}存储至数组qv；
[0194]
s2b.10：输出数组qv，得到网络中所有乘客的出行链。
[0195]
作为本发明的一个优选实施例，本发明还提供了一种城市轨道交通乘客出行链推断系统，采用前述的乘客出行链推断方法构建，系统包括路网数据加载模块、路网时空拓扑模型构建及带约束的广度优先路径搜寻算法模块、乘客出行链重构模块；其中，
[0196]
路网数据加载模块，用于加载地铁网络站点和线路基础信息、afc交易数据和列车运营时刻表数据；
[0197]
路网时空拓扑模型构建及带约束的广度优先路径搜寻算法模块，用于构建城市轨道网络时空拓扑模型，实现路径搜寻；
[0198]
乘客出行链重构模块，用于确定乘客在每个出行子链上乘坐的列车，重构乘客在网络中的完整出行链。
[0199]
以上所述仅为本发明的具体实施方式，并不用于限制本发明，凡在本发明的精神和原则之内，所做的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。