列車運行調整與到發線運用的協同優化研究

王宇晴， 查偉雄,2*， 萬平

(1.華東交通大學交通運輸工程學院， 南昌 330013； 2.華東交通大學交通運輸與經濟研究所， 南昌 330013)

列車運行調整與到發線運用都是鐵路行車調度指揮工作中的重點，列車運行調整的主要目標是列車占用區間的次序和列車占用區間的時長，同時需要調整列車的到發時刻等。到發線運用則是列車在車站具體占用進路和到發線的固定方案，故列車運行調整的維度相對于到發線運用較高。同時這兩者也是相輔相成的關系。僅針對列車運行調整的優化問題，中外學者已有一定的研究成果，但是同時考慮到發線運用方面的研究還是較少。

Zhu等[1]建立了能夠對多個突發事件同時進行優化的動態列車運行調整模型，并通過算例驗證其有效性。Hong等[2]建立了列車取消運行情況下的運行圖與停站方案一體化調整模型，通過能加停站次數，將延誤旅客運送至目的地。Zhang等[3]提出一種運行調整與線路應急維護的協同優化策略，在解決線路應急維護的同時，進行運行調整降低列車延誤，提升運行控制的魯棒性。李曉娟等[4]以各列車在各車站的總延誤時間最小為目標，設計了一種分階段多叉樹的算法來求解。戶佐安等[5]以乘客總旅行時間最小為目標建立了基于列車運行一體化調整方法的模型，并設計嵌套式遺傳算法進行求解。高如虎等[6]構建了基于Time-Station-Track網絡的0-1整數規劃模型，并設計拉格朗日松弛算法進行求解。牛晉才等[7]以列車進入車站和駛離車站的總晚點時間最少為目標，并運用人工魚群算法求解。徐陪娟等[8]以到發線變更次數最少和列車晚點延誤時間最短為目標，建立混合整數線性優化模型并設計兩階段近似算法進行求解。彭其淵等[9-10]以加權總晚點時間與到發線使用費用之和最小為優化目標，建立了線性0～1規劃模型并設計了算法進行求解。王藝楠等[11]、李智等[12]分別將滿意度與智能化應用加入列車運行調整的模型中，并設計算法進行求解。

從以上研究中可以發現，大多數學者在建模過程中約束和目標都考慮得比較全面。但在考慮到發線運用方面，大多只考慮了各站到發線的數量。在發生列車大面積的延誤情況下，晚點列車占用到發線大多是依照調度人員的主觀意識，在運輸效率方面難以保證。在研究列車運行調整問題的同時，綜合考慮到發線運用的協同優化問題非常有必要。

因此，現主要研究列車運行調整與到發線運用的協同優化問題。建模過程中，綜合考慮宏觀層面的列車流運行調整與微觀層面車站的到發線運用調整，以列車的加權總到發晚點時間最少和到發線的占用總消耗最小為目標函數，并結合模型特點運用分層序列鴿群優化算法，以求得突發晚點情況下的列車運行調整計劃時刻表和到發線運用變更情況，為鐵路管理部門的臨時調度情況提供決策借鑒。

1 問題描述

1.1 列車運行圖描述

選用雙線自動閉塞高速鐵路的單一方向線路為研究對象，且假設列車僅在車站內發生晚點。為后續便于程序設計以及晚點情況的表達，將列車運行圖的計劃線分別用到達線與出發線表示，橫軸表示時間，縱軸表示車站，列車運行線與到達線和出發線的交點即列車的到達時間與出發時間，同時將運行圖分成以分鐘為單位1 440個離散時間點的集合，如圖1所示。

圖1 列車運行圖表示Fig.1 Train operation diagram

1.2 問題假設

在列車出現晚點情況后，調度員將列車運行調整與到發線運用結合，并根據故障信息，在短時間內及時的做出決策，是一項困難性較高的工作。在這個過程中需要考慮的方面比較多，如列車運行時的安全性、列車及車站設備的能力約束以及場站的各項調度規則等方面。為了簡化建模過程中的不必要因素，結合現場實際調度情況，做出如下假設。

