高速鐵路列車運行圖一體化自動編制方法研究

安 迪，武晉飛，張宇墨

(1.中國鐵道科學研究院 研究生部，北京 100081；2.中國鐵道科學研究院集團有限公司 運輸及經濟研究所，北京 100081；3.中國鐵道科學研究院集團有限公司 電子計算技術研究所，北京 100081；4.中國鐵路經濟規劃研究院有限公司 科技管理部，北京 100038)

高速鐵路(以下簡稱“高鐵”)列車運行圖編制一直以來都是高鐵運輸組織的核心問題之一。目前,全路采用的列車運行圖編制系統仍以人工編制為主,究其原因,高鐵列車運行圖除包含列車時刻表外,還包含車底交路方案、運行圖結構方案、車站股道運用方案等,是運輸需求與運輸供給的集中體現。由于高鐵列車運行圖編制影響因素都具有一定的復雜性,且相互耦合,一體化自動編制的難度則更大。

針對運行圖編制的復雜問題,國內外學者對列車運行圖自動編制問題進行過很多研究。部分學者采用簡化或分步式方法求解。馬建軍等[1]針對不同速度列車,建立高中速列車運行圖數學模型,設計高中速列車分層始發區域滾動鋪畫算法;許紅等[2]研究不同種類列車的布點模型,設計基于改進型遺傳算法的優化策略和算法;Castillo等[3]基于單雙線混合鐵路,提出基于二分法的優化算法,將運行圖編制問題進行簡化從而求解;張小炳等[4]將列車運行圖結構優化問題轉化為旅行商問題,以巡回路徑總費用最小化為目標建立0-1整數規劃模型,利用遺傳算法求解;張琴等[5]提出區間—咽喉區—到發線三段式列車運行圖編制框架,以列車運行總費用最小為目標建立0-1整數規劃模型;Feng等[6]針對高鐵提出一種在日常需求波動下的運行線合并與新增方法,并采用組合啟發式局部搜索算法求解。部分學者針對運行圖編制的多個階段,研究一體化(或協同)編制的技術和方法。Kaspi等[7]以旅客全程旅行時間和運營成本最小化為目標,建立運行圖優化模型,并采用交叉熵元啟發式方法求解;張寧[8]按照協同學相變理論,提出協同優化思路和方法;于汝濱等[9]以列車停站方案數、越行次數、區間群數、運行圖四邊形平均面積、運行線距離作為運行圖結構指標,批量鋪畫列車運行圖;Barrena等[10]基于旅客動態需求,提出單條線路上的非周期性列車時刻表一體化編制方法;Martin-iradi等[11]基于旅客出行時間提出期性列車運行圖編制算法,并結合丹麥鐵路進行實例驗證;張新等[12]考慮運行圖參數、車站停站次數等因素,構建列車停站方案與運行圖協同編制模型,并以京滬高鐵為例求解。

國內外學者對鐵路運行圖自動編制問題進行了大量探索,特別是對分階段思路下的高鐵列車運行圖編制技術方面的研究有一定基礎,但由于運行圖編制涉及因素較多,針對運行圖一體化自動編制仍處于探索階段,運行圖編制自動化程度仍不高。為此,本文面向高鐵運行圖編制,在不改變現有編圖模式的前提下,提出基于車底交路方案、列車結構方案、人工與自動調整在內的一體化自動編制流程,并考慮微觀站場進路占用策略,提出運行圖優化編制模型,以京滬高鐵作為案例進行驗證,為提升我國高鐵列車運行圖編制效率、提高列車運行圖編制質量提供技術支撐。

1 人工運行圖編制流程及原則概述

目前,我國鐵路列車運行圖的編制均由人工操作計算機鋪畫完成,全年一共編制4次季度運行圖、1次春運運行圖、1次暑運運行圖,按運行圖編制需求可分為新圖鋪畫和現圖調整2類,新圖鋪畫是在開通新線路后第一次進行運行圖鋪畫,現圖調整是在上一季度運行圖基礎上進行增加、刪除和修改,我國高鐵運行圖編制大部分情況下為現圖調整。

