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

（1.天津軌道交通運(yùn)營集團(tuán)有限公司，天津 300392；2.北京城建設(shè)計(jì)發(fā)展集團(tuán)股份有限公司，北京 100045；3.東南大學(xué)智能運(yùn)輸系統(tǒng)研究中心軌道交通研究所，南京 210018）

1 概述

城市軌道交通具有運(yùn)量大、速度快、時(shí)間準(zhǔn)、污染少和安全舒適等特點(diǎn)，在緩解大城市交通擁堵方面具有獨(dú)特優(yōu)越性，已成為城市公共交通系統(tǒng)中的重要組成部分。截至2019 年底，中國大陸地區(qū)共40 個(gè)城市開通城市軌道交通服務(wù)，19 個(gè)城市進(jìn)入網(wǎng)絡(luò)化運(yùn)營階段。在網(wǎng)絡(luò)化運(yùn)營階段，客流量急劇增大且乘客出行路徑選擇增多，需要運(yùn)營管理者從宏觀角度把握客流特征，安排運(yùn)營組織。構(gòu)建合理的軌道交通路網(wǎng)模型，能夠?yàn)檫\(yùn)營組織者提供決策依據(jù)，而路網(wǎng)模型的關(guān)鍵在于路徑選擇算法。

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

2 路徑搜索算法

2.1 路網(wǎng)模型

本文所建立的軌道交通路網(wǎng)拓?fù)浣Y(jié)構(gòu)可表示為G=｛L(s)｝，G表示所構(gòu)建的軌道交通路網(wǎng)，L表示軌道交通路網(wǎng)中的線路。其中：

L=｛l1,l2,…,lm｝，m為路網(wǎng)中所包含的線路數(shù)量；

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

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

軌道交通網(wǎng)絡(luò)由不同的線路組成，各線路間通過換乘車站銜接。本文提出的搜索算法以換乘站為核心節(jié)點(diǎn)進(jìn)行搜索，故需在構(gòu)建路網(wǎng)模型時(shí)，依據(jù)車站與線路的邏輯關(guān)系，實(shí)現(xiàn)如下兩個(gè)基本方法。

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

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

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

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

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

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

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

2.3 算法流程

步驟1:從自動售檢票系統(tǒng)（AFC）記錄的交易數(shù)據(jù)中提取乘客出行的起訖點(diǎn)。

步驟2:構(gòu)建3 個(gè)換乘站列表，換乘站列表1、換乘站列表2、換乘站列表3，分別對應(yīng)如圖1 所示的3 個(gè)換乘節(jié)點(diǎn)。列表為一維列表，用于存放車站(sin)信息，在記錄路徑時(shí)分別稱從換乘站列表1、換乘站列表2、換乘站列表3 中提取出的站點(diǎn)為換乘站1、換乘站2、換乘站3。

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

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

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

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

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

注1：在步驟4、步驟5 向換乘站列表中添加站點(diǎn)時(shí)，如果該站點(diǎn)已經(jīng)存在于列表中，則不再繼續(xù)添加。若找到的換乘車站為起點(diǎn)站，同樣無需將起點(diǎn)站加入換乘站列表中。

注2：在搜索步驟4、步驟5 中，之所以會往換乘站列表1、換乘站列表2 中回添站點(diǎn)，是為了避免同一線路上出現(xiàn)多個(gè)換乘站，導(dǎo)致經(jīng)過3個(gè)換乘站后無法由起點(diǎn)到達(dá)終點(diǎn)，即路徑中的換乘站指乘客實(shí)際發(fā)生換乘的車站，而非簡單的物理換乘站。

2.4 有效路徑篩選

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

1）找出搜索結(jié)果中經(jīng)過換乘站數(shù)目最少的路徑，刪除比最少換乘路徑多兩個(gè)及以上換乘站的路徑。

2）找出搜索結(jié)果中經(jīng)過車站數(shù)目最少的路徑，刪除路徑中經(jīng)過車站數(shù)比最少經(jīng)過車站數(shù)多n個(gè)以上車站的路徑(n可根據(jù)實(shí)際調(diào)查設(shè)定)。

3）如果經(jīng)1）、2）兩條原則篩選過后，剩余路徑的條數(shù)仍多于3 條，則優(yōu)先考慮換乘站數(shù)較少的路徑，換乘站數(shù)相同的情況下，保留經(jīng)過站點(diǎn)數(shù)較少或舒適度較高的路徑。

3 應(yīng)用實(shí)例

3.1 路網(wǎng)結(jié)構(gòu)設(shè)計(jì)

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

3.2 結(jié)果與討論

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

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

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

評價(jià)路徑搜索算法優(yōu)劣主要從準(zhǔn)確性與搜索效率兩個(gè)角度進(jìn)行考慮，本文使用天津地鐵線網(wǎng)客流數(shù)據(jù)，按上述介紹的算法，尋找全線網(wǎng)20 306 個(gè)OD 對之間的有效路徑。從準(zhǔn)確性角度講，本文的搜索不會漏掉任何換乘次數(shù)≤3 的路徑，對有效路徑的篩選也滿足人們?nèi)粘３鲂械男袨榱?xí)慣，算法的準(zhǔn)確性可以得到保障。從效率角度講，本文提出的搜索算法完成全部OD 對的搜索共耗時(shí)127 s，找到有效路徑210 001 條。相比于基于線路組合的路徑搜索算法[10]，本文的方法在搜索時(shí)間上有明顯優(yōu)勢。兩種算法的搜索效率對比如表2 所示，可以看到，在路網(wǎng)復(fù)雜度明顯增大的情況下，本文所實(shí)現(xiàn)的方法在搜索時(shí)間上仍有明顯優(yōu)勢。

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

4 結(jié)語

本文基于軌道交通線網(wǎng)拓?fù)涮攸c(diǎn)，利用深度優(yōu)先的搜索思想，提出了一種高效的路徑搜索算法，相比于傳統(tǒng)深度優(yōu)先算法，該算法在搜索之前，首先進(jìn)行路徑簡化，減少了搜索節(jié)點(diǎn)，同時(shí)在搜索過程中，限制了搜索深度，避免無效搜索，大幅提高了搜索效率。此外，本文提出的基于3 層換乘的搜索算法具有良好的可移植性，對城市軌道交通路網(wǎng)模型的建立具有一定的參考價(jià)值。