基于逐步優(yōu)化的軌道交通網(wǎng)絡(luò)行車(chē)計(jì)劃銜接

李 偉，羅 欽

1) 深圳大學(xué)光電工程學(xué)院，光電子器件與系統(tǒng)教育部/廣東省重點(diǎn)實(shí)驗(yàn)室, 廣東深圳 518060；2) 深圳技術(shù)大學(xué)城市交通與物流學(xué)院，廣東深圳 518118

隨著城市軌道交通的不斷發(fā)展，城市軌道交通運(yùn)營(yíng)管理逐步進(jìn)入網(wǎng)絡(luò)化運(yùn)營(yíng)階段，直接體現(xiàn)在網(wǎng)絡(luò)中不同線路間的換乘銜接．良好的換乘銜接會(huì)縮短乘客的換乘等待時(shí)間，提升乘客的軌道交通出行良好感受，相反糟糕的換乘銜接則會(huì)大大延長(zhǎng)乘客的換乘時(shí)間，降低軌道交通的服務(wù)水平．因此，在研究制定城市軌道交通列車(chē)行車(chē)計(jì)劃時(shí)應(yīng)盡可能縮短乘客在路徑上的換乘等待時(shí)間．行車(chē)計(jì)劃的主要內(nèi)容包括該時(shí)段的列車(chē)開(kāi)行間隔以及換乘站換乘銜接方案．

傳統(tǒng)意義上的行車(chē)計(jì)劃優(yōu)化是指在滿(mǎn)足眾多運(yùn)營(yíng)和安全約束(如到達(dá)或出發(fā)間隔要求)的條件下，生成一個(gè)使目標(biāo)函數(shù)可行或使給定目標(biāo)函數(shù)較優(yōu)的列車(chē)運(yùn)行圖．列車(chē)運(yùn)行計(jì)劃優(yōu)化問(wèn)題是一個(gè)典型的NP難(non-deterministic polynomial-time hard)問(wèn)題[1-3]，不少學(xué)者利用如啟發(fā)式算法[4]、分支定界法[5-6]、仿真方法[7]及銜接分層優(yōu)化算法[8]等求解該優(yōu)化問(wèn)題．然而，隨著客流在制訂軌道交通列車(chē)行車(chē)計(jì)劃、合理配置運(yùn)能方面的指導(dǎo)作用日趨重要，如今優(yōu)化模型的目標(biāo)函數(shù)不僅局限于軌道交通運(yùn)營(yíng)層面．文獻(xiàn)[9-11]通過(guò)引入動(dòng)態(tài)客流需求研究行車(chē)計(jì)劃銜接與優(yōu)化問(wèn)題，以時(shí)變客流需求為背景，以乘客在車(chē)站的候車(chē)時(shí)間最小化為目標(biāo)函數(shù)，利用啟發(fā)式算法求解列車(chē)運(yùn)行計(jì)劃優(yōu)化問(wèn)題．

以上增加時(shí)變客流因素的研究大大增加了列車(chē)運(yùn)行計(jì)劃編制的科學(xué)性和先進(jìn)性．然而，當(dāng)前中國(guó)許多大城市的軌道交通網(wǎng)絡(luò)規(guī)模十分龐大，線路及換乘站數(shù)量多，換乘方向繁多復(fù)雜，各線路間、各換乘站內(nèi)部的關(guān)系具有關(guān)聯(lián)和不確定性，若將網(wǎng)絡(luò)上所有換乘站均考慮在內(nèi)，求解起來(lái)十分困難，使用常規(guī)的建模及優(yōu)化方法分析該問(wèn)題已無(wú)法得到滿(mǎn)意結(jié)果，較難用于實(shí)際．因此，研究一個(gè)貼近實(shí)際并且易于實(shí)現(xiàn)的行車(chē)計(jì)劃銜接優(yōu)化模型顯得尤為重要．

面對(duì)一個(gè)具有復(fù)雜關(guān)系和眾多參變量的大系統(tǒng)，需從系統(tǒng)內(nèi)部相互關(guān)聯(lián)子系統(tǒng)的分解出發(fā)，逐步、逐級(jí)地研究．基于以上考慮，本研究探討在時(shí)變客流需求下的網(wǎng)絡(luò)行車(chē)計(jì)劃銜接優(yōu)化問(wèn)題，采用逐步優(yōu)化思想，優(yōu)先考慮換乘客流大的車(chē)站和銜接方向，并依次考慮換乘客流小的銜接方向，逐步形成優(yōu)化的列車(chē)運(yùn)行計(jì)劃．該問(wèn)題可以被闡述為：以具體客流需求數(shù)據(jù)為基礎(chǔ)，以列車(chē)開(kāi)行間隔與列車(chē)到達(dá)時(shí)刻為變量，以整體換乘銜接為目標(biāo)函數(shù)的優(yōu)化模型，旨在減少乘客總候車(chē)時(shí)間及提升軌道交通運(yùn)營(yíng)服務(wù)頻率與運(yùn)營(yíng)服務(wù)水平，提升軌道交通整體網(wǎng)絡(luò)動(dòng)態(tài)可達(dá)性．

