基于線性規(guī)劃模型的城軌列車運(yùn)行圖調(diào)整策略

何占元,陰佳騰,王明主

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

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

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

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

圖1 考慮存車線的軌道交通線路拓?fù)浣Y(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é)合“跳?！焙汀凹娱_(kāi)備車”兩種常用的行車調(diào)度手段,用以優(yōu)化故障場(chǎng)景下的列車運(yùn)行圖調(diào)整方案,以提高線路的故障恢復(fù)能力,盡快疏散因線路故障而滯留的乘客。

1 問(wèn)題描述

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

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

1.1 本文基本假設(shè)

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

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

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

1.2 符號(hào)和變量表示

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

表1 本文使用的符號(hào)和定義Tab.1 The symbols and definitions

續(xù)表1

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

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

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

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

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

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

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

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

1.3 模型約束

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

約束一:運(yùn)行時(shí)分約束

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

(1)

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

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

(2)

?k∈KE∪KF∪KAi∈Sk

(3)

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

?k∈KE∪KF∪KAi∈Sk

(4)

約束三:列車運(yùn)行間隔約束

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

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

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

(5)

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

(6)

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

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

如果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之間保持一定的運(yùn)行間隔。

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

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

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

(8)

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

約束四:列車運(yùn)行次序約束

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

(9)

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

(10)

(11)

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

(12)

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

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

約束五:列車折返約束

yk,i+1-yk,i=Tturn

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

(13)

列車折返約束限制了列車在折返站的折返時(shí)間。

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

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

接下來(lái)考慮構(gòu)建模型的目標(biāo)函數(shù)。本文所考慮的基本問(wèn)題是故障修復(fù)、線路恢復(fù)正常運(yùn)營(yíng)時(shí)間段,此時(shí)行車調(diào)度的主要目的是盡快疏散站臺(tái)滯留的乘客,維持正常的列車運(yùn)行秩序。在考慮備車的情況下,本文的主要優(yōu)化目標(biāo)是盡可能保證列車運(yùn)行安全的情況下提高線路運(yùn)力、增大發(fā)車頻次。因此本文將列車到達(dá)終點(diǎn)站的時(shí)間總和設(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上運(yùn)行。此外,本文使用分支定界法求解模型(14),分支定界算法在軟件IBM ILGO CPLEX 12.3 Academic Version上實(shí)現(xiàn)。本文算例的線路拓?fù)浣Y(jié)構(gòu)如圖3所示,我們規(guī)定僅有備車可以在調(diào)整過(guò)程中實(shí)施跳停決策,并且每輛列車至多在一個(gè)車站進(jìn)行跳停。

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

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

3 結(jié)論

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

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