任禹謀 ，張 琦，袁志明，周曉昭

（1.中國鐵道科學(xué)研究院 研究生部，北京 100081；2.中國鐵道科學(xué)研究院集團(tuán)有限公司 通信信號研究所，北京 100081)

0 引言

隨著中國城市化建設(shè)的逐步完善和經(jīng)濟(jì)的蓬勃發(fā)展，人們出行的需求和頻率不斷增加，高速鐵路的競爭優(yōu)勢越來越突出。高速鐵路車站內(nèi)列車作業(yè)過程種類多樣，行車密集，列車的接續(xù)關(guān)系繁雜，到發(fā)線運用合理與否直接影響列車的通過效率。鐵路系統(tǒng)與開放式的環(huán)境交互過程中，難免受到人、天氣等因素的影響，當(dāng)列車發(fā)生晚點事故時，車站調(diào)度員依靠經(jīng)驗往往難以及時有效地調(diào)整階段計劃下發(fā)的圖定到發(fā)線運用方案。因此，為盡快恢復(fù)晚點列車及連帶晚點列車的正點運行，應(yīng)快速高效地制定到發(fā)線動態(tài)調(diào)整方案，保證高速鐵路旅客列車服務(wù)質(zhì)量。

國內(nèi)外學(xué)者針對到發(fā)線運用問題已經(jīng)進(jìn)行了大量的研究，主要分為車站作業(yè)計劃編制階段到發(fā)線分配問題和列車運行階段到發(fā)線動態(tài)調(diào)整問題。針對到發(fā)線分配問題，呂紅霞等[1]提出“時間片”的概念，通過簡化到發(fā)線運用計劃的二次0-1 規(guī)劃模型，明顯降低了問題求解的困難度；史峰等[2]考慮一端咽喉區(qū)接發(fā)車進(jìn)路和到發(fā)線的關(guān)聯(lián)關(guān)系，以避免到發(fā)線和進(jìn)路沖突為約束構(gòu)建模型，采用模擬退火算法求解；賈文崢等[3]建立一種約束規(guī)劃模型來描述股道分配問題，采用約束識別、值排序以及BT 搜索方法進(jìn)行求解；李濤等[4]構(gòu)建滿足到發(fā)線均衡使用的整數(shù)規(guī)劃模型，采用模擬退火遺傳算法進(jìn)行求解。針對到發(fā)線動態(tài)調(diào)整問題，彭其淵等[5]從離散化的到發(fā)線時空資源描述出發(fā)，構(gòu)建了到發(fā)線運用方案調(diào)整問題的線性0-1 規(guī)劃模型；馬駟等[6]利用道岔分組的概念建立了涵蓋到發(fā)線的列車進(jìn)路分配方案動態(tài)調(diào)整模型，采用軟件內(nèi)置的分支定界算法求解；劉偉[7]引入“虛擬列車”概念建立到發(fā)線異常條件下咽喉區(qū)利用優(yōu)化模型，并采用遺傳算法求解；彭其淵等[8]在考慮分段解鎖的條件下建立混合整數(shù)線性規(guī)劃模型解決到發(fā)線運用調(diào)整問題，設(shè)計基于分支定界的算法框架求解。

綜上所述，目前針對干擾條件下到發(fā)線動態(tài)調(diào)整的研究相對較少，大部分通過調(diào)整到發(fā)線來疏解沖突，而有可能導(dǎo)致沖突無法疏解，從而需要調(diào)整列車的到發(fā)時刻。因此，引入滾動時域調(diào)度策略對到發(fā)線分配計劃進(jìn)行動態(tài)調(diào)整，建立到發(fā)線動態(tài)調(diào)整的整數(shù)規(guī)劃模型，求解滾動時域時間窗內(nèi)到發(fā)線分配方案，降低原問題的求解規(guī)模，得到一系列能適應(yīng)外界干擾的動態(tài)調(diào)整方案。

1 高速鐵路車站到發(fā)線動態(tài)調(diào)整模型構(gòu)建

1.1 問題描述

