張若惠 ，王奇志，田海寧，苗建瑞，譚憶涵

（1.北京交通大學 軌道交通控制與安全國家重點實驗室，北京 100044；2.北京交通大學 交通運輸學院，北京 100044；3.中國鐵路沈陽局集團有限公司 調(diào)度所，遼寧 沈陽 110001)

0 引言

京張高速鐵路的開通運營標志著我國正式進入智能高速鐵路時代，意味著高速鐵路將在運輸組織、客運服務(wù)、安全監(jiān)控等方面實現(xiàn)智能化升級[1]。智能調(diào)度不僅是實現(xiàn)鐵路高效運營管理的有效措施[2]，更是實現(xiàn)高速鐵路全網(wǎng)智能運營的基礎(chǔ)保障。作為鐵路運輸?shù)年P(guān)鍵節(jié)點，大型高速鐵路客運站復(fù)雜的線路結(jié)構(gòu)和運用規(guī)則，導(dǎo)致車站作業(yè)調(diào)整成為智能調(diào)度技術(shù)的一個難點。

當高速列車發(fā)生晚點，導(dǎo)致既定的車站作業(yè)計劃不可執(zhí)行時，需要實時調(diào)整列車到發(fā)線、進路甚至到發(fā)時刻，以恢復(fù)列車的正常運行秩序。既有研究[3-6]表明采用高效的調(diào)整方法可減少列車晚點對車站作業(yè)秩序的影響。為滿足車站作業(yè)計劃調(diào)整的高時效性要求，彭其淵等[7]考慮車站設(shè)備故障及列車晚點的情況，對高速鐵路列車到發(fā)時刻及進路調(diào)整方法進行了研究。馬駟等[8]結(jié)合道岔分組方法研究了車站作業(yè)計劃調(diào)整問題。為了便于描述列車沖突，彭其淵等[9]在使用離散時空資源描述到發(fā)線的基礎(chǔ)上，建立了客運站到發(fā)線運用調(diào)整的整數(shù)規(guī)劃模型。李濤等[10]運用數(shù)理統(tǒng)計方法預(yù)估列車到發(fā)時刻，并建立了客運站到發(fā)線運用優(yōu)化模型。高速客運站的調(diào)整計劃既包含到發(fā)線和進路的調(diào)整，也包含列車到發(fā)時刻的調(diào)整，既有研究大多側(cè)重某一個方面，將所有調(diào)整內(nèi)容一體優(yōu)化的研究目前較少?；谝陨戏治?，并結(jié)合車站的實際運營情況，構(gòu)建基于離散時空網(wǎng)絡(luò)的多商品流的車站作業(yè)計劃一體化調(diào)整模型，根據(jù)調(diào)度調(diào)整實時性需求和模型特點，設(shè)計基于列生成的啟發(fā)式算法，并以長春西站為案例進行驗證。

1 車站作業(yè)計劃調(diào)整問題分析

1.1 問題描述

在具有動車組接續(xù)關(guān)系的終到和始發(fā)列車?？客坏桨l(fā)線，且不考慮車站內(nèi)進行動車組重聯(lián)和拆解的條件下，所有列車在高速鐵路客運站辦理的作業(yè)流程都可歸納為進站、占用到發(fā)線和出站3 個作業(yè)環(huán)節(jié)。高速鐵路車站作業(yè)計劃調(diào)整就是當列車運行發(fā)生干擾時，在滿足車站作業(yè)安全間隔時間、列車技術(shù)作業(yè)需求、線路和進路運用規(guī)則等約束的基礎(chǔ)上，快速地為各列車安排合理的到發(fā)線、進出站進路和到發(fā)時刻，以確保車站的服務(wù)水平及作業(yè)組織的有序性。

由于列車運行具有時空屬性，其在車站內(nèi)的作業(yè)過程可表述為從進站端至出站端的一條時空軌跡。一般而言，列車根據(jù)其作業(yè)的起止時刻在空間上有多條可選用的線路。若選取道岔、到發(fā)線等站內(nèi)關(guān)鍵設(shè)施來刻畫車站的空間結(jié)構(gòu)，并將時間按照一定的精度進行離散化時，列車的時空軌跡可用由〈關(guān)鍵設(shè)施，離散時刻〉構(gòu)成，且按時間順序排列的二元組序列描述。

