蔡昌俊 葉 茂 馬靈玲 何建濤 殷世松

(1.廣州地鐵集團(tuán)有限公司，510330，廣州；2.南京理工大學(xué)交通工程系，210094，南京；3.交通信息融合與系統(tǒng)控制工業(yè)和信息化部重點(diǎn)實(shí)驗(yàn)室，210094，南京∥第一作者，正高級工程師)

隨著城市軌道交通線網(wǎng)越來越發(fā)達(dá)，乘客的出行路徑更加多樣化。有效路徑的確定是軌道交通客流合理分配的基礎(chǔ)和斷面客流估算的前提，是軌道交通票務(wù)清分重要的一部分[1-2]。同一OD(起訖點(diǎn))對之間通常有很多條不同路徑，乘客最初的出行都是基于最短路徑的。隨著城市軌道交通線網(wǎng)的擴(kuò)大，存在多條費(fèi)用差別不大的路徑可供乘客選擇。乘客出行的路徑選擇行為受到多種因素的影響，包括乘客類別[3]、列車擁擠度[4]和旅行時(shí)間等。因此，在某一OD對之間，存在一條或幾條路徑費(fèi)用相近的可選路徑，乘客若總是選擇這一條或幾條路徑出行，這樣的路徑稱為有效路徑。

目前，國內(nèi)外關(guān)于網(wǎng)絡(luò)路徑搜索算法的研究已經(jīng)較為成熟，其中，最短路徑法已經(jīng)形成了非常經(jīng)典的算法并被廣泛采用[5-6]。與最短路徑法相關(guān)的還有K最短路算法。文獻(xiàn)[7]建立了突發(fā)事件下的網(wǎng)絡(luò)受影響客流重分布預(yù)測算法，基于突發(fā)事件下乘客出行行為特征變化的分析,提出一種受影響客流的界定算法。文獻(xiàn)[8]在K最短路算法的基礎(chǔ)上，提出基于軌道網(wǎng)絡(luò)特點(diǎn)的K最短路算法，將軌道站點(diǎn)之間K最短路徑搜索轉(zhuǎn)化為不同出行點(diǎn)對之間的換乘線路組合搜索，極大地縮小了搜索空間，同時(shí)將該算法與基于最短路徑點(diǎn)分支變化的向外搜索算法進(jìn)行路徑搜索對比，證明該算法的高效性。除了基于遺傳算法、蟻群算法、深度優(yōu)先算法、廣度優(yōu)先算法和Dail算法等的路徑生成算法，還有學(xué)者從另一種角度設(shè)計(jì)了有效路徑生成算法。文獻(xiàn)[9]基于軌道交通旅客出行所能承受的換乘次數(shù)是有上限的這一事實(shí)，設(shè)計(jì)出基于換乘次數(shù)的有效路徑集生成算法，并用算例將該算法與全路徑搜索算法對比，證明了該算法的高效性。

以往的研究往往追求OD對間有效路徑的搜索效率，并沒有考慮到路徑集生成后后續(xù)使用的便利性，如缺乏對換乘關(guān)系的描述，客流預(yù)測就無法從路徑集中直接生成換乘站在各個(gè)方向的換乘量。本文在不涉及軌道交通共線、共軌、并線運(yùn)行的條件下，提出乘客出行有效路徑應(yīng)滿足的基本假設(shè)。對路網(wǎng)中的線路和站點(diǎn)進(jìn)行編號，將線路分割成連續(xù)的單位區(qū)間；基于路徑選擇影響因素分析，在最短路徑法基礎(chǔ)上改進(jìn)并構(gòu)建有效路徑搜索模型；以2015年廣州地鐵網(wǎng)絡(luò)為例進(jìn)行應(yīng)用分析，證明了所提有效路徑搜索方法的有效性，為城市后續(xù)的軌道交通線網(wǎng)客流分配、斷面客流估算及清分提供了較好的路徑結(jié)構(gòu)基礎(chǔ)和方法支撐。

1 路徑選擇影響因素分析

在網(wǎng)絡(luò)化條件下，某一OD對之間通常有多條路徑，一般而言乘客總是選擇出行費(fèi)用較小的路徑。而影響出行費(fèi)用的因素不止一個(gè)，本文將這些影響因素歸為客觀因素與主觀因素兩種情況。

1.1 客觀因素

客觀因素主要為軌道交通線網(wǎng)結(jié)構(gòu)與乘客出行的起始站和終點(diǎn)站位置，此類因素不受乘客自身感受的影響，主要分為無換乘出行和有換乘出行兩種情況。無換乘出行情況是指城市中只存在一條軌道交通線路或乘客在一條沒有換乘站的線路上出行時(shí)，只存在一條有效路徑。有換乘出行情況是指當(dāng)乘客出行的起始站和終點(diǎn)站不在同一條線上時(shí)，乘客出行時(shí)必須通過換乘才能到達(dá)，此時(shí)可能有多條路徑可供選擇。

