,,

(蘇州大學(xué)軌道交通學(xué)院， 江蘇 蘇州 215131)

隨著我國城市軌道交通的不斷建設(shè)和發(fā)展，許多城市的軌道交通逐漸由單線運(yùn)營向網(wǎng)絡(luò)化運(yùn)營轉(zhuǎn)變。因此，城市軌道交通網(wǎng)絡(luò)中的每一對(duì)起訖站點(diǎn)之間可能存在多條合理的出行路徑。在無縫換乘模式下，通過AFC刷卡數(shù)據(jù)可以得到乘客具體的上下車站和時(shí)間信息，但卻無法直接獲得乘客在網(wǎng)絡(luò)中的具體走行路徑。把握乘客在軌道交通網(wǎng)絡(luò)中的出行路徑對(duì)于分析網(wǎng)絡(luò)客流規(guī)律和多家運(yùn)營商背景下的票務(wù)清分來說具有重大的意義。

目前，在城市道路網(wǎng)絡(luò)中出行者選擇行為和路徑搜索算法方面，國內(nèi)外專家學(xué)者取得了豐富的成果，提出了許多路徑搜索理論和算法[1-4]。Dial[1]認(rèn)為當(dāng)一條路徑所包含的所有路段都使出行者離起始節(jié)點(diǎn)越來越遠(yuǎn)，離終點(diǎn)節(jié)點(diǎn)越來越近，則這條路徑是“有效”的，并提出一種有效路徑求解算法。Hoffman等[2]最早提出了K短路徑的算法，用以求出起終點(diǎn)間最短、次短和第K短路徑。Christopher和Brace[3]研究了K短路徑長度、不經(jīng)過重復(fù)節(jié)點(diǎn)的K短路徑和帶單邊約束的最短路徑等問題。

但是與城市道路網(wǎng)絡(luò)相比，城市軌道交通網(wǎng)絡(luò)在節(jié)點(diǎn)性質(zhì)、網(wǎng)絡(luò)構(gòu)成、阻抗計(jì)算方法、影響因素等方面都具有不同的特性[5-7]。軌道交通網(wǎng)絡(luò)節(jié)點(diǎn)處存在節(jié)點(diǎn)阻抗(停車時(shí)間、換乘時(shí)間)，因此在實(shí)際應(yīng)用中往往需要進(jìn)行特殊的處理。林湛等[8]根據(jù)最短路徑費(fèi)用定義OD之間的有效路徑集合，錢堃等[9]重點(diǎn)研究了換乘時(shí)間對(duì)乘客路徑選擇行為的影響，但都沒有對(duì)軌道交通網(wǎng)絡(luò)節(jié)點(diǎn)的具體處理方式進(jìn)行闡述。四兵鋒等[10]在客流分配模型中將網(wǎng)絡(luò)節(jié)點(diǎn)阻抗合并到區(qū)間阻抗中，這樣處理雖然簡化了問題，但是可能造成搜索過程中路徑阻抗的計(jì)算偏差。周薇[11]在改進(jìn)的Dial算法中將一個(gè)軌道交通車站表示成兩個(gè)節(jié)點(diǎn)，郭彥云[12]在對(duì)軌道交通網(wǎng)絡(luò)拓?fù)潢P(guān)系建模中同樣分拆了網(wǎng)絡(luò)節(jié)點(diǎn)，這樣處理有效地體現(xiàn)了節(jié)點(diǎn)阻抗，但是這種處理方式導(dǎo)致的有效路徑中可能存在冗余路段的問題卻沒有被提及。

基于上述分析，結(jié)合城市軌道交通自身特性，給出有效路徑中冗余路段的定義并提出增加冗余路段判定步驟的改進(jìn)的有效路徑搜索算法，期望以此為基礎(chǔ)建立一個(gè)完整的軌道交通網(wǎng)絡(luò)客流路徑分析系統(tǒng)。

1 網(wǎng)絡(luò)節(jié)點(diǎn)及有效路徑定義

1.1 網(wǎng)絡(luò)節(jié)點(diǎn)處理

城市軌道交通網(wǎng)絡(luò)主要由區(qū)間和車站兩個(gè)部分組成，除了軌道交通區(qū)間有運(yùn)行時(shí)間阻抗，軌道交通車站也存在停車時(shí)間阻抗，因此軌道交通網(wǎng)絡(luò)每個(gè)節(jié)點(diǎn)都存在節(jié)點(diǎn)阻抗。為了表示車站的停站時(shí)間，將每個(gè)軌道交通普通車站分拆表示為停車節(jié)點(diǎn)和出發(fā)節(jié)點(diǎn)，其間增加停車弧表示停車時(shí)間。