1 換乘站的主動(dòng)銜接與換乘銜接

軌道交通換乘銜接優(yōu)化模型的主要思路為：參考最小生成樹(shù)思想，先對(duì)換乘站換乘銜接方向按客流量大小排序，優(yōu)先考慮換乘站換乘客流大的銜接方向，并綜合考慮同一換乘站內(nèi)相關(guān)換乘銜接方向，以平均換乘等待時(shí)間為目標(biāo)函數(shù)進(jìn)行局部?jī)?yōu)化求解，逐步求解得到全網(wǎng)絡(luò)所有換乘站的優(yōu)化列車(chē)行車(chē)計(jì)劃．

在此之前，先提出主動(dòng)銜接與被動(dòng)銜接概念，由于同一換乘站內(nèi)，換乘銜接方向A-B的產(chǎn)生就必然會(huì)有換乘銜接方向B-A，調(diào)整線路A和B任意的列車(chē)開(kāi)行間隔和到達(dá)時(shí)刻均會(huì)導(dǎo)致這兩個(gè)換乘銜接方向乘客的換乘等待時(shí)間發(fā)生改變，因此，線路A和線路B之間換乘銜接就存在主動(dòng)銜接和被動(dòng)銜接概念，由線路A去主要銜接線路B稱(chēng)之為主動(dòng)銜接，相應(yīng)線路B銜接線路A稱(chēng)為被動(dòng)銜接．定義符號(hào)?*」表示不大于*的最大整數(shù)，「*?表示不小于*的最小整數(shù)．

1.1 主動(dòng)銜接平均換乘等待時(shí)間

假設(shè)主動(dòng)銜接方向?yàn)橛删€路換向線路，換乘路徑的示意圖如圖1．

圖1 主動(dòng)銜接示意圖Fig.1 Active coordination of transfer connection direction

(1)

同時(shí)，可得線路r上列車(chē)在車(chē)站的發(fā)車(chē)時(shí)間為

(2)

(3)

整理可得

(4)

考慮到理性乘客首選候車(chē)后第1趟到達(dá)的列車(chē)，則

(5)

因此，第s列列車(chē)上乘客的換乘等待時(shí)間Wl→r(S)為

(6)

(7)

1.2 被動(dòng)銜接平均換乘等待時(shí)間

主動(dòng)銜接方向?yàn)橛删€路l換向線路r， 相應(yīng)被動(dòng)銜接方向?yàn)榫€路r換向線路l， 對(duì)應(yīng)的換乘示意圖如圖2．其平均換乘等待時(shí)間的計(jì)算方法與主動(dòng)銜接平均等待時(shí)間的計(jì)算方法相類(lèi)似．

圖2 被動(dòng)銜接示意圖Fig.2 Passive coordination of transfer connection direction

(8)

(9)

(10)

整理可得

(11)

考慮到理性乘客第一選擇始終是候車(chē)后第一趟到達(dá)的列車(chē)，因此

(12)

則第s′列列車(chē)上乘客的換乘等待時(shí)間Wr→l(s′)可以表示為

(13)

(14)

1.3 總平均換乘等待時(shí)間

綜合主動(dòng)銜接和被動(dòng)銜接兩個(gè)平均換乘等待時(shí)間，在車(chē)站i的總換乘等待時(shí)間F為

(15)

其中，fi,l→r(T)為在時(shí)間段T內(nèi)，在車(chē)站i中從線路l換向線路r的總客流量；fi,r→l(T)為在時(shí)間段T內(nèi)，在車(chē)站i中從線路r換向線路l的總客流量．

要求換乘車(chē)站i的主動(dòng)銜接方向和被動(dòng)銜接方向的銜接程度最優(yōu)，即使得總平均換乘等待時(shí)間最小，需滿(mǎn)足

(16)

s.t.Hmin,l≤Hi,l≤Hmax,l

Hmin,r≤Hi,r≤Hmax,r

其中，Hmin,l和Hmin,r表示列車(chē)開(kāi)行間隔能取的最小值，其與線路折返能力、追蹤能力有關(guān)；Hmax,l和Hmax,r表示列車(chē)開(kāi)行間隔能取的最大值．