單方式和多方式路徑換乘示意圖如圖1所示。單方式換乘是指乘客出行的起始站和終點(diǎn)站之間只有一種換乘方式。例如，乘客想從站點(diǎn)A到站點(diǎn)C，只能在站點(diǎn)B進(jìn)行換乘，此時(shí)有效路徑只有一條。多方式換乘是指當(dāng)網(wǎng)絡(luò)中存在多個(gè)換乘站，乘客可按自己需求選擇合適的換乘站路徑到達(dá)目的地。如乘客由站點(diǎn)A上車至目的地站點(diǎn)D，可以通過站點(diǎn)B或站點(diǎn)C進(jìn)行換乘。

圖1 路徑換乘示意圖Fig.1 Diagram of path interchange

1.2 主觀因素

主觀因素為出行過程中使乘客具有自我感受、自我判斷和自我選擇的因素。當(dāng)多數(shù)起、終點(diǎn)站之間有多條可達(dá)路徑，在主觀因素的影響下，大多數(shù)乘客只會(huì)把其中幾條作為有效路徑，主觀因素有以下幾種：

1) 候車時(shí)間：乘客采用軌道交通出行時(shí)，購票、安檢和等車過程中有出行時(shí)耗。

2) 乘車時(shí)間：主要包括列車在各區(qū)段的運(yùn)行時(shí)間和在各站點(diǎn)的停站時(shí)間。

3) 換乘時(shí)間：在軌道交通網(wǎng)絡(luò)中，當(dāng)某一OD對之間不能直達(dá)時(shí)，需通過換乘站進(jìn)行換乘，且不同換乘站的換乘過程所消耗的換乘時(shí)間也不相同。

4) 換乘次數(shù)：當(dāng)乘客對軌道交通網(wǎng)絡(luò)不熟悉或是兩種路徑所花費(fèi)的旅行時(shí)間相差不大時(shí)，通常乘客更偏向于選擇換乘次數(shù)少的路徑。

2 有效路徑建模前提

2.1 有效路徑的假設(shè)前提

基于地鐵線網(wǎng)的實(shí)際情況和乘客的出行習(xí)慣，將有效路徑搜索模型的假設(shè)定義如下：

假設(shè)1：若起始站和終點(diǎn)站屬于同一條線路，則僅存在一條有效路徑，即乘客只在該條線路上出行；

假設(shè)2：線網(wǎng)中不存在較大的弧線，即在假設(shè)1成立的條件下，乘客在一條線路上出行時(shí)不存在繞行情況；

假設(shè)3：線網(wǎng)中不存在環(huán)線情況；

假設(shè)4：在假設(shè)1成立的條件下，當(dāng)起始站和終點(diǎn)站同為換乘站，且為同兩條線路的換乘站時(shí)，需特殊考慮，即可能存在兩條有效路徑。

2.2 軌道交通線網(wǎng)的抽象表示

1) 站點(diǎn)編號原則。對線網(wǎng)中的每一個(gè)車站進(jìn)行編號。編號的基本原則為：每個(gè)站的編號共4位，前2位為該站所在的線路編號，后2位為該站在所在線路中的排序。廣州地鐵5號線部分車站編號情況如圖2所示。

圖2 廣州地鐵站點(diǎn)的編號情況示意圖Fig.2 Diagram of the numbering of Guangzhou metro stations

一般車站只位于一條線路上，映射在圖中的結(jié)點(diǎn)是唯一的，所以一般站只需要一個(gè)車站編號便可唯一確定。而線網(wǎng)中的換乘站至少在兩條線路上，只用一個(gè)車站編號不能完全記錄換乘車站的全部信息，則其編號原則為：將換乘站的編號個(gè)數(shù)定為所在線路個(gè)數(shù)，在不同線路上采用不同編號，每個(gè)編號仍根據(jù)一般站的編號。如廣州地鐵線網(wǎng)中的坦尾站、廣州火車站站、區(qū)莊站這3個(gè)換乘站的編號(見圖2)，在這種情況下，便可看成線網(wǎng)中各條線之間只能通過換乘站相互銜接，減少了線路間的相互干擾。

2) 線網(wǎng)單位區(qū)間定義原則。本文提出單位區(qū)間的概念，即線網(wǎng)中的各條線路可以分割成相鄰站點(diǎn)的最小區(qū)間，或乘客發(fā)生換乘行為的換乘站內(nèi)的換乘虛擬區(qū)間，如圖3所示。其中：不同線條表示不同線路，實(shí)線段表示相鄰車站間的單位區(qū)間；虛線段表示乘客在換乘站發(fā)生換乘行為的換乘虛擬區(qū)間。

