城市軌道交通路網建模中路徑搜索算法的實現

肖 晨，何躍齊，趙嘉偉，張 寧

（1.天津軌道交通運營集團有限公司，天津 300392；2.北京城建設計發展集團股份有限公司，北京 100045；3.東南大學智能運輸系統研究中心軌道交通研究所，南京 210018）

1 概述

城市軌道交通具有運量大、速度快、時間準、污染少和安全舒適等特點，在緩解大城市交通擁堵方面具有獨特優越性，已成為城市公共交通系統中的重要組成部分。截至2019 年底，中國大陸地區共40 個城市開通城市軌道交通服務，19 個城市進入網絡化運營階段。在網絡化運營階段，客流量急劇增大且乘客出行路徑選擇增多，需要運營管理者從宏觀角度把握客流特征，安排運營組織。構建合理的軌道交通路網模型，能夠為運營組織者提供決策依據，而路網模型的關鍵在于路徑選擇算法。

以圖的方式描述路網已成為交通研究中廣泛使用的方法，如何從路網中提取有效路徑一直以來都受到廣泛關注，相關學者先后提出了Dijkstra 算法[1]、FLOYD 算法[2]、A*算法[3]等一系列最短路徑求解方法。然而在網絡化運營的軌道交通路網中，起訖點（OD 對）之間可能會存在多條有效路徑，如果僅按最短路徑進行客流量的分配，會與實際情況有較大出入，故需要求解OD 對間的K 短路徑。K短路徑搜索問題最早由Hoffman 等[4]提出，并得到不斷完善。在軌道交通方面，在找到K 短路徑之后，一般情況下，需進一步尋找有效路徑進行客流量的分配[5-6]。徐瑞華等[7]通過刪除法獲得軌道交通網絡上任意兩點不重復的K 條路徑，四兵鋒等[8]先利用深度優先的搜索算法，搜索出OD 對之間一條有效路徑，接著利用回溯的方法再次進行深度優先遍歷，直至找出所有有效路徑。這兩種方法雖然能夠保證搜索路徑的完整性，但是復雜程度明顯增大，而且在搜索過程中并未對路徑進行簡化處理，在構建軌道交通路網模型進行客流實時仿真時，可能存在搜索效率不高的問題。周瑋騰等[9]對路徑做了簡化，構建了只包含換乘車站的拓撲網絡，利用深度優先的搜索策略搜索出所有有效路徑，最后通過對比還原的方法找出完整網絡下OD 對之間的有效路徑，但是該方法增加了匹配的難度并且沒有對搜索深度進行限制，同樣會產生一定的無效搜索。本文在簡化搜索路徑的基礎上，利用深度優先的搜索思想并結合軌道交通路網的拓撲特征，提出一種更加高效的有效路徑搜索算法。

2 路徑搜索算法

2.1 路網模型

本文所建立的軌道交通路網拓撲結構可表示為G=｛L(s)｝，G表示所構建的軌道交通路網，L表示軌道交通路網中的線路。其中：

L=｛l1,l2,…,lm｝，m為路網中所包含的線路數量；

li=｛si1,si2,…,sin｝，n為線路i上的車站數，sin表示線路li上的第n個車站。

車站sin又包含車站名、所屬線路編號、車站編號和是否為換乘站點4 個屬性。其中，車站所屬線路編號為該車站所在所有線路的集合；車站編號由車站在線路上的相對位置確定，按從下行到上行依次遞增。換乘站在不同的線路中分別設置不同的編號以示區分。

軌道交通網絡由不同的線路組成，各線路間通過換乘車站銜接。本文提出的搜索算法以換乘站為核心節點進行搜索，故需在構建路網模型時，依據車站與線路的邏輯關系，實現如下兩個基本方法。

1）尋找與非換乘站最近的換乘站

