城市軌道交通列車運行圖魯棒性優(yōu)化模型

曹志超, 袁振洲 , 李得偉, 張思林, 馬伶伶

(1.北京交通大學 城市交通復雜系統(tǒng)理論與技術(shù)教育部重點實驗室，北京　100044；2.北京交通大學 軌道交通控制與安全國家重點實驗室，北京　100044；3.中國民航大學 民航空管研究院，天津　300300)

隨著城市軌道交通技術(shù)裝備水平的提高，以及為滿足乘客出行要求，客流高峰時段高密度行車已成為城市軌道交通運輸?shù)闹匾卣?。例如，北京市城市軌道交通在移動信號閉塞系統(tǒng)[1]下已實現(xiàn)90 s的列車發(fā)車間隔。但是，在高密度行車條件下列車一旦晚點，對整個路網(wǎng)的運輸組織會產(chǎn)生很大的影響。因此，如何在計劃階段通過調(diào)整列車運行圖以減小此影響，從而實現(xiàn)城市軌道交通列車運行圖抗干擾性(即魯棒性)的優(yōu)化，是高密度行車條件下列車運行計劃編制和調(diào)整的重要目標。

傳統(tǒng)的列車運行圖優(yōu)化模型較少考慮為滿足客流需求而導致的隨機干擾，缺乏魯棒性優(yōu)化的空間。國內(nèi)學者對計劃階段運營管理的研究重點多集中在列車開行方案上，對城市軌道交通列車運行圖研究較少。文獻[2]提出以平峰時段換乘客流總等待時間最少為目標的網(wǎng)絡周期運行圖編制方法；文獻[3]提出以列車總旅行時間最少和使用動車組車底數(shù)最少為目標的高速鐵路周期性運行圖優(yōu)化模型；文獻[4]研究了城市軌道交通車底運用方式、列車發(fā)車間隔和首末班車銜接方案等共線交路列車運行圖鋪畫的關(guān)鍵問題；文獻[5]提出以鐵路企業(yè)效益最大化為目標的旅客列車開行方案和運行圖綜合優(yōu)化的雙層規(guī)劃模型；文獻[6]提出2種不同恢復方法的列車運行圖可恢復魯棒性的優(yōu)化模型；文獻[7]提出采用“時間控制點法(Time-control strategy)”提高公交開行計劃魯棒性的優(yōu)化模型。以上研究為準確理解列車運行圖編制問題提供了重要的研究基礎。完成城市軌道交通列車運行圖的編制需要以下3個基本步驟。

(1)確定列車的發(fā)車頻率或發(fā)車間隔；

(2)規(guī)定列車的開行區(qū)段、折返交路和停站方案；

(3)確定列車的出發(fā)時刻、到達時刻、緩沖時間(Buffer-time)、區(qū)間運行時間。

基于以上背景，本文以步驟(3)為研究目標，考慮乘客在車站的等待行為和列車的交互關(guān)系，以城市軌道交通列車運行圖擾動時間之和最小化為目標，構(gòu)建滿足客流需求的城市軌道交通列車運行圖魯棒性優(yōu)化模型，并提出求解算法。

1　問題描述

城市軌道交通列車運行圖之所以受到干擾，不能按計劃時間開車，除設備技術(shù)故障外，很大程度上是由于客流高峰時段內(nèi)乘客持續(xù)上車，使列車車門無法關(guān)閉而導致列車出發(fā)時刻延誤，進而產(chǎn)生列車晚點。如果列車運行圖的魯棒性差，還將導致列車晚點傳播范圍增大，甚至有些列車停運。

本文的研究思路為：在計劃層的列車運行時段內(nèi)，調(diào)整列車緩沖時間，以優(yōu)化列車運行圖的魯棒性。其中如何確定站間的緩沖時間是優(yōu)化列車運行圖魯棒性的關(guān)鍵。因為如果緩沖時間過長，勢必會延長乘客在途時間，降低列車發(fā)車頻率；但緩沖時間過短，又無法提高列車運行圖的抗干擾能力。

本文首先詳述列車運行組織計劃的約束，然后在考慮列車載客能力的情況下，基于歷史客流數(shù)據(jù)并通過候車乘客與列車的交互關(guān)系確定列車的實際停站時間，最后基于列車運行圖擾動時間的遞推關(guān)系進行建模。