高鐵運行圖編制流程可分為基礎資料收集、開行方案確定、高等級與長交路列車運行線鋪畫、較低等級與短交路列車運行線鋪畫、運行圖輸出等步驟,各步驟具體含義如下:

1)基礎資料收集。由工務、電務、供電等部門在新圖鋪畫時提供新開通線路的基礎數據,由機務部門提供運行圖標尺,由車輛部門提供車型、配置、編組、數量、檢修地點等數據,由客運部門提供車底交路方案及停站需求,以上資料都提供給運輸部門作為編圖依據。

2)開行方案確定。中國國家鐵路集團有限公司(以下簡稱“國鐵集團”)組織各路局、各專業部門協商,下達本次調圖的輪廓性計劃,并通過溝通協調,確定具體列車開行方案,在現圖調整時主要為上一季度運行圖的車底交路方案和修改計劃。

3)高等級與長交路列車運行線鋪畫。根據國鐵集團確定的開行方案或車底交路方案修改計劃,鋪畫繁忙干線、跨局的長交路高速度等級列車運行線。

4)較低等級與短交路列車運行線鋪畫。根據國鐵集團、本局客運部門確定的開行方案或車底交路方案修改計劃,鋪畫與繁忙干線相銜接的其他線路、局管內、短交路以及較低速度等級列車運行線。

5)運行圖輸出。運行圖編制完成后,客運、車輛、機務人員都需要對涉及自身的運行圖要素進行驗證,然后根據運行圖輸出自己專業的相關信息。

高鐵運行圖編制原則有以下幾項:

1)適應客流。高鐵運行圖編制要適應高鐵沿線各站客流特點,滿足旅客出行的需要,盡可能均衡停站,并按時段、頻率安排列車運行線。

2)提高能力。高鐵運行圖編制要盡可能利用線路和車站的通過能力,減少不必要的越行與避讓,同時還要有一定冗余時間。

3)順序鋪畫。從列車速度等級看,列車按速度等級和交路長度進行劃分,旅行速度越高、交路越長、所跨路局越多的列車,其鋪畫的越優級越高,鋪畫好高等級列車運行線后再鋪畫較低等級列車運行線。從能力運用看,優先編制能力最為緊張的線路和區間,再鋪畫其他線路和區間。

4)合理運用。充分提高動車組車底運用效率,降低動車組運用數量,同時兼顧列車旅行速度、動車組檢修、司機換班等因素。

5)影響最小。當列車運行線鋪畫遇到沖突時,采用影響最小的改動方式協調運行線間的沖突,對于跨局列車來說,盡量不改動分界站列車到發時刻。

由人工運行圖編制流程及原則可見,高鐵運行圖編制涉及多專業、多部門,在編制過程中往往需要多方協調才能完成,且某條運行線一經修改,可能“牽一發而動全身”。因此,為實現列車運行圖的計算機自動編制,需要借鑒人工編制經驗,在目前編圖機制的基礎上盡可能實現自動化。

2 運行圖一體化自動編制流程

2.1 總體流程

高鐵列車運行圖一體化自動編制充分考慮高速鐵路運行圖人工編制機制和經驗,考慮現有運行圖編制流程和原則,提出迭代加入帶有車底交路的運行線自動編制方法,并結合調整策略,以全面適應現有列車運行圖調整、加密或重新編制等需求。高鐵列車運行圖一體化自動編制總體流程見圖1。

圖1 高鐵列車運行圖一體化自動編制總體流程

1)數據準備

與人工運行圖編制類似,一體化自動編制流程需要數據準備作為支撐。數據主要包含高速鐵路基礎設施、運行圖要素、運輸組織方案、模型參數4類。其中,高鐵基礎設施數據主要包含線路和站場數據;運行圖要素包含各類列車追蹤間隔時間及各類車站間隔時間;運輸組織方案數據主要包含上一季度列車時刻表、車底交路方案、本次調圖的相關列車結構方案;模型參數指與優化編制模型求解、自動調整等相關的參數。

2)數據處理

