考慮換乘客流的城市軌道交通網(wǎng)絡末班車銜接優(yōu)化研究

鄭亞晶 李耀輝 靳文舟

(華南理工大學 土木與交通學院，廣東 廣州 510640)

隨著我國城市軌道交通的飛速發(fā)展，城市軌道交通網(wǎng)絡中各條線路末班車乘客的換乘協(xié)調問題受到了越來越多的關注。一般來說，由于城市軌道交通網(wǎng)絡上各條線路的運營時間有一定差異，在末班車時段，乘客通過城市軌道交通網(wǎng)絡出行的可達性會因為各線路逐步結束運營而出現(xiàn)變動，無論怎樣確定各換乘站末班車的推算順序及銜接關系，總會有部分乘客因趕不上換乘線路的末班車而無法依靠城市軌道交通完成出行。在此情形下，通過調整城市軌道交通末班車在換乘站的銜接關系，將因趕不上換乘線路末班車的換乘乘客人數(shù)最小化，是針對這一問題相對較好的解決方案。

目前，關于城市軌道交通網(wǎng)絡中各條線路末班車之間的銜接研究，已成為一個熱點。Kang等[1- 5]以換乘站成功方向數(shù)最大為目標，構建了針對末班車的時刻表優(yōu)化模型，并設計了遺傳算法求解；徐瑞華等[6]借鑒最小生成樹Kruskal算法的基本思想，提出了考慮客流需求及運營者的特定銜接需求的網(wǎng)絡末班車銜接方案優(yōu)化算法；郭建媛等[7]提出了路網(wǎng)可達性與OD對最晚可達時間的計算方法；袁振洲等[8]以乘客換乘感知費用總和最小為目標構建了全網(wǎng)條件下末班車時段多趟列車的時刻表銜接優(yōu)化模型，并設計了多種群遺傳算法進行求解；Chen等[9]通過延長換乘站停站時間，建立了以換乘成功客流量最大為目標的末班車時刻表優(yōu)化模型；溫芳等[10]在考慮運營結束延遲懲罰的基礎上構建了以提高時段內各間隔起始時刻的關鍵OD可達對數(shù)之和為目標的數(shù)學模型，并據(jù)此對各線路的末班車發(fā)車時刻進行了優(yōu)化。

從既有研究來看，研究者主要是在確定換乘站末班車停站銜接關系的基礎上進行各線路末班車開行時刻表的制定；換句話說，確定各條線路的換乘客流上下行在換乘站的換乘銜接關系，是協(xié)調編制城市軌道交通網(wǎng)絡中各條線路末班車計劃的前提。不過在網(wǎng)絡化運營條件下，各個城市的城市軌道交通網(wǎng)絡具有規(guī)模大、換乘站數(shù)量多、換乘關系復雜等特點，換乘客流在各換乘站的換乘銜接關系相互制約、相互影響，制定全網(wǎng)絡最合理的末班車客流換乘站銜接方案難度很大；故目前對末班車客流在換乘站的銜接方案的研究成果還存在關鍵OD的選取主觀性太強、求解中對模型松弛過大等問題。基于此，本研究在建立城市軌道交通末班車換乘銜接關系網(wǎng)絡的基礎上，通過求解該網(wǎng)絡的最大有向無環(huán)子圖，從而確定換乘人數(shù)最大的末班車換乘銜接方案，并通過算例，對這一模型進行驗證。

1 換乘銜接網(wǎng)絡

1.1 換乘站內部的銜接網(wǎng)絡

我國的城市軌道交通線網(wǎng)中，承擔兩條線路換乘的兩線換乘站是最常見的，這類換乘站一般需要負責8個方向的換乘客流。由于每條運營線路都由上下行兩個方向組成，因此這8個方向的換乘客流可由代表線路和上下行的4個節(jié)點以及它們之間的8條有向邊表示，如圖1(a)所示，其中，v1(a)，1和v1(a)，2分別表示換乘站a中線路1的上、下行方向站臺停靠的末班車，v2(a)，1和v2(a)，2分別表示換乘站a中線路2的上、下行方向站臺停靠的末班車。承擔多線換乘任務的換乘站與兩線換乘站類似，圖1(b)所示為三線換乘站中換乘流向的示意。為描述方便，本研究中，將圖1中這種換乘站內部的換乘客流銜接有向邊稱之為“換乘邊”。

