基于雙向BFS 算法的城市軌道交通有效路徑研究

曾 誠，吳佳媛，羅無瑕，羅 霞

（1. 西南交通大學，交通運輸與物流學院，成都 611756；2. 綜合交通運輸智能化國家地方聯合工程實驗室，成都 611756；3. 西南交通大學，公共管理與政法學院，成都 610031）

0 引 言

隨著我國城市化與現代化進程的推進，城市規模不斷擴大，軌道交通逐漸成為城市的大動脈。城市軌道交通具有大運能、高效率、安全可靠的特點，其中地鐵的效用尤為顯著。《“十三五”規劃》指出，超大城市和特大城市應積極建設城市軌道網絡，“十三五”期間共新增城市軌道交通運營里程3 000 km 以上。截至2019 年底，我國仍處于城市軌道交通建設發展的熱潮，以成都市地鐵運營現狀為例，共計有7 條線路，207 座車站，運營里程位居全國第八，單日最高客流533 萬人次，2020 年12 月18 日更是一次性開通5 條線路。

面對如此龐大的客流和日趨復雜的地鐵網絡，客流預測和客流清分等工作顯得尤為重要。其中，有效路徑的確定是上述實際工作的理論基礎。如何計算出完備、無冗余的有效路徑集是研究乘客出行選擇行為[1-4]、客流預測[5]和客流清分[6]工作的第一步。

目前，用于城市軌道交通有效路徑求解的算法主要包括Dial 算法、K 短路算法、深度優先算法、廣度優先算法、基于定向樹遍歷搜索算法，以及各種啟發式算法和改進算法等。其中，Dial首先提出了不考慮擁擠程度情況的有效路徑求解算法，能有效解決交通網絡隨機分配問題，適用于大規模交通網絡。但由于算法對有效路徑的定義過于嚴格，導致關鍵路徑識別階段出現異常，且當網絡中存在環形通路時，該算法也會遺漏部分路徑[7,8]。四兵鋒、張好智等針對上述問題對Dial 算法進行了改進，將路段費用信息作為判定有效路徑的必要條件，提出了基于網絡拓撲結構排序的模型算，并進一步驗證了該算法的有效性，能夠同時避免Dial 算法的有效路徑遺漏問題和非有效路徑的錯誤判別問題，但算法復雜度較高[9]。隨后K 短路徑搜索算法進入人們的視野，它由Hoffman 等在1959 年提出，能夠有效搜索出最短、次短、第K 短路徑[10]。其后一些學者提出了采用刪邊法的K 短路徑搜索算法來求解有效路徑，比傳統的全路徑法有了很大的提高，但是這種限定有效路徑數目的方法并不能真正滿足出行者路徑選擇范圍的要求[11]。如牛新奇等提出的基于Dijkstra 算法的K 短路搜索僅適用于小規模網絡，限定有效路徑數目后會遺漏部分路徑[12]。葉晉、趙烈秋應用遺傳算法求解軌道交通換乘路徑，提出一種求解軌道交通K 條最佳換乘路徑的遺傳算法[13,14]。隨著計算機計算能力的提高，全路徑搜索算法得以應用。如毛保華運用深度優先遍歷搜索算法求解有效路徑，在該算法基礎上提出了基于回溯遍歷的搜索算法，即沿著圖的一個分支搜索直到該分支終點，然后進行回溯遍歷，在搜索過程中同時判斷有效路徑是否滿足相對閥值和絕對閥值的定義[15]。劉劍鋒等提出了一種基于分支定界思想的深度優先有效路徑搜索算法，當路徑費用大于出行路徑廣義費用最大閾值時，停止該條路徑搜索[16]。郭彥云利用廣度優先算法求解有效路徑，針對枚舉算法效率低的問題，采用了增加有效路徑限制條件和定義關鍵節點的方法[17]。

綜上所述，可將目前各類求解有效路徑的算法中存在的缺點總結為四類：算法復雜、有效路徑結果缺失、有效路徑結果冗余或有效路徑結果不合理。針對這種情況，本文充分利用城市軌道交通乘客的出行特征和網絡特點，提出了一種基于廣度優先算法的雙向BFS（Breadth-First Search）算法來求解有效路徑，并利用算例驗證其有效性。

