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

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

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

0 引 言

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

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

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

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

1 有效路徑的定義與假設(shè)

1.1 有效路徑定義

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

1.2 有效路徑基本假設(shè)

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

（1）城市軌道交通中的每個車站節(jié)點(diǎn)、每個區(qū)間路段最多只能經(jīng)過一次。

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

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

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

2 城市軌道交通網(wǎng)絡(luò)編號原則

2.1 線路編號原則

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

（1）地鐵1～4 號線延續(xù)運(yùn)營編號，并且省略7 號線環(huán)線以外的支線部分。

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

圖1 成都市地鐵網(wǎng)絡(luò)簡化圖

2.2 車站及區(qū)間編號原則

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

在對城市軌道交通區(qū)間進(jìn)行標(biāo)號時，為了減少算法中車站和區(qū)間的遞歸求解，縮短求解時間，將城市軌道交通網(wǎng)絡(luò)中區(qū)間按上下行依次編號，如圖2 所示。

圖2 路網(wǎng)的次序化編號

2.3 虛擬換乘區(qū)間編號原則

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

圖3 換乘弧示意圖

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

3 有效徑路集求解算法

3.1 雙向BFS 搜索算法簡介

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

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

3.2 網(wǎng)絡(luò)拓?fù)浣?/h3>

通過上一節(jié)對路網(wǎng)的分層次序化處理，將軌道交通路網(wǎng)轉(zhuǎn)化為用有向連通圖G=＜V , E ,T ＞來描述的軌道交通網(wǎng)絡(luò)模型：

設(shè)有效路徑所包含的有序區(qū)間集為C，其中實際運(yùn)行區(qū)間有序集為X ，換乘區(qū)間有序集為Y 。給定任意起訖點(diǎn)，則起訖點(diǎn)間的有效路徑滿足以下條件：

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

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

3.3 算法步驟

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

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

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

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

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

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

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

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

算法流程圖如圖4 所示。

圖4 雙向BFS 算法流程圖

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

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

4 算例分析

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

圖5 OD 對示意圖

第一步 初始化一系列必要參數(shù)。

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

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

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

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

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

第六步 根據(jù)前文Step 5、Step 6 的方法，刪除路徑中包含重復(fù)區(qū)段的路徑，得到最終有效路徑集。本例共計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換乘表示換乘次數(shù)，用表示換乘時間，其中k 表示r - s間的第k 條路徑，提出如下的路徑廣義費(fèi)用函數(shù)：

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

表2 模型參數(shù)的取值

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

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

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

表4 有效路徑廣義費(fèi)用

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

改變OD 后進(jìn)一步驗算，結(jié)果見表5。

表5 其他OD 的算法結(jié)果

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

5 結(jié)束語

本文設(shè)計的雙向BFS 算法有如下優(yōu)點(diǎn)：

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

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

（3）復(fù)雜度低，運(yùn)算迅速。相比現(xiàn)有其他算法，本文算法對城市軌道交通網(wǎng)絡(luò)的針對性更強(qiáng)，算法前期工作較多，因此輸入數(shù)據(jù)較少。算法結(jié)構(gòu)存在一定的對稱性，執(zhí)行每條指令所需的時間和語句重復(fù)次數(shù)都較少，所以運(yùn)算速度上優(yōu)勢明顯。具體運(yùn)算時間與路網(wǎng)規(guī)模、路網(wǎng)復(fù)雜度、OD 點(diǎn)位置和計算機(jī)性能有關(guān)。