2 逐步優(yōu)化求解算法

模型求解思路主要基于逐步優(yōu)化思想，① 將換乘站換乘銜接方向按換乘客流大小排序；② 對(duì)換乘客流大的銜接方向優(yōu)先構(gòu)建連接邊，確定該方向列車(chē)開(kāi)行間隔和列車(chē)到達(dá)時(shí)刻，并進(jìn)行標(biāo)記，逐步按換乘客流大小依次將網(wǎng)絡(luò)上所有換乘方向覆蓋，形成一個(gè)完整列車(chē)運(yùn)營(yíng)計(jì)劃．具體求解思路的流程框架如圖3．

圖3 算法流程圖Fig.3 Algorithm flow chart

2.1 換乘客流排序

模型求解首先要得到按換乘客流量排序的全網(wǎng)絡(luò)換乘銜接方向．得益于近來(lái)興起的軌道交通自動(dòng)售檢票系統(tǒng)(automatic fare collection, AFC)，我們可以獲得大量乘客出行數(shù)據(jù)，進(jìn)而獲得在微觀層面上量化的客流時(shí)空分布結(jié)果．具體使用方法為利用給出的路徑清分比例表，分析計(jì)算指定日期和指定時(shí)間段的進(jìn)出站AFC刷卡數(shù)據(jù)，可得每個(gè)時(shí)間點(diǎn)和每個(gè)車(chē)站上的客流量，隨即獲得該時(shí)段內(nèi)各換乘站各換乘方向的客流量．將排序后的換乘站和換乘方向集合存儲(chǔ)供后續(xù)步驟調(diào)用．

2.2 逐步優(yōu)化

逐步優(yōu)化目標(biāo)可描述為：① 制定一個(gè)列車(chē)行車(chē)計(jì)劃，使所有換乘站的所有換乘方向均能被接上，且網(wǎng)絡(luò)所有換乘站的總換乘等待時(shí)間最?。鶕?jù)排序好的換乘銜接方向，對(duì)換乘客流大的換乘銜接方向優(yōu)先構(gòu)建銜接計(jì)劃，確定該方向列車(chē)開(kāi)行間隔和首列列車(chē)到達(dá)時(shí)刻，并將該換乘方向進(jìn)行標(biāo)記；② 按換乘客流大小依次將網(wǎng)絡(luò)上所有換乘方向連接上．若該方向列車(chē)開(kāi)行間隔和列車(chē)到達(dá)時(shí)刻已被標(biāo)記，則無(wú)需改變它們；若該方向列車(chē)開(kāi)行間隔或列車(chē)到達(dá)時(shí)刻有其中一個(gè)未標(biāo)記確定，則求解之．最終形成一個(gè)完整的列車(chē)行車(chē)計(jì)劃．

2.3 分級(jí)求解算法

換乘銜接求解中存在兩種情況，一是主動(dòng)銜接與被動(dòng)銜接中4個(gè)變量(分別為列車(chē)開(kāi)行間隔與列車(chē)到達(dá)間隔)均未知，或3個(gè)變量未知1個(gè)變量已知；另一種是主動(dòng)銜接與被動(dòng)銜接中2個(gè)變量未知2個(gè)變量已知，或1個(gè)變量未知3個(gè)變量已知．從建立模型的公式可以看出，模型為弱約束最優(yōu)化問(wèn)題，當(dāng)變量數(shù)量過(guò)多時(shí)(如情況一)，將很難求出優(yōu)化結(jié)果，此時(shí)通常采取啟發(fā)式算法，本研究選取模擬退火算法求解；而當(dāng)變量數(shù)量少時(shí)(如情況二)，為得到較優(yōu)結(jié)果，可采用最優(yōu)化理論求解，本研究選取一維線性搜索算法求解．

模擬退火算法源于固體退火原理[12]，將固體加溫至足夠高的溫度，加溫時(shí)固體內(nèi)部分子隨升溫變?yōu)闊o(wú)序狀呈現(xiàn)隨機(jī)排列狀態(tài)，而逐步降溫時(shí)粒子漸趨有序．最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)部分子以低能狀態(tài)排列，固體達(dá)到某種穩(wěn)定狀態(tài)．

具體模擬退火算法步驟如下：

步驟1設(shè)定初始溫度值T0， 初始狀態(tài)解x， 計(jì)算其目標(biāo)函數(shù)值E．

步驟2內(nèi)部循環(huán)．

1)產(chǎn)生一個(gè)隨機(jī)干擾，得到新解x′， 并計(jì)算其目標(biāo)函數(shù)值E′．