除固定的區(qū)間運(yùn)行時(shí)間、停車時(shí)間之外，換乘步行時(shí)間和換乘等待時(shí)間也是軌道交通網(wǎng)絡(luò)阻抗的重要組成部分。對(duì)于軌道交通換乘站而言，節(jié)點(diǎn)阻抗存在兩種情況：一方面，如果乘客在換乘站不需要換乘，則只經(jīng)歷停車時(shí)間，可看作普通車站，通過停車弧對(duì)其進(jìn)行表示；另一方面，如果乘客在換乘站進(jìn)行了換乘，則存在換乘時(shí)間，需要引入換乘弧對(duì)其進(jìn)行描述。處理后的整個(gè)城市軌道交通網(wǎng)絡(luò)可以用“帶權(quán)有向圖”來描述。圖1和圖2分別表示普通車站和換乘車站的網(wǎng)絡(luò)節(jié)點(diǎn)示意圖。

圖1 普通車站停車弧示意圖

圖2 換乘車站換乘弧示意圖

1.2 有效路徑判定規(guī)則

在一次出行中，軌道交通乘客總是希望選擇出行費(fèi)用(時(shí)間、票價(jià)等)最少的路徑，當(dāng)起訖站點(diǎn)間有多條路徑可選時(shí)，乘客不會(huì)考慮全部的路徑，而是將其中幾條作為備選方案，那些被大多數(shù)乘客所考慮的費(fèi)用相近的路徑便稱為“有效路徑”。

常用的有效路徑判定規(guī)則采用“相對(duì)值”法[13-15]，同時(shí)考慮到換乘次數(shù)的增加也會(huì)降低乘客的舒適性，因此在有效路徑的判定規(guī)則中增加換乘次數(shù)的限制。

定義1 當(dāng)OD對(duì)(r,s)間的路徑k滿足以下3個(gè)條件，則稱其為有效路徑。

1)路徑k中不存在環(huán)路，即不重復(fù)經(jīng)過同一個(gè)節(jié)點(diǎn)。

2)路徑k的阻抗小于等于最短路徑阻抗的1+Hrs倍，即：

(1)

3)路徑k的換乘次數(shù)小于等于網(wǎng)絡(luò)最大換乘次數(shù)限制，即

Tk≤Tmax

(2)

式中：Tk為路徑k的換乘次數(shù)；Tmax為網(wǎng)絡(luò)最大換乘次數(shù)限制。

2 冗余路段定義及判定

2.1 路徑冗余路段定義

由于軌道交通車站節(jié)點(diǎn)的特殊處理，在實(shí)際操作過程中，通過未改進(jìn)的有效路徑算法搜索到的僅僅滿足1.2中有效路徑判定規(guī)則的部分路徑中還包含了不符合換乘邏輯的路段。為了說明上述路段的特征，圖3為某個(gè)換乘車站網(wǎng)絡(luò)節(jié)點(diǎn)的示意圖，虛線框線內(nèi)的節(jié)點(diǎn)歸屬于同一個(gè)車站，其中節(jié)點(diǎn)18、19、74、75為換乘車站節(jié)點(diǎn)，其余為普通車站節(jié)點(diǎn)。

圖3 換乘車站網(wǎng)絡(luò)節(jié)點(diǎn)示意圖

假如某位乘客從車站A上車，在車站B下車，其間經(jīng)過了兩段區(qū)間運(yùn)行時(shí)間和一段換乘時(shí)間，可以看出，符合該乘客正確換乘邏輯的路徑應(yīng)該是17-18-75-76。通過未改進(jìn)的算法搜索到的相同起終點(diǎn)的路徑有17-18-74-75-76、17-18-19-75-76和17-18-74-19-75-76。這些路徑中均包含了不符合邏輯的停車時(shí)間和換乘時(shí)間，相應(yīng)的18-74-75、18-19-75、18-74-19-75均可判定為冗余路段。結(jié)合以上分析，給出冗余路段的定義。