為方便建模，對列車的運行特征作如下假設。

(1)基于文獻[8]的假設，以城市軌道交通單一線路為研究對象，并采用站站停的停站方案。

(2)根據(jù)國內(nèi)外城市軌道交通運營實踐，采用2站式的長交路運行，即始發(fā)站1為車輛段所在站，終到站n為列車折返站。

(3)所有列車編組一致，即列車具有相同的載客能力(列車內(nèi)的座位數(shù)與可容納站立人數(shù)之和)，并用C表示，人·列-1。

(4)每個車站同時僅能容納1列列車，全線不允許有列車越行。

(5)列車站間運行包括3個階段：起動加速階段、勻速運行階段和制動減速階段。

2　模型構(gòu)建

令城市軌道交通線路網(wǎng)絡N=(J,E)，其中J={1,2,…,j-1,j,…,n}為車站集；E={e(j-1,j)|j∈J}為區(qū)間集，區(qū)間e(j-1,j)∈E為車站j-1與相鄰車站j之間的區(qū)間；區(qū)間e(j-1,j)的里程長度(簡稱站間距)記為l(j-1,j)，m。

2.1　列車運行組織計劃約束

設在運營時段[t0,te]內(nèi)計劃開行的列車的集合為I={1,2,…,i-1,i,…,m}。

在E上的列車計劃出發(fā)時刻需滿足安全追蹤間隔時間的約束，即

(1)

根據(jù)假設(4)和(5)，列車運行圖中任意一班列車的計劃到達和出發(fā)時刻存在如下關(guān)系。

(2)

(3)

(4)

由于有

因此將上述公式帶入式(4)后可得

(5)

列車勻速運行速度vi,j-1,j應滿足

(6)

(7)

2.2　乘客和列車的交互關(guān)系約束

在車站j等待乘坐列車i的客流量Wi,j為

(8)

其中，

(9)

式中：Wi,j,k為在車站j等待乘坐列車i前往車站k∈J的客流量，人；Li-1,j,k為因上一班列車i-1滿員而滯留在車站j的打算前往車站k的客流量，人；λj,k為從車站j出發(fā)前往車站k的客流到達率，人·s-1。

列車i在車站j的下車客流量Ui,j為

(10)

其中，

Ui,f,j=Wi,f,j-Li,f,j

(11)

式中：Ui,f,j為列車i上在車站f上車且在車站j下車的客流量，人。

列車i在離開車站j時，車內(nèi)客流量Qi,j為

Qi,j=Qi,j-1-Ui,j+Bi,j

(12)

其中，

(13)

(14)

在客流高峰時段，由于受列車載客能力的限制，列車i在車站j滯留的客流量Li,j為

(15)

Li,j還可以由下式得到，即

(16)

(17)

式中：β1，β2，β3，β4分別為擬合參數(shù)；d為每列車上下乘客的車門數(shù)量，個·列-1。

2.3　列車運行圖魯棒性約束

(18)

其中，

(19)

圖1　列車運行圖擾動時間

(20)

式中：δi,j-1,j為列車i在區(qū)間e(j-1,j)的可恢復因子，0≤δi,j-1,j≤1，令δi,1,2=0，即列車i在始發(fā)站正點出發(fā)。

(21)

類似式(2)和式(3)，列車i在車站j的實際出發(fā)時刻為

(22)

(23)

基于式(18)，上式可進一步寫成

(24)

因為列車在始發(fā)站正點發(fā)車，那么

(25)

如果令

因為t和τ可根據(jù)歷史客流量數(shù)據(jù)計算得到，δ為經(jīng)驗取值變量，所以將t，τ，δ作為輸入變量，而緩沖時間x則為輸出結(jié)果。

2.4　優(yōu)化模型

(26)

γ1和γ2可通過列車實際運行數(shù)據(jù)進行標定。

以式(1)—式(26)為約束條件，列車運行圖的擾動時間之和最小化為目標，構(gòu)建的城市軌道交通列車運行圖魯棒性優(yōu)化模型為

(27)

3　求解算法