數據處理階段實現列車運行圖的生成,包括迭代加入車底交路、迭代加入列車結構方案、自動調整等等。其中,一體化指自動編制生成的列車運行圖完整包含列車時刻表、車底交路方案、車站股道運用方案,無需分階段生成;人工與自動調整指可人工或自動中斷自動編制過程,利用專家知識和經驗,調整相關內容后,繼續進行。

3)數據輸出

數據輸出結果為完整的列車運行圖,主要包含列車時刻表、車底交路方案、車站股道運用方案3類。

2.2 車底交路方案與列車結構方案

車底交路方案是高鐵列車運行圖一體化自動編制過程的重要基礎資料之一。利用車底交路方案自動編制運行圖的基本思路是,依據上一季度與新一季度運行圖車底交路方案,按優先級順序,依次將車底交路改動方案進行鋪畫。為控制求解規模,保持已加入列車的停站方案、路徑方案和開行順序,一體化生成待加入列車的時刻、停站方案和路徑方案。

列車結構方案是列車結構的集合,1個列車結構是1組列車的共同結構信息,主要內容包括:

1)車底信息。包括速度級、編組方案等。

2)停站方案信息。指在每個車站的停站方案,包括是否必停、禁?；蛲Ｕ颈壤?、是否整點發車、出發和到達時間范圍、最小出發和到達間隔時間等。

3)分區段方案。對開行路徑上的某個區段,設置越行、停站數量、慢行時分等要求。

2.3 人工與自動調整

人工與自動調整策略主要用于解決列車運行圖結構優化問題,包括以下典型情形:①在一個時空范圍內,組織多列車的停站方案規律化,包括交錯停站、成組交錯停站、集中停站或通過等模式,優化利用通過能力;②對特定OD,使時段服務頻率與時段客流量分布相匹配。人工調整的因素主要為迭代車底交路或列車結構加入運行圖時存在隨機性、迭代間隔時間過長等。

當前的數學規劃方法均難以描述多列車的停站方案組合優化以及開行時段分布優化等要求,即在列車開行順序以及時段均不確定的情況下,難以構建線性約束或優化目標。對于①類問題,需要在保持列車開行順序的情況下,人工或自動調整列車停站方案。對于②類問題,需要人工調整列車開行順序。

3 微觀站場進路占用策略

3.1 備選路徑

列車在每個車站或線路所均有一個備選路徑集合,每條備選路徑由列車作業的進路依次連接構成?；谡€通過、側線停站的一般規則,備選路徑和停站方案有對應關系。

考慮進路占用時間不同,將進路分為股道區段和咽喉區段,統稱為進路區段。每個進路區段的占用開始和結束時刻基本均以列車到達或出發時刻為基準,提前或推遲固定的時長表示,進路占用時間示意見圖2。

圖2 進路占用時間示意

圖2中,對于發車和通過作業,由于發車進路釋放與第一離去出清時刻存在較小的冗余時間,對運行圖編制的影響很小,因而每個進路區段的占用時間與列車到達或出發時刻關聯最為緊密。每條備選路徑由股道方案、停站方案、進路區段集合與進路區段占用時間所決定。

3.2 間隔時間

間隔時間作為運行圖編制的重要參數,是運行線鋪畫的主要限制條件之一。高速鐵路列車運行圖一體化自動編制流程中主要考慮以下兩種間隔時間情形。

1)一般間隔時間

根據Q/CR 471—2015《高速鐵路列車間隔時間查定辦法》[13],除具體需要確定的間隔時間以外,列車追蹤間隔類型共含6種,車站間隔時間共含4種。由于運行圖編制屬于中觀列車運行體現,流程中主要考慮列車出發追蹤間隔、列車到達追蹤間隔、列車通過追蹤間隔、同方向列車到通間隔、同方向列車通發間隔、敵對進路相對方向不同時到發間隔以及不同時發到間隔等8種。理論上,只要進路占用時間參數取值準確,運行圖編制無需額外考慮間隔時間要求。

2)動車所出入庫特殊情形