定義2 當(dāng)有效路徑的路段兩端節(jié)點(diǎn)為換乘車站節(jié)點(diǎn)，且在路徑中體現(xiàn)為冗余停車時(shí)間或冗余換乘時(shí)間，則稱該路段為冗余路段。

2.2 路徑冗余路段判定

通過分析可以發(fā)現(xiàn)，不包含冗余路段的有效路徑中，路徑經(jīng)過某換乘車站或在某換乘車站進(jìn)行換乘則有且只有兩個(gè)換乘車站節(jié)點(diǎn)。因此，路徑中冗余路段的判斷邏輯為：如果有效路徑中有連續(xù)3個(gè)或3個(gè)以上換乘車站節(jié)點(diǎn)，則該路徑包含冗余路段。

為了篩選出包含冗余路段的有效路徑，設(shè)立變量transfer記錄網(wǎng)絡(luò)中某節(jié)點(diǎn)是否為換乘車站節(jié)點(diǎn)，具體定義為：

(3)

在此基礎(chǔ)上，根據(jù)每個(gè)節(jié)點(diǎn)的換乘節(jié)點(diǎn)變量transfer，搜索到的每條路徑便有1個(gè)對(duì)應(yīng)的相同長度的換乘節(jié)點(diǎn)序列。遍歷路徑換乘節(jié)點(diǎn)序列的子序列，如果子序列集合中包含“1-1-1”或者“1-1-1-1”的元素，則說明該路徑中包含冗余路段，需要剔除?；谏鲜龇治?，以從節(jié)點(diǎn)17到節(jié)點(diǎn)76為例的路徑換乘節(jié)點(diǎn)序列和冗余路段判定見表1。

表1 路徑換乘節(jié)點(diǎn)序列和冗余路段判定示例

3 改進(jìn)的有效路徑搜索算法

在充分考慮各種路徑搜索算法優(yōu)缺點(diǎn)的情況下，采用深度優(yōu)先遍歷算法來實(shí)現(xiàn)有效路徑搜索過程。

深度優(yōu)先遍歷的思想是：假設(shè)初始狀態(tài)圖中所有頂點(diǎn)均未被訪問，從某個(gè)頂點(diǎn)v出發(fā)，首先訪問該頂點(diǎn)，然后依次從它的各個(gè)未被訪問的鄰接點(diǎn)出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有和v有路徑相通的頂點(diǎn)都被訪問到。若此時(shí)尚有其他頂點(diǎn)未被訪問到，則另選一個(gè)未被訪問的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問到為止。

在上述深度優(yōu)先遍歷搜索算法中增加冗余路段判定步驟(Step 4)后，改進(jìn)的有效路徑搜索算法具體步驟如下：

Step 0：初始化。給相關(guān)變量賦初值，輸入鄰接矩陣，設(shè)定參數(shù)。

Step 1：利用Dijkstra算法計(jì)算最短路徑阻抗，設(shè)根節(jié)點(diǎn)v為當(dāng)前節(jié)點(diǎn)。

Step 2：從當(dāng)前節(jié)點(diǎn)i出發(fā)，遍歷與節(jié)點(diǎn)i相鄰的節(jié)點(diǎn)，例如節(jié)點(diǎn)j，如果從根節(jié)點(diǎn)v出發(fā)沿著該路徑的阻抗小于或等于設(shè)定閾值并且滿足換乘限制條件，則令節(jié)點(diǎn)j為當(dāng)前點(diǎn)，轉(zhuǎn)下一步，否則轉(zhuǎn)Step 6。

Step 3：判斷節(jié)點(diǎn)j是否為終節(jié)點(diǎn)，如果不是則轉(zhuǎn)入Step 2，否則進(jìn)行下一步。

Step 4：判斷該路徑是否包含冗余路段，如果是則忽略該路徑并轉(zhuǎn)入Step 2，否則進(jìn)行下一步。

Step 5：搜索前驅(qū)節(jié)點(diǎn)序列并輸出路徑。

Step 6：退回上一層，若未退回到根節(jié)點(diǎn)則轉(zhuǎn)入Step 2。

4 案例分析

為了檢驗(yàn)改進(jìn)的有效路徑搜索算法的可行性及有效性，利用某市軌道交通網(wǎng)絡(luò)進(jìn)行案例分析。該市軌道交通網(wǎng)絡(luò)由1號(hào)線、2號(hào)線、3號(hào)線和4號(hào)線組成，共有5座換乘車站，網(wǎng)絡(luò)示意圖如圖4所示。

