[發明專利]基于特征換乘路徑的地鐵線網尋路方法及地鐵清分系統

有效

• 申請號: 202011117669.0
• 申請日: 2020-10-19
• 公開（公告）號: CN112365028B
• 公開（公告）日: 2022-07-08
• 發明（設計）人: 姜富強;馬天明;徐哲民
• 申請（專利權）人: 浙江眾合科技股份有限公司
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q50/30
• 代理公司: 杭州華鼎知識產權代理事務所(普通合伙) 33217
• 代理人: 秦曉剛

本發明公開了一種基于特征換乘路徑的地鐵線網尋路方法，包括如下步驟：S1：為每個換乘站計算出所有換乘次數為1的特征換乘路徑；S2：依據換乘次數為k’的特征換乘路徑，計算換乘次數為k’+1的特征換乘路徑；S3：把所有特征換乘路徑，從起點開始向外擴展，從終點開始向外擴展，擴展的過程中，不允許任何換乘發生，從而生成線網中所有的換車次數不大于K的有效路徑；S4：向計算結果中補充0次換乘路徑。本發明還提供了一種地鐵清分系統，線路客流分布模塊根據地鐵線網尋路模塊、乘客進出站交易計算模塊的計算結果，計算線網的客流分布。本發明與現有技術相比，降低了時間復雜度。

技術領域

本發明涉及軌道交通技術領域，具體涉及地鐵線網尋路算法。

背景技術

地鐵線網尋路算法是為了找到地鐵線網圖中，任意車站間換乘次數不超過K 的所有乘車路徑。

算法應用的場景：

地鐵清分系統，依據算法的計算結果，和乘客產生的進出站交易，計算線網的客流分布，并在線路運營方之間分配收益。

算法涉及到的符號：

G：根據地鐵線網構造的有向圖，車站是G中的頂點，上行、下行路段是G 中的有向邊。

N：線網圖中所有車站的數量，也就是G中頂點的數量，隨著線網擴展會不斷增大。

V：G中的一個頂點。

V1,V2,…Vn：乘客的一條乘車路徑，依次經過了V1、V2、…Vn等車站。

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

K：乘客一次出行的最大換乘次數，為預定義的固定數值，通常可以取5。

Mse：從Vs到Ve的所有可能乘車路徑的集合。

nX：線網中每條線路的平均換乘站數量，取決于每條線路設計的換乘站數量，隨著線網擴展變化不大，估算時可以取10，通常不超過15。

nV：每條線路的平均車站數量，隨著線網擴展變化不大。

nL：線網中的線路數量，隨著線網擴展會不斷增大。

現有算法：

對G中的每一對頂點組成的二元組(Vs,Ve)，以Vs為出發點，反復調用深度優先遍歷算法，直到找到所有能夠達到Ve的路徑，具體步驟如下：

把Mse設置為空集合。

調用DFS_ACC(Vs)；

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

現有算法的時間復雜度非常高，簡單分析如下：