基于時空網(wǎng)絡(luò)的列車運行計劃應(yīng)急調(diào)整方法

段卿培， 馮小芳， 李欣

（1. 中國鐵路北京局集團有限公司 調(diào)度所，北京 100860；2. 中國鐵道科學(xué)研究院集團有限公司 電子計算技術(shù)研究所，北京 100081；3. 北京經(jīng)緯信息技術(shù)有限公司 鐵路運輸與調(diào)度技術(shù)中心，北京 100081）

0 引言

列車運行過程中會遇到一些外界因素干擾，無法按照計劃運行，造成不同程度的晚點，如大風(fēng)天氣導(dǎo)致列車限速運行、設(shè)備故障導(dǎo)致區(qū)間封鎖等。因此鐵路運輸組織除了需要制定列車運行計劃，還需根據(jù)實際突發(fā)情況對列車運行計劃進行相應(yīng)調(diào)整。隨著高速鐵路的不斷發(fā)展，繁忙干線上高速列車開行列數(shù)日益增長，當面臨大規(guī)模擾動時，傳統(tǒng)人工調(diào)整列車開行計劃的方法使調(diào)度員面臨高強度的工作挑戰(zhàn)，且該調(diào)整方法也很難滿足調(diào)度調(diào)整時效性的要求。

目前，列車運行計劃調(diào)整問題的研究方法主要有：（1）基于規(guī)則的專家系統(tǒng)模式［1?2］；（2）基于遺傳算法、模擬退火算法等智能優(yōu)化算法模式［3?4］；（3）基于運籌學(xué)模型的模式，常用建模方式包括基于網(wǎng)絡(luò)流建模［5?6］、基于替代圖建模［7?8］等。鑒于網(wǎng)絡(luò)流建模方法是針對每一列車建立獨立的網(wǎng)絡(luò)流模型，有助于區(qū)分不同等級列車，更符合我國高速鐵路運輸生產(chǎn)場景，在依照既有調(diào)度策略規(guī)律［9］的基礎(chǔ)上，將以時空網(wǎng)絡(luò)的網(wǎng)絡(luò)流建模方式研究列車運行計劃應(yīng)急調(diào)整方法，使調(diào)度員能夠快速、合理地制定調(diào)整計劃，提高應(yīng)急行車指揮的決策效率。

1 關(guān)鍵技術(shù)

1.1 時空網(wǎng)絡(luò)

通過時空網(wǎng)絡(luò)對時間、空間的離散化表示，構(gòu)建列車所有可能時空軌跡的枚舉（見圖1）。網(wǎng)絡(luò)中共有4 種節(jié)點：（1）虛擬起點，表示列車在時空網(wǎng)絡(luò)中生成；（2）虛擬終點，表示列車在時空網(wǎng)絡(luò)中消失；（3）到達節(jié)點，表示列車在某一時刻在車站進行到達作業(yè)；（4）出發(fā)節(jié)點，表示列車在某一時刻在車站進行出發(fā)作業(yè)。網(wǎng)絡(luò)中共有4 種弧段：（1）虛擬起始弧，表示列車駛?cè)霑r空網(wǎng)絡(luò)表示的時空范圍；（2）虛擬終止弧，表示列車駛出時空網(wǎng)絡(luò)表示的時空范圍；（3）站內(nèi)停站（通過）弧，表示列車在某一車站從到達作業(yè)向出發(fā)作業(yè)的轉(zhuǎn)變，可分為列車停站和列車通過；（4）站間運行弧，表示列車在區(qū)間運行。

圖1 時空網(wǎng)絡(luò)示意圖

在圖1構(gòu)建的時空網(wǎng)絡(luò)中，節(jié)點和弧線需要滿足問題約束和臨時限速（封鎖）命令限制，因此構(gòu)建模型時，各節(jié)點和弧線需滿足：（1）站間運行弧的運行時間不得小于運行時分標尺；（2）不得在列車原計劃停站車站建立站內(nèi)通過??；（3）所有站內(nèi)停站弧的停站時間不得小于車站最小停站時分；（4）在臨時封鎖命令的時空范圍內(nèi)不得有站間運行弧；（5）列車出發(fā)時間范圍應(yīng)考慮車底接續(xù)關(guān)系。其中（5）具體指：具有車底接續(xù)關(guān)系的列車，在折返站應(yīng)滿足最小折返作業(yè)時間要求［10］。另外，為了限制時空網(wǎng)絡(luò)的網(wǎng)絡(luò)規(guī)模，還需設(shè)置列車在首站的出發(fā)時間范圍和沿途各站的最大作業(yè)時間。通過逐一枚舉滿足以上約束的時空路徑，得到各列車的時空網(wǎng)絡(luò)。由于實際運輸生產(chǎn)環(huán)境中列車等級不同、列車停站方案不同、臨時限速（封鎖）命令對列車的影響范圍不同，因此時空網(wǎng)絡(luò)應(yīng)參照各列車的區(qū)間運行時分標尺、技術(shù)作業(yè)時間標準、停站方案、受臨時封鎖（限速）的影響范圍，針對每一列車構(gòu)建時空網(wǎng)絡(luò)。