優(yōu)化模型為單目標非線性混合整數(shù)規(guī)劃模型，主要通過調(diào)整緩沖時間實現(xiàn)列車運行圖擾動時間之和最小，從而使列車的計劃出發(fā)時刻與實際出發(fā)時刻盡可能一致。由于模型中需要輸入的變量較多，直接求解具有很大難度，因此本文采用改進的遺傳算法和計算機模擬的方法進行求解，其總體思路是首先將復雜的非線性規(guī)劃問題通過遞推公式轉(zhuǎn)化為線性規(guī)劃問題，然后通過迭代求最優(yōu)解，當在限定的時間和迭代次數(shù)內(nèi)目標函數(shù)值不再優(yōu)化時，則認為得到的解為最優(yōu)解或較優(yōu)解。具體步驟如下。

步驟2基因設置。以列車i在區(qū)間e(j-1,j)的緩沖時間xi,j-1,j作為基因，因模型僅考慮單線單方向，則基因按順序排列的集合(即染色體)為模型的解集{xi,j-1,j|i∈I,j∈J}。

步驟3求解優(yōu)化模型。基于式(27)和遺傳算法的求解特點，優(yōu)化模型又可寫為

(28)

步驟4最優(yōu)解。在限定的時間或迭代次數(shù)內(nèi)，最優(yōu)解已收斂且不能更優(yōu)，則找到最優(yōu)解的解集{xi,j-1,j,i∈I,j∈J}，運算終止。

4　算　例

北京市城市軌道交通房山線共設有10個車站，列車的技術(shù)參數(shù)見表1，區(qū)間集E的運營參數(shù)見表2所示，下行客流OD的到達規(guī)律見表3，車站集J中各列車的實際停站時間見表4。選取1 h的研究時段并且針對γ1和γ2取不同值的3個算例，利用Matlab對問題進行描述，并根據(jù)本文模型和算法對該線下行列車的運行圖進行魯棒性優(yōu)化，優(yōu)化結(jié)果見表5。對表5中數(shù)據(jù)進行絕對值求和，得到表6。

表1　列車技術(shù)參數(shù)

表2　區(qū)間集E的運營參數(shù)

表3　下行客流OD的到達規(guī)律　人·s-1

表4　列車在各站停站時間　s

由表5和表6可得出以下結(jié)論：

(1)算例1表明模型對發(fā)車晚點和發(fā)車提前的懲罰一致，列車運行圖魯棒性可恢復時間(以下簡稱：可恢復時間)最短，為209 s，計劃運行的總時間為2 971 s；

(2)算例2表明模型對發(fā)車晚點的懲罰小于發(fā)車提前，可恢復時間最長，為253 s，但計劃運行的總時間最短，為2 951 s；

(3)算例3表明模型對發(fā)車晚點的懲罰大于發(fā)車提前，可恢復時間為231 s，但計劃運行的總時間最長，為3 053 s。

表5中的計算結(jié)果可直接轉(zhuǎn)化為該線的列車運行圖或列車時刻表形式。例如，假設列車在始發(fā)站(郭公莊站)的出發(fā)時刻為15:30:00，則列車時刻表見表7。

表5　優(yōu)化結(jié)果　s

表6　列車運行圖魯棒性恢復時間　s

表7　列車時刻表

5　模型的擴展

在城市軌道交通列車運行時段內(nèi)，可能出現(xiàn)無法保證在每個車站都能準點發(fā)車的情況。當運營部門只要求大型樞紐站等重要車站準點發(fā)車即可時，本文在既有模型的基礎上，提出“時間控制點法”來實現(xiàn)指定車站發(fā)車準點的目標，以提高規(guī)定區(qū)段內(nèi)的列車運行圖魯棒性。

時間控制點法的思想是在計劃層同時間軸條件下引入虛擬層，如圖2所示。虛擬層每個時間控制點對應準點率要求高的車站，時間控制點對應的車站集合R?J，旨在形成時間控制點區(qū)段內(nèi)包含多個區(qū)間的形式，即列車在時間控制點間的運行時間等于列車在多個區(qū)間運行的時間之和。

圖2　時間控制點示意圖

表8　時間控制法的求解結(jié)果 s

