普速鐵路列車運行圖緩沖時間 優化分配研究

蔣沐弘，鄭屹桐，李 帥，孫國鋒

（蘭州交通大學 交通運輸學院，甘肅 蘭州 730070)

0 引言

受天氣、設備等因素影響，普速鐵路列車運行時容易出現晚點情況。列車間運行秩序可能受到晚點擾亂，且由于列車運行線之間的關聯性及整體性，列車晚點往往會向后傳播[1]，因而調度人員需要根據具體情況進行晚點恢復調整。在編制列車運行圖時，編圖人員往往會預留緩沖時間，以備列車運行調整及晚點恢復。設置合理的緩沖時間既可以有效抑制晚點傳播，還可以有效避免冗余浪費。

在列車運行圖實際編制過程中，緩沖時間的設置具有重點取向，設置的優劣主要取決于編圖人員的經驗和技術水平[2-3]。國內外既有文獻對緩沖時間的研究主要基于晚點延誤、晚點恢復等指標，運用概率論，采用計算機仿真技術進行研究，從隨機模擬的結果來推導必要的緩沖時間[4-7]，但因實際情況下晚點延誤的復雜性與不可控性，估計結果可能會出現偏差[8]。國內學者對列車運行圖緩沖時間的研究多集中在高速鐵路[9-10]，對普速鐵路列車運行圖緩沖時間優化分配的研究較少。相比高速鐵路，普速鐵路受天氣和設備因素影響產生晚點的可能性更大，同時由于普速鐵路線路實行“客貨混跑”，開行多速度等級列車，結合我國國情、路情，普速鐵路列車運行圖緩沖時間優化分配是亟待研究的問題。

針對普速鐵路緩沖時間優化分配問題，首先利用壓縮列車運行圖思想，建立列車運行圖壓縮模型，獲取列車運行圖中可利用的總緩沖時間容量。然后，基于列車運行線協同優化思想，建立列車運行圖緩沖時間優化分配模型，優化列車運行圖緩沖時間分配和布局。最后，重點分析緩沖時間價值計算方法，設計貪心算法求解緩沖時間優化模型，并結合案例進行驗證。

1 普速鐵路列車運行圖緩沖時間優化分配問題模型構建

1.1 問題描述

列車運行圖緩沖時間分為列車區間運行緩沖時間、車站作業緩沖時間和其他緩沖時間。由于各部分作業之間存在內在相互依賴性，對單個作業時間進行緩沖可能與其他作業時間產生沖突。因此，從列車運行圖的整體結構出發，將緩沖時間定義為在列車運行圖中列車圖定作業時分與標準作業時分之間的差值[11]。

通過以下例子說明緩沖時間分配的作用。設計由A，B，C，D，E共5個車站組成的列車運行圖簡圖，未分配緩沖時間情形簡單案例如圖1所示，相鄰列車在滿足追蹤間隔時間的條件下運行。當10001次貨物列車在E站發生初始晚點后，考慮后方高等級列車的準時性與正點率條件下，在D站進行越行作業，最終導致10001次貨物列車在A站晚點抵達。為預防該晚點發生或是減輕后續晚點傳播現象，在10001次貨物列車與Z3次旅客列車間適當插入緩沖時間，以提高列車運行圖抗干擾能力，分配緩沖時間情形簡單案例如圖2所示。

圖1 未分配緩沖時間情形簡單案例Fig.1 Simple case without buffer time allocation

圖2 分配緩沖時間情形簡單案例Fig.2 Simple case with buffer time allocation

普速鐵路列車運行圖緩沖時間優化分配問題研究為在已知列車定序運行，列車種類、數量、圖定運行速度與實際運行速度條件下，綜合列車運行線間安全運行因素，采用協同優化思想，確定最佳緩沖時間分配方案。

根據普速鐵路列車運行圖鋪畫實踐，提出以下假設：①不考慮列車越行情況，即列車運行圖中列車順序保持不變。②不考慮列車起停附加時分對緩沖時間分配的影響。③不考慮天窗對列車運行圖緩沖時間分配的影響。④不考慮閉塞方式對緩沖時間分配的影響。

在列車運行圖緩沖時間優化分配時，首先建立列車運行圖壓縮模型，通過壓縮既有列車運行圖，得到每個區間緩沖時間總容量。然后建立緩沖時間優化分配模型，確定列車運行圖中各區間緩沖時間優化分配的位置及數量。

