基于Max-plus代數法的市域鐵路快慢車運行特性

鄭 翔 徐行方 劉 薇 魯 玉

(1.廣州地鐵設計研究院股份有限公司, 510010, 廣州; 2.同濟大學道路與交通工程教育部重點實驗室, 201804, 上海; 3.上海市軌道交通結構耐久與系統安全重點實驗室, 201804, 上海; 4.國家開發銀行蘇州市分行, 215128, 蘇州∥第一作者, 高級工程師)

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

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

1 Max-plus離散事件動態系統與列車運行過程

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

圖1 車站、列車事件與車站作業點之間的映射關系

1.1 定義模型變量和參數

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

1) 狀態變量xij。記錄列車Pi運行狀態躍遷至車站作業點Wj的時刻,即列車Pi在始發車站S1的發車時刻(作業點位置為W1)記為xi1;以此類推,在第p個車站Sp的到達時刻(作業點位置為Wj)記為xij,出發時刻(作業點位置為Wj+1)記為xi,j+1,在終點站Sq的到達時刻(作業點位置為Wn)記為xin。

2) 輸入變量ui。記錄每列列車計劃在始發站S1的發車時刻。

3) 輸出變量yi。記錄每列列車在終點站Sq完成停站作業的時刻。

4) 作業時間tij。列車Pi的運行狀態從一站作業點躍遷至另一站作業點所需時間。例如:列車Pi在車站作業點W1的作業時間,表示列車Pi從S1站出發至S2站的區間運行時間,記為ti1;列車Pi在車站作業點W2的作業時間,表示列車Pi從到達S2站至由S2站出發所需時間,即列車Pi在S2站的停站作業時長,記為ti2。在實際問題求解中,區間運行時間不為0,停站作業時長可為0(表示列車在該站越行,不停車通過)。

5) 追蹤間隔時間zij。列車Pi在車站作業點Wj與下一列車Pi+1之間的追蹤間隔時間。

6) 周期T和批次k。設定若干列車為一個列車群,在一個批次內從始發站間隔發車,此后列車運行計劃按批次重復循環,列車開行復現時間間隔稱為一個周期T。k表示第k批次。模型參數周期與批次示意圖如圖2所示。

圖2 模型參數周期與批次示意圖

1.2 系統約束規則

1) 首班車P1狀態。始發站出發時刻受初始既定時刻的約束;在非始發站首班車的到發時刻受自身接續規則的約束。Max-plus代數形式可以分別表示為:

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運行狀態分別躍遷至車站作業點W1、Wj-1、Wj的時刻;

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

t1,j-1——首班車P1從作業點Wj-1躍遷至作業點Wj所需時間。

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

