基于特征换乘路径的地铁线网寻路方法及地铁清分系统

摘要

本发明公开了一种基于特征换乘路径的地铁线网寻路方法，包括如下步骤：S1：为每个换乘站计算出所有换乘次数为1的特征换乘路径；S2：依据换乘次数为k’的特征换乘路径，计算换乘次数为k’+1的特征换乘路径；S3：把所有特征换乘路径，从起点开始向外扩展，从终点开始向外扩展，扩展的过程中，不允许任何换乘发生，从而生成线网中所有的换车次数不大于K的有效路径；S4：向计算结果中补充0次换乘路径。本发明还提供了一种地铁清分系统，线路客流分布模块根据地铁线网寻路模块、乘客进出站交易计算模块的计算结果，计算线网的客流分布。本发明与现有技术相比，降低了时间复杂度。

说明书

技术领域

本发明涉及轨道交通技术领域，具体涉及地铁线网寻路算法。

背景技术

地铁线网寻路算法是为了找到地铁线网图中，任意车站间换乘次数不超过K 的所有乘车路径。

算法应用的场景：

地铁清分系统，依据算法的计算结果，和乘客产生的进出站交易，计算线网的客流分布，并在线路运营方之间分配收益。

算法涉及到的符号：

G：根据地铁线网构造的有向图，车站是G中的顶点，上行、下行路段是G 中的有向边。

N：线网图中所有车站的数量，也就是G中顶点的数量，随着线网扩展会不断增大。

V：G中的一个顶点。

：乘客的一条乘车路径，依次经过了V1、V2、…Vn等车站。

{V1,V2,…Vn}：一组车站形成的集合。

K：乘客一次出行的最大换乘次数，为预定义的固定数值，通常可以取5。

Mse：从Vs到Ve的所有可能乘车路径的集合。

nX：线网中每条线路的平均换乘站数量，取决于每条线路设计的换乘站数量，随着线网扩展变化不大，估算时可以取10，通常不超过15。

nV：每条线路的平均车站数量，随着线网扩展变化不大。

nL：线网中的线路数量，随着线网扩展会不断增大。

现有算法：

对G中的每一对顶点组成的二元组(Vs,Ve)，以Vs为出发点，反复调用深度优先遍历算法，直到找到所有能够达到Ve的路径，具体步骤如下：

把Mse设置为空集合。

调用DFS_ACC()；

DFS_ACC定义如下：

FUNCTION DFS_ACC(Path0)

BEGIN

如果Path0中的换乘次数超过K，直接返回。

记录Vc为Path0中的最后一个顶点。

记录Vc的所有邻接车站组成的集合为{Vs1,Vs2,…Vsn}

FOR Vsi in{Vs1,Vs2,…Vsn}：

如果Vsi没有在Path0出现过

用Path0中的所有的车站，再加上Vsi，组成新路径，记为Path1。

如果Vsi＝＝Ve，则把Path1加入到Mse中。

否则，则递归调用DFS_ACC(Path1)

END

现有算法的时间复杂度非常高，简单分析如下：

首先,要对每对车站调用一次DFS_ACC方法，总共调用N*(N-1)次。

然后，DFS_ACC执行时，如果Vc是双线换乘站，一般会产生3次DFS_ACC 调用。如果Vc是非换乘站，会产生一次DFS_ACC调用。因此，最大产生 (3nX*nL+(nV-nX)*nL)次DFS_ACC次调用。虽然在遍历过程中，会根据Path0、K 进行过滤，但这不影响计算的复杂度。

因此，现有算法的时间复杂度为N*(N-1)*(3nX*nL+(nV-nX)*nL)。

发明内容

本发明所要解决的技术问题就是提供一种基于特征换乘路径的地铁线网寻路算法，降低时间复杂度。

