何占元,陰佳騰,王明主

(1.朔黃鐵路發(fā)展有限責(zé)任公司,河北 肅寧 062350;2.北京交通大學(xué) 軌道交通控制與安全國家重點實驗室,北京 100044;3.北京交通大學(xué) 電子信息工程學(xué)院,北京 100044)

在過去,城市軌道交通的客運需求相對現(xiàn)在而言較小,城軌列車之間的追蹤間隔較大,這種情況下學(xué)者們普遍認為城市軌道交通由于線路網(wǎng)絡(luò)結(jié)構(gòu)單一、列車運行交路固定、列車運行速度較低,在本質(zhì)上屬于一種簡化的干線鐵路,可以將干線鐵路的列車實時調(diào)度方法直接用于城市軌道交通的列車實時調(diào)度調(diào)整,因此過去的列車調(diào)度研究主要針對于干線鐵路或高速鐵路[1][2],專門針對城市軌道交通列車調(diào)度調(diào)整的文獻研究相對較少。近年來,隨著城市規(guī)模擴大、人口增多,城市軌道交通迅速發(fā)展,城市軌道交通系統(tǒng)呈現(xiàn)了網(wǎng)絡(luò)化、大客流以及高密度運行的趨勢,從列車延誤產(chǎn)生原因、延誤傳播規(guī)律和調(diào)整方法上講,都已經(jīng)與傳統(tǒng)的干線(或高速)鐵路產(chǎn)生了很大的差異。因此近年來很多國內(nèi)外學(xué)者開始關(guān)注城市軌道交通的列車行車調(diào)度和調(diào)整問題[3]。

從延誤產(chǎn)生原因上講,當(dāng)前城市軌道交通中列車運行延誤主要由設(shè)備故障(線路設(shè)備、信號設(shè)備、供電設(shè)備和車輛設(shè)備等)、人為原因(如司機誤操作、突發(fā)大客流、乘客跳下站臺等)和其他突發(fā)故障(如極端天氣、火災(zāi)、恐怖襲擊等)三類構(gòu)成?？傮w上來說,設(shè)備和人為故障占到了日常運營管理中的絕大部分,約占到90%以上,設(shè)備和人為原因占的比率與每條地鐵線路的實際運營情況和設(shè)備可靠度有關(guān)。比如,倫敦地鐵沒有加裝屏蔽門(Platform Screen Doors, PSD)系統(tǒng),因此經(jīng)常出現(xiàn)人為原因(如乘客隨身物品落入軌道)導(dǎo)致列車突發(fā)停車產(chǎn)生延誤;北京地鐵2號線于2017年上半年剛剛加裝屏蔽門系統(tǒng),試運行期間系統(tǒng)可靠性相對較差,出現(xiàn)多起屏蔽門故障而導(dǎo)致的列車延誤情況。

城市軌道交通系統(tǒng)中存車線是輔助線的一種,主要用于備用列車、故障列車的存放。合理使用存車線的備車能為運營組織創(chuàng)造方便、靈活的調(diào)整手段[4]。現(xiàn)有幾乎所有的軌道交通線路,包括北京地鐵、上海地鐵等,都在線路中設(shè)計了若干條存車線。如圖1所示,在城市軌道交通線路中存車線可以設(shè)置于兩個車站之間的運行區(qū)間內(nèi),在存車線中可以存放一輛備車,如果線路中出現(xiàn)嚴(yán)重故障導(dǎo)致列車運行間隔不均時,可以通過加開備車的方式彌補線上運能的不足,盡快疏散站臺滯留乘客。通常情況下,備車可以根據(jù)不同的線路布局通過多種路徑(Route)進入正線?！疤！眲t指的是列車在經(jīng)過站臺時組織列車以不停站的方式通過站臺(也稱越站),通常用于故障消除后,列車為恢復(fù)至正常運行圖而進行的“趕點”運行,跳停對于恢復(fù)至初始運行圖非常有效。實際中,結(jié)合以上兩種調(diào)度方式,在遇到突發(fā)故障或列車延誤時,能夠迅速得到并及時實施最優(yōu)的列車調(diào)度方案,以降低故障或運行延誤對乘客的服務(wù)質(zhì)量造成的影響,并能盡快使軌道交通系統(tǒng)恢復(fù)至正常的運營秩序與性能指標(biāo)。