若將〈關(guān)鍵設(shè)施，離散時刻〉二元組實例作為節(jié)點，以關(guān)鍵設(shè)施之間的空間聯(lián)系和時間步進關(guān)系作為弧，由此可構(gòu)建一個離散的車站作業(yè)時空網(wǎng)絡(luò)。此時，車站作業(yè)計劃調(diào)整問題就是在該網(wǎng)絡(luò)中為每列車尋找一條與其他列車無沖突，且滿足其作業(yè)要求的最優(yōu)路徑的組合優(yōu)化問題。若將列車看作商品，列車的進、出站看作商品在時空網(wǎng)中流進和流出，車站作業(yè)計劃調(diào)整問題則抽象為基于離散時空網(wǎng)絡(luò)的多商品流問題。

在此基礎(chǔ)之上，由于列車占用設(shè)備具有一定時長及列車之間必須保持安全間隔時間的特性，車站作業(yè)計劃調(diào)整需要解決對設(shè)備占用和間隔時間刻畫的問題。因此，以下針對性分析車站作業(yè)離散時空網(wǎng)絡(luò)的構(gòu)建、線路占用時間的刻畫。

1.2 車站作業(yè)離散時空網(wǎng)絡(luò)構(gòu)建

為了能夠刻畫列車的到發(fā)方向、列車對線路的排他性占用原則，以及不同種類列車對線路的選擇規(guī)則，以站界、軌道區(qū)段分界點及到發(fā)線中心等位置作為關(guān)鍵設(shè)施。二元組中的離散時刻是對自TS時刻起至TE時刻止的調(diào)整時間段[TS，TE]，以Δ為單位，如1 s 或5 s，進行離散后形成的一系列時刻點。以上的關(guān)鍵設(shè)施和離散時刻點則構(gòu)成離散時空網(wǎng)絡(luò)中的實體節(jié)點集合。實體節(jié)點表示列車在何時處于何處。除實體節(jié)點外，為了便于搜索列車路徑，給每列車設(shè)置一個用來表示其開始和結(jié)束的虛擬起點和虛擬終點。這類虛擬節(jié)點上的關(guān)鍵設(shè)施和離散時刻均沒有具體的物理含義，其作用僅表示搜索的起點和終點。

網(wǎng)絡(luò)中的邊分為連接實體節(jié)點之間的作業(yè)弧，以及實體節(jié)點和虛擬節(jié)點之間，虛擬節(jié)點與虛擬節(jié)點之間的虛擬弧。作業(yè)弧包括用來表示列車從一個位置位移到另外一個位置的運行弧，列車在弧上的運行時間就是2 個節(jié)點之間的時間差；還包括用來表示列車在到發(fā)線上停留的作業(yè)弧。作業(yè)弧連接的2 個節(jié)點的關(guān)鍵設(shè)施屬性必須為到發(fā)線類，同時離散時刻屬性不能相同。虛擬弧包括表示列車進入時空網(wǎng)絡(luò)的虛擬進站弧和表示列車駛離時空網(wǎng)絡(luò)前往虛擬終點的虛擬出站弧，即分別為由虛擬起點轉(zhuǎn)移至實體節(jié)點和由實體節(jié)點轉(zhuǎn)移至虛擬終點所對應(yīng)的虛擬??；還包括由虛擬起點至虛擬終點的虛擬弧，該弧表示列車的虛擬路徑，若列車選擇該條路徑，則表示該列車在實際中沒有無沖突路徑可選擇。以下以一個虛構(gòu)的車站為例對車站作業(yè)離散時空網(wǎng)絡(luò)進行詳細說明。

虛構(gòu)車站作業(yè)時空網(wǎng)絡(luò)示意圖如圖1 所示。車站空間網(wǎng)絡(luò)如圖1a 所示，其中節(jié)點表示車站關(guān)鍵設(shè)施，邊表示連接關(guān)鍵設(shè)施之間的線路。將時間進行離散化處理后，構(gòu)建的車站離散時空網(wǎng)絡(luò)如圖1b 所示。其中縱軸上的數(shù)字代表空間網(wǎng)絡(luò)中節(jié)點的編號，橫軸上的數(shù)字代表離散時刻的編號。在圖1b 中給出了列車?？?G 的空間路徑(虛線)對應(yīng)的2 條時空路徑和一條虛擬路徑。該網(wǎng)絡(luò)中的時空節(jié)點包含由實心圓表示的含有〈關(guān)鍵設(shè)施，離散時刻〉物理意義的實體節(jié)點和由空心圓表示的虛擬節(jié)點。網(wǎng)絡(luò)中的運行弧表示列車在站內(nèi)的走行過程，如弧B；停站弧表示列車在到發(fā)線上的停留過程，如弧C；弧A 和弧D 分別為虛擬進站弧和虛擬出站弧，表示列車在時空網(wǎng)絡(luò)中的生成與消失。