1 有效路徑的定義與假設

1.1 有效路徑定義

本文對有效路徑的定義如下：在特定OD 對之間存在若干條可供乘客選擇的路徑，這些會被出行者考慮的路徑我們稱為有效路徑，非有效路徑的廣義出行費用更大，且都不可能被乘客選擇。由兩點之間的有效路徑組成的集合稱之為有效路徑集。

1.2 有效路徑基本假設

考慮乘客的出行習慣和后文算法的需求，對滿足有效路徑的路線作如下假設：

（1）城市軌道交通中的每個車站節點、每個區間路段最多只能經過一次。

（2）乘客所能接受的換乘次數是有限的，一般不超過3 次。

（3）乘客在旅行過程中經過換乘站進入一條線路，就不會再次換入該線路。

（4）在同一線路上的OD 對，乘客只在該條線路上進行旅行。

2 城市軌道交通網絡編號原則

2.1 線路編號原則

本文以成都軌道交通為研究對象，主要包含線路有地鐵1 號線、2 號線、3 號線、4 號線和7號線。根據研究需要確定編號原則如下：

（1）地鐵1～4 號線延續運營編號，并且省略7 號線環線以外的支線部分。

（2）由于7 號線為環線，所以當起點和終點都在環線上時，最優路徑可能需要換乘，這與有效路徑假設（4）矛盾。因此本文將7 號線重新劃分為7A、7B、7C、7D 四條線路，劃分站點分別為一品天下、駟馬橋、成都東客站和太平園（分別對應圖中節點1、3、5、7）。具體編號如圖1所示。

圖1 成都市地鐵網絡簡化圖

2.2 車站及區間編號原則

在對城市軌道交通車站進行標號時，采用基于相鄰換乘站或終點站的標號方法進行次序化處理[18]。如圖1 所示，編號1～14 為換乘站，編號15～22 為終點站，建模時用表示，k 為編號，l 為所屬線路。設其他普通車站用符號表示，i、j 表示相鄰的換乘站或終點站，k 為沿下行方向的車站編號，例如“西南交大站”可表示為。

在對城市軌道交通區間進行標號時，為了減少算法中車站和區間的遞歸求解，縮短求解時間，將城市軌道交通網絡中區間按上下行依次編號，如圖2 所示。

圖2 路網的次序化編號

2.3 虛擬換乘區間編號原則

根據本文的線路編號原則，將7 號線環線劃分為7A、7B、7C、7D 四條線路，因此當有效路徑中包含上述站點并且換出線路與換入線路同為7M（M=A、B、C、D）號線時，實際上并沒有換乘成本，需引入虛擬換乘弧的概念[18]，如圖3 所示。

圖3 換乘弧示意圖

由上圖可以看出，一個兩線換乘站存在8 個換乘方向，可用換乘弧表示，“0”表示上行方向，“1”表示下行方向，則換乘弧（1，0）表示從一條線的下行方向換乘到另一條線的上行方向。當換乘站弧銜接的兩條線實際是一條時，例如7A和7B 號線，則該換乘弧為虛擬換乘弧，虛擬換乘弧廣義費用為0。

3 有效徑路集求解算法

3.1 雙向BFS 搜索算法簡介

本文基于城市軌道交通的換乘特性，借用廣度優先算法理念，設計了同時以O 點和D 點作為起始點的雙向BFS 算法。

本文設計的雙向BFS 搜索算法主要基于兩個“乘客容忍度原則”（由調研獲得）：一是乘客選擇出行路徑時換乘次數不超過3 次（否則選擇其他交通方式）；二是從時間成本或廣義成本上講，所有有效路徑的成本不超過最短路的（σ +1）倍。不同城市σ 的不同，如北京為0.15[19]，成都為0.25（由筆者通過問卷調查獲得）。

3.2 網絡拓撲建模