(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運行狀態分別躍遷至車站作業點W1、Wj-1、Wj的時刻;

xi-1,1(k)、xi-1,j(k)——在第k批次中,列車Pi的前列列車Pi-1運行狀態躍遷至車站作業點W1、Wj的時刻;

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

ti,j-1——列車Pi從作業點Wj-1躍遷至作業點Wj所需時間;

zi-1,1、zi-1,j——列車Pi的前列車Pi-1分別在車站作業點W1、Wj時與列車Pi之間的追蹤間隔時間。

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

yi(k)=xin(k)?tin

(5)

i=1,2,…,m

式中:

yi(k)——在第k批次中,列車Pi在終點站完成停站作業的時刻;

xin(k)——在第k批次中,列車Pi運行狀態分別躍遷至終點站作業點Wn的時刻;

tin——列車Pi在終點站作業點Wn的停站作業時間。

2 基于Max-plus代數法的列車時刻表編制模型

2.1 列車運行系統Max-plus開環線性模型

首先,基于Max-plus代數法建立站站停運行模型。列車P1,P2,…,Pm按間隔時間依次發車,每列列車依次通過每個車站,并依次到達終點站完成一個周期的運行過程,期間前后接續列車次序保持固有順序。站站停列車運行計時事件圖如圖3所示。

圖3 站站停列車運行計時事件圖

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

(6)

y(k)=Cx(k)

(7)

(8)

(9)

(10)

(11)

(12)

式中:

Ji——自身接續約束矩陣(未標注的元均為ε元),非零元記錄第i(i=1,2,…,m)列列車依次在第1,2,…,n-1個車站作業點的作業時長;

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

由于同一區間列車的運行時間相同,且同一車站的停站時長相同,則有J1=J2=…=Jm,I1=I2=…=Im。B中無標注的元均為ε元,矩陣B中的單位元素分布在第1行和第n的整數倍+1行。C中無標注的元均為ε元,矩陣C中的非零元分布在第n的整數倍列。

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

x(k)=A*Bu(k)

(13)

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

(14)

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

y(k)=CA*Bu(k)

(15)

2.2 快慢車模式下開環線性模型的變換

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

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

快車P3在S2站辦理通過作業,即停站時長為0,在系統狀態矩陣中表示為t32=0

在列車運行開環線性模型中(見圖4),越行不會改變列車自身的接續約束,即自身接續約束矩陣Ji無變化。越行會對快車P3、越行前列列車P2和越行后的列車P4這3列列車在越行后的次序有所影響,即3列列車在車站作業點W3,W4,…,Wn的狀態方程都將發生改變。

以3列列車在車站作業點W3的狀態方程變換為例:

(16)

(17)

(18)

(19)

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

2.3 列車運行系統Max-plus閉環線性模型

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

(20)

i,j=1,2,…,m

式中:

Ki——反饋常數,表示批次間的列車發車間隔約束。

列車運行系統的閉環線性模型為:

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 市域鐵路快慢車閉環模型輸出演化

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

表1 案例區段各車站及區間時間參數

利用Max-plus代數法建立快慢車運行上行方向閉環模型。

輸入系統的初始取值為:u=[u1u2u3u4]T=[0 140 600 740]T,表示每列車在S1站的發車時刻。

服務時間矩陣F取值為:

反饋矩陣K中的反饋元素Ki取0,構建閉環模型。閉環系統輸出矩陣M為:

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

表2 列車在S4終點站完成停站作業的輸出時刻

該快慢車運行系統特征值λ為慢車運行一周期所花費的時間,即λ=909 s。系統列車計劃運行周期T為1 200 s,因此一個周期系統的緩沖時間為:

Δ=T-λ=291 s

緩沖時間大于0,表示系統穩定。此外,還可通過x(k)得到對應的列車時刻表。假設首班車7:00從S1站發車,前3個批次列車在各站的到發時刻信息如表3所示。

表3 前3個批次列車在各站的到發時刻信息

3.2 單參數攝動情形的魯棒性分析

則系統穩態參量(特征值)λ對于元mij的增性攝動是魯棒的。通過常用的準則來定量刻畫穩態參量λ相對于系統矩陣各元素mij的魯棒性,定義魯棒性準則RF(mij)和RM(mij)分別為[4]:

(25)

(26)

考察魯棒性準則RF(mij)和RM(mij)(符號“-”表示該位置不屬于攝動元),則有:

(27)

(28)

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

4 結語

編制快慢車運行計劃時,應滿足系統穩定性和

魯棒性的要求。為考察快慢車方案的系統穩態特征,本文針對市域鐵路快慢車運行特點,基于Max-plus代數法構建市域鐵路快慢車運行系統閉環模型。以一段計劃開行快慢車的市域鐵路為例,從變量輸入到系統輸出演化求解了列車運行動態轉移的全過程,并通過狀態轉移變量矩陣的求解結果生成列車運行時刻表,分析該系統的穩定性和魯棒性,實現了Max-plus代數法在市域鐵路快慢車運行系統上的應用,為快慢車運行計劃編制和系統魯棒性分析提供了一種新的分析模型。目前,所提Max-plus代數法模型僅限于在滿足已知運行方案要素條件下生成快慢車運行時刻表和系統穩態特性評價,下一步還可深入分析Max-plus代數法在快慢車系統魯棒性優化和列車運行調整方面的研究。