對于動車所出入庫線(或可雙向開行的任意單線區間),需額外考慮先發后到與先到后發間隔時間要求,動車所出入庫線先發后到與先到后發間隔時間示意見圖3。

圖3 動車所出入庫線先發后到與先到后發間隔時間示意

情形A時,只有前行出發列車出清區間且鄰站進路釋放后,后行到達列車才可辦理鄰站發車作業進入動車所出入庫線。情形B與一般敵對進路相對方向不同時到發間隔基本相同。由于動車所在列車運行圖上也作為車站節點之一,當鋪畫動車所出入庫運行線時,需額外考慮先發后到間隔時間。

4 運行圖優化編制模型與求解

4.1 問題描述

為實現運行線自動編制,運行圖優化編制模型的問題描述如下:在已有基本圖或空白圖基礎上,根據需求建立車底交路方案,將每個車底交路依次迭代加入列車運行圖,為待加入列車一體化生成時刻、停站方案和路徑方案,同時待加入列車運行線、交路滿足微觀站場占用約束。迭代加入車底交路失敗時,采用人工或自動調整方法,直至所有車底交路鋪完為止。

4.2 參數和變量

運行圖優化編制模型參數與變量定義見表1。

表1 運行圖優化編制模型參數與變量定義

4.3 優化目標

1)最大化車站股道運用方案的性能

使車站股道運用方案的性能值之和最大,對于大型客運站,盡可能選用平行進路接發車,即

(1)

2)最小化期望停站方案的偏差

使車站停站方案盡可能按照預先設置的列車結構進行停站,即

(2)

3)最小化車底周轉時間

使動車組車底周轉時間盡可能小,最大化利用動車組車底,即

(3)

4.4 基本約束

1)列車停站方案約束

對當前列車,保持停站方案;對待加入的列車,除指定必停站和禁停站外,其他車站的停站方案通過模型優化生成,即

(4)

2)列車路徑方案約束

對已加入的列車,保持路徑方案;對待加入的列車,路徑方案通過模型優化生成,即

(5)

3)列車區間開行順序約束

對已加入的任意兩列車,保持區間開行順序;待加入列車與已加入列車的區間開行順序通過模型優化生成,即

(6)

4)列車停站時間約束

列車停站時間與停站方案有關,即

(7)

5)列車區間運行時間約束

列車區間運行時間由純運行時間、慢行時分、起車和停車附加時間構成,與列車在兩端車站的停站方案有關,即

(8)

6)列車接續時間約束

列車接續時間與接續方式有關,即

(9)

7)列車跨線運行時間約束

對列車的始發站和終到站,若不在優化編制模型的路網區域內,應考慮列車在區域外的運行時間,滿足始發站和終到站的開行時間范圍要求,即

8)車站路徑選擇約束

路徑方案與停站方案存在對應關系,即

9)車站進路占用約束

10)禁止同時辦理列車作業約束

對特定條件的車站,如進站信號機外方為6‰下坡道,且股道無隔開設備時,盡管兩條進路在空間上不沖突,仍禁止同時辦理列車作業。用符號≠表示兩個進路區段位于禁止同時辦理的兩條進路上。不失一般性,禁止同時辦理可表示為:一個進路區段的占用開始時刻與另一個進路區段的占用結束時刻存在最小間隔時間要求。用常量t常表示進路區段占用的最小間隔時間,即

11)列車結構約束

(20)

(21)

4.5 求解流程

針對固定數量的車底交路,按優先級順序,每次將1個車底交路加入列車運行圖,每個車底交路中的列車帶有列車結構,一體化生成待加入列車的時刻、停站方案和路徑方案。在數據準備完成后,運行圖編制流程如下:

Step2遍歷車底交路ci,若C=?時,結束。

Step3對車底交路ci進行排序,若選擇人工調整轉Step4,否則轉Step5。

Step4人工調整列車運行圖或車底交路。

Step5選擇車底交路ci,加入列車運行圖,成功時轉Step2,失敗時轉Step6。

Step6自動調整,若選擇人工調整轉Step3,否則轉Step5。