鐵路運輸環(huán)境多變，各種隨機擾動事件時有發(fā)生，不可避免地會發(fā)生計劃在執(zhí)行過程中偏離圖定的情況，到發(fā)線分配計劃也不例外。在干擾發(fā)生時，影響運輸?shù)闹苯咏Y(jié)果通常是列車發(fā)生晚點，通過在列車運行圖設(shè)置緩沖時間可以緩解全線的列車到發(fā)延時，但當(dāng)晚點集中在某些車站時該方法并不能完全滿足要求，需要車站調(diào)度配合調(diào)整，減小干擾對車站作業(yè)的影響，以免加劇列車的晚點傳播。調(diào)整車站作業(yè)計劃中的到發(fā)線分配方案是車站調(diào)度工作的難點之一，即通過改變列車計劃占用的到發(fā)線和接發(fā)車時刻規(guī)避列車間的沖突。調(diào)整后的方案應(yīng)盡量降低偏離原計劃的程度，減少列車晚點的總時長，同時應(yīng)充分考慮到發(fā)線占用最小安全間隔時間和咽喉區(qū)交叉沖突的影響。

高速鐵路車站到發(fā)線動態(tài)調(diào)整問題本質(zhì)上是按時間順序確定列車行經(jīng)車站時占用的資源，可以視為動態(tài)調(diào)度問題進(jìn)行決策分析。滾動時域調(diào)度(Rolling Horizon Scheduling，RHS) 策略廣泛應(yīng)用于工業(yè)動態(tài)調(diào)度領(lǐng)域，其特點是利用沿時間線滾動進(jìn)行的一系列小規(guī)模或有限時段的局部調(diào)度代替大規(guī)?；驘o限時段的一次全局調(diào)度[9]。RHS 是一個隨時間推進(jìn)的迭代過程，在每一個調(diào)度時刻更新已有信息，確定一個滾動窗口，局部調(diào)度在滾動窗口進(jìn)行，其解的一部分被執(zhí)行，這部分解的完成時刻就是新的調(diào)度時刻，然后重復(fù)迭代進(jìn)行，直至完成全部調(diào)度任務(wù)[10]。RHS 策略可以降低大規(guī)模調(diào)度問題的求解難度，提高隨機環(huán)境下生產(chǎn)系統(tǒng)的調(diào)度敏捷性和穩(wěn)定性，加快調(diào)度調(diào)整的響應(yīng)時間。

傳統(tǒng)到發(fā)線調(diào)整策略是將持續(xù)時間較長的到發(fā)線分配問題作為整體對象構(gòu)建模型，其缺點是對系統(tǒng)不確定環(huán)境的敏感性和穩(wěn)定性差。利用RHS 策略可以將調(diào)度調(diào)整周期分割為若干個疊加的時間段，再針對當(dāng)前時間段內(nèi)的列車建模求解到發(fā)線分配方案，并保留滾動窗口內(nèi)的決策，然后時間向前滾動，重復(fù)相同的策略進(jìn)行優(yōu)化。值得注意的是，RHS 策略中每個時間段內(nèi)的列車到站時間均可根據(jù)最新的預(yù)確報信息進(jìn)行實時更新，從而保證了方案的優(yōu)越性。

1.2 模型構(gòu)建

設(shè)某高速鐵路車站到發(fā)線集合為I= {1，2，…，i，…，m}，其中i為到發(fā)線的編號，m為到發(fā)線的總數(shù)；計劃時間內(nèi)到達(dá)的列車集合為L= {1，2，…，l，…，n}，其中l(wèi)為列車到達(dá)車站的順序，n為到達(dá)列車的總數(shù)；同一到發(fā)線相鄰作業(yè)最小安全間隔時間為Tmin。綜合考慮現(xiàn)場實際情況和調(diào)度員工作量，當(dāng)列車晚點發(fā)生時，應(yīng)盡量減少列車實際到發(fā)時間與計劃的偏離程度，即列車總晚點時長，避免晚點效應(yīng)在路網(wǎng)中的傳播，確定第1 個目標(biāo)函數(shù)為

式中：為列車l圖定到達(dá)時間，min；為列車l實際到達(dá)時間，min；為列車l圖定出發(fā)時間，min；為列車l實際出發(fā)時間，min。

為了方便客運組織，需保證列車優(yōu)先選擇圖定方案中預(yù)計?？康牡桨l(fā)線或同臺到發(fā)線，采用到發(fā)線占用費用的方式進(jìn)行表示，確定第2 個目標(biāo)函數(shù)為

式中：xli為0-1 變量，xli= 1 表示列車l占用到發(fā)線i，否則xli= 0。cli為列車l占用到發(fā)線i的費用，其值越小則該選擇對計劃方案影響越小。當(dāng)與圖定到發(fā)線一致時，cli= 0；當(dāng)與圖定到發(fā)線同臺時，cli= 1；當(dāng)與圖定到發(fā)線不一致且不同臺時，cli= 100。