(1)僅考慮列車在車站出發晚點的情況，不考慮線路區段內的突發情況導致的晚點。

(2)車站出現晚點的情況后，在列車出現晚點伊始，列車晚點具體時間并不確定。需要對接下來使用晚點列車所占用到發線的到發線運用方案進行調整。

(3)列車在車站的到發線運用，僅考慮停站通過的情況。

(4)列車正常運行情況下，都是嚴格按圖行車。本文假定各列車在發生晚點前與恢復圖定運行時間后，都嚴格按照運行圖行車。

2 模型的建立

2.1 變量與符號說明

以某高速鐵路下行方向為例，有如下變量定義。

(1)下行方向進入運行調整時間段的列車集合為I={i1,i2…,im,…,iM}。

(2)下行方向列車運行調整區段內，車站集合為J={j1,j2…,jn,…,jN}。

(3)在一些大型車站，一條到發線可能對應著多個接發車進路，所有車站對應的接車進路數量為g1,g2，…，gn，發車進路數量為h1,h2，…，hn。

車站jn接車進路集合為JCjn={w1,w2，…，wgn}，發車進路集合為FCjn={r1,r2，…，rhn}。

(4)n個車站下行方向各站到發線數量為k1,k2，…，kn，以Kjn表示車站jn到發線的集合，如第二個車站Kj2={l1,l2，…，lk2}。

(6)車站內接發車進路與到發線之間的邏輯關系采取0～1變量的方式，定義如下。

(1)

(2)

(3)

(7)列車優先等級用η(im)表示，值越大表示列車優先等級越高。不同等級列車所對應的權重為φ(im)，不等級列車相鄰兩站之間的最小運行時分用Tim，jn-jn+1表示，列車的列車im在車站jn最小作業時分用Timjn表示，相鄰兩列車的達到通過同一車站的最小間隔時間用Tjn-jn表示。

(8)最小到達、出發時間間隔分別用Td和Tc表示，列車的起、停附加時分分別用tq和tt表示。

(9)列車im通過車站jn的作業類型用βimjn表示。

(4)

2.2 約束條件

所建立的列車運行調整模型共有10組約束條件，這些約束中(1)～(6)為列車運行計劃相關的約束條件，(7)～(10)為結合列車運行調整實際情況所提出的到發線運用約束條件。

(1)同車站，前后兩列不同列車均滿足最小到達、出發時間間隔。

(4)

(5)

(2)列車在相鄰兩站之間的運行時間，必需滿足列車最小運行時分，并加上起停附加時分。

?im∈I，?jn，jn+1∈J

(6)

(3)列車若在某站停車，作業時間不得小于該車站的最小作業時間：

(7)

(4)所有列車發車時間不得早于圖定出發時分。

(8)

(5)相鄰兩列車到達通過同一站的最小間隔時間。

(9)

(6)列車越行條件(后車im+1滿足該條件，才能越行前車im)：

η(im+1)>η(im)

(10)

?im，im+1∈I，?jn∈J

(11)

?im，im+1∈I，?jn∈J

(12)

(7)列車占用咽喉區接發車進路和到發線，兩者的唯一性約束。每列車在進站時，只能占用一個接發車進路和一條到發線。

接發車進路唯一性：

(13)

到發線選擇唯一性：

(14)

(8)到發線與接發車進路的選擇確定：

?im∈I，?jn∈J，?l∈Kjn

(15)

(9)到發線被占用約束：

?im,im+1∈I，?jn∈J，?l∈Kjn

(16)

(10)到發線占用數量約束：

?l∈Kjn

(17)

2.3 目標函數

當列車偏離圖定運行計劃后，不同速度等級列車晚點后的類型也有一定的差異，并且調整措施也不相同。高等級列車相比于低等級的列車來說，運行調整所產生的效益較大。同時用于評價運行調整目標的類型也較多，本文使用的優化目標為總加權到發晚點時間最小，φ(im)為不同等級高速列車的權重，目標函數為

(18)