運行圖優化編制模型屬于多目標MIP問題,同時包含整數和連續變量,而整數變量的數量直接影響模型求解速度。為控制求解規模,使模型每一步迭代過程中的約束和變量數量可控,在新加入列車時,保持已加入列車L當前的停站方案、路徑方案和開行順序不變,僅調整列車時刻。針對3個優化目標,采用加權疊加方法將原問題轉化為單目標優化問題求解,根據以往研究經驗,通用算法中如列生成算法、分支切割法可有效求解大規模線性規劃問題,使用商業計算軟件對該問題進行求解。

5 案例研究

根據以上運行圖優化編制模型,完整集成一體化自動編制技術,并以京滬高速鐵路某季度季度列車運行圖為基礎,采用運行圖一體化自動編制流程編制下一季度列車運行圖。

5.1 數據準備

1)線路數據。建立京滬高速鐵路全線數據,包含站間距、線路屬性等。

2)站場數據。建立京滬高鐵23個車站及6個線路所站場拓撲圖,關聯各站到發線、正線關系,輸入進路連接關系。因篇幅有限,對北京南站、濟南西站、南京南站、上海虹橋站4個站場數據進行展示,見圖4～圖7。

圖4 北京南站站場數據

圖5 濟南西站站場數據

圖6 南京南站站場數據

圖7 上海虹橋站站場數據

3)運行圖要素數據。包含不同速度等級列車區間運行時分(含起停附加時分)、車站進路占用時分、車站進路間隔時分、區間運行間隔時分、車站停時等。

4)運輸組織方案數據。輸入上一季度運行圖車底交路方案與列車時刻表,根據本季度運行圖修改計劃,建立新列車開行結構方案。本次案例研究共輸入362個車底交路方案,通過分析上一季度列車運行圖開行結構,本次案例研究共輸入104個列車開行結構方案。

5.2 案例計算結果

通過基于車底交路方案和列車結構方案的運行圖一體化自動編制流程,編制過程中適時人工中斷調整,用時48h,完成京滬高鐵案例運行圖。

京滬高速鐵路案例下行各站列車數統計見表2。

表2 京滬高速鐵路案例下行各站列車數統計 列

京滬高鐵案例上行各站列車數統計見表3。京滬高鐵案例部分下行列車停站方案見圖8。京滬高鐵案例部分動車組車底交路方案見圖9。

表3 京滬高鐵案例上行各站列車數統計 列

圖8 京滬高鐵案例部分下行列車停站方案

圖9 京滬高鐵案例部分動車組車底交路方案

案例計算所得到運行圖,鋪畫運行線共585列,其中下行292列,上行293列,包含京滬高速鐵路各車次車底交路方案以及各車站股道運用方案。京滬高速鐵路案例與真實運行圖統計指標比較見表4。

表4 京滬高速鐵路案例與真實運行圖統計指標比較

由表4可見,在上一季度運行圖基礎上,案例計算所得到的京滬高速鐵路列車運行圖,相比下一季度真實運行圖多鋪畫列車24列,旅行速度、技術速度、速度系數、平均停站時分等統計指標均與真實運行圖相近,驗證了一體化自動編制方法的有效性。由于列車結構方案參數存在一定隨機性,列車結構方案越細致、具體,所計算得到的運行圖越滿足編圖需求。

6 結論

高速鐵路列車運行圖一體化自動編制方法實現了列車時刻表、車站股道運用方案、車底交路方案的一體化自動編制,充分借鑒人工運行圖編制經驗,將人工與自動調整流程嵌入一體化自動編制流程,為列車運行圖結構優化提供了切實可行的途徑,通過京滬高速鐵路案例研究,驗證了運行圖一體化自動編制技術的可行性。研究結果表明,高速鐵路列車運行圖一體化自動編制方法所計算得到的運行圖與人工編制的真實運行圖相近,可顯著減少人工運行圖編制流程中的人力和物力?，F階段,為使高速鐵路列車運行圖一體化自動編制所得結果更為理想,還需要進一步細化列車結構,同時適時采用人工調整策略,未來仍需要對高速鐵路列車運行圖一體化自動編制流程進行優化。