通過上一節對路網的分層次序化處理，將軌道交通路網轉化為用有向連通圖G=＜V , E ,T ＞來描述的軌道交通網絡模型：

設有效路徑所包含的有序區間集為C，其中實際運行區間有序集為X ，換乘區間有序集為Y 。給定任意起訖點，則起訖點間的有效路徑滿足以下條件：

式中：j 為區間在集合C 中次序；i 為x 在集合X中的次序；n 為y 在集合Y 中的次序；1k 、 k2分別表示區間起、終點車站的編號；1l 、 l2分別表示換乘區間銜接的起、終點車站所屬的線路。

式（6）保證有效徑路在同一線路上的連續性；同理式（7）、（8）保證有效徑路在換乘過程中實際區間與換乘區間的連續性；式（9）使有效徑路滿足基本假設（3）；式（10）限制換乘次數滿足基本假設（2）。

3.3 算法步驟

由于乘客出行路徑的選擇行為可以描述為換乘站的不同選擇，所以本文的雙向BFS 算法以僅保留換乘站和終點站的簡化路網為基礎，從起點和終點同時利用檢索相鄰站的方法獲得OD 之間的有效路徑。雙向BFS 搜索算法的具體步驟如下：

Step 1 初始化有效路徑集W 、換乘站和終點站集合V 、鄰接矩陣A、起始站點Ov 和目的站點 vD、相鄰換乘站v1k與vk2之間的站點集合Vk1k2、線路-車站矩陣L、換乘矩陣H。

Step 2 檢索站點 vO所在線路LO，檢索站點vD所在線路LD，判斷起訖點是否在同一條線路上，若是，則轉入Step 5；若否，則繼續。判斷 vO、vD中是否存在換乘站或終點站，若是，則相鄰站則為該站本身；若不是，則通過檢索集合Vk1k2分別確定起訖點相鄰的換乘站(p =1,2)、(q =1,2)。1 表示沿上行方向的換乘站，2 表示沿下行方向的換乘站。

Step 3 交叉判斷起點的相鄰換乘站與終點的相鄰換乘站是否在同一條線路上。共需判斷p × q組。若在，則找到一條有效路徑O→→→D，并將其存入有效路徑集W 。直到判斷完所有相鄰站組合，進入下一步。

Step 5 檢索O、D 點的同線路非相鄰換乘站（廣義相鄰站）。在O 點所在線路上按上行方向從開始檢索換乘站，結果生成上行廣義相鄰站集合（集合包含）；同理生成下行廣義相鄰站集合（集合包含）。 D 點同理可生成上、下行廣義相鄰換乘站集合、。

Step 6 初始化m= 1，c 為W 中有效路徑條數。從有效路徑集W 中的第一條路徑開始，判斷是否同時存在集合、中的元素，或同時存在集合、中的元素，若有則說明存在重復路段，刪除該路徑。令m = m+ 1，當m ＞ c時，轉入Step 7；否則，重復上述步驟。

Step 7 計算廣義費用，令虛擬換乘弧廣義費用為0，確定有效路徑中最小出行成本wmin。通過比較其他路徑與(σ +1)wmin的大小，剔除出行成本超過容忍度的路徑。

Step 8 刪除空白行，輸出算法最終有效路徑集合W ，算法結束。

算法流程圖如圖4 所示。

圖4 雙向BFS 算法流程圖

Step 3 中由于算法規定了最大換乘次數為3次，所以當起訖點的相鄰換乘站之間不在同一條線路時，想要搜索到有效路徑必須找到一個換乘站 Ttran。該站既和O 點相鄰站之一在同一條線路上，又和D 站相鄰站之一在同一條線路上。

Step 6 中通過廣義相鄰換乘站刪除包含重復路段的路徑，該方法可以有效降低算法復雜度，避免了檢索路徑所有途經站點和區間的工作。

4 算例分析

本文以成都城市軌道交通網絡為例，選取7號線茶店子站作為O 點，3 號線磨子橋站作為D點，如圖5 所示。線路編號、換乘站編號按照前文所述進行編排，下面根據本文提出的“雙向搜索算法”給出有效路徑集的搜索過程。