在到發線運用方面，應考慮到調整過程中對于車站作業秩序的影響程度最小，即盡量少地去調整到發線運用方案。所以，到發線運用問題的最優化目標為列車占用到發線的總消耗最小，即盡量選擇對車站作業秩序影響較小的到發線。由于列車在車站停站通過時，選用非原到發線運用方案后，車站內人員、設備、場站之間工作調整，存在一定的復雜性，表達目標函數時，對于不符合原到發線運用方案的列車占用到發線情況進行統一，采取僅考慮單一權重的方式。ωiml為表示列車im占用到發線l的權重，取值為1和100。ωiml取1 時表示列車im在占用到發線l時，符合到發線運用方案。當取值100 時，表示列車im可以占用到發線l,但是不符合原到發線運用方案。在現場實際操作時，應當首選ωiml=1的到發線，但是在ωiml=1的到發線能力緊張的情況下，確保不產生多余的干擾，則可以視情形選用ωiml=100的到發線進行接發車。目標函數為

(19)

上述兩個目標函數所對應的函數值量綱不同，同時求解會十分困難，所以在鴿群優化算法的基礎上，引入分層序列法，設計了一種適用于求解上述多目標不同量綱問題的分層序列鴿群優化算法，進行求解。

3 分層序列鴿群優化算法

3.1 算法介紹

由于多目標、多約束問題大多是求解難度較高的NP-hard問題，所以在求解該類問題時，對于算法的選擇也是求解的關鍵一步。

分層序列法是解決兩個或兩個以上目標，不宜用加權合成為單目標問題進行求解的有效方法。僅需對不同的目標確定優先等級，并在求解時設定不同等級目標所對應的檢驗數集合Qn。通過算法迭代，當所有檢驗數為非負時，進入下一層級目標的算法迭代。當所有目標的檢驗數集合均為非負時，即得到整體目標規劃模型的滿意解。

鴿群優化算法是通過模擬鴿子飛行過程中受地磁與地標影響的歸巢習性，模擬設計出的一種較簡易的群智能算法。該算法原理簡潔明了，在設計過程中需要調節的參數較少，在編程時相對其他算法容易實現，同時魯棒性也較強[13-14]。鴿群優化算法中有兩個基本部分，分別為：指南針算子、地標算子。當目的地距離鴿子較遠時，它利用的是附近的地磁場來判別飛行方向。當目的地距離較近時，則用附近熟悉的地標來定位飛行。

指南針算子：鴿群前期在飛行的過程中，判斷方向的依據主要來自地磁場，通過地磁場來不斷的調整飛行方向。在函數優化問題方面，鴿群算法就是把每個可行解作為一個個體i，而每個個體都有其相應位置和速度，分別記為Xi=[xi1,xi2,…,xiD]和Vi=[vi1,vi2,…,viD]，其中i∈{1,2,…,Np}，Np表示可行解數量，即產生初始解初始鴿群的數量；D表示維度數。個體的位置與速度在D維解空間中每次都隨著迭代而更新。在第t次迭代中，每個個體的位置Xi與速度Vi計算公式為

Vi(t)=Vi(t-1)e-Rt+rand[Xg-Xi(t-1)]

(20)

Xi(t)=Xi(t-1)+Vi(t)

(21)

式中：R為指南針算子中的指南針因子；rand為取0～1的一個數值；Xg為目前為止全局的最優位置，可以視作是指南針所指向的位置。

地標算子：當它們飛行逐漸靠近目的地后，會通過尋找附近熟悉的地標來導航，如果某個個體附近有熟悉的地標，則該個體就會徑直飛向目的地，假如該個體附近沒有熟悉的地標，它就會跟著熟悉地標的鴿子飛行達到目的地。在每次迭代過程中將鴿群數量Np減半，選擇適應度值較優的前一半作為當前種群，計算剩余鴿群的位置中心Xc，求解本文模型的地標算子為列車的圖定運行時間與原到發線運用方案，將其作為參考方向，對每只鴿子的位置進行更新：

(22)

(23)

Xi(t)=Xi(t-1)+rand[Xc(t)-Xi(t-1)]

(24)

式中：fitness為用來評價解質量的函數。鴿群優化算法在地標算子階段的總體參考方向是那些相對較優個體的位置中心，因為該階段沒有個體自身的速度和慣性干擾，種群能夠在很短的時間內快速收斂，并且得到最優值。當算法的迭代總次數達到了初始設定的最大值，地標算子停止運行，輸出最優值。

