基于Max-plus代數(shù)法的市域鐵路快慢車運(yùn)行特性

鄭 翔 徐行方 劉 薇 魯 玉

(1.廣州地鐵設(shè)計(jì)研究院股份有限公司, 510010, 廣州; 2.同濟(jì)大學(xué)道路與交通工程教育部重點(diǎn)實(shí)驗(yàn)室, 201804, 上海; 3.上海市軌道交通結(jié)構(gòu)耐久與系統(tǒng)安全重點(diǎn)實(shí)驗(yàn)室, 201804, 上海; 4.國(guó)家開發(fā)銀行蘇州市分行, 215128, 蘇州∥第一作者, 高級(jí)工程師)

市域鐵路是連接市區(qū)與郊區(qū)、周圍衛(wèi)星城鎮(zhèn)及都市圈的軌道交通線路,具有運(yùn)量大、速度快、站距長(zhǎng)(設(shè)站少)等特點(diǎn)。采用高密度、周期化的快慢車運(yùn)行模式可以減少乘客的出行時(shí)間,滿足多元化、快速化的出行需求。由于快慢車模式中采用快車越行、慢車避讓的行車模式,一旦出現(xiàn)晚點(diǎn),列車恢復(fù)運(yùn)行的調(diào)整難度隨之增大。這就要求列車運(yùn)行圖在計(jì)劃階段就能保證列車運(yùn)行系統(tǒng)的魯棒性,提高列車運(yùn)行圖的抗干擾能力。文獻(xiàn)[1]利用改進(jìn)遺傳算法優(yōu)化城市軌道交通列車運(yùn)行圖的魯棒性,但其未對(duì)快慢車行車模式進(jìn)行研究。文獻(xiàn)[2]提出2種可恢復(fù)魯棒性的優(yōu)化模型(RRT-1模型和RRT-2模型),在開行2種速度的客運(yùn)專線上加以驗(yàn)證,分別研究魯棒算法和魯棒性代價(jià),但其求解存在樣本規(guī)模大、概率分布不明、NP-hard等不足之處。

Max-plus代數(shù)法可以在特定規(guī)則下實(shí)現(xiàn)矩陣運(yùn)算,建立并求解具有一定運(yùn)算規(guī)模的離散線性系統(tǒng)模型,目前已成功應(yīng)用于系統(tǒng)制造、交通運(yùn)輸系統(tǒng)等領(lǐng)域。交通運(yùn)輸系統(tǒng)是典型的離散事件動(dòng)態(tài)系統(tǒng),目前Max-plus代數(shù)法已成功應(yīng)用于鐵路系統(tǒng),將鐵路運(yùn)行的過程類比為串行生產(chǎn)線上工件依次順序加工的過程。文獻(xiàn)[3]基于Max-plus代數(shù)法的極大時(shí)間約束,研究軌道交通系統(tǒng)開環(huán)和閉環(huán)周期的運(yùn)行規(guī)律。文獻(xiàn)[4-5]通過極大代數(shù)框架評(píng)價(jià)了軌道交通系統(tǒng)及運(yùn)行圖的穩(wěn)定性。由于快慢車模式中的快車在列車事件時(shí)序上會(huì)發(fā)生躍遷,現(xiàn)有的Max-plus列車運(yùn)行系統(tǒng)閉環(huán)模型無(wú)法模擬快車越行、通過事件?；诖?本文提出一種基于Max-plus代數(shù)法的市域鐵路快慢車運(yùn)行系統(tǒng)的閉環(huán)模型,用狀態(tài)變量的解生成滿足運(yùn)行方案需求的列車時(shí)刻表,并分析運(yùn)行系統(tǒng)的穩(wěn)態(tài)特性。本文研究可為市域鐵路快慢車運(yùn)行的計(jì)劃編制和魯棒性檢驗(yàn)提供理論依據(jù)。

1 Max-plus離散事件動(dòng)態(tài)系統(tǒng)與列車運(yùn)行過程