圖5 OD 對示意圖

第一步 初始化一系列必要參數。

第二步 分別確定O、D 點的相鄰換乘站或終點站。根據線路和站點的從屬關系，即車站—線路矩陣L，確定起點O 的相鄰換乘站為1 和2，終點D 的相鄰換乘站為13 和14。

第三步 分別確定各個相鄰換乘站所在的線路。如換乘站1 從屬于2 號線、7A 號線、7D號線。

第四步 交叉判斷各相鄰換乘站是否在同一條線路上。發現站點1 和14、站點2 和13 均不在同一條線路上，因此需要進一步搜索換乘站。站點1 和13 在都位于2 號線上，因此可以確定一條有效路徑O→1→13→D；站點2 和14在都位于1 號線上，因此可以確定另一條有效路徑O→2→14→D。

第五步 搜索包含3 次換乘的有效路徑，搜索過程如表1 所示。

表1 包含三個換乘站的有效路徑搜索

第六步 根據前文Step 5、Step 6 的方法，刪除路徑中包含重復區段的路徑，得到最終有效路徑集。本例共計6 條：

O→1→13→D

O→2→14→D

O→1→11→14→D

O→1→7→14→D

O→2→11→13→D

O→2→3→13→D

由于上述算法搜索得到的有效路徑仍比較多，存在一些因出行成本相差較大，實際上不會被乘客選擇的路徑（城市軌道交通旅客考慮的路徑往往只有1～3 條），因此本文用表示旅行時間，用nk換乘表示換乘次數，用表示換乘時間，其中k 表示r - s間的第k 條路徑，提出如下的路徑廣義費用函數：

式中： α·( nk)β·為換乘費用，α 、β 為待定的參數。另外，基于有效路徑成本不超過最短路（σ +1）倍的假設，定義σ 為容忍系數，本文根據一定量的出行路徑選擇調查，對模型中的參數進行標定，取值見表2。

表2 模型參數的取值

根據前文篩選出的6 條有效路徑計算每條路徑的旅行時間、換乘時間和換乘次數，具體結果如表3 所示。

表3 六條路徑的旅行時間、換乘時間和換乘次數

其中路徑4 和6 由于包含虛擬換乘弧，因此實際換乘次數比經過的換乘站要少。接著，將上述指標帶入概率模型中，分別得到廣義費用值見表4。

表4 有效路徑廣義費用

第七步 根據路徑的容忍系數σ 剔除路徑。經計算，廣義費用最小的路徑為有效路徑6，其費用的1.25 倍為2 000.6，因此路徑4 也可作為有效路徑。最終確定茶店子站和磨子橋站之間的有效路徑共兩條，分別為O→1→7→14→D 和O→2→3→13→D。兩條路徑都只需要換乘一次，側面反映出城市軌道交通旅客對換乘的敏感性。

改變OD 后進一步驗算，結果見表5。

表5 其他OD 的算法結果

綜上所述，本文的有效路徑搜索算法很大程度上證明是完備和高效的。

5 結束語

本文設計的雙向BFS 算法有如下優點：

（1）結合實際，結果完備。充分利用了城市軌道交通網絡和出行者選擇行為的特點，設定了換乘次數和廣義費用的容忍閾值。路徑搜索結果不存在冗余或不合理的有效路徑，也不存在缺失的有效路徑。

（2）邏輯清晰，設計巧妙。通過重新劃分線路和定義虛擬換乘弧的概念，消除環線對求解的影響；從邏輯上巧妙地解決了雙向搜索中路徑交匯點的確定問題；并定義廣義相鄰換乘站快速刪除包含重復路徑的路徑，避免了檢索站點和區間的復雜計算。

（3）復雜度低，運算迅速。相比現有其他算法，本文算法對城市軌道交通網絡的針對性更強，算法前期工作較多，因此輸入數據較少。算法結構存在一定的對稱性，執行每條指令所需的時間和語句重復次數都較少，所以運算速度上優勢明顯。具體運算時間與路網規模、路網復雜度、OD 點位置和計算機性能有關。