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

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

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

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

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

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

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

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

1　問題描述

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

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

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

為方便建模，對(duì)列車的運(yùn)行特征作如下假設(shè)。

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

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

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

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

(5)列車站間運(yùn)行包括3個(gè)階段：起動(dòng)加速階段、勻速運(yùn)行階段和制動(dòng)減速階段。

2　模型構(gòu)建

令城市軌道交通線路網(wǎng)絡(luò)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)的里程長(zhǎng)度(簡(jiǎn)稱站間距)記為l(j-1,j)，m。

2.1　列車運(yùn)行組織計(jì)劃約束

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

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

(1)

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

(2)

(3)

(4)

由于有

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

(5)

列車勻速運(yùn)行速度vi,j-1,j應(yīng)滿足

(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的客流到達(dá)率，人·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時(shí)，車內(nèi)客流量Qi,j為

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

(12)

其中，

(13)

(14)

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

(15)

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

(16)

(17)

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

2.3　列車運(yùn)行圖魯棒性約束

(18)

其中，

(19)

圖1　列車運(yùn)行圖擾動(dòng)時(shí)間

(20)

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

(21)

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

(22)

(23)

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

(24)

因?yàn)榱熊囋谑及l(fā)站正點(diǎn)發(fā)車，那么

(25)

如果令

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

2.4　優(yōu)化模型

(26)

γ1和γ2可通過(guò)列車實(shí)際運(yùn)行數(shù)據(jù)進(jìn)行標(biāo)定。

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

(27)

3　求解算法

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

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

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

(28)

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

4　算　例

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

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

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

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

表4　列車在各站停站時(shí)間　s

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

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

(2)算例2表明模型對(duì)發(fā)車晚點(diǎn)的懲罰小于發(fā)車提前，可恢復(fù)時(shí)間最長(zhǎng)，為253 s，但計(jì)劃運(yùn)行的總時(shí)間最短，為2 951 s；

(3)算例3表明模型對(duì)發(fā)車晚點(diǎn)的懲罰大于發(fā)車提前，可恢復(fù)時(shí)間為231 s，但計(jì)劃運(yùn)行的總時(shí)間最長(zhǎng)，為3 053 s。

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

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

表6　列車運(yùn)行圖魯棒性恢復(fù)時(shí)間　s

表7　列車時(shí)刻表

5　模型的擴(kuò)展

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

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

圖2　時(shí)間控制點(diǎn)示意圖

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

6　結(jié)束語(yǔ)

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

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

[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)絡(luò)周期運(yùn)行圖編制研究[J]. 鐵道學(xué)報(bào), 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]聶磊, 張淵, 武鑫. 計(jì)算機(jī)編制周期性列車運(yùn)行圖關(guān)鍵技術(shù)[J]. 中國(guó)鐵道科學(xué), 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]江志彬, 徐瑞華, 吳強(qiáng), 等. 計(jì)算機(jī)編制城市軌道交通共線交路列車運(yùn)行圖[J]. 同濟(jì)大學(xué)學(xué)報(bào):自然科學(xué)版, 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]周文梁,史峰, 陳彥,等. 客運(yùn)專線網(wǎng)絡(luò)列車開行方案與運(yùn)行圖綜合優(yōu)化方法[J]. 鐵道學(xué)報(bào), 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ùn)行圖可恢復(fù)魯棒性優(yōu)化模型[J]. 鐵道學(xué)報(bào), 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]鄧連波, 曾強(qiáng), 高偉, 等. 基于彈性需求的城市軌道交通列車開行方案研究[J]. 鐵道學(xué)報(bào), 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.