1.2 列車運行圖壓縮模型

通常用事件—活動網絡圖G=(E，A)來表示列車運行圖中列車的各項作業及相互之間關系，在整體層面上對列車運行圖建模。其中，節點E表示事件為列車車站作業的集合，弧線(有向弧)A表示過程為列車運行過程，模型中只包括在車站中發生的事件。令Arun，Adwell，Ahead，Acon分別為列車在區間運行、列車停站、列車追蹤間隔、列車接續時間集合。令ai,j表示事件—活動網絡圖G中任一列車活動，ai,j∈A。ai,j由2個列車車站作業i，j構成，i，j∈E，其中ti,j為列車圖定活動時間，為列車最小活動時間[9]。通過壓縮列車運行圖的方法，得到每個區間的總緩沖時間容量，壓縮列車運行圖簡單示例如圖3所示。

圖3所示簡例表示在滿足列車在運行圖中各項作業安全完成的情況下，通過壓縮車站作業時間、列車追蹤間隔時間與列車區間運行時間，得到壓縮的列車運行圖。根據上述緩沖時間定義可以計算運行圖中每列車的緩沖時間，得出列車運行圖每個區間緩沖時間容量。

圖3 壓縮列車運行圖簡單示例Fig.3 Simple example for a compressed train timetable

為充分利用列車運行圖能力，以得出列車運行圖中緩沖時間容量最大為目標，建立列車運行圖壓縮模型，目標函數如公式(1)所示，約束條件如公式(2)至公式(5)所示。模型中，公式(2)、公式(3)表示列車運行線定序約束，即作業時間范圍約束，公式(4)表示列車區間最小運行時分與車站最小作業時間約束，公式(5)表示列車之間的最小發車間隔時間約束。

1.3 緩沖時間優化分配模型

列車運行圖壓縮模型可以壓縮得到列車運行圖中各區間緩沖時間容量，可將壓縮后相鄰列車運行線間的作業間隔時間區域視為可分配緩沖時間的候選位置，然后使緩沖時間優化分配至此候選位置中。將整個事件—活動網絡圖G =(E，A)中緩沖時間分配問題建模轉化為背包問題模型。定義在可分配緩沖時間位置的緩沖時間容量為wn，對應的價值為Pn。背包問題模型如公式(6)和公式(7)所示，公式(6)為目標函數，公式(7)為背包容量限制約束。

式中：xn為0-1變量，如果第n個容量背包被選擇，則xn等于1，否則等于0；S表示列車運行圖中區間的集合；wn,s為各個區間分配緩沖時間位置的緩沖時間容量。

緩沖時間的設置目的是預防晚點發生或降低晚點傳播，在同一位置多次分配緩沖時間的效用呈現遞減規律，即當首次分配緩沖時間后，再分配給該位置緩沖時間時，緩沖時間的作用價值應降低，故引入效用函數。既有研究表明，指數分布可以很好地擬合列車晚點時間的概率分布，因而在目標函數中引入指數分布函數作為效用函數，表示緩沖時間可作用于初始晚點產生或晚點傳播的概率[10]。同時，為在緩沖時間分配時充分體現效用函數的作用，以1min為間隔將緩沖時間離散化處理，引入變量m表示緩沖時間的等分間隔，即運行圖中設置的緩沖時間總容量等于mmin內的緩沖時間之和。對緩沖時間離散化處理如公式(8)至公式(10)所示，效用函數如公式(11)所示。

式中：λ為大于1的常數，其值與線路中相鄰列車之間的區間總運行時分之比成正相關。

綜上，以緩沖時間的效用最大化為目標函數，建立緩沖時間優化分配模型如公式(12)至公式(14)所示。公式(12)為緩沖時間分配優化模型的目標函數，公式(13)為每個維度區間緩沖時間優化分配不超過該區間緩沖時間的總量約束，公式(14)為分配第(m+1)min時，前mmin必須被分配約束。

式中：xn,m為0-1變量，表示第n個緩沖時間選擇區域里的第mmin被分配，被分配則為1，否則為0。

此外，還要考慮列車運行圖中運行線間隔約束及停站時間約束，停站時間約束如公式(15)所示，列車運行線間隔約束如公式(16)和公式(17)所示。

2 緩沖時間價值計算及算法設計