圖3 線網(wǎng)單位區(qū)間示意圖Fig.3 Diagram of line network unit interval

3 有效路徑建模

3.1 構(gòu)建線網(wǎng)拓?fù)鋱D

構(gòu)建全網(wǎng)拓?fù)鋱D，用線段表示線路，用節(jié)點(diǎn)表示車站。在城市軌道交通中，各線路是雙向開行的，因此拓?fù)鋱D中的線段都表示雙向線段。換乘站的節(jié)點(diǎn)數(shù)等于該換乘站所在的線路個(gè)數(shù)。對拓?fù)鋱D中的所有節(jié)點(diǎn)進(jìn)行排序，使得不同節(jié)點(diǎn)之間可以用序號進(jìn)行區(qū)分，這樣簡化了城市軌道交通網(wǎng)絡(luò)的表達(dá)形式，以便于編程的實(shí)現(xiàn)。

用G={V,E,T}來描述軌道交通網(wǎng)絡(luò)模型，G為軌道交通網(wǎng)絡(luò)模型，V為車站集合，E為站間單位區(qū)間集合，T為換乘虛擬區(qū)間集合，則有：

vi∈V，ei,j∈E， (ti,j，tmi′,nj′)∈T

(1)

式中：

vi——拓?fù)鋱D中序號為i的車站；

ei,j——拓?fù)鋱D中序號為i的車站到序號為j的車站單位區(qū)間；

ti,j——拓?fù)鋱D中序號為i的車站到序號為j的車站虛擬區(qū)間；

tmi′,nj′——乘客從線路m的車站i′換乘到線路n的車站j′的虛擬區(qū)間。

ei,j、ti,j的出行費(fèi)用單位區(qū)間個(gè)數(shù)(xei,j、xti,j)以及單位區(qū)間運(yùn)行時(shí)間(yei,j、yti,j)可以表示為：

(2)

式中：

α、β——取值為0或1的系數(shù)，當(dāng)α=1時(shí)，β=0；當(dāng)β=1時(shí)，α=0。

3.2 基于改進(jìn)最短路徑法的有效路徑生成

基于對路徑選擇影響因素的分析，構(gòu)造兩個(gè)關(guān)于全網(wǎng)出行費(fèi)用的鄰接矩陣，運(yùn)用最短路徑法搜索每個(gè)鄰接矩陣下的最短路徑，并以此為基準(zhǔn)設(shè)置乘客忍受閾值，構(gòu)建有效路徑搜索模型。

1) 對網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)構(gòu)造關(guān)于線網(wǎng)出行費(fèi)用的鄰接矩陣，則有：

(3)

矩陣A用來記錄拓?fù)鋱D中連接相鄰節(jié)點(diǎn)的所有有向線段在實(shí)際線網(wǎng)中的費(fèi)用值。矩陣A中的行(列)號對應(yīng)各車站在拓?fù)鋱D中的節(jié)點(diǎn)序號，其取值方式可以表示為：

(4)

根據(jù)ei,j和ti,j的取值情況，將所構(gòu)造的兩個(gè)全網(wǎng)鄰接矩陣，運(yùn)用改進(jìn)的最短路徑法分別在每一個(gè)鄰接矩陣中搜索某OD對間的有效路徑，在這兩種情況下搜索得出的路徑均為該OD對的有效路徑。

2) 構(gòu)建最短路徑搜索模型，其最短路徑的計(jì)算方法可以表示為：

(5)

式中：

s——站點(diǎn)總數(shù)；

COD i,j——一個(gè)OD對間所有可達(dá)路徑出行費(fèi)用的集合。

3) 改進(jìn)最短路徑搜索模型，構(gòu)建有效路徑搜索模型。最短路徑法只能搜索出某OD對間的最短路徑，對其進(jìn)行改進(jìn)后，能成功搜索出某OD對間的幾條有效路徑，并在此基礎(chǔ)上生成全網(wǎng)的有效路徑集。改進(jìn)的過程可以表示為：

(6)

式中：

COD有效——一個(gè)OD對間所有有效可達(dá)路徑出行費(fèi)用的集合；

COD——一個(gè)OD對間所有路徑出行費(fèi)用的集合。

4 實(shí)例分析