(a)兩線換乘站

1.2 線路中換乘站之間的銜接關系

確定線網(wǎng)中末班車換乘客流的銜接方案，實質上是確定各線末班車在換乘站的到站時間先后順序關系。由于在城軌網(wǎng)絡中，一條線路會包括若干換乘站，該線路上的末班車在這些換乘站會因上下行關系存在固定的時間先后順序，如圖2(a)中目標線路中的兩個換乘站a和b，上行方向末班車到達a站的時間一定早于b站，下行方向末班車到達b站的時間一定早于a站，也即從乘客的角度來看的話，這兩個站之間的乘客換乘流線，可由4個節(jié)點和它們之間的2條有向邊表示(如圖2(b)所示，v1(a)，1和v1(a)，2分別為目標線路在換乘站a的上、下行方向站臺?？康哪┌嘬嚕籿1(b)，1和v1(b)，2分別為目標線路在換乘站b的上、下行方向站臺停靠的末班車)。為描述方便，本研究中，將圖2示意的這種代表同一線路不同換乘站之間乘客流的有向邊稱之為“列車邊”。

(a)實際線路方向

1.3 銜接關系的邏輯約束

針對某一城市軌道交通網(wǎng)絡系統(tǒng)，按文中第1.1節(jié)及1.2節(jié)構建換乘站內的換乘邊與同一線路換乘站間的列車邊即可得到該城市軌道交通末班車的換乘銜接關系網(wǎng)絡，這一網(wǎng)絡可近似視為末班車乘客在整個城軌系統(tǒng)中客流的可能流向集合。在這一網(wǎng)絡中，列車邊由列車的行駛方向確定，是客流在乘坐列車時隨列車開行的行進方向；而換乘邊之間則存在著互相制約關系：一條換乘邊代表的客流換乘方向是否能實現(xiàn)，必須考慮其他換乘邊所代表的客流換乘方向是否能實現(xiàn)，換句話說，換乘邊之間存在著復雜的取舍關系，而這之中，不同決策目標下的不同取舍方案，即為城市軌道交通系統(tǒng)中不同的末班車銜接方案。

換乘邊一般會成對出現(xiàn)，其銜接關系可歸納成3種情況[6]：雙方向銜接、單方向銜接和無方向銜接。雙方向銜接是指成對的兩條換乘邊所代表的兩個方向的末班車換乘乘客均能順利互相換乘，如圖3(a)所示；單方向銜接是指在成對的兩條換乘邊所代表的兩個方向的末班車換乘乘客中，僅一個方向的乘客可以順利完成換乘，如圖3(b)所示；無方向銜接是指成對的兩條換乘邊所代表的兩個方向的末班車換乘乘客均不能順利完成換乘，如圖3(c)所示。由于雙方向銜接需要至少有一個方向的末班車停站時間超過換乘乘客的換乘時間，考慮到地鐵的運行效率及末班車收班后的檢修作業(yè)，這一情形應該盡量避免，因此對于換乘站的內部銜接關系來說，兩條成對的換乘邊在最后的銜接方案中往往是無法同時存在的，也即在最后的銜接方案中，兩條成對的換乘邊最終會以單方向銜接和無方向銜接的形式出現(xiàn)。

(a)雙方向銜接

若將以上對成對的換乘邊的分析進行擴展，對于城市軌道交通末班車換乘銜接關系網(wǎng)絡來說，任何由有向邊組成的“回路(環(huán))”的接續(xù)關系都不可能被全部滿足，否則就意味著末班車的乘客在進行多次換乘接續(xù)以及乘坐后，仍然能在原下車站乘坐上該末班車，這顯然與城軌列車在車站短暫的停站時間相矛盾。