圖1 考慮存車線的軌道交通線路拓撲結(jié)構(gòu)示意圖Fig.1 A schematic diagram of the topological structure of rail transit lines considering car storage lines

本文在以上背景下建立基于混合整數(shù)線性規(guī)劃(Mixed integer linear programming, MILP)的數(shù)學(xué)模型,結(jié)合“跳?！焙汀凹娱_備車”兩種常用的行車調(diào)度手段,用以優(yōu)化故障場景下的列車運行圖調(diào)整方案,以提高線路的故障恢復(fù)能力,盡快疏散因線路故障而滯留的乘客。

1 問題描述

本文中我們用KE={1,2,…ke}表示正線運行的列車集合;KA={1,2,…ka}表示存車線備車的集合;KF={1,2,…kf}表示故障后從車輛段發(fā)車、進入正線運營的列車集合。在故障結(jié)束、線路恢復(fù)運行時,本章所考慮問題就是對正線列車、存車線備車和車輛段列車的運行計劃重新進行調(diào)整,通過跳停的策略使線路快速恢復(fù)至正常運行秩序(如圖2所示)。

圖2 考慮跳停和加開備車的列車運行圖調(diào)整Fig.2 Train rescheduling based on stop-skipping and backup trains

1.1 本文基本假設(shè)

根據(jù)城市軌道交通系統(tǒng)的實際運營特點,本文研究的模型和方法主要基于以下假設(shè):

假設(shè)1:列車運行調(diào)整過程中可以采用“跳?！辈呗?即在某些車站直接通過不停車。跳停策略能夠在一定程度上緩解站臺客流擁堵情況、降低乘客平均等待時間。

假設(shè)2:軌道交通線路設(shè)計了若干條存車線,并且存車線中事先存儲了備車可用于應(yīng)急情況下的列車運行調(diào)整。實際中運營公司可以根據(jù)體育賽事或節(jié)假日等預(yù)測客流信息,在運營前的天窗期將備車置于存車線。

1.2 符號和變量表示

為方便對考慮問題的建模,表1中統(tǒng)一列出了本文使用的參數(shù)和符號的定義。

表1 本文使用的符號和定義Tab.1 The symbols and definitions

續(xù)表1

符號定義Sk列車k需要經(jīng)過的車站集合i,j車站索引,i∈SkSt禁止跳停的車站集合,St?SST折返站索引Tturn列車折返所需時間dmaxi列車在車站最大站停時間dmini列車在車站最小站停時間hmin列車最小追蹤間距ri+1,i車站i與i+1之間的計劃運行時間

本文的決策變量包括以下幾部分:

nk,i列車k是否在i站跳停(0-1變量)。對于任意k∈KE∪KF∪KA,i∈SSt,如果列車在i站跳停,則nk,i=1;否則nk,i=0

xk,i列車k到達車站i的時間(整數(shù)變量)

yk,i列車k離開車站i的時間(整數(shù)變量)

zk,l列車運行次序(0-1變量)。對于任意l∈KA,k∈KE∪KF,如果列車k先于列車l, 則zk,l=1;否則zk,l=0

pk,l列車運行次序(0-1變量)。對任意k,l∈KA,如列車k先于列車l, 則pk,l=1; 否則pk,l=0.