時空網(wǎng)絡(luò)中，每條弧線上占用一定數(shù)量的時空點表示列車運行過程中對股道的占用，這些時空點也被稱為“時空資源”［6，11］，通過約束各時空資源至多被1列車占用的策略，保證列車間的追蹤間隔時間。約束時空資源需首先定義車站“行車資源”。將車站離散為接車進路、到發(fā)線、正線和發(fā)車進路4 種類型，這4 種類型線路被稱為行車資源（見圖2），列車通過車站時需占用行車資源。將行車資源沿時間軸展開，得到時空資源。按對應(yīng)的行車資源類別，時空資源也可分為接車時空資源、發(fā)車時空資源、股道時空資源。站間運行弧會占用發(fā)車時空資源和接車時空資源，站內(nèi)停站（通過）弧會占用股道時空資源。各弧段行車資源占用的時間范圍可根據(jù)最小間隔時間標準得到。由于在實際調(diào)度調(diào)整過程中，采用的最小間隔時間標準可能與編制列車運行圖所采用的間隔時間標準不一致，在此所指的所有間隔時間均指調(diào)度調(diào)整中所采用的間隔時間標準。以到達間隔時間為例（見圖3），最小到達間隔時間和最小到通間隔時間可分為2 部分：前車延后釋放時間、后車提前占用時間。其中延后釋放時間指從列車車頭到達接車進路起，至接車進路解鎖為止的時間。提前占用時間是指從接車進路開始辦理，至列車車頭到達接車進路為止的時間。發(fā)車進路占用時間范圍與接車進路類似。對于到發(fā)線和股道，其占用時間范圍等同于列車停留（通過）股道時長。

圖2 車站“行車資源”

圖3 最小到達間隔與占用“時空資源”轉(zhuǎn)換

1.2 多商品流模型

在時空網(wǎng)絡(luò)中，列車運行線就是1條由節(jié)點和邊順序銜接的路徑，運行調(diào)整問題就是為每一列車分配1條與其他列車沒有沖突關(guān)系的路徑。若將1 列車視為1 支網(wǎng)絡(luò)流，則運行調(diào)整問題可歸結(jié)為時空網(wǎng)絡(luò)上的多商品流問題［12?13］。在此基礎(chǔ)上可構(gòu)建列車運行調(diào)整問題的模型，模型參數(shù)見表1。

表1 模型參數(shù)

具體模型定義如下：式（1）表示目標函數(shù)，即總晚點時分最小。假設(shè)列車到達s點（或駛離s點）的計劃時刻為t0，則|t0?t|；式（2）為流平衡約束；式（3）標記了各列車時空網(wǎng)絡(luò)中每條時空弧所占用的時空資源；式（4）標記了列車對各時空資源占用的約束；式（5）表示任意時空資源最多只能被1列車占用。當1時，就會出現(xiàn)列車沖突；式（6）為決策變量的取值約束。

1.3 拉格朗日松弛算法

制約上述模型求解效率的約束是約束（5）（即式（5）），它導(dǎo)致各列車之間產(chǎn)生了大規(guī)模的組合優(yōu)化，進而影響求解速度。拉格朗日松弛是處理這種組合優(yōu)化問題的常用方法，它將復(fù)雜約束松弛，并將其構(gòu)造為懲罰項加入目標函數(shù)中，形成拉格朗日對偶問題，從而使得原本的組合優(yōu)化問題轉(zhuǎn)變?yōu)獒槍我粋€體的優(yōu)化問題，降低了模型求解難度，在此采用拉格朗日松弛算法解決求解效率問題。

首先將約束（5）松弛，利用拉格朗日乘子λrs，t，構(gòu)造拉格朗日對偶問題Z(D)，Z(D)的目標函數(shù)為：

對式（7）進行恒等變換，得：

為使拉格朗日對偶問題的解逼近原問題的最優(yōu)解，需要迭代更新拉格朗日乘子的值。采用次梯度法更新拉格朗日乘子：

式中：q表示當前迭代次數(shù)，

一般情況下，拉格朗日對偶問題計算得到的是不可行解，還需利用啟發(fā)式算法對結(jié)果進行可行化。當?shù)Y(jié)束后，由于拉格朗日乘子λrs，t實際上代表違背約束（5）的懲罰值，即λrs，t越大，各列車子問題求解結(jié)果在(s，t)處的沖突越大。利用式（11）可以計算列車f總沖突值CVf。