上述模型有兩個優化目標：總加權到發晚點時間最小、列車占用到發線的總消耗最小。直接用單一算法進行求解較為困難。所以將分層序列法引入鴿群優化算法中，用于求解模型。以總加權到發晚點時間最小為優先層級的求解目標，其檢驗數集合為Q1，列車占用到發線的總消耗最小次之，其檢驗數集合為Q2。

3.2 分層序列鴿群優化算法步驟

求解列車運行調整與到發線運用協同優化模型的分層序列鴿群優化算法步驟如下。

步驟1參數輸入，圖定列車到發時刻、列車數與車站數、列車等級權重、最小到達出發時間間隔、最小列車運行時分、起停附加時分、各站到發線數量以及占用費用、晚點情況假設等。

步驟2初始化種群數目Np、解空間維度D、不同層級目標的檢驗數集合Qn、指南針算子最大迭代次數Nc1、地標算子最大迭代次數Nc2，隨機產生初始解的適應度函數值。

步驟3對列車運行調整目標進行計算，鴿群中的每個個體尋優路徑和速度進行設置。把每只鴿子的適應度值進行對比，得到最好的飛行路徑，即對正點列車順序進行保留，對晚點列車及后續列車進行調整。

步驟4進入指南針算子操作。通過式(20)和式(21)，對每只鴿子速度與路徑的更新。接著依據約束條件再對比鴿子的適應度值，得到較優的列車運行調整方案。

步驟5當Nc>Nc1max后，指南針算子操作中止，進入到下一步操作。否則，繼續步驟4。

步驟6進入地標算子操作。對已經得到的適應度值，依據式(22)進行減半。接著依據式(23)找到留下來適應度值的中心，即鴿子的理想目的地。將所有鴿子依據式(24)調整方向。最后，存儲該最佳目標函數與相應的列車到發時刻。

步驟7當Nc>Nc2max后，地標算子操作中止，輸出計算結果。否則，轉到步驟 6。

步驟8驗證列車運行調整目標的檢驗數集合Q1。若均為非負，則進入下一層級的目標計算。否則，轉到步驟3。

步驟9對到發線運用目標進行計算，鴿群中的每個個體尋優路徑和速度進行設置。把每只鴿子的適應度值進行對比，得到最好的飛行路徑，即對正點列車到發線運用方案進行保留，對晚點列車及后續列車到發線運用方案進行調整。

步驟10進入指南針算子操作。通過式(20)和式(21)，對每只鴿子速度與路徑的更新。接著依據約束條件再對比鴿子的適應度值，得到較優的到發線運用方案。

步驟11當Nc>Nc1max后，指南針算子操作中止，進入到下一步操作。否則，繼續步驟10。

步驟12進入地標算子操作。對已經得到的適應度值，依據式(22)進行減半。接著依據式(23)找到留下來適應度值的中心，即鴿子的理想目的地。將所有鴿子依據式(24)調整方向。最后，存儲該最佳目標函數與相應的到發線運用調整情況。

步驟13當Nc>Nc2max后，地標算子操作中止，輸出計算結果。否則，轉到步驟12。

步驟14驗證到發線運用目標的檢驗數集合Q2。若均為非負，輸出所有層級目標的計算結果。否則，轉到步驟9。

4 算例分析

為了驗證模型與分層序列鴿群優化算法求解的有效性，選取文獻[15]中鄭西高鐵某區間段13：00—19：00的實際運行數據為仿真算例。已知數據如下：下行方向列車數11，車站數6，將列車速度等級分為一級、二級、三級，對應的列車權重φ(im)為3、2、1。11列車的等級為[1 1 1 1 3 3 3 3 2 2 2]，相應列車等級權重為[3 3 3 3 1 1 1 1 2 2 2]。列車的起停附加時分為2 min和1 min。各站到發線的數量分別為3、3、3、2、2、3條，各站到發線集合為K1,K2，…，K6，且有3條到發線的車站中，到發線l3是占用權重為100。