6　結(jié)束語

本文以城市軌道交通列車運行圖擾動時間之和最小化為目標，構(gòu)建了城市軌道交通列車運行圖魯棒性優(yōu)化模型，通過改進的遺傳算法對問題進行求解。通過模型分析發(fā)現(xiàn)，不同懲罰參數(shù)的取值對列車運行圖魯棒性的影響較大，需根據(jù)實際問題對參數(shù)進行標定。以北京市城市軌道交通房山線為例，優(yōu)化后的列車運行圖有效縮短了總擾動時間，證明了本文方法能夠有效提高列車運行圖的魯棒性。

本文還擴展了城市軌道交通列車運行圖魯棒性優(yōu)化模型的應用場景，引入時間控制點變量，可實現(xiàn)約束不變的情況下，提高指定車站發(fā)車準點率的目標，優(yōu)化規(guī)定區(qū)段內(nèi)的列車運行圖魯棒性。

[1]TAKEUCHI H, GOODMAN C, SONE S.Moving Block Signaling Dynamics: Performance Measures and Re-Starting Queued Electric Trains[J]. IEE Proceedings on Electric Power Applications, 2003, 150(4)：483-492.

[2]汪波, 韓寶明, 戰(zhàn)明輝, 等. 城市軌道交通網(wǎng)絡周期運行圖編制研究[J]. 鐵道學報, 2013, 35(4): 9-15.

(WANG Bo, HAN Baoming, ZHAN Minghui，et al. Study on Formulation of Periodic Train Diagram of Urban Rail Transit Network[J]. Journal of the China Railway Society, 2013, 35(4): 9-15. in Chinese)

[3]聶磊, 張淵, 武鑫. 計算機編制周期性列車運行圖關(guān)鍵技術(shù)[J]. 中國鐵道科學, 2014, 35(1): 114-121.

(NIE Lei, ZHANG Yuan, WU Xin. Key Technologies for Computer Generation of Cyclic Train Timetable[J]. China Railway Science, 2014, 35(1): 114-121. in Chinese)

[4]江志彬, 徐瑞華, 吳強, 等. 計算機編制城市軌道交通共線交路列車運行圖[J]. 同濟大學學報:自然科學版, 2010, 38(5): 692-696.

(JIANG Zhibin, XU Ruihua, WU Qiang, et al. Shared-Path Routing Timetable Computer Designing in Rail Transit System[J]. Journal of Tongji University:Natural Science, 2010, 38(5): 692-696. in Chinese)

[5]周文梁,史峰, 陳彥,等. 客運專線網(wǎng)絡列車開行方案與運行圖綜合優(yōu)化方法[J]. 鐵道學報, 2011, 33(2):1-7.

(ZHOU Wenliang, SHI Feng, CHEN Yan, et al. Method of Integrated Optimization of Train Operation Plan and Diagram for Network of Dedicated Passenger Lines[J]. Journal of the China Railway Society, 2011, 33(2):1-7. in Chinese)

[6]劉敏, 韓寶明. 列車運行圖可恢復魯棒性優(yōu)化模型[J]. 鐵道學報, 2013, 35(10):1-8.

(LIU Ming, HAN Maobing. Recoverable Robust Timetabling Models for Railways[J]. Journal of the China Railway Society, 2013, 35(10):1-8. in Chinese)

[7]YAN Y, MENG Q, WANG S, et al. Robust Optimization Model of Schedule Design for a Fixed Bus Route[J]. Transportation Research Part C: Emerging Technologies, 2012, 25: 113-121.

[8]鄧連波, 曾強, 高偉, 等. 基于彈性需求的城市軌道交通列車開行方案研究[J]. 鐵道學報, 2012, 34(12):16-25.

(DENG Lianbo, ZENG Qiang, GAO Wei, et al. Research on Train Plan of Urban Rail Transit with Elastic Demand[J]. Journal of the China Railway Society, 2012, 34(12):16-25. in Chinese)

[9]WANG Y, DE S B, VAN D B T J J, et al. Efficient Bilevel Approach for Urban Rail Transit Operation with Stop-Skipping[J]. IEEE Transactions on Intelligent Transportation Systems, 2014, 15(6):2658-2670.