對于一個非換乘車站，找出其所在的線路上的所有換乘車站，并選擇與其間隔車站數最少的換乘站作為其最近換乘站。若同時存在兩個或兩個以上最近換乘站，則隨機選擇一個作為其最近換乘站。

2）尋找與換乘站相鄰的換乘站

換乘車站是多條線路的交匯點，為保證路徑搜索的完整性，需要找出與之相鄰的所有換乘車站。對于一個換乘站點，遍歷其所在的線路，找出每條線路上與之相鄰的換乘車站，形成換乘車站集合，作為與該換乘站相鄰的換乘車站。

2.2 限制搜索深度的搜索算法

對于國內大多數軌道交通路網而言，從任意一點出發，最多經過3 次換乘，可以到達路網中任意一個節點。故本文將一個行程分為5 個部分，如圖1所示。對于不同的OD 對，換乘站的數目可能有所差別，需要根據實際情況進行調整。在路徑搜索的過程中，只考慮由起終點及換乘站組成的簡化路網，從給定的起點站開始，通過逐層搜索中間換乘站點的方式，找到與終點站屬于同一線路的換乘站以完成路徑搜索。同時，為了提高搜索效率，算法限制了搜索深度，搜索到第3 層換乘車站后，如果其不與終點站在同一線路，則放棄該條路徑的搜索，這樣選擇性的放棄了一些明顯不合理的路徑，節約了搜索時間但不會遺漏合理路徑。

圖1 出行行程劃分Fig.1 Typical travel partition

2.3 算法流程

步驟1:從自動售檢票系統（AFC）記錄的交易數據中提取乘客出行的起訖點。

步驟2:構建3 個換乘站列表，換乘站列表1、換乘站列表2、換乘站列表3，分別對應如圖1 所示的3 個換乘節點。列表為一維列表，用于存放車站(sin)信息，在記錄路徑時分別稱從換乘站列表1、換乘站列表2、換乘站列表3 中提取出的站點為換乘站1、換乘站2、換乘站3。

步驟3:判斷起終點是否在同一條線路上，如果是，則記錄路徑[起點站，終點站]，如果不是，則找出與起點站相鄰的換乘車站（如果起點站為非換乘車站，找到與之最近的換乘車站，如果起點站為換乘車站，找到與之相鄰的所有換乘車站），添加到換乘站列表1 中。

步驟4:遍歷換乘站列表1 中的車站，判斷其是否與終點站在同一線路上。如果是，則記錄路徑[起點站，換乘站1，終點站]，繼續遍歷，直至換乘站列表1 中的車站全部被遍歷，執行步驟7；如果不是，則中斷遍歷，找出與之相鄰的換乘站，添加到換乘站列表2 中，執行步驟5。

步驟5:遍歷換乘站列表2 中的站點，判斷其是否與起點站位于同一條線路上。如果是，則將其添加到換乘站列表1 中；如果不是，判斷其是否與終點站在同一條線路上，如果是，則記錄路徑[起點站，換乘站1，換乘站2，終點站]，繼續遍歷換乘站列表2 中的站點，直至換乘站列表2 中的站點均被遍歷，清空換乘站列表2、換乘站列表3，返回步驟4 繼續遍歷下一個車站，如果不是，則中斷遍歷，繼續尋找與之相鄰的換乘站并添加到換乘站列表3 中，執行步驟6。

步驟6:遍歷換乘站列表3 中的站點，如果其與換乘站1 在同一條線路上，則將此站點添入換乘站列表2，如果其與起點站在同一線路上，則將該站點添入換乘站列表1；否則，判斷該站點是否與終點站在同一線路上，如果是，則記錄路徑[起點站，換乘站1，換乘站2，換乘站3，終點站]，繼續遍歷換乘站3 中的站點，直至列表3 中的換乘站點均被遍歷，清空換乘站列表3，返回步驟5 繼續遍歷下一個車站。

步驟7:輸出所有記錄的路徑。