因此，確定網(wǎng)絡末班車銜接關系，其實質就是從銜接關系集中選出不會組成“回路(環(huán))”的最大客流銜接關系子集，也即求城市軌道交通末班車換乘銜接關系網(wǎng)絡的最大有向無環(huán)子圖。

2 網(wǎng)絡末班車銜接方案優(yōu)化模型

2.1 網(wǎng)絡表示

2.2 有向圖中的無環(huán)概念

在圖論中，如果一個有向圖無法從某個頂點出發(fā)經(jīng)過若干條邊回到該點，則該圖是一個有向無環(huán)圖。有向圖中的無環(huán)與無向圖中的無環(huán)有較大區(qū)別，例如圖4(a)和圖4(b)，一個為有向圖，一個為無向圖，雖然在視覺上這兩個網(wǎng)絡圖結構一樣，但圖4(a)無環(huán)，圖4(b)則有環(huán)。由于有向圖中一個點經(jīng)過兩種路線到達另一個點也未必形成環(huán)，因此有向無環(huán)圖未必能轉化成樹，故無向圖中求解無環(huán)子圖的“避圈法”或“破圈法”均無法在此運用。

(a)有向圖

2.3 模型構建

根據(jù)圖論的相關知識，任何一個有向無環(huán)圖都可轉化為其頂點的一個線性序列，該線性序列滿足以下兩個條件：

①每個頂點出現(xiàn)且只出現(xiàn)一次；

②若存在一條從頂點A到頂點B的路徑，那么在序列中頂點A出現(xiàn)在頂點B的前面。

這一頂點序列稱為該有向無環(huán)圖的拓撲排序[11]，一般來說，一個有向圖可以有一個或多個拓撲排序序列；反過來，在有向圖中，將其所有頂點進行隨機排序，然后僅保留該序列中符合拓撲序列規(guī)則的邊，即可得到原有向圖的一個與該頂點序列對應的有向無環(huán)子圖。據(jù)此，可定義整數(shù)變量ui(n)，a表示有向圖G=(V，E)某個頂點排序中節(jié)點vi(n)，a的序號，顯然，該頂點排序與對應的有向無環(huán)子圖的有向邊關系如下：

(1)

其次，換乘客流僅能在列車邊和換乘邊中實現(xiàn)，故

(2)

此外，列車邊的客流是必須存在的，能夠調整的僅僅是換乘邊，則有

(3)

本研究以考慮換乘客流為前提，故將可成功換乘的乘客人數(shù)最多作為目標，目標函數(shù)式如下所示：

(4)

至此，模型構建完畢。

3 模型求解

本研究構建的模型為非線性整數(shù)規(guī)劃模型，傳統(tǒng)方法較難求解，考慮到有向無環(huán)子圖與頂點的拓撲排序的對應關系，文中提出一種基于有向圖頂點拓撲排序編碼染色體的遺傳算法對模型進行求解。

一般來說，對于類似文中的網(wǎng)絡路徑問題，采用普通的二進制編碼，以0- 1分別表示對應的邊是否在最終路徑之中的編碼方式，在進化過程中染色體往往無法表達一個合法的路徑，因此文中采用的編碼，是在“基于優(yōu)先級編碼[12]”的基礎上通過加入列車邊的客流方向實現(xiàn)，具體編碼過程如下：

步驟1將頂點集V中的頂點按列車邊形成的鏈(文中稱為“列車鏈”)進行分組，并從1開始給每個分組一個組號。

步驟2將所有頂點進行隨機排序后再用組號進行替換。

通過以上兩個步驟，即可得到一條可行染色體，染色體長度等于頂點集V中的頂點數(shù)，每條染色體表示有向圖G=(V，E)的一個有向無環(huán)子圖。