2)計(jì)算內(nèi)能增量ΔE， 若ΔE<0， 則接受新解x′， 設(shè)新解為當(dāng)前解x←x′， 跳轉(zhuǎn)步驟4)，否則跳轉(zhuǎn)步驟3)．

3)若ΔE>0， 計(jì)算概率p=e-ΔE/kTi， 并隨機(jī)生成一個(gè)0～1的均勻分布變量，用以判斷是否接受新解，若接受則設(shè)新解為當(dāng)前解x←x′； 否則保持原解x， 轉(zhuǎn)步驟4)．

4)若滿(mǎn)足內(nèi)循環(huán)終止條件，跳出內(nèi)循環(huán)；一般內(nèi)循環(huán)終止條件取為連續(xù)若干個(gè)新解都沒(méi)有被接受，即當(dāng)前解保持不變?nèi)舾纱窝h(huán)．

步驟3外部循環(huán)．

1)判斷當(dāng)前溫度Ti是否滿(mǎn)足終止條件，即Ti→Tmin， 其中，Tmin為目標(biāo)溫度，若達(dá)到終止條件，則終止算法，輸出當(dāng)前解為最優(yōu)解；

2)設(shè)置當(dāng)前溫度為T(mén)i→Ti×ε， 其中，ε為溫度衰減參數(shù)，一般設(shè)置為0.99或0.98，跳轉(zhuǎn)步驟2開(kāi)始內(nèi)部循環(huán)．

本研究采用的一維線性搜索中“改進(jìn)0.618法”來(lái)計(jì)算模型求解中未知變量少的情況二．0.618法(又稱(chēng)黃金分割法)是美國(guó)數(shù)學(xué)家KIEFER[13]于1953年提出，屬于分割法函數(shù)求極值方法，分割類(lèi)方法僅需計(jì)算函數(shù)值，因此使用范圍較廣，尤其適用于非光滑及導(dǎo)數(shù)表達(dá)式復(fù)雜或?qū)懖怀龅惹樾危倪M(jìn)0.618法是針對(duì)目標(biāo)函數(shù)是單峰函數(shù)，也就是目標(biāo)函數(shù)為凸的情形的分割類(lèi)方法，因其不要求函數(shù)可微，且每次迭代只需計(jì)算1個(gè)函數(shù)值，程序簡(jiǎn)單容易實(shí)現(xiàn)而被廣泛采用．由于黃金分割法是以等比例0.618分割縮小區(qū)間的，因此，針對(duì)在實(shí)際問(wèn)題中遇到的目標(biāo)函數(shù)往往不是單峰函數(shù)的情況，它是一種近似最優(yōu)方法．

3 案例分析

以上海軌道交通網(wǎng)絡(luò)為例，對(duì)本研究提出的城市軌道交通行車(chē)計(jì)劃銜接優(yōu)化算法進(jìn)行分析驗(yàn)算，以平峰時(shí)期(如13∶00—15∶00)的列車(chē)銜接進(jìn)行說(shuō)明．實(shí)例分析中所需的數(shù)據(jù)如下：

1) AFC刷卡數(shù)據(jù)．選用2014-12-09的客流刷卡數(shù)據(jù)，其中選用時(shí)間段13∶00—15∶00的客流，共有1 386 402條配對(duì)好的進(jìn)出站AFC刷卡數(shù)據(jù)．

2) 清分比例表．共有119 918個(gè)起終點(diǎn)(origin destination, OD)對(duì)，總共有288 200條路徑．

3) 換乘走行時(shí)間．各換乘站各換乘方向的步行時(shí)間，可從上海軌道交通運(yùn)營(yíng)公司票務(wù)部門(mén)獲?。?/p>

3.1 換乘方向排序

按照換乘站換乘客流大小進(jìn)行排序，可得如表1的換乘銜接方向．

表1 平峰時(shí)期排序后換乘銜接方向示例Table 1 Examples of transfer connection direction ordered by passenger flow during flat period

3.2 優(yōu)化求解