假設(shè)市域鐵路上有S1,S2,…,Sq共q個(gè)車站,假設(shè)已確定列車開行方案,計(jì)劃每周期從S1到Sq站開行m列列車,表示為P1,P2,…,Pm。任一列車Pi(i=1,2,…,m)在每個(gè)非首末站均包含到達(dá)和出發(fā)兩個(gè)事件,始發(fā)站僅有出發(fā)事件,終點(diǎn)站僅有到達(dá)事件。為了表述列車在車站的到發(fā)作業(yè)時(shí)刻,將列車在每一站Sj(j=1,2,…,q)發(fā)生的事件一一對(duì)應(yīng),共建立2q-2個(gè)車站作業(yè)點(diǎn),為標(biāo)注方便,重新編號(hào)車站作業(yè)點(diǎn)為W1,W2,…,Wn,其中n=2q-2。車站、列車事件與車站作業(yè)點(diǎn)之間的映射關(guān)系如圖1所示。

圖1 車站、列車事件與車站作業(yè)點(diǎn)之間的映射關(guān)系

1.1 定義模型變量和參數(shù)

假設(shè)只存在S1—Sq站單一交路,車底充足,不考慮車底銜接。線路運(yùn)行方案已知,即列車在區(qū)間和站點(diǎn)的作業(yè)時(shí)間、列車追蹤間隔等均為已知參數(shù),利用Max-plus代數(shù)法描述滿足運(yùn)行方案條件下的列車運(yùn)行全過程,記錄每一列列車運(yùn)行狀態(tài)遷移,求解列車到發(fā)事件發(fā)生時(shí)刻。

1) 狀態(tài)變量xij。記錄列車Pi運(yùn)行狀態(tài)躍遷至車站作業(yè)點(diǎn)Wj的時(shí)刻,即列車Pi在始發(fā)車站S1的發(fā)車時(shí)刻(作業(yè)點(diǎn)位置為W1)記為xi1;以此類推,在第p個(gè)車站Sp的到達(dá)時(shí)刻(作業(yè)點(diǎn)位置為Wj)記為xij,出發(fā)時(shí)刻(作業(yè)點(diǎn)位置為Wj+1)記為xi,j+1,在終點(diǎn)站Sq的到達(dá)時(shí)刻(作業(yè)點(diǎn)位置為Wn)記為xin。

2) 輸入變量ui。記錄每列列車計(jì)劃在始發(fā)站S1的發(fā)車時(shí)刻。

3) 輸出變量yi。記錄每列列車在終點(diǎn)站Sq完成停站作業(yè)的時(shí)刻。

4) 作業(yè)時(shí)間tij。列車Pi的運(yùn)行狀態(tài)從一站作業(yè)點(diǎn)躍遷至另一站作業(yè)點(diǎn)所需時(shí)間。例如:列車Pi在車站作業(yè)點(diǎn)W1的作業(yè)時(shí)間,表示列車Pi從S1站出發(fā)至S2站的區(qū)間運(yùn)行時(shí)間,記為ti1;列車Pi在車站作業(yè)點(diǎn)W2的作業(yè)時(shí)間,表示列車Pi從到達(dá)S2站至由S2站出發(fā)所需時(shí)間,即列車Pi在S2站的停站作業(yè)時(shí)長(zhǎng),記為ti2。在實(shí)際問題求解中,區(qū)間運(yùn)行時(shí)間不為0,停站作業(yè)時(shí)長(zhǎng)可為0(表示列車在該站越行,不停車通過)。

5) 追蹤間隔時(shí)間zij。列車Pi在車站作業(yè)點(diǎn)Wj與下一列車Pi+1之間的追蹤間隔時(shí)間。

6) 周期T和批次k。設(shè)定若干列車為一個(gè)列車群,在一個(gè)批次內(nèi)從始發(fā)站間隔發(fā)車,此后列車運(yùn)行計(jì)劃按批次重復(fù)循環(huán),列車開行復(fù)現(xiàn)時(shí)間間隔稱為一個(gè)周期T。k表示第k批次。模型參數(shù)周期與批次示意圖如圖2所示。

圖2 模型參數(shù)周期與批次示意圖

1.2 系統(tǒng)約束規(guī)則

1) 首班車P1狀態(tài)。始發(fā)站出發(fā)時(shí)刻受初始既定時(shí)刻的約束;在非始發(fā)站首班車的到發(fā)時(shí)刻受自身接續(xù)規(guī)則的約束。Max-plus代數(shù)形式可以分別表示為:

x11(k)=max{u1}=0?u1(k)

(1)

x1j(k)=x1,j-1(k)?t1,j-1

(2)

j=2,3,…,n

式中:

x11(k)、x1,j-1(k)、x1j(k)——在第k批次中,首班車P1運(yùn)行狀態(tài)分別躍遷至車站作業(yè)點(diǎn)W1、Wj-1、Wj的時(shí)刻;

u1(k)——在第k批次中,首班車P1計(jì)劃在始發(fā)站S1的發(fā)車時(shí)刻,數(shù)值上等于x11(k);

t1,j-1——首班車P1從作業(yè)點(diǎn)Wj-1躍遷至作業(yè)點(diǎn)Wj所需時(shí)間。

2) 非首班列車Pi(i≠1)狀態(tài)。始發(fā)站出發(fā)時(shí)刻受初始既定時(shí)刻和列車追蹤間隔時(shí)間的約束;非始發(fā)站首班車到發(fā)時(shí)刻受自身接續(xù)規(guī)則和列車追蹤間隔時(shí)間的約束。Max-plus代數(shù)形式可以分別表示為:

(3)

i≠1

xij(k)=xi-1,j(k)?zi-1,j⊕xi,(j-1)(k)?ti,(j-1)

(4)

i≠1,j=2,3,…,n

式中:

xi1(k)、xi,j-1(k)、xij(k)——在第k批次中,列車Pi運(yùn)行狀態(tài)分別躍遷至車站作業(yè)點(diǎn)W1、Wj-1、Wj的時(shí)刻;

xi-1,1(k)、xi-1,j(k)——在第k批次中,列車Pi的前列列車Pi-1運(yùn)行狀態(tài)躍遷至車站作業(yè)點(diǎn)W1、Wj的時(shí)刻;

ui(k)——在第k批次中,列車Pi計(jì)劃在始發(fā)站S1的發(fā)車時(shí)刻;

ti,j-1——列車Pi從作業(yè)點(diǎn)Wj-1躍遷至作業(yè)點(diǎn)Wj所需時(shí)間;

zi-1,1、zi-1,j——列車Pi的前列車Pi-1分別在車站作業(yè)點(diǎn)W1、Wj時(shí)與列車Pi之間的追蹤間隔時(shí)間。

3) 輸出條件yi。y1—ym表征在一個(gè)周期內(nèi),第i(i=1,2,…,m)列列車在終點(diǎn)站完成停站作業(yè)的時(shí)刻,可以表示為:

yi(k)=xin(k)?tin

(5)

i=1,2,…,m

式中:

yi(k)——在第k批次中,列車Pi在終點(diǎn)站完成停站作業(yè)的時(shí)刻;

xin(k)——在第k批次中,列車Pi運(yùn)行狀態(tài)分別躍遷至終點(diǎn)站作業(yè)點(diǎn)Wn的時(shí)刻;

tin——列車Pi在終點(diǎn)站作業(yè)點(diǎn)Wn的停站作業(yè)時(shí)間。

2 基于Max-plus代數(shù)法的列車時(shí)刻表編制模型

2.1 列車運(yùn)行系統(tǒng)Max-plus開環(huán)線性模型

首先,基于Max-plus代數(shù)法建立站站停運(yùn)行模型。列車P1,P2,…,Pm按間隔時(shí)間依次發(fā)車,每列列車依次通過每個(gè)車站,并依次到達(dá)終點(diǎn)站完成一個(gè)周期的運(yùn)行過程,期間前后接續(xù)列車次序保持固有順序。站站停列車運(yùn)行計(jì)時(shí)事件圖如圖3所示。

圖3 站站停列車運(yùn)行計(jì)時(shí)事件圖

x(k)=Ax(k)⊕Bu(k)

(6)

y(k)=Cx(k)

(7)

(8)

(9)

(10)

(11)

(12)

式中:

Ji——自身接續(xù)約束矩陣(未標(biāo)注的元均為ε元),非零元記錄第i(i=1,2,…,m)列列車依次在第1,2,…,n-1個(gè)車站作業(yè)點(diǎn)的作業(yè)時(shí)長(zhǎng);

Ii——列車追蹤間隔約束矩陣(未標(biāo)注的元均為ε元),非零元記錄第i(i=1,2,…,m)列列車依次在第1,2,…,n-1個(gè)車站追蹤列車的發(fā)車間隔時(shí)間zi1,zi3,…,zi,n-1,以及追蹤列車的到達(dá)間隔時(shí)間zi2,zi4,…,zin。