利用線性加權(quán)的方式得到優(yōu)化模型的最終目標(biāo)函數(shù)為

式中：λ1和λ2為2 個子目標(biāo)函數(shù)的權(quán)重，且λ1?λ2。

公式(3)保證了在列車晚點情況下，優(yōu)先考慮調(diào)整到發(fā)線運用方案，再調(diào)整其到發(fā)時刻，符合車站的基本調(diào)整邏輯。從到發(fā)線運用規(guī)則和列車作業(yè)時間角度考慮，模型受到如下約束。

（1）到發(fā)線占用相容性約束。同一時間一條到發(fā)線最多可以容納一列列車，且列車占用到發(fā)線后不得換線。

（2）到發(fā)線作業(yè)的時間間隔約束。同一到發(fā)線上先后作業(yè)的2 列列車的時間間隔需要滿足最小安全間隔時間要求，即后繼列車的到達(dá)時刻與前行列車的出發(fā)時刻的差值不小于最小安全間隔時間。

（3）咽喉區(qū)交叉干擾安全約束。引用時間片[1]的定義，將某一階段的時間劃分幾個時間片，不同列車在同一時間片內(nèi)占用咽喉區(qū)表示列車在時間上存在干擾，即進(jìn)路交叉沖突，需要安排平行作業(yè)進(jìn)路。

式中：為0-1 變量，= 1 表示當(dāng)列車l占用到發(fā)線i時的進(jìn)路與其他列車進(jìn)路r發(fā)生干擾沖突，否則= 0。

（4）到發(fā)線停車時間約束。列車在到發(fā)線上的實際停車時間需要滿足圖定停站時間要求，否則會影響旅客乘降等作業(yè)內(nèi)容。

（5）列車到發(fā)時間約束。列車l的實際到發(fā)時間均不能早于圖定到發(fā)時間。

（6）正線通過約束。車站正線只接發(fā)不停站通過列車，且通過列車不能通過到發(fā)線。

式中：I正為到發(fā)線正線集合；L通為通過列車集合。

2 高速鐵路車站到發(fā)線動態(tài)調(diào)整模型求解

2.1 滾動時域調(diào)整策略

到發(fā)線動態(tài)調(diào)整問題不是離線優(yōu)化，而是在線進(jìn)行的，因而需要充分考慮模型的求解規(guī)模和列車的實時變化。RHS 策略通過引入時域的概念將復(fù)雜的調(diào)度模型轉(zhuǎn)化為多階段決策模型，在每一個階段的采樣時刻僅利用當(dāng)前列車信息進(jìn)行局部優(yōu)化，并隨著時間滾動反復(fù)進(jìn)行，以此代替原問題的全局優(yōu)化，從而減少優(yōu)化問題的時間，提高優(yōu)化性能的敏感度。

滾動窗口技術(shù)是RHS 的核心內(nèi)容，在運用RHS 進(jìn)行動態(tài)調(diào)度時，應(yīng)首先劃分滾動窗口和預(yù)測窗口[11]。滾動窗口是局部優(yōu)化區(qū)間的一段，也稱為調(diào)整區(qū)域；預(yù)測窗口是整個局部優(yōu)化區(qū)間，窗口內(nèi)包含已知信息和短時預(yù)測信息。假設(shè)當(dāng)前正在調(diào)整第k個滾動窗口的到發(fā)線分配計劃，滾動窗口的起止時間為[tk，tk+ΔT]，基于當(dāng)前已知的列車運行信息，預(yù)測未來b個窗口，則其預(yù)測窗口為[tk，tk+bΔT]。需要注意的是，在干擾發(fā)生后，列車會偏離圖定線運行，隨著時間向前滾動，列車預(yù)計到發(fā)時刻也在不停變化，實時搜集更新預(yù)測窗口內(nèi)的列車信息非常重要。到發(fā)線動態(tài)調(diào)整過程示意圖如圖1 所示。

根據(jù)上述分析可以制定完整的到發(fā)線動態(tài)調(diào)整策略。優(yōu)先對實時搜集到的到達(dá)時刻在預(yù)測窗口內(nèi)的列車建立調(diào)整模型并求解，獲得到發(fā)線調(diào)整的初步方案。再將調(diào)整后到發(fā)時刻落在滾動窗口內(nèi)的列車按上述方案確定對應(yīng)到發(fā)線，放棄時間[tk+1，tk+(b- 1) ΔT]內(nèi)的優(yōu)化結(jié)果。當(dāng)時間推進(jìn)至滾動窗口的結(jié)束時刻時，滾動窗口向前推移，新的預(yù)測窗口周期開始，根據(jù)該預(yù)測窗口時間重新確定待優(yōu)化列車集合及相關(guān)時間信息，重復(fù)上述調(diào)整操作，直至全部列車按到發(fā)時刻先后分配至到發(fā)線。具體調(diào)整步驟如下。