圖4 軌道交通網(wǎng)絡(luò)示意圖

4.1 網(wǎng)絡(luò)參數(shù)取值

網(wǎng)絡(luò)中停車時(shí)間、區(qū)間運(yùn)行時(shí)間、換乘步行時(shí)間參數(shù)均為多次實(shí)測數(shù)據(jù)的平均值，換乘等待時(shí)間取各條線路平峰行車間隔的一半，網(wǎng)絡(luò)最大換乘次數(shù)限制取2。

除此之外，定義1中的路徑伸展系數(shù)是有效路徑判定條件中的重要參數(shù)。如果路徑伸展系數(shù)取值過大，路徑阻抗過大甚至存在繞行情況的路徑就被納入到有效路徑中；相反，如果取值過小，則會(huì)遺漏部分有效路徑。因此，路徑伸展系數(shù)的取值應(yīng)根據(jù)具體的網(wǎng)絡(luò)形式確定，通過式(4)計(jì)算網(wǎng)絡(luò)主要換乘方向起訖點(diǎn)間最大合理路徑的伸展系數(shù)，具體計(jì)算結(jié)果見表2。

定義3 當(dāng)一條路徑不經(jīng)過背離起訖點(diǎn)方向的換乘站進(jìn)行換乘，且在所有滿足條件的路徑中阻抗最大，則稱該路徑為最大合理路徑。

如從A站到E站，經(jīng)過G站換乘的路徑則是不合理的路徑。

(4)

可以看出，除D—E起訖點(diǎn)外，其他起訖點(diǎn)間最大合理路徑的阻抗與最短路徑阻抗十分接近。對(duì)于該市軌道交通網(wǎng)絡(luò)來說，路徑伸展系數(shù)取0.3即可滿足要求。

表2 主要起訖點(diǎn)間最大合理路徑伸展系數(shù)

4.2 有效路徑搜索結(jié)果

利用Python程序語言編寫改進(jìn)后的搜索算法，并對(duì)A站與H站之間的有效路徑進(jìn)行搜索。如果采用未改進(jìn)的算法，則程序輸出結(jié)果顯示有20條，但是經(jīng)過人工辨識(shí)，其中有18條都包含冗余路段。這正是由于網(wǎng)絡(luò)節(jié)點(diǎn)的特殊處理方式以及多個(gè)換乘站間冗余路段的乘積效應(yīng)導(dǎo)致的有效路徑數(shù)量與實(shí)際數(shù)量產(chǎn)生明顯偏差。同時(shí)，由于冗余路段的存在，輸出的路徑阻抗也與真實(shí)的路徑阻抗存在偏差。

現(xiàn)采用改進(jìn)后的算法對(duì)A站與H站之間的有效路徑進(jìn)行搜索，共得到2條有效路徑，結(jié)果表明改進(jìn)后的算法能有效剔除包含冗余路段的路徑，具體路徑信息如表3所示。程序輸出的有效路徑信息符合乘客實(shí)際的換乘行為，并且保證了有效路徑信息的正確性。

表3 A站-H站間有效路徑信息

5 結(jié)束語

基于對(duì)軌道交通網(wǎng)絡(luò)節(jié)點(diǎn)處理方式和有效路徑搜索算法進(jìn)行研究，對(duì)于在實(shí)際操作過程中發(fā)現(xiàn)的通過未改進(jìn)算法搜索有效路徑仍可能包含冗余路段的問題，給出了一種解決方法。

歸因于軌道交通網(wǎng)絡(luò)車站節(jié)點(diǎn)的特殊處理，通過深度優(yōu)先算法搜索到的有效路徑中可能包含冗余的停車時(shí)間或換乘時(shí)間。通過實(shí)例分析冗余路段的特征并給出冗余路段的定義。在深度優(yōu)先搜索算法中增加了冗余路段判定步驟，具體為分析路徑換乘節(jié)點(diǎn)序列的子序列集合中是否存在特定元素，進(jìn)而改進(jìn)了算法。實(shí)例分析中算法改進(jìn)前后的搜索結(jié)果表明改進(jìn)后的算法能夠正確地篩選出軌道交通網(wǎng)絡(luò)有效路徑，得到完整的有效路徑信息。研究成果為建立完整的城市軌道交通網(wǎng)絡(luò)客流路徑分析系統(tǒng)奠定了基礎(chǔ)。