例如圖5(b)就是圖5(a)所示線網(wǎng)的換乘銜接關系網(wǎng)絡，在該網(wǎng)絡中，列車鏈共4條(v1(a)，1-v1(b)，1，v2(a)，1-v2(b)，1，v1(b)，2-v1(a)，2，v2(b)，2-v2(a)，2)，按列車鏈對頂點進行分組：第1組節(jié)點為v1(a)，1、v1(b)，1，第2組節(jié)點為v2(a)，1、v2(b)，1，第3組節(jié)點為v1(b)，2、v1(a)，2，第4組節(jié)點為v2(b)，2、v2(a)，2；將這8個節(jié)點隨機排序并用其所在組號替代，即可得到一個染色體。例如“1- 2- 3- 1- 2- 4- 3- 4”即為一個染色體。

(a)線網(wǎng)

(b)換乘銜接關系網(wǎng)

而在對染色體進行解碼時，只需先將每組頂點按“列車接續(xù)邊”的方向進行組內排序，再將每組頂點按組號及組內順序，從左至右順次替換染色體中的數(shù)字。

例如解碼染色體“1- 2- 3- 1- 2- 4- 3- 4”時：左邊第1位上的基因片段“1”，是“1”在這個染色體中第1次出現(xiàn)，即替換為組1中的第1個頂點；第2位上的基因片段“2”，是“2”在這個染色體中第1次出現(xiàn)，即替換為組2中的第1個頂點；第3位上的基因片段“3”，是“3”在這個染色體中第1次出現(xiàn)，即替換為組3中的第1個頂點；第4位上的基因片段“1”，是“1”在這個染色體中第2次出現(xiàn)，即替換為組1中的第2個頂點；剩下的編碼均按此規(guī)則進行替換，也即該染色體可替換為“v1(a)，1-v2(a)，1-v1(b)，2-v1(b)，1-v2(b)，1-v2(b)，2-v1(a)，2-v2(a)，2”；再在原始有向圖G=(V，E)中，僅保留與“v1(a)，1-v2(a)，1-v1(b)，2-v1(b)，1-v2(b)，1-v2(b)，2-v1(a)，2-v2(a)，2”從左至右方向一致的“列車接續(xù)邊”和“換乘接續(xù)邊”，此時，即得到有向圖G=(V，E)的一個無環(huán)子圖，如圖6所示。

圖6 線網(wǎng)的一個有向無環(huán)子圖

至此，染色體“1- 2- 3- 1- 2- 4- 3- 4”解碼完成。

本研究構建的模型為單目標，可直接將染色體對應的目標值的排序作為評價函數(shù)的計算依據(jù)，利用式(5)計算染色體Zi的評價函數(shù)[13]

eval(Zi)=θ(1-θ)i-1

(5)

式中：i為該代種群中，染色體按式(4)計算的目標值的降序排列；θ為給定的參數(shù)，值取在0和1之間，在文中算例中取0.02。

此外，由于文中構建的染色體中的基因片段的前后關系與接續(xù)方案密切相關，因此本研究的交叉操作建議采用類OX法[14]進行。例如有兩父代染色體A和B，隨機選擇一個匹配區(qū)域：

A=1- 2|3- 1- 2- 4|3- 4，

B=2- 4|1- 1- 2- 4|3- 3。

將A的匹配區(qū)域加到B的前面，B的匹配區(qū)域加到A的前面，得到：

A′=1- 1- 2- 4|1- 2- 3- 1- 2- 4- 3- 4，

B′=3- 1- 2- 4|2- 4- 1- 1- 2- 4- 3- 3。

然后在A′和B′中自匹配區(qū)域后依次刪除與匹配區(qū)域中相同的基因片段，得到最終的兩個子串：

A″=1- 1- 2- 4- 3- 2- 3- 4，

B″=3- 1- 2- 4- 1- 2- 4- 3。

文中算法對變異操作并無要求，采用經(jīng)典的對換變異(即隨機選擇染色體中的兩個基因片段，將其進行交換)即可。

4 算例