在求解緩沖時間優化分配模型前，需要先明確各個候選位置緩沖時間對應的價值，用以確定該位置需要設置緩沖時間的重要程度。由于我國普速鐵路采用不同速度等級列車共線運行的模式，發生列車晚點后，不同速度等級或相同速度等級但運行范圍不同的列車受到的影響程度存在差異。因此，有必要結合不同等級列車在不同候選位置設置緩沖時間的重要程度，對緩沖時間對應的價值Pn,m的計算進行研究。

2.1 緩沖時間價值計算

對各次列車分配緩沖時間的重要程度進行換算統一處理，以體現相鄰列車間設置緩沖時間造成的影響。不僅需要考慮每一列車在運行中產生晚點可能影響后續列車，同時還應考慮該列車的前行車發生晚點對其可能產生的影響?？赡艿臋嘀厍闆r分析如下。

（1）列車等級權重系數。將普速鐵路列車等級分為直達特快旅客列車、直通特快旅客列車、跨局快速旅客列車、普快旅客列車、普客列車、普慢列車與貨物列車等5個等級[2]。由于實際運行中高等級列車應優先分配緩沖時間，定義T為不同列車等級的權重，取直達特快旅客列車等級為5，依此類推，則貨物列車等級為1。即T∈ {1，2，3，4，5}。

（2）相鄰列車間開行方式權重系數。由于相鄰2列車之間存在運行速差，因而相鄰2列車的開行方式具有較大的區別，不同的列車開行方式導致列車運行圖結構不同，將會產生列車運行圖冗余時間，相鄰列車在不同情況下影響示意圖如圖4所示，圖中b表示緩沖時間。

分析列車運行圖相鄰列車在速差不同情況下對緩沖時間分配的影響，圖4a中后行列車與前行列車存在速差形成的“冗余”時間為Δb，當前行列車在該區間發生晚點后，可利用該時間進行晚點恢復調整，因而此“緩沖”可起到預防或降低列車在區間運行晚點的效果；圖4b中前行列車和后行列車運行速度相同，不會產生由前后行列車速差形成的該類緩沖時間Δb；圖4c中由前行列車與后行列車速差形成的“冗余”時間Δb，當前行列車在區間發生晚點時，該“冗余”時間Δb在沒有起到緩沖作用的同時，還會造成無效浪費。因此相較圖4a和圖4b的列車運行情況，圖4c情況對列車運行晚點恢復的影響最嚴重。

圖4 相鄰列車在不同情況下影響示意圖Fig.4 Influence of adjacent trains in different situations

考慮相鄰列車開行方式對晚點的影響，定義α為前后行列車不同等級下緩沖時間的分配權重，根據前行列車晚點對后行列車的影響程度，取α∈ {1， 2，3}分別為前后行列車不同開行方式下的緩沖時間權重。

（3）相鄰列車間的間隔時間權重系數。相鄰列車運行受晚點影響的程度，除上述不同速差情況下的影響外，還與列車之間的間隔時間有關。例如：相鄰列車間追蹤間隔時間越短，發生晚點后，產生的延誤影響越大。定義列車之間緩沖時間相互影響關系如公式(18)所示。

式中：R為影響系數；λ為大于1的常數，其值與線路中相鄰列車間的區間運行時分之比成正相關；λT后-T前 為后行列車對該列車影響大于前行列車對該列車影響；λT前-T后 為前行列車對該列車影響大于后行列車對該列車影響；T前為前行列車等級，T前∈ {1，2，3，4，5}；T后為后行列車等級，T后∈ {1， 2，3，4，5}。

指數分布可以良好地擬合列車晚點時間的概率分布[9]。理想情況下，優化分配的緩沖時間可以恰好抵消晚點延誤時間，利用該分布可計算列車運行圖中每個位置分配緩沖時間的期望。概率函數如公式(19)所示。

式中：Q為每個位置分配緩沖時間的期望。

綜上，設置緩沖時間的價值Pn,m的計算方法如公式(20)所示。

式中：Q為每個位置分配緩沖時間的期望；R為影響系數；α為前后行列車不同開行方式下的緩沖時間權重。

2.2 算法設計