圖1 虛擬車站作業(yè)時空網(wǎng)絡(luò)示意圖Fig.1 Diagram of time-space network based on virtual station operation

1.3 線路占用時間刻畫

目前，列車在高速鐵路車站中的走行均以進路為單位，且進路采用一次鎖閉和分段解鎖的聯(lián)鎖方式。列車在車站的走行和停留過程可體現(xiàn)為對軌道區(qū)段占用和釋放的過程。根據(jù)時空網(wǎng)絡(luò)的構(gòu)建方法，可知每個作業(yè)弧對應(yīng)的是一個軌道區(qū)段，因而如何刻畫軌道區(qū)段的占用就成為精準描述車站作業(yè)過程的基礎(chǔ)。閉塞時間(Blocking Time)[11]是一種刻畫列車排他性占用特定范圍線路的描述方法，既可以描述列車在線路上的走行時間，也能描述列車之間的間隔時間。列車占用軌道區(qū)段的閉塞時間如圖2 所示，主要由以下3 部分構(gòu)成。①鎖閉時間：指自開始辦理列車進路時刻起至列車頭部到達軌道區(qū)段入口處止的時間范圍，表示為T鎖閉。②運行時間：指列車頭部自軌道區(qū)段入口處運行至軌道區(qū)段出口處的時間范圍，表示為T運行。③清空時間：指自列車頭部越過軌道區(qū)段出口處起至該軌道區(qū)段解鎖時刻止的時間范圍，表示為T釋放。

圖2 中a12為列車k1，k2先后占用軌道區(qū)段q的空閑間隔時間，結(jié)合兩列車在q上的閉塞時間，其間隔時間為則為列車k1，k2使用軌道區(qū)段q的最小安全間隔時間，若a12＜ 0，即k1的閉塞時間與k2的閉塞時間發(fā)生重疊，表示k1與k2在使用軌道區(qū)段q時有沖突。

圖2 列車占用軌道區(qū)段的閉塞時間Fig.2 Blocking-time of track sections occupied by train

2 車站作業(yè)計劃調(diào)整模型與算法

2.1 車站作業(yè)計劃調(diào)整模型構(gòu)建

為便于研究車站作業(yè)的調(diào)整，做出以下假設(shè)：列車折返作業(yè)均為同到發(fā)線立折；不考慮動車段能力限制；若當前時刻距列車調(diào)整到達時刻小于指定時長時，該列車的到發(fā)線不能被調(diào)整。從減少調(diào)度、車站作業(yè)工作量及方便乘客出行的角度出發(fā)，調(diào)整車站作業(yè)計劃時，應(yīng)使列車總晚點時間最小，盡量避免列車晚點在路網(wǎng)中的傳播；同時，在滿足列車作業(yè)要求的前提下盡可能少地調(diào)整到發(fā)線運用方案，以減少對車站作業(yè)秩序的影響。以列車晚點時間最短為首要調(diào)整目標，以減少車站作業(yè)秩序影響為次要調(diào)整目標，并通過線性相加將雙目標轉(zhuǎn)換為以時間為量綱的單目標，構(gòu)建車站作業(yè)計劃調(diào)整模型為

式中：Φ 為總目標函數(shù)；K為調(diào)整時間段內(nèi)的列車集合；λk為列車權(quán)重參數(shù)，列車等級越高該值越大；分別為列車k∈K的調(diào)整到達時刻和出發(fā)時刻；分別為列車k∈K的圖定到達時刻和出發(fā)時刻；p為時空路徑編號；Pk為列車k的備選時空路徑集合；e(ijst)為時空??；i，j為車站關(guān)鍵設(shè)施；s，t為離散時刻；E為時空弧集合；是否包含于p中，若包含于則為列車k使用e(ijst)的成本，其中為列車k占用e(ijst)的時長，為列車k占用e(ijst)的單位時間成本；為0-1 決策變量，當列車k選擇時空路徑p時，= 1，否則，=0；參數(shù)ε1，ε2分別為列車早點到達和晚點出發(fā)的時間裕量；ωk為列車k的最小停站時間；Ee(ijst)為時空弧e(ijst)的沖突弧集合，對于任意e(ijst)∈E，若存在e(i"j"s"t")∈E與其閉塞時間發(fā)生重疊，即e(ijst)與e(i"j"s"t")具有沖突關(guān)系，則有e(i"j"s"t")，e(ijst)∈Ee(ijst)成立。