为解决上述技术问题，本发明采用如下技术方案：基于特征换乘路径的地铁线网寻路算法，对于路径P＝，假设其经历了k次换乘，第一次换乘的车站为Vx1,最后一次换乘的车站为Vxk,Vx1之前的车站为Va，Vxk之后的车站为Vb，则把路径叫做P的特征换乘路径，如果Vx1或者Vxk为终点站，则Va或者Vb也不出现在特征换乘路径中，基于特征换乘路径的地铁线网寻路算法包括如下步骤：

S1：为每个换乘站计算出所有换乘次数为1的特征换乘路径；

S2：依据换乘次数为k’的特征换乘路径，计算换乘次数为k’+1的特征换乘路径；

S3：把所有特征换乘路径，从起点开始向外扩展，从终点开始向外扩展，扩展的过程中，不允许任何换乘发生，从而生成线网中所有的换车次数不大于K 的有效路径；

S4：向计算结果中补充0次换乘路径。

优选的，所述步骤S2的实现方法为：从k’的特征换乘路径最后一个站出发，向前搜索到下一次换乘，一直找到所有换乘次数为K的特征换乘路径。

优选的，所述步骤S4的实现方法为：对所有车站二元组(Vs,Ve)，其中Vs 和Ve都属于线路L，L上Vs和Ve之间按顺序经过的所有的车站，就构成了Vs 到Ve的一条0次换乘路径。

本发明还提供了一种地铁清分系统，包括基于特征换乘路径的地铁线网寻路模块、乘客进出站交易计算模块以及线路客流分布模块，所述基于特征换乘路径的地铁线网寻路模块采用基于特征换乘路径的地铁线网寻路算法进行计算，所述线路客流分布模块根据地铁线网寻路模块、乘客进出站交易计算模块的计算结果，计算线网的客流分布。

本发明还提供了一种电子设备，包括存储器、处理器以及存储在所述存储器中并可在所述处理器上运行的计算机程序，所述处理器执行所述计算机程序时实现基于特征换乘路径的地铁线网寻路算法。

本发明还提供了一种介质，所述介质存储有计算机程序，所述计算机程序被处理器执行时能够实现基于特征换乘路径的地铁线网寻路算法。

本发明对特征换乘路径做出定义，并基于特征换乘路径运行地铁线网寻路算法，可以快速找到地铁线网图中，任意车站间换乘次数不超过K的所有乘车路径，与现有技术相比，降低了时间复杂度。

本发明的具体技术方案及其有益效果将会在下面的具体实施方式中进行详细的说明。

附图说明

下面结合附图和具体实施方式对本发明作进一步描述：

图1是地铁线路图例。

具体实施方式

下面对本发明实施例的技术方案进行解释和说明，但下述实施例仅为本发明的优选实施例，并非全部。基于实施方式中的实施例，本领域技术人员在没有做出创造性劳动的前提下所获得其他实施例，都属于本发明的保护范围。

实施例一

基于特征换乘路径的地铁线网寻路算法：

特征换乘路径：对于路径P＝，假设其经历了k次换乘，第一次换乘的车站为Vx1,最后一次换乘的车站为Vxk,Vx1之前的车站为Va，Vxk之后的车站为Vb，则把路径叫做P的特征换乘路径。如果Vx1或者Vxk为终点站，则Va或者Vb也不出现在特征换乘路径中。

具体算法：

第一步：为每个换乘站计算出所有换乘次数为1的特征换乘路径。比如图1 中，换乘站Vx1的换乘次数为1的特征换乘路径为以下八条：，

,,,,

,,。

第二步：依据换乘次数为k’的特征换乘路径，计算换乘次数为k’+1的特征换乘路径。方法为从k’的特征换乘路径最后一个站出发，向前搜索到下一次换乘。迭代方式为，首先取k’＝1，依据换乘次数为1的特征换乘路径，计算出换乘次数为2的特征换乘路径；然后取k’＝2，依据换乘次数为2的特征换乘路径，计算出换乘次数为3的特征换乘路径；一直迭代，直到计算出换乘次数为K的特征换乘路径。