計算完畢后對各列車CVf進行排序，CVf越大代表該列車產(chǎn)生沖突越嚴重，應(yīng)當在調(diào)整中優(yōu)先鋪畫。各列車依次鋪畫完畢后，即得到1個可行解。

相應(yīng)的拉格朗日算法，輸入為模型相關(guān)輸入；輸出為對偶問題的解、原問題可行解。具體求解步驟如下：

步驟1：初始化。

步驟2：求解對偶問題。（1）利用最短路徑算法求解拉格朗日對偶問題；（2）求解對偶問題最優(yōu)解下界。

步驟3：將對偶解轉(zhuǎn)換為可行解，采用基于優(yōu)先級規(guī)則的實現(xiàn)算法將對偶解轉(zhuǎn)換為可行解，并計算對偶問題最優(yōu)解上界。

步驟4：計算最優(yōu)解上下界的最優(yōu)偏差。

步驟5：更新拉格朗日乘子。

步驟6：迭代結(jié)束條件。

2 實現(xiàn)方法

基于以上關(guān)鍵技術(shù)做后臺算法支撐，設(shè)計研發(fā)了列車運行計劃應(yīng)急調(diào)度調(diào)整原型系統(tǒng)，并給出具體算例作為測試用例，借助系統(tǒng)直觀體現(xiàn)調(diào)整結(jié)果，通過系統(tǒng)結(jié)果分析驗證基于時空網(wǎng)絡(luò)的列車運行計劃應(yīng)急調(diào)整方法的效果。

2.1 原型系統(tǒng)

系統(tǒng)前端基于apache tomcat 架構(gòu)，采用Java 開發(fā)語言；后端基于.net framework 4.0 框架，采用C#開發(fā)語言。系統(tǒng)主界面見圖4，可以設(shè)置故障線路、故障區(qū)間、線路封鎖行別、線路封鎖時間范圍等選項，同時可實現(xiàn)調(diào)整計劃發(fā)布、調(diào)整計劃導(dǎo)出等功能。點擊“運行圖”按鈕，可跳轉(zhuǎn)至自動調(diào)整結(jié)果展示界面，通過列車運行圖方式顯示所有車次調(diào)整后的運行計劃和正晚點情況，可分別選擇不同線路行別查看，同時可以在調(diào)整結(jié)果展示界面進行人工手動調(diào)整，用戶可根據(jù)實際需求調(diào)整列車運行計劃。并根據(jù)晚點時長差異，分紅、黃、綠3 色站址運行線（見圖5）。

圖4 系統(tǒng)主界面

圖5 調(diào)整結(jié)果展示界面及手動調(diào)整界面

2.2 算法示例

算例以京廣高鐵為背景構(gòu)造，共包含中國鐵路北京局集團有限公司管內(nèi)的北京西—安陽東共12 個車站和1個線路所。本算例模擬的運輸場景為：模擬徐水東站—保定東站的上行和下行區(qū)間均被臨時封鎖場景，模擬封鎖從12：05 開始至14：05 結(jié)束。按照上述模型和算法調(diào)整后的運行圖結(jié)果見圖6、圖7。該算例在CPU 為Intel（R）i7?10750H、內(nèi)存為16G 運行環(huán)境下的優(yōu)化結(jié)果見表2。

表2 算例優(yōu)化結(jié)果

圖6 優(yōu)化后上行方向列車運行圖

圖7 優(yōu)化后下行方向列車運行圖

2.3 結(jié)果分析

算例求解結(jié)果中，下行方向晚點時長更長，這是由于北京西站屬于折返站，大部分下行列車需依賴上行列車的車底進行作業(yè)，因此算例中下行列車發(fā)車時間范圍還受到上行列車晚點的影響，晚點時長更長。

另一方面，在為各列車的時空網(wǎng)絡(luò)劃定封鎖區(qū)間影響時空范圍時，不僅包含徐水東站—保定東站的封鎖區(qū)間，還考慮到實際現(xiàn)場運輸指揮時，調(diào)度員通常不允許臨時封鎖結(jié)束時間前對車站扣車提前發(fā)車，因此在圖6、圖7 中，各車站在封鎖時間內(nèi)的扣車均未提前發(fā)車。

3 結(jié)束語

從算例求解效果看，上述基于時空網(wǎng)絡(luò)的列車運行計劃應(yīng)急調(diào)整方法的模型和算法以及依此設(shè)計的列車運行計劃自動調(diào)整系統(tǒng)，能夠適應(yīng)實際運輸生產(chǎn)場景的準確性和時效性要求，對實際應(yīng)急調(diào)度指揮工作具有一定指導(dǎo)作用，并有助于減輕調(diào)度員工作強度。