經過數次實驗平臺仿真分析后，初始參數設置如下：初始鴿群數量設置為No=30，地圖和指南針算子最大迭代次數Nc1=5，地標算子最大迭代次數Nc2=15，地圖與指南針因子R=0.2。為驗證分層序列鴿群優化算法在求解上述模型時的有效性，結合文獻[15]中設定的三種不同的晚點情況，并增加三種晚點情況都發生的情況進行模型求解分析。

三種假設晚點情況為：車次5在車站1晚點 10 min、車次9在車站1晚點15 min、車次8在車站3晚點30 min。運行調整結果如表1～表5所示，加粗字體表示經過調整后的到發時刻。

從表1和表5中可知：第一種晚點情況，車次5在車站1晚點10 min后，經調整，列車在第4站恢復為圖定運行時間，同時造成車次6在第1站晚點4 min、第2站晚點1 min。到發線運用方面由于車次5在第1站發生晚點，為車次6更換至車站1的到發線2辦理接發車作業。最后得到目標函數值Z1為56，總到發晚點時間為56 min，列車占用到發線總消耗Z2不變。

第二種晚點情況，車次9在車站1晚點15 min，算法調整結果以及到發線運用方案調整情況，如上表2所示。從表3中可知，第三種晚點情況，車次8在車站3晚點30 min后，經調整，車次9、10和11在車站3對車次8越行，只有車次8晚點，同時通過加快列車區間運行速度與壓縮列車停站時分，總晚點時間為72 min，目標函數值Z1為144。并且在第三種晚點情況下，鴿群優化算法要明顯優于免疫蟻群算法，優化效果為81.4%。從表4中可知，三種晚點情況都發生的場景下，經調整后的總晚點時間為394 min，也較優于免疫蟻群算法的調整結果，優化效果為7.3%。從表5中可知，假設的4種晚點情況，在到發線運用調整方面，調整后得到列車占用到發線總消耗Z2的值均為71，若現實中依據調度人員的主觀判斷調整該值則會無法確定，所以上述模型在實際生產調度方面具有一定的指導意義。

表1 第一種晚點情況算法調整后的列車運行時刻表

表2 第二種晚點情況算法調整后的列車運行時刻表

表3 第三種晚點情況算法調整后的列車運行時刻表

表4 三種晚點情況都發生算法調整后的列車運行時刻表

表5 不同晚點情況下到發線運用方案調整情況表

圖2 第二種晚點情況目標Z1算法收斂曲線圖Fig.2 Convergence curve of Z1 algorithm in the second case of delay

圖3 第二種晚點情況目標Z2算法收斂曲線圖Fig.3 Convergence curve of Z2 algorithm in the second case of delay

表6 不同晚點情況免疫蟻群算法與分層序列鴿群優化算法求解總到發晚點時間的結果對比

算法求解第二種晚點情況下，目標Z1與Z2的迭代圖，如圖2和圖3所示。不同晚點情況免疫蟻群算法與分層序列鴿群優化算法求解總到發晚點時間的結果對比，如表6所示。從圖2和表6可知，總到發晚點時間鴿群優化算法僅用4次左右迭代就得出了結果。而文獻[15]中免疫蟻群算法在求解總到發晚點時間時，需要迭代50次左右，所以鴿群優化算法在求解本文優化模型時，具有一定的優越性。

5 結論

建立了列車運行調整與到發線運用協同優化模型，以列車在各站的總加權晚點時間最少以及列車在各站占用到發線的總費用最小為目標，同時考慮列車運行調整約束和到發線運用約束。結合現有群體智能算法求解該類問題時，收斂速度較低、求解速度慢的缺點，在鴿群優化算法的基礎上引入分層序列法，對列車運行調整與到發線協同優化模型進行求解，得到的運行調整結果與免疫蟻群算法相比總是相同或者優于后者，算法迭代次數明顯較少，并且還得到了滿意的到發線運用調整方案，具有一定的實際參考價值。但是，模型考慮的僅為單方向條件下列車運行調整與到發線運用協同優化問題，下一步研究重點將是探究雙線調度區段的列車運行調整與到發線運用協同優化問題。