步驟1：初始化當(dāng)前時刻，確定滾動窗口、預(yù)測窗口的時間長度、當(dāng)前列車占用情況以及其他參數(shù)。

步驟2：根據(jù)已知列車計劃到達(dá)信息確定預(yù)測窗口時間[tk，tk+bΔT]內(nèi)列車到發(fā)時刻信息。

步驟3：對步驟2 中列車建立到發(fā)線動態(tài)調(diào)整模型并設(shè)計算法求解調(diào)整結(jié)果。

步驟4：執(zhí)行滾動窗口時間[tk，tk+ΔT]內(nèi)到發(fā)線分配調(diào)整方案，放棄時間[tk+1，tk+(b- 1) ΔT]內(nèi)的調(diào)整決策。

步驟5：判斷當(dāng)前預(yù)測窗口結(jié)束時間是否為全部調(diào)度任務(wù)完成時間，若判定結(jié)果為yes，則停止調(diào)度調(diào)整，否則，向前滾動一個時域，即k=k+1，tk+1=tk+bΔT，并返回步驟2。

2.2 遺傳算法設(shè)計

滾動時域調(diào)整策略中步驟3 需要設(shè)計相應(yīng)算法求解到發(fā)線調(diào)整結(jié)果，由于到發(fā)線調(diào)整問題是大規(guī)模組合優(yōu)化問題，適合采用啟發(fā)式算法求解，設(shè)計相應(yīng)遺傳算法流程如圖2 所示。

（1）染色體編碼及初始種群生成。染色體編碼根據(jù)到發(fā)線編號為自然數(shù)的特點選擇采用自然數(shù)編碼的形式，染色體的長度定義為預(yù)測窗口時域內(nèi)到站列車的數(shù)量，染色體的基因位置編號按照列車到站順序進(jìn)行排列，基因位置所對應(yīng)信息則表示占用的到發(fā)線編號，每個染色體代表了一種到發(fā)線運用方案。初始種群的生成按照列車到站順序的先后分配到發(fā)線，分配規(guī)則遵照列車的圖定方案。

圖1 到發(fā)線動態(tài)調(diào)整過程示意圖Fig.1 Dynamic adjustment process of arrival and departure track

圖2 遺傳算法流程Fig.2 Process of the genetic algorithm

（2）計算適應(yīng)度函數(shù)。適應(yīng)度函數(shù)用于評價個體的適應(yīng)度值，由于目標(biāo)函數(shù)是求取極小值，結(jié)合實際問題考慮，選取目標(biāo)函數(shù)的倒數(shù)作為適應(yīng)度函數(shù)。

（3）遺傳操作。選擇操作采用精英保留策略，并以輪盤賭的方法選擇父代個體；交叉操作選擇單點交叉方法；變異操作采用單點變異方法。

（4）可行解修復(fù)。遺傳操作過程中可能會產(chǎn)生違背到發(fā)線調(diào)整約束的個體，通過約束公式(4)至公式(11)進(jìn)行可行性驗證。對于違背約束的個體，需要隨機生成新的可行解進(jìn)行替換，保證種群數(shù)量。

3 算例分析

以某高速鐵路車站2 h 的行車數(shù)據(jù)為例驗證到發(fā)線動態(tài)調(diào)整模型和算法，研究時段的開始時間置為0 時刻，高速鐵路車站站場布置示意圖如圖3所示。車站共有6 條到發(fā)線，2 條正線，股道IG，3G，5G，7G 接發(fā)下行列車，股道IIG，4G，6G，8G 接發(fā)上行列車。到發(fā)線運用計劃圖定方案如圖4 所示。在該時段內(nèi)共辦理30 列列車到發(fā)作業(yè)，根據(jù)《車站行車工作細(xì)則》規(guī)定，該站到發(fā)線占用最小安全間隔時間Tmin為5 min。遺傳算法參數(shù)設(shè)置如下：種群規(guī)模為50，交叉概率為0.9，變異概率為0.05，最大迭代次數(shù)為50。考慮到一般鐵路車站階段計劃為3 ～ 4 h，動態(tài)調(diào)整范圍不易超過階段計劃的時間范圍，且高速鐵路車站車流密集，可減小滾動窗口的時間長度來提高方案的實時性，因而滾動時域調(diào)度方法參數(shù)設(shè)置如下：預(yù)測窗口向前看時間間隔b為1，滾動窗口ΔT大小為30 min，預(yù)測窗口大小為60 min，算例中共包含3 個滾動窗口。