公式(1)表示列車的廣義成本之和最小，其中第1 項表示列車加權(quán)晚點時間，第2 項表示列車使用時空路徑的成本；公式(2)和公式(3)表示調(diào)整后的列車到達和出發(fā)時刻只能在圖定時刻周邊一定范圍內(nèi)取值；公式(4)表示列車的停留時間應(yīng)滿足其最短作業(yè)時長，通過列車的ωk取值為0；公式(5)表示每列車只能從其備選路徑集合Pk中選擇一條時空路徑約束；公式(6)表示線路的排他性占用及間隔時間約束，即任意2 列車不會選擇具有沖突關(guān)系的時空路徑。

2.2 基于列生成的啟發(fā)式算法

車站作業(yè)計劃調(diào)整模型是建立在可行列車時空路徑集合∪Pk上的，該集合規(guī)模較大且存在全部枚舉困難的問題，但由于模型的優(yōu)化解是由各列車的最優(yōu)或較優(yōu)路徑構(gòu)成，因而該問題只需在質(zhì)量較好的時空路徑子集中求解即可。列生成算法[12]是以隱枚舉的方式提供較優(yōu)子集的有效算法。其求解思路為：先在不考慮沖突約束的條件下尋找每列車的最優(yōu)路徑，生成路徑備選集；若列車最優(yōu)路徑之間存在沖突，則為有沖突的列車尋找次優(yōu)路徑，并加入路徑備選集；以此循環(huán)迭代，直至生成無沖突的最優(yōu)解。針對時空路徑組合優(yōu)化問題，列生成算法將其分解為限制性線性松弛主問題(RMP)，用以在較優(yōu)子集中尋找無沖突的路徑組合；以及最短路子問題，用于動態(tài)地為列車生成備選路徑子集。

2.2.1 模型分解

（1）限制性線性松弛主問題。針對∪Pk過大的問題，為每列車定義其備選路徑集合Bk?Pk，并使用Bk代替Pk，將車站作業(yè)調(diào)整問題轉(zhuǎn)換為一個規(guī)模較小的問題。由于該問題仍然是求解困難的0-1 整數(shù)規(guī)劃，為此將其整數(shù)約束松弛，即0 ≤≤ 1，使其成為易于求解的RMP。RMP 求解后，若得到整數(shù)解，則表明已得到車站作業(yè)計劃調(diào)整問題的最優(yōu)解。若得到含分數(shù)的解，則表明存在進路沖突，此時用求解中產(chǎn)生的對偶變量激發(fā)子問題，以生成新的可行路徑，實現(xiàn)對Bk的擴容。反復(fù)迭代，直到找到最優(yōu)解或無法產(chǎn)生新的可行路徑為止。

（2）最短路徑子問題模型。子問題的目的是為列車尋找新的較優(yōu)可行路徑。公式（2）—公式（4）對車站作業(yè)離散時空網(wǎng)絡(luò)中的弧進行限定后，根據(jù)列生成的思想，最短路徑子問題模型表示為

式中：σk為子問題的目標函數(shù)；為0-1 變量，當列車k選擇e(ijst)時，分別為公式(5)和公式(6)的對偶變量。

最短路徑子問題模型利用公式(7)來判斷列車k是否有更優(yōu)的時空路徑：若σk＜0，則說明為列車k搜索到一條費用更小，能使目標函數(shù)下降的時空路徑，并將其加入到Bk中。

2.2.2 啟發(fā)式算法

RMP 是原問題的線性松弛問題，當最優(yōu)解是非整數(shù)且子問題無法生成新路徑時，需要將RMP的解轉(zhuǎn)換為原問題的可行解。利用RMP 對偶問題的最優(yōu)解為啟發(fā)信息，定義列車的重要度為

式中：fk為列車的重要度，該值越大表示列車越重要；為RMP 的最優(yōu)解。

啟發(fā)式算法為：首先對fk的值由大到小進行排序，之后采用最短路算法按順序為每列車尋找時空路徑。若出現(xiàn)無解列車，則調(diào)整列車順序，每次優(yōu)先鋪化前次無解列車，以此迭代，直至找到可行解。

圖3 長春西客運站站型圖Fig.3 Layout of Changchun West Railway Station

3 實例驗證

以長春西高速鐵路客運站為例對模型和算法進行驗證。車站銜接沈陽、哈爾濱、長春3 個方向，以及長春西動車所，長春西客運站站型圖如圖3 所示。Ⅰ，Ⅱ正線只接發(fā)下、上行通過列車；其余9條到發(fā)線可用于接發(fā)上、下行列車，其中3，4 道可供長春站始發(fā)終到動車組出入段走行使用。列車占用到發(fā)線的費用如表1 所示，“-”表示該列車不能使用對應(yīng)的到發(fā)線。車站咽喉區(qū)采用分段解鎖，各軌道區(qū)段的占用時間根據(jù)其位置、列車長度、運行速度等因素確定。在考慮變通進路條件下共有192條接發(fā)車進路。