以2015年廣州地鐵線網(wǎng)為例，基于AFC(自動(dòng)售檢票系統(tǒng))數(shù)據(jù)用所提方法搜索全網(wǎng)OD的有效路徑集。2015年廣州地鐵線網(wǎng)的拓?fù)浣Y(jié)構(gòu)，如圖4所示。其中：每條線段表示雙向開行的情況；為了簡化拓?fù)鋱D，只將線網(wǎng)中的換乘站節(jié)點(diǎn)顯示出來，用虛線圈表示，同一虛線圈內(nèi)的小圈表示同一換乘站在不同線路上的節(jié)點(diǎn)。拓?fù)鋱D中各線路對應(yīng)的編號如表1所示。8號線上各車站在線網(wǎng)中的編號和拓?fù)鋱D中的序號如表2所示。其余線路的站點(diǎn)編號與序號與之同理。

圖4 2015年廣州地鐵線網(wǎng)拓?fù)鋱DFig.4 Topology of Guangzhou metro line network in 2015

表1 2015年廣州地鐵線路編號Tab.1 Guangzhou metro line numbers in 2015

表2 8號線站點(diǎn)名稱及編號Tab.2 Station names and numbers of Line 8

根據(jù)2015年廣州地鐵線網(wǎng)的運(yùn)營情況，確定網(wǎng)絡(luò)中ei,j和ti,j的取值情況，分別取α=1、β=0和β=1、α=0，構(gòu)造兩個(gè)關(guān)于線網(wǎng)單位區(qū)間出行費(fèi)用的鄰接矩陣；用改進(jìn)的最短路徑法，生成全網(wǎng)OD的有效路徑集。2015年廣州地鐵線網(wǎng)OD對擁有不同有效路徑條數(shù)的比例情況如表3所示。用所提方法搜索得到的(西塱站→體育西路站)、(西塱站→體育中心站)單一有效路徑的結(jié)果，如圖5所示。用所提方法搜索得到的(西塱站→廣州南站站)和(西塱站→廣州火車站站)OD對間的多條有效路徑，如圖6所示。

表3 2015年廣州地鐵線網(wǎng)OD對擁有不同有效路徑條數(shù)的比例情況

圖5 單一有效路徑Fig.5 Single valid path

圖6 多條有效路徑Fig.6 Multiple valid paths

由表3可知，運(yùn)用所提有效路徑集生成方法生成有效路徑時(shí)，58.29%的OD對只有一條有效路徑，86.21%的OD對有效路徑條數(shù)不超過3條，95%的OD對有效路徑條數(shù)不超過5條。由此可知，運(yùn)用本文提出的方法生成的有效路徑集符合實(shí)際情況。由圖5和圖6中的4個(gè)OD對可以看出，當(dāng)起終點(diǎn)在同一線路上時(shí)，只存在一條有效路徑；當(dāng)起終點(diǎn)不在同一線路上時(shí)，能有效運(yùn)用該方法搜索出該OD對的有效路徑。

5 結(jié)語

本文根據(jù)乘客在城市軌道交通中的實(shí)際出行情況，提出乘客出行有效路徑應(yīng)滿足的基本假設(shè)，構(gòu)建線網(wǎng)拓?fù)鋱D，通過對路徑選擇影響因素的分析，構(gòu)造兩個(gè)關(guān)于全網(wǎng)出行費(fèi)用的鄰接矩陣，運(yùn)用最短路徑法搜索每個(gè)鄰接矩陣下的最短路徑，并以此為基準(zhǔn)設(shè)置乘客忍受閾值，構(gòu)建全網(wǎng)OD對有效路徑集搜索模型。以2015年廣州地鐵線網(wǎng)為例，證明了本文提出的有效路徑搜索方法的有效性，為后續(xù)研究提供了較好的數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)。本文獲得的主要結(jié)論為：

1) 對軌道交通線網(wǎng)中的線路和站點(diǎn)進(jìn)行編號，將線路分割成單位區(qū)間，使軌道交通線網(wǎng)次序化。

2) 在最短路徑法的基礎(chǔ)上進(jìn)行改進(jìn)，解決了最短路徑法針對一個(gè)OD對只能搜索出最短路徑的問題。所提方法主要以時(shí)間代價(jià)為基準(zhǔn)，遍歷生成的有效路徑集，并以線路路徑費(fèi)用最短為條件進(jìn)行篩選，較好地解決了K最短路算法中生成重復(fù)路徑的問題。

3) 所提方法最后生成的有效路徑集詳細(xì)記錄了路徑經(jīng)過的所有站點(diǎn)以及涉及的換乘關(guān)系，便于后續(xù)客流分配以及斷面客流估算研究。本文從AFC數(shù)據(jù)中隨機(jī)選取了100條數(shù)據(jù)，最低的準(zhǔn)確度為81.76%，90%以上的路徑準(zhǔn)確率高于85%，從而可以論證所提方法的有效性。