針對建立的列車運行圖緩沖時間優化分配模型，采用貪心算法求解。首先求解列車運行圖壓縮模型作為該問題的初始解，再運用貪心算法對緩沖時間優化分配模型求解得到優化后列車運行圖。貪心算法的核心思想是找出整體當中每個局部的最優解，并且將所有的局部最優解合起來形成整體上的最優解。主要計算步驟如下。

步驟1：把求解的問題分成若干子問題。將列車運行圖中總體緩沖時間優化分配問題分解為各區間緩沖時間優化分配問題。

步驟2：尋找初始解。利用列車運行圖壓縮模型求解各區間緩沖時間分配的初始數值作為初始解。通過鐵路列車運行圖編制系統求解列車運行圖壓縮模型，求得各區間緩沖時間初始數值。

步驟3：計算局部最優解。利用緩沖時間優化分配模型對問題進行求解，得到各區間緩沖時間優化分配局部最優解后，將局部最優解整合為全局最優解；當多個位置同時出現價值Pn,m最大時，設計將緩沖時間分配到最后位置，并將多個位置同時利用效用函數進行迭代，即可滿足緩沖時間在列車運行線群的分配情況，也可防止緩沖時間分配時可能造成過多分配緩沖時間的情況。

步驟4：對計算結果進行判斷。將計算得到的緩沖時間放入列車運行圖中，判斷是否滿足停站時間約束、列車運行線間安全約束等，滿足各項約束情況下的最優解即為最終解。否則，需對計算得到的解進行調整，直到滿足各項約束條件。

3 案例分析

以隴海線隴西—蘭州東區段下行方向列車運行圖為例進行案例分析，選取2020年第4季度列車運行圖9 : 00—14 : 00為研究時段。根據列車運行圖壓縮模型計算緩沖時間容量，根據圖定作業取相鄰列車追蹤間隔時間為6min；直達特快旅客列車、直通特快旅客列車速度為120 km/h，跨局快速旅客列車速度為110 km/h，普快旅客列車速度為100 km/h，普慢旅客列車與貨物列車速度為90 km/h；列車在特等、一等、二等、三等、四等及中間站的最短作業時間分別為8min，6min， 4min，2min，2min和1min；λ取1.3。既有列車運行圖如圖5所示。

圖5 既有列車運行圖Fig.5 Existing train timetable

運用鐵路列車運行圖編制系統計算列車運行圖壓縮模型得到緩沖時間初始分配情況，各區間緩沖時間分配表如表1所示。表1中定西站車站緩沖時間包含在景家店—定西區間，從表1中可得出緩沖時間分配數值與列車等級成正比，通過壓縮列車運行圖模型計算出緩沖時間的總量為258min。

表1 各區間緩沖時間分配表 minTab.1 Buffer time allocation for each interval

根據緩沖時間初始價值計算方法，得到選取研究時段內列車運行圖中各列車的初始價值，緩沖時間初始價值表如表2所示。X8015/6/5次和X8155次列車在定西—蘭州東區段的各區間中價值均為1.10400，表示所分配緩沖時間的重要程度最大；最小為T112/3次列車在定西—梁家坪區間權重0.00020。

表2 緩沖時間初始價值表Tab.2 Initial value of buffer time

運用貪心算法計算緩沖時間優化分配模型得到每個位置優化后的緩沖時間，優化后新生成列車運行圖的緩沖時間總量為 227min，總價值約為32。緩沖時間分配后的列車運行圖如圖6所示。由表1可知，每列車在各區間所設置的緩沖時間與列車等級相關，高等級列車在各區間緩沖時間較多，當列車發生晚點延誤時，可有效地進行晚點延誤恢復，低等級列車在發生晚點延誤時，較易產生晚點傳播情況。優化后緩沖時間分配表如表3所示。比較表1與表3中的數據可知，每列車所需緩沖時間并不絕對與列車等級相關。在實際列車運行圖執行過程中，先需確保高等級列車正點運行，但同樣也不能忽視低等級列車的正點率，且緩沖時間并不絕對與列車等級成正比關系，而是與相鄰列車運行線的時空布置有關。例如表1中Z292/3次、X8015/6/5次、X8155次列車在各區間所擁有緩沖時間與表3有明顯變化。結合圖5與圖6可知，此相鄰列車之間通過重新分配緩沖時間后，列車運行線時空分布發生變化，可以提升預防晚點延誤的能力。各區間緩沖時間容量優化前后對比表如表4所示。

表3 優化后緩沖時間分配表 minTab.3 Buffer time allocation after optimization