首先我們以圖1為例來解釋數(shù)學(xué)模型中的符號和變量定義。圖1中的軌道交通線路包括八個車站,可得|S|=8表示車站集合中的元素數(shù)量為8. 線路中有兩個存車線,分別位于車站1和2、車站6和7之間。為了便于理解,這里我們假設(shè)車站3的供電系統(tǒng)出現(xiàn)故障導(dǎo)致列車無法發(fā)車、后續(xù)車輛無法進入車站。故障于t0時刻結(jié)束,車站3恢復(fù)發(fā)車能力。此時由于列車延誤導(dǎo)致車站中大量乘客滯留,因此需要啟用存車線中的備車來盡快恢復(fù)線路運力。本文中我們考慮了三種列車類型:第一種是正線運行列車(即集合KE),這些列車在故障結(jié)束時于正線運行,如正線列車1、正線列車2;第二種是存車線的備車(即集合KA),如圖1所示的備車1和備車2可以從側(cè)線分別駛?cè)胲囌?和車站6;第三種列車在故障結(jié)束后從車輛段發(fā)車、進入正線運營(即集合KF)。在本文考慮的列車運行調(diào)整問題中,正線列車和備車按照既有路徑從當(dāng)前車站開始運行,因此對于每一輛列車k我們定義集合Sk表示列車將要運行的路徑。比如,圖1中的正線列車2對應(yīng)集合Sk={2,3,4,5,6,7,8},表示正線列車2將依次經(jīng)過車站2,3,4…,8;備車2對應(yīng)Sk={7,8},表示備車2將依次經(jīng)過車站7和車站8。假設(shè)計劃運行圖所規(guī)定的列車運行次序為K={e1,e2,…,f1,f2,…}, 在列車運行調(diào)整過程加入備車a1和a2后,備車位置不同會產(chǎn)生多種可行的列車運行次序,例如K={e1,a1,e2,…,f1,f2,a2,…}或者K={e1,e2,a1,…,f1,f2,a2,…}等等。因此,在使用備車的情況下如何優(yōu)化列車之間的運行次序也是本文解決的問題。為此我們定義變量zk,l表示正線列車與備車之間的次序;并且定義pk,l表示備車之間的先后次序,以這種方式可以將所有列車的運行次序完備地表示出來。

1.3 模型約束

下面介紹數(shù)學(xué)模型的基本約束,包括列車運行時分約束、站停時分約束、運行間隔約束、折返約束和運行次序約束等。

約束一:運行時分約束

xk,i+1-yk,i≤ri+1,i,?k∈KE∪KF∪KA,i,i+1∈Sk

(1)

其中ri+1,i表示列車在車站i+1與車站i之間的最短運行時分,對應(yīng)列車在區(qū)間使用最大速度曲線得到的運行時分。

約束二:列車跳停與站停約束

(2)

?k∈KE∪KF∪KAi∈Sk

(3)

yk,i-xk,i≤M×(1-nk,i)

?k∈KE∪KF∪KAi∈Sk

(4)

約束三:列車運行間隔約束

列車運行間隔約束用來確保列車的運行間隔在一個合適的范圍,從而避免前后列車相撞或ATP緊急制動。在正常情況下列車的發(fā)車次序不變,可以分別定義前后兩兩列車之間的安全間隔。本文由于考慮了三種類型列車,列車之間的運行次序可能發(fā)生改變,因此我們將列車運行分為如下四種情況分別定義其運行間隔約束:

(1)正線列車運行間隔約束

yk+1,i-yk,i≥hmin?k∈KE∪KF,i∈Sk

(5)

xk+1,i-xk,i≥hmin?k∈KE∪KF,i∈Sk

(6)

由于本文不考慮列車的越行,因此正線列車和車輛段列車的次序保證不變。以上兩組約束定義了正線列車和車輛段的列車按照計劃運行圖保證運行間隔。

(2)正線列車與備車之間的運行間隔約束

如果zk,l=1,則模型中加入下面的約束:

?i∈Sl,k,k+1∈KE∪KF,l∈KA

(7)

以上約束表示,由zk,l=1可知備車l的次序是在列車k和k+1之間。因此式(7)確保備車列車l與列車k和k+1之間保持一定的運行間隔。

(3)備車與備車之間的運行間隔約束

如果pk,l=1,則模型中加入下面的約束:

yl,i-yk,i≥hmin?i∈Sl∪Sk,k,l∈KA

(8)

以上約束表示備車k和備車l之間也需要滿足運行間隔約束。

約束四:列車運行次序約束

下面一組約束規(guī)定了是否在調(diào)整中使用備車。如果調(diào)度員希望使用所有存車線中的備車,則對于每輛備車l∈KA定義如下約束。

(9)

此外,決策變量pk,l也需要滿足一定的約束,來保證備車之間合理的運行次序。

(10)

(11)

pk,l=0 ?k,l∈KA,k=l

(12)

公式(9)表示,每一輛備車k至多只有一輛備車l追蹤;公式(12)表示,對于一輛列車k自身,其運行次序變量pk,l=0.

