段卿培， 馮小芳， 李欣

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

0 引言

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

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

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

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

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

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

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

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

圖2 車站“行車資源”

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

1.2 多商品流模型

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

表1 模型參數(shù)

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

1.3 拉格朗日松弛算法

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

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

對(duì)式（7）進(jìn)行恒等變換，得：

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

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

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

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

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

步驟1：初始化。

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

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

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

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

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

2 實(shí)現(xiàn)方法

基于以上關(guān)鍵技術(shù)做后臺(tái)算法支撐，設(shè)計(jì)研發(fā)了列車運(yùn)行計(jì)劃應(yīng)急調(diào)度調(diào)整原型系統(tǒng)，并給出具體算例作為測(cè)試用例，借助系統(tǒng)直觀體現(xiàn)調(diào)整結(jié)果，通過系統(tǒng)結(jié)果分析驗(yàn)證基于時(shí)空網(wǎng)絡(luò)的列車運(yùn)行計(jì)劃應(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ū)間、線路封鎖行別、線路封鎖時(shí)間范圍等選項(xiàng)，同時(shí)可實(shí)現(xiàn)調(diào)整計(jì)劃發(fā)布、調(diào)整計(jì)劃導(dǎo)出等功能。點(diǎn)擊“運(yùn)行圖”按鈕，可跳轉(zhuǎn)至自動(dòng)調(diào)整結(jié)果展示界面，通過列車運(yùn)行圖方式顯示所有車次調(diào)整后的運(yùn)行計(jì)劃和正晚點(diǎn)情況，可分別選擇不同線路行別查看，同時(shí)可以在調(diào)整結(jié)果展示界面進(jìn)行人工手動(dòng)調(diào)整，用戶可根據(jù)實(shí)際需求調(diào)整列車運(yùn)行計(jì)劃。并根據(jù)晚點(diǎn)時(shí)長差異，分紅、黃、綠3 色站址運(yùn)行線（見圖5）。

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

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

2.2 算法示例

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

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

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

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

2.3 結(jié)果分析

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

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

3 結(jié)束語

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