圖7為一城市軌道交通線網(wǎng)圖例，一共4條線路，其中L4為環(huán)線，線網(wǎng)共包含6個換乘站{a，b，c，d，e，g}，其中a站為3線換乘站，其他站為2線換乘站。

圖7 城市軌道交通網(wǎng)絡

根據(jù)客流統(tǒng)計數(shù)據(jù)，在該地鐵網(wǎng)絡的末班車運行時段，列車與列車之間換乘客流的數(shù)據(jù)如表 1-表6所示。

表1 a站的換乘客流流量

表2 b站的換乘客流流量

表3 c站的換乘客流流量

表4 d站的換乘客流流量

表5 e站的換乘客流流量

表6 g站的換乘客流流量

利用第1節(jié)的方法，可將該地鐵網(wǎng)絡轉化為換乘銜接網(wǎng)絡，結果如圖8所示。

圖8 線網(wǎng)轉化的換乘銜接網(wǎng)絡

圖8中的26個頂點共組成8條列車鏈，具體如表7所示。

表7 列車鏈

種群規(guī)模100，進化160代，交叉概率取0.95，評價函數(shù)中參數(shù)θ取0.02，為避免種群早熟，變異概率線性變化，在開始時取0.000 1，160代時取0.1。運行10次，10次求解中種群的收斂情況如圖9所示，其中的最好結果為2 143。而利用隨機游走算法[15]游走10 000 000步，最好結果為1 558，即便在文中構造的初始種群的基礎上再利用隨機游走算法游走10 000 000步，得到的最好結果也僅為2 108，這說明文中采用的遺傳算法有較好的優(yōu)化效果；而從種群收斂情況來看，算法進化30～60代種群即開始保持穩(wěn)定，這說明文中采用的遺傳算法具有良好的魯棒性。

圖9 遺傳算法種群收斂圖

在以上的10次計算中，最優(yōu)染色體為“5- 8- 1- 5- 3- 3- 7- 8- 3- 1- 4- 1- 5- 1- 6- 4- 1- 6- 4- 2- 2- 2- 2- 7- 2- 6”，對其進行解碼，可得到對應的頂點排序為“v2(b)，1-v3(d)，1-v4(b)，1-v2(a)，1-v1(c)，1-v1(a)，1-v3(a)，2-v3(a)，1-v1(g)，1-v4(g)，1-v1(g)，2-v4(e)，1-v2(e)，1-v4(d)，1-v2(e)，2-v1(a)，2-v4(c)，1-v2(a)，2-v1(c)，2-v4(c)，2-v4(d)，2-v4(e)，2-v4(g)，2-v3(d)，2-v4(b)，2-v2(b)，2”，將該排序解碼后，即可得到最終各換乘站點保留的換乘銜接關系，如表8所示。

表8 線網(wǎng)各換乘站的末班車銜接關系表

以表8中的換乘銜接關系為基礎，依據(jù)各線路列車運行的相關參數(shù)，即可逐步對全網(wǎng)絡各線路的末班車時刻表進行推算。

5 結語

城市軌道交通各線路末班車之間乘客換乘協(xié)調問題的實質是確定各換乘站末班車之間的推算順序及銜接關系。本研究以末班車成功換乘乘客人數(shù)最大化為優(yōu)化目標，提出了網(wǎng)絡末班車的銜接方案優(yōu)化模型和算法，通過該算法可最終得到整個城市軌道交通網(wǎng)絡的末班車換乘乘客銜接關系表。基于該關系表，即可對各線路的末班車在換乘站的經(jīng)過時刻先后進行判定，并據(jù)此計算出各線路末班車的始發(fā)時刻及在所有車站的到發(fā)時刻。但需要說明的是，城市軌道交通網(wǎng)絡末班車計劃的編制需要考慮的因素較多，換乘乘客的人數(shù)最大化只是其中較重要的一項考慮因素，故文中的這一方法只可作為末班車計劃編制的輔助手段，為城市軌道交通網(wǎng)絡中各線路末班車時刻表的編制提供一定的決策依據(jù)。