圖3給出了一個簡單的例子用于直觀地說明以上的約束。該例子中考慮了三輛備車、三輛正線運營列車以及四輛車輛段列車。從運行圖中可以看出,三輛備車分別于正線列車1、正線列車2和車輛段列車3之后發(fā)車,根據(jù)這種運行次序可知變量zke1,1=1,zke2,2=1,zkf3,3=1, 其中ke1,ke2,kf3分別表示正線列車1、正線列車2和車輛段列車3。此外,根據(jù)三輛備車的運行次序我們也可以得到p1,2=1以及p2,3=1.

約束五:列車折返約束

yk,i+1-yk,i=Tturn

?k∈KE∪KF∪KA,i=ST

(13)

列車折返約束限制了列車在折返站的折返時間。

圖3 考慮存車線的雙向軌道交通運行線Fig.3 Bi-directional rail transitline based on car storage line

1.4 模型目標(biāo)函數(shù)構(gòu)建

接下來考慮構(gòu)建模型的目標(biāo)函數(shù)。本文所考慮的基本問題是故障修復(fù)、線路恢復(fù)正常運營時間段,此時行車調(diào)度的主要目的是盡快疏散站臺滯留的乘客,維持正常的列車運行秩序。在考慮備車的情況下,本文的主要優(yōu)化目標(biāo)是盡可能保證列車運行安全的情況下提高線路運力、增大發(fā)車頻次。因此本文將列車到達終點站的時間總和設(shè)置為目標(biāo)函數(shù)。目標(biāo)函數(shù)定義如下:

(14)

s.t., 公式(1)-(13)

xk,i∈Z+,yk,i∈Z+,nk,i∈{0, 1},

pk,l∈{0,1},zk,l∈{0, 1}

2 仿真算例

本文的算例使用VC++編碼,并在CPU為i7-5600U-2.60Ghz的Windows 8上運行。此外,本文使用分支定界法求解模型(14),分支定界算法在軟件IBM ILGO CPLEX 12.3 Academic Version上實現(xiàn)。本文算例的線路拓撲結(jié)構(gòu)如圖3所示,我們規(guī)定僅有備車可以在調(diào)整過程中實施跳停決策,并且每輛列車至多在一個車站進行跳停。

圖4 考慮跳停和加開備車情況下的優(yōu)化列車運行圖調(diào)整方案Fig.4 Optimized train diagram adjustment scheme based on stop-skipping and backup trains

本算例給出了本文所構(gòu)建模型和算法的求解結(jié)果,并給出了11輛列車在最小運行間隔為200 s情況下的最優(yōu)列車運行圖以及跳停方案。圖4顯示了使用三輛備車的列車運行圖。從中可以看出,該運行圖滿足了列車運行間隔,所有列車都按照一定的間隔有序運行。另外可以看出,三輛備車采取了不同的跳停策略:第一輛和第二輛備車由于離終點站較近,沒有采取跳停決策;而最后一輛備車在車站6采取了跳停決策。通過這樣的優(yōu)化調(diào)整使線路的列車運行密度更高,能夠更好地緩解故障導(dǎo)致的線路客流負荷。

3 結(jié)論

列車運行調(diào)整是城市軌道交通日常運營管理中需要掌握的關(guān)鍵技術(shù)之一。本文從應(yīng)急條件下的列車運行調(diào)整出發(fā),提出了一種考慮跳停和加開備車策略的城軌列車運行圖調(diào)整方法,通過結(jié)合多種行車調(diào)度策略使線路盡快恢復(fù)行車秩序,保障應(yīng)急條件下的線路運力。將列車運行過程轉(zhuǎn)化為相應(yīng)的狀態(tài)約束,構(gòu)建了混合整數(shù)線性規(guī)劃模型(Mixed-integer linear programming),并使用分支定界和CPLEX優(yōu)化軟件進行求解。最后設(shè)計仿真實驗驗證了本文方法的有效性。

隨著城市軌道交通系統(tǒng)復(fù)雜性、網(wǎng)絡(luò)性的提高,調(diào)度中心如何實現(xiàn)大量信息的集成和快速處理是今后急需解決的核心問題,也是今后全自動運行系統(tǒng)的發(fā)展趨勢。今后的列車運行調(diào)整研究將更趨向于結(jié)合多種調(diào)整手段,從一體化的角度實現(xiàn)系統(tǒng)性能的最優(yōu),為乘客提供更高質(zhì)量的服務(wù)水平[5]。