圖3 高速鐵路車站站場布置示意圖Fig.3 Layout of high-speed railway station

在0 ～ 30 min 內(nèi)選取2 列列車設(shè)置干擾：5 號列車晚點3 min 到達(dá)，4 號列車晚點9 min 到達(dá)。根據(jù)以上參數(shù)和條件構(gòu)建模型，運用仿真軟件進(jìn)行求解，每個預(yù)測窗口模型時間內(nèi)算法均保持收斂，程序共運行20 次，從多次求解后得到的解中選擇目標(biāo)函數(shù)值最小的對應(yīng)方案作為最終調(diào)整方案。到發(fā)線滾動時域調(diào)整方案如圖5 所示。

圖4 到發(fā)線運用計劃圖定方案Fig.4 Arrival and departure track utilization scheme

圖5 到發(fā)線滾動時域調(diào)整方案Fig.5 Arrival and departure track adjustment scheme based on rolling horizon

調(diào)整前后列車信息比較如表1 所示，其余未提及的列車到發(fā)線分配方案保持不變。通過調(diào)整前后2 個方案的對比分析可知：在0 ～ 30 min 滾動時間窗內(nèi)，5 號列車到達(dá)延誤，導(dǎo)致其發(fā)車進(jìn)路與3 號列車的發(fā)車進(jìn)路在排路時間上發(fā)生沖突，為疏解該沖突，3 號列車的到發(fā)時間均推遲1 min，由于上述調(diào)整列車的到達(dá)時刻都落入當(dāng)前滾動窗口，則按照調(diào)整結(jié)果執(zhí)行；4 號列車到達(dá)延誤，導(dǎo)致其占用到發(fā)線發(fā)生了變化，由計劃到發(fā)線4G 變更至同臺到發(fā)線6G，同時為了滿足相同到發(fā)線相鄰列車作業(yè)時間間隔不少于5 min 的要求，8 號列車到發(fā)時刻被迫向后推遲2 min，12 號列車占用到發(fā)線由計劃到發(fā)線6G 變更至同臺到發(fā)線4G，4 號和8 號列車的到達(dá)時刻都落入當(dāng)前滾動窗口，所以按照調(diào)整結(jié)果執(zhí)行，12 號列車的到達(dá)時刻未落入當(dāng)前滾動窗口，暫時放棄其調(diào)整方案。然后，時間滾入下一個滾動窗口，重新計算調(diào)整方案。

表1 調(diào)整前后列車信息比較Tab.1 Comparison of the train information before and after adjustment

根據(jù)計算結(jié)果分析，引入滾動時域優(yōu)化策略的調(diào)整方案后，在第1 個預(yù)測窗口模型中列車數(shù)量由30 列減少為16 列，計算時間降幅達(dá)21.1%，在第2 個預(yù)測窗口結(jié)束后列車調(diào)整全部完成，保證了方案的實時性。同時調(diào)整后的列車晚點總時長為6 min，到發(fā)時間受干擾的正點列車為2 列，變更同臺到發(fā)線的列車為2 列，在可接受的調(diào)整范圍內(nèi)保持了車站運輸?shù)姆€(wěn)定性，說明模型和調(diào)整策略合理、有效，能夠解決高速鐵路車站到發(fā)線動態(tài)調(diào)整的實際問題。

4 結(jié)束語

建立基于滾動時域優(yōu)化的高速鐵路車站到發(fā)線動態(tài)調(diào)整模型，實現(xiàn)到發(fā)線調(diào)整智能化，提升了高速鐵路列車的安全、穩(wěn)定運行，在加快列車晚點恢復(fù)的同時，減少原計劃的改變，保證了一定的實時性?？紤]到高速鐵路網(wǎng)絡(luò)組成復(fù)雜，單個車站的到發(fā)線調(diào)整對于列車大量晚點的吸收能力有限，還應(yīng)將列車運行圖和區(qū)間內(nèi)多個車站作為整體對象進(jìn)行研究，最大化降低列車晚點在路網(wǎng)中的傳播影響。