注1：在步驟4、步驟5 向換乘站列表中添加站點時，如果該站點已經存在于列表中，則不再繼續添加。若找到的換乘車站為起點站，同樣無需將起點站加入換乘站列表中。

注2：在搜索步驟4、步驟5 中，之所以會往換乘站列表1、換乘站列表2 中回添站點，是為了避免同一線路上出現多個換乘站，導致經過3個換乘站后無法由起點到達終點，即路徑中的換乘站指乘客實際發生換乘的車站，而非簡單的物理換乘站。

2.4 有效路徑篩選

經過上述方法搜索后，某一OD 對之間可能會搜索到多條可達路徑，但在實際環境中，乘客在進行路徑選擇時，不會考慮所有的可達路徑，而會從有效路徑中進行選擇。通常情況下，采用3 條以內漸短路徑作為有效路徑。故找到可達路徑后，還需從中篩選出有效路徑，本文考慮設置如下3 條篩選原則。

1）找出搜索結果中經過換乘站數目最少的路徑，刪除比最少換乘路徑多兩個及以上換乘站的路徑。

2）找出搜索結果中經過車站數目最少的路徑，刪除路徑中經過車站數比最少經過車站數多n個以上車站的路徑(n可根據實際調查設定)。

3）如果經1）、2）兩條原則篩選過后，剩余路徑的條數仍多于3 條，則優先考慮換乘站數較少的路徑，換乘站數相同的情況下，保留經過站點數較少或舒適度較高的路徑。

3 應用實例

3.1 路網結構設計

以天津地鐵為例，首先構建軌道交通路網模型。目前天津地鐵包含6 條運營線路，143 個車站及15個換乘車站，在軌道交通路網模型中為每個站點設置包括所屬線路、站點編號、是否為換乘站點等3個屬性。其中，站點編號由站點在線路上的相對位置確定，從下行到上行依次遞增，換乘站在不同的線路中分別設置不同的編號以示區分。

3.2 結果與討論

以咸陽路站為起始站，以營口道站為終點站，采用本文的搜索方法，共搜索到8 條路徑，如表1所示。

表1 咸陽路站至營口道站路徑搜索結果Tab.1 Search results of the paths between Xianyang Road Station and Yingkou Road Station

可以看到，此11 條路徑均可由咸陽路車站到達營口道車站，但各條路徑所經過的站點數及換乘車站的數目不同。根據上述有效路徑篩選原則進行篩選，7、9、10、11 號路徑為從咸陽路站到營口道站的有效路徑，經驗證，乘客在出行路徑選擇時很少會考慮其他路徑出行。

評價路徑搜索算法優劣主要從準確性與搜索效率兩個角度進行考慮，本文使用天津地鐵線網客流數據，按上述介紹的算法，尋找全線網20 306 個OD 對之間的有效路徑。從準確性角度講，本文的搜索不會漏掉任何換乘次數≤3 的路徑，對有效路徑的篩選也滿足人們日常出行的行為習慣，算法的準確性可以得到保障。從效率角度講，本文提出的搜索算法完成全部OD 對的搜索共耗時127 s，找到有效路徑210 001 條。相比于基于線路組合的路徑搜索算法[10]，本文的方法在搜索時間上有明顯優勢。兩種算法的搜索效率對比如表2 所示，可以看到，在路網復雜度明顯增大的情況下，本文所實現的方法在搜索時間上仍有明顯優勢。

表2 兩種搜索算法效率對比Tab.2 Efficiency comparison of two search algorithms

4 結語

本文基于軌道交通線網拓撲特點，利用深度優先的搜索思想，提出了一種高效的路徑搜索算法，相比于傳統深度優先算法，該算法在搜索之前，首先進行路徑簡化，減少了搜索節點，同時在搜索過程中，限制了搜索深度，避免無效搜索，大幅提高了搜索效率。此外，本文提出的基于3 層換乘的搜索算法具有良好的可移植性，對城市軌道交通路網模型的建立具有一定的參考價值。