第三步：把所有特征换乘路径，从起点开始向外扩展，从终点开始向外扩展，扩展的过程中，不允许任何换乘发生，从而生成线网中所有的换车次数不大于K的有效路径。

第四步，向计算结果中补充0次换乘路径。方法为：对所有车站二元组 (Vs,Ve)，其中Vs和Ve都属于线路L，L上Vs和Ve之间按顺序经过的所有的车站，就构成了Vs到Ve的一条0次换乘路径。

本算法的优点是时间复杂度低。假设线网中均为二次换乘，做以下估算：

第一步和第二步的复杂度分析如下：

换乘次数为1的特征换乘路径数量为nL*8*nX

换乘次数为2的特征换乘路径数量最大为nL*8*nX*(nX-1)*2

换乘次数为3的特征换乘路径数量最大为nL*8*nX*(nX-1)*2*(nX-1)*2

根据等比数列求和公式，换乘次数不超过K次的特征换乘路径数量最大为 nL*8*nX*(1-qK)/(1-q)，其中q＝(nX-1)*2。其中，nX、K是固定值，因此以上求和可简记为d*nL，其中d＝8*nX*(1-qK)/(1-q)，为固定值。

第三步的复杂度分析如下：

第三步进行了d*nL次循环，每次循环最多进行(nV)2次计算，因此总共最多进行d*nL*(nV)2次计算。每次计算为简单扩展，占用常量时间。

第四步的复杂度分析如下：

第四步是对所有的线路循环，找到每条线路中的车站对，执行nL*nV*(nV-1) 次计算。

因此，该算法的最大计算次数为d*nL+d*nL*(nV)2+nL*nV*(nV-1),算法复杂度为C*nL*(nV)2，C为常量。该多项式复杂度明显优于原技术方案的指数复杂度。

实施例二

地铁清分系统，包括基于特征换乘路径的地铁线网寻路模块、乘客进出站交易计算模块以及线路客流分布模块，所述基于特征换乘路径的地铁线网寻路模块采用基于特征换乘路径的地铁线网寻路算法进行计算，所述线路客流分布模块根据地铁线网寻路模块、乘客进出站交易计算模块的计算结果，计算线网的客流分布。

其中，上述计算线网的客流分布的计算方法可以参考现有技术，这里不再赘述。

实施例三

一种电子设备，包括存储器、处理器以及存储在所述存储器中并可在所述处理器上运行的计算机程序，所述处理器执行所述计算机程序时实现如实施例一所述的基于特征换乘路径的地铁线网寻路算法。

本发明实施例中的电子设备可以包括但不限于诸如移动电话、笔记本电脑、 PDA(个人数字助理)、PAD(平板电脑)等的移动终端以及诸如台式计算机等的固定终端。

电子设备可以包括处理装置(例如中央处理器)，其可以根据存储在只读存储器(ROM)中的程序或者从存储装置加载到随机访问存储器(RAM)中的程序而执行各种适当的动作和处理。在RAM中，还存储有电子设备操作所需的各种程序和数据。处理装置、ROM以及RAM通过总线彼此相连。输入/输出(I/O)接口也连接至总线。

承载在计算机可读介质上的计算机程序，包含用于执行算法的程序代码。在这样的实施例中，该计算机程序可以通过通信装置从网络上被下载和安装，或者从存储装置被安装，或者从ROM被安装。在该计算机程序被处理装置执行时，执行本公开实施例的方法中限定的上述功能。

需要说明的是，本公开上述的计算机可读介质可以是计算机可读信号介质或者计算机可读介质或者是上述两者的任意组合。

上述计算机可读介质可以是上述电子设备中所包含的；也可以是单独存在，而未装配入该电子设备中。

以上所述，仅为本发明的具体实施方式，但本发明的保护范围并不局限于此，熟悉该本领域的技术人员应该明白本发明包括但不限于上面具体实施方式中描述的内容。任何不偏离本发明的功能和结构原理的修改都将包括在权利要求书的范围中。