令當前時刻為15 : 00，按照提前2 h 下發(fā)計劃到車站的規(guī)定，設(shè)置調(diào)整階段為17 : 00—19 : 00，調(diào)整范圍內(nèi)的列車共計29 列。其中OD4606，OG4723為出段去往長春始發(fā)的動車組，在本站無作業(yè)；C1016 為長春站終到，通過本站入段的動車組；G8017 為通過列車，其余為停站列車。17 : 00—19 : 00 時段圖定車站作業(yè)計劃如圖4 所示。

列車權(quán)重λk設(shè)置通過列車為100，停站列車中G = 30，C = 20，D = 10。離 散 時 間 間隔?取值15 s。最小停站時間設(shè)置為120 s。在此基礎(chǔ)上，假設(shè)G4116 預(yù)計晚點5 min，G716 晚點13 min，G755 晚點6 min，G4722晚點10 min到達。

依據(jù)車站作業(yè)計劃調(diào)整模型和基于列生成的啟發(fā)式算法，在CPU 為Intel (R) i7-8550U 3.0GHz、內(nèi)存為8G 的電腦上，運用C#編程，并調(diào)用CPLEX12.6.2求解RMP 模型。列生成計算得到的結(jié)果是整數(shù)解，目標函數(shù)值為138 490 s，得到的是原問題的最優(yōu)解，列生成算法收斂過程如圖5 所示。經(jīng)驗證，啟發(fā)式算法得到的可行解和列生成算法得到的結(jié)果一致，程序共運行23 s，說明基于列生成的啟發(fā)式算法可在短時間內(nèi)得到質(zhì)量較高的滿意解。

車站作業(yè)計劃調(diào)整方案如圖6 所示，圖中紅色線條標記的是到發(fā)線或到發(fā)時刻發(fā)生調(diào)整的列車，黑色線條標記的是沒有發(fā)生任何調(diào)整的列車。

表1 列車占用到發(fā)線的費用Tab.1 Occupancy cost of arrival-departure tracks

圖4 17 : 00—19 : 00 時段圖定車站作業(yè)計劃Fig.4 The planned station operation plan during 17 : 00-19 : 00

圖5 列生成算法收斂過程Fig.5 Convergence procedure of the column generation algorithm

圖6 車站作業(yè)計劃調(diào)整方案Fig.6 The rescheduling solution of station operation plan

將圖4 和圖6 對比分析得：①G8077 受G4116延誤的影響產(chǎn)生延誤60 s；②G716，G4722 晚點后的列車進路與C1016 的通過進路分別發(fā)生沖突，為保證C1016 正點通過并減少總晚點量，將G716由4 道調(diào)整為8 道，等待C1016 通過之后再發(fā)車，G4722 增晚60 s 到達且停站時間由180 s 變?yōu)?20 s。其余列車的到發(fā)時刻及到發(fā)線運用方案保持不變。經(jīng)調(diào)整后，在滿足車站線路能力等約束的基礎(chǔ)上，列車總晚點時間增晚120 s，以減少列車晚點對車站作業(yè)秩序的影響。干擾條件下列車信息調(diào)整結(jié)果如表2 所示。

表2 干擾條件下列車信息調(diào)整結(jié)果Tab.2 Adjustment results of train information under interference condition

4 結(jié)束語

大型高速鐵路客運站作業(yè)計劃實時調(diào)整是行車調(diào)度調(diào)整的關(guān)鍵內(nèi)容，也是技術(shù)難點所在。針對調(diào)度調(diào)整高時效性、高精度的要求及車站作業(yè)的實際約束條件，運用數(shù)學優(yōu)化方法構(gòu)建相應(yīng)的模型和快速求解算法，能實現(xiàn)列車到發(fā)時刻、咽喉進路和到發(fā)線的實時同步調(diào)整。通過實例驗證表明，該模型可以有效解決大型高速鐵路客運站作業(yè)計劃調(diào)整問題，并且能夠同時兼顧車站運營的高效性和乘客出行的便捷性，快速生成的調(diào)整方案可作為列車調(diào)度員調(diào)整的參考依據(jù)。然而，還需要進一步考慮調(diào)車與行車作業(yè)之間的交叉干擾，以實現(xiàn)車站作業(yè)計劃的綜合實時優(yōu)化調(diào)整。