利用C#.Net程序語(yǔ)言對(duì)本節(jié)提出的模型與算法進(jìn)行編程求解，按排序后的換乘銜接方向?qū)Q乘站換乘方向進(jìn)行銜接優(yōu)化，優(yōu)化后進(jìn)行標(biāo)號(hào)，并依次處理余下?lián)Q乘銜接方向，直至所有換乘銜接方向均已優(yōu)化．優(yōu)化過(guò)程如圖4，其表示隨程序求解步驟的推進(jìn)，當(dāng)前狀態(tài)下網(wǎng)絡(luò)平均換乘等待時(shí)間的改變程度．圖中x軸表示程序求解步驟，即當(dāng)前計(jì)算到排序后換乘銜接方向的順序；y軸表示當(dāng)前網(wǎng)絡(luò)中已確定的模型決策變量數(shù)，包括列車(chē)開(kāi)行間隔和首列到達(dá)時(shí)刻．圖中數(shù)據(jù)散點(diǎn)圓的半徑大小表示當(dāng)前狀態(tài)下網(wǎng)絡(luò)平均換乘等待時(shí)間．?dāng)?shù)據(jù)點(diǎn)的大小隨求解步驟的推移先增后減，說(shuō)明隨著換乘銜接方向的不斷優(yōu)化，乘客的平均換乘等待時(shí)間越來(lái)越優(yōu)．

需指出，在圖4程序求解步驟的后期，出現(xiàn)較長(zhǎng)時(shí)間空白，原因在于該迭代時(shí)間點(diǎn)，換乘銜接的變量均在前面的求解步驟中被標(biāo)定過(guò)，此步驟中無(wú)決策變量可求解，因此出現(xiàn)該數(shù)據(jù)點(diǎn)上的空白．

圖4 求解代數(shù)-平均等待時(shí)間圖Fig.4 Diagram of solving steps and average passenger waiting time

3.3 求解結(jié)果

最終獲得所有換乘站換乘方向的銜接方案結(jié)果如表2．可見(jiàn)，平峰時(shí)段上海軌道交通1、2、4、5及11號(hào)線，由于存在換乘客流大的換乘站，其列車(chē)開(kāi)行間隔優(yōu)先得到銜接滿(mǎn)足，而3、12、13及16號(hào)線，由于其中的換乘站客流較小，其列車(chē)開(kāi)行計(jì)劃主要用于銜接其他線路．此外，表2還顯示，平峰時(shí)段線路上下行的列車(chē)開(kāi)行間隔均保持相同，并且多條線路的開(kāi)行間隔由于換乘銜接關(guān)系的密切，列車(chē)開(kāi)行間隔呈相同或倍數(shù)的關(guān)系．同理，幾個(gè)重要的換乘站首列到達(dá)時(shí)刻如表3．

表2 優(yōu)化后各線路開(kāi)行間隔Table 2 Train interval of metro lines after optimization s

表 3 優(yōu)化后各換乘站首列列車(chē)到達(dá)時(shí)間示例Table 3 First train arrival time of metro lines after optimization s

3.4 結(jié)果分析

本文研究時(shí)段為平峰時(shí)間段13∶00—15∶00，共計(jì)2 h，經(jīng)計(jì)算共有換乘客流226 726人次，在未銜接優(yōu)化之前，各線獨(dú)立運(yùn)營(yíng)，未考慮相互之間的銜接關(guān)系，乘客的平均換乘等待時(shí)間為128.9 s．經(jīng)優(yōu)化銜接后，乘客的平均換乘等待時(shí)間為93.9 s，較之前平均減少換乘等待時(shí)間約27.1%，優(yōu)化后的網(wǎng)絡(luò)整體銜接效果較之前有一定提升．由此可見(jiàn)，通過(guò)調(diào)整線路間的換乘銜接關(guān)系，優(yōu)化城市軌道交通網(wǎng)絡(luò)整體銜接程度，可使乘客的平均換乘等待時(shí)間縮短，提升乘客出行效率，為網(wǎng)絡(luò)上的出行乘客提供優(yōu)質(zhì)的客運(yùn)服務(wù)．

結(jié) 語(yǔ)

本研究探討常規(guī)時(shí)間下的城市軌道交通網(wǎng)絡(luò)行車(chē)計(jì)劃銜接優(yōu)化問(wèn)題，模型通過(guò)優(yōu)化列車(chē)的開(kāi)行間隔與列車(chē)的首列到達(dá)時(shí)刻，使乘客換乘站的總平均等待時(shí)間最短．建模中提出主動(dòng)銜接和被動(dòng)銜接概念，并利用它們計(jì)算換乘方向的總平均等待時(shí)間，并設(shè)計(jì)基于逐步優(yōu)化的算法來(lái)解該模型．通過(guò)案例分析說(shuō)明，本算法求解過(guò)程思路清晰，易于實(shí)現(xiàn)，能夠優(yōu)先匹配換乘客流量大的換乘銜接方向．且得出換乘銜接中，不同線路的列車(chē)開(kāi)行間隔呈現(xiàn)相同或者倍數(shù)的關(guān)系，網(wǎng)絡(luò)的整體銜接程度較優(yōu)．