圖6 緩沖時間分配后的列車運行圖 Fig.6 Train timetable after buffer time allocation

在表4中，優化前的緩沖時間是通過列車運行圖壓縮模型得到的各區間總的緩沖時間容量，優化后的緩沖時間是通過緩沖時間優化分配模型得到的實際分配到各個區間的緩沖時間容量。例如許家臺—夏官營區間通過列車運行圖壓縮模型得到總緩沖時間為26min，運用緩沖時間優化分配模型實際分配緩沖時間為18min。對比優化前后緩沖時間總容量，優化后緩沖時間總容量為227min，較優化前減少31min，且滿足緩沖時間優化分配模型約束，可有效避免分配緩沖時間造成的列車運行圖能力浪費。優化前后各列車緩沖時間分配表如表5所示，優化前后各列車緩沖時間分配趨勢對比圖如圖7所示。

表4 各區間緩沖時間容量優化前后對比表minTab.4 Comparison of buffer time capacity at each interval before and after optimization

由表5和圖7可知，優化前既有列車運行圖中Z126/7次—Z292/3次列車之間的列車發生晚點時，具有較充足的緩沖時間進行晚點恢復，而X8015/6/5次—X208/5次列車之間的列車可利用緩沖時間較少，當列車按照優化前列車運行圖運行時，若在Z126/7次—Z292/3次列車之間不發生晚點，在X8015/6/5次—X208/5次列車之間發生晚點時，將會使Z126/7次—Z292/3次列車之間設置的緩沖時間大量浪費，并且在X8015/6/5次—X208/5次列車之間可能會出現緩沖時間不充足的情況。優化后對該時段所有列車來說，可用緩沖時間整體呈現增長趨勢，當前行列車發生晚點時，后行列車可用緩沖時間增多，能夠增加列車運行圖的魯棒性，可避免在列車發生晚點延誤時向后大規模傳播，同時有效地防止在列車運行圖前端過多鋪設緩沖時間造成浪費。結合圖6與表5可知，通過緩沖時間優化分配模型求解，充分利用了列車運行圖結構產生的冗余時間，如：Z126/7次列車運行線在圖中與后行列車間本身存在冗余時間，繼續對該列車設置緩沖時間會造成冗余浪費。

圖7 優化前后各列車緩沖時間分配趨勢對比圖Fig.7 Comparison of buffer time allocation trend for each train before and after optimization

表5 優化前后各列車緩沖時間分配表minTab.5 Buffer time allocation for each train before and after optimization

對比優化前后列車運行圖，優化前后列車開行方式發生改變，如Z292/3次與X8015/6/5次列車在隴西—云田鄉的開行方式，優化前Z292/3次與X8015/6/5次列車的關系為前行小于后行(如圖4 c)，優化后通過重新分配緩沖時間，Z292/3次與X8015/6/5次列車的關系在隴西—云田鄉區間為前行等于后行(如圖4 b)，在云田鄉—夏官營區間變為前行大于后行(如圖4 a)，列車運行圖結構產生的空費時間減少。優化前X8015/6/5次與X8155次列車在定西—梁家坪區間的追蹤間隔時間為7min 30 s，列車極易在該區間發生晚點，且當前行X8015/6/5次列車發生晚點后，直接會將晚點延誤傳播至后行X8155次列車。優化后2列車在該區間的追蹤間隔時間為10min，提高了該相鄰列車運行線之間的抗干擾能力。

4 結束語

為提高列車運行圖的抗干擾能力，基于緩沖時間優化分配的思想，在列車運行圖壓縮模型基礎上，提出緩沖時間優化分配模型。相比于傳統列車運行圖緩沖時間優化方法，引入效用函數，達到避免過多分配緩沖時間造成能力浪費的目的，同時分析不同情況下設置緩沖時間的重要程度，設計緩沖時間價值和模型求解方法。案例分析結果表明，在優化后的列車運行圖中，緩沖時間的分布較優化前更為合理，呈現在圖中列車運行線的時空分布更趨于均衡，且列車運行圖本身結構導致的空費時間減少，有效提高了列車運行圖的抗干擾能力。但是，該方法僅考慮了列車定序運行的情況，沒有考慮列車越行對緩沖時間分配的影響，還應進一步研究考慮列車越行情況的緩沖時間優化方法。