由于同一區(qū)間列車的運(yùn)行時(shí)間相同,且同一車站的停站時(shí)長(zhǎng)相同,則有J1=J2=…=Jm,I1=I2=…=Im。B中無(wú)標(biāo)注的元均為ε元,矩陣B中的單位元素分布在第1行和第n的整數(shù)倍+1行。C中無(wú)標(biāo)注的元均為ε元,矩陣C中的非零元分布在第n的整數(shù)倍列。

對(duì)于式(6),在表達(dá)式兩端逐次左圈乘矩陣E,A,A2,…,Ap-2,Ap-1,再將各方程迭代相加可推導(dǎo)出:

x(k)=A*Bu(k)

(13)

A*=E⊕A⊕A2⊕A3⊕…⊕Ap-1

(14)

代入式(7),輸出解表達(dá)式為:

y(k)=CA*Bu(k)

(15)

2.2 快慢車模式下開環(huán)線性模型的變換

快慢車模式下,由于存在快車越行慢車,運(yùn)行圖編制的特點(diǎn)在于考慮列車停站分布和運(yùn)行順序變換,在列車運(yùn)行系統(tǒng)線性模型中,這兩者對(duì)應(yīng)于系統(tǒng)狀態(tài)矩陣參數(shù)的重新賦值與排序。假設(shè)開行1列快車P3,且設(shè)定在S2站越行。列車P3在車站S2越行前后的方案示意圖如圖4所示。

圖4 列車P3在車站S2越行前后的方案示意圖

快車P3在S2站辦理通過作業(yè),即停站時(shí)長(zhǎng)為0,在系統(tǒng)狀態(tài)矩陣中表示為t32=0

在列車運(yùn)行開環(huán)線性模型中(見圖4),越行不會(huì)改變列車自身的接續(xù)約束,即自身接續(xù)約束矩陣Ji無(wú)變化。越行會(huì)對(duì)快車P3、越行前列列車P2和越行后的列車P4這3列列車在越行后的次序有所影響,即3列列車在車站作業(yè)點(diǎn)W3,W4,…,Wn的狀態(tài)方程都將發(fā)生改變。

以3列列車在車站作業(yè)點(diǎn)W3的狀態(tài)方程變換為例:

(16)

(17)

(18)

(19)

除了A的矩陣元素位置轉(zhuǎn)移外,z13、z23的取值也發(fā)生了變動(dòng)。站站停模式下,z13、z23均表示S2站追蹤列車發(fā)車間隔時(shí)間,即z13=z23;快慢車模式下,z13、z23表示S2站列車同向通發(fā)(通過和發(fā)車)、發(fā)通(發(fā)車和通過)追蹤間隔時(shí)間。B、C與其他變量矩陣均不做狀態(tài)置換。

2.3 列車運(yùn)行系統(tǒng)Max-plus閉環(huán)線性模型

編制規(guī)律性的列車運(yùn)行計(jì)劃有利于提高乘客的出行選擇黏性。為使系統(tǒng)形成周期性運(yùn)行節(jié)奏,建立列車運(yùn)行系統(tǒng)閉環(huán)模型。引入反饋方程,即U(k)=K?Y(k-1),K為m×m的常數(shù)矩陣,其元素ki,j滿足以下關(guān)系式:

(20)

i,j=1,2,…,m

式中:

Ki——反饋常數(shù),表示批次間的列車發(fā)車間隔約束。

列車運(yùn)行系統(tǒng)的閉環(huán)線性模型為:

y(k)=My(k-1),k=2,3,…,N+

(21)

x(k)=Nx(k-1),k=2,3,…,N+

(22)

M=CA*BK

(23)

N=A*BKC

(24)

3 算例分析

3.1 市域鐵路快慢車閉環(huán)模型輸出演化

假設(shè)某市域鐵路上的4個(gè)車站S1—S4,其中車站S2具備越行條件。已知運(yùn)行方案為:計(jì)劃每20 min(列車計(jì)劃運(yùn)行周期T=1 200 s)周期在上行方向(S1→S4)開行同一批次的4列列車P1—P4,慢車和快車以1∶1間隔開行,快車在S2站越行。案例區(qū)段各車站及區(qū)間時(shí)間參數(shù)如表1所示。

表1 案例區(qū)段各車站及區(qū)間時(shí)間參數(shù)

利用Max-plus代數(shù)法建立快慢車運(yùn)行上行方向閉環(huán)模型。

輸入系統(tǒng)的初始取值為:u=[u1u2u3u4]T=[0 140 600 740]T,表示每列車在S1站的發(fā)車時(shí)刻。

服務(wù)時(shí)間矩陣F取值為:

反饋矩陣K中的反饋元素Ki取0,構(gòu)建閉環(huán)模型。閉環(huán)系統(tǒng)輸出矩陣M為:

累計(jì)計(jì)算6個(gè)周期(合計(jì)2 h),列車在S4終點(diǎn)站完成停站作業(yè)的輸出時(shí)刻y(k)如表2所示。

表2 列車在S4終點(diǎn)站完成停站作業(yè)的輸出時(shí)刻

該快慢車運(yùn)行系統(tǒng)特征值λ為慢車運(yùn)行一周期所花費(fèi)的時(shí)間,即λ=909 s。系統(tǒng)列車計(jì)劃運(yùn)行周期T為1 200 s,因此一個(gè)周期系統(tǒng)的緩沖時(shí)間為:

Δ=T-λ=291 s

緩沖時(shí)間大于0,表示系統(tǒng)穩(wěn)定。此外,還可通過x(k)得到對(duì)應(yīng)的列車時(shí)刻表。假設(shè)首班車7:00從S1站發(fā)車,前3個(gè)批次列車在各站的到發(fā)時(shí)刻信息如表3所示。

表3 前3個(gè)批次列車在各站的到發(fā)時(shí)刻信息

3.2 單參數(shù)攝動(dòng)情形的魯棒性分析

則系統(tǒng)穩(wěn)態(tài)參量(特征值)λ對(duì)于元mij的增性攝動(dòng)是魯棒的。通過常用的準(zhǔn)則來定量刻畫穩(wěn)態(tài)參量λ相對(duì)于系統(tǒng)矩陣各元素mij的魯棒性,定義魯棒性準(zhǔn)則RF(mij)和RM(mij)分別為[4]:

(25)

(26)

考察魯棒性準(zhǔn)則RF(mij)和RM(mij)(符號(hào)“-”表示該位置不屬于攝動(dòng)元),則有:

(27)

(28)

考察魯棒性準(zhǔn)則RM(mij),若RM(mij)=0,則λ對(duì)于RM(mij)是非魯棒的。前文案例中,RM(m11)=RM(m33)=0,即首班車在始發(fā)站出發(fā)時(shí)刻不具備魯棒性,第4列列車為快車,越行后成為第3列列車,在越行站越行時(shí)刻不具備魯棒性;若RM(mij)≠0,則λ對(duì)于RM(mij)是魯棒的,且RM(mij)的值越大,魯棒性程度越高。

4 結(jié)語(yǔ)

編制快慢車運(yùn)行計(jì)劃時(shí),應(yīng)滿足系統(tǒng)穩(wěn)定性和

魯棒性的要求。為考察快慢車方案的系統(tǒng)穩(wěn)態(tài)特征,本文針對(duì)市域鐵路快慢車運(yùn)行特點(diǎn),基于Max-plus代數(shù)法構(gòu)建市域鐵路快慢車運(yùn)行系統(tǒng)閉環(huán)模型。以一段計(jì)劃開行快慢車的市域鐵路為例,從變量輸入到系統(tǒng)輸出演化求解了列車運(yùn)行動(dòng)態(tài)轉(zhuǎn)移的全過程,并通過狀態(tài)轉(zhuǎn)移變量矩陣的求解結(jié)果生成列車運(yùn)行時(shí)刻表,分析該系統(tǒng)的穩(wěn)定性和魯棒性,實(shí)現(xiàn)了Max-plus代數(shù)法在市域鐵路快慢車運(yùn)行系統(tǒng)上的應(yīng)用,為快慢車運(yùn)行計(jì)劃編制和系統(tǒng)魯棒性分析提供了一種新的分析模型。目前,所提Max-plus代數(shù)法模型僅限于在滿足已知運(yùn)行方案要素條件下生成快慢車運(yùn)行時(shí)刻表和系統(tǒng)穩(wěn)態(tài)特性評(píng)價(jià),下一步還可深入分析Max-plus代數(shù)法在快慢車系統(tǒng)魯棒性優(yōu)化和列車運(yùn)行調(diào)整方面的研究。