列車運行圖天窗分段與銜接優化技術研究

徐長安，李晟東，陳釘均，3，倪少權，3

(1.西南交通大學交通運輸與物流學院，四川 成都 610031；2.西南交通大學全國鐵路列車運行圖編制研發培訓中心，四川 成都 610031；3.西南交通大學綜合交通運輸智能化國家地方聯合工程實驗室，四川 成都 610031)

1 引言

天窗是列車運行圖中不鋪畫列車運行線或調整、抽減列車運行線為施工和維修作業預留的時間[1]。主要用于對現有鐵路設備進行有計劃的維修和技術改造，是協調列車運行與線路施工維修矛盾的有效措施，對保障鐵路運輸安全至關重要。

我國鐵路具有高鐵與既有線貫通成網、既有線客貨混跑、運能與運量矛盾突出等特點，天窗設置的困難性較其它國家更加突出，根據現行的中國鐵路總公司2014年頒布的《列車運行圖編制規則》，我國高速鐵路設置全線垂直矩形天窗，既有線單線鐵路采用分段矩形天窗，既有雙線鐵路一般采用V型或者X型天窗，天窗要求盡量設置在白天，以方便維修施工。整體而言，我國高鐵天窗設置比較固定，而既有線天窗設置具有影響因素復雜、計劃性強、局部變化大等特點，是一個十分復雜的組合優化過程。

既有線天窗設置的一個關鍵問題是如何進行線路天窗的分段和合理銜接，使得天窗設置對鐵路能力的影響降到最低。由于天窗分段和銜接的可選方案很多，靈活性比較大。如何立足整條線路，統籌考慮路網因素，對線路天窗區段進行劃分，并以合適的時間、傾斜角度進行銜接組合，對優化運行圖結構，釋放鐵路能力具有重要意義[1]。

從實踐層面看，我國鐵路列車運行圖天窗設置采用計算機輔助系統，天窗分段與銜接主要依賴于編圖人員的經驗判斷。這種基于人工經驗的天窗設置模式在鐵路能力充裕的情況下尚能基本滿足鐵路生產需要，但當鐵路能力緊張時，人機交互調整的工作量仍然很大。

從理論研究看，國內外關于天窗分段與銜接的研究很少，大多數研究集中在運行圖既定情形下天窗設置優化[2]，天窗開設時段優化[3]，天窗與開行方案協同優化[4]等幾個方面，僅有少量文獻部分涉及了天窗分段與銜接，文獻[5]運用情景分析法構建了天窗設置模型，能夠根據成本收益比選出最優天窗分段。文獻[6]提出了根據車站等級、客流區段以及是否銜接站進行天窗分段的思路。文獻[7]考慮了路網條件下不同線路之間天窗方案的銜接匹配問題。總體而言，現有文獻通常將天窗分段與天窗銜接作為兩個相對獨立的問題進行研究，且在研究過程中只關注天窗設置對列車運行的影響，未充分考慮由于天窗分段與銜接產生的天窗錯位對車站能力的影響。

鑒于此，本文從天窗設置對列車運行方案的影響以及不同天窗分段時間配合兩個方面考慮，提出了既有線列車運行圖天窗分段與銜接優化模型，并設計并行蟻群算法進行求解。最后通過實例對模型算法的有效性進行了驗證。

2 問題分析與描述

2.1 問題分析

天窗單元是實現維修施工作業的最小基本單位，既有電氣化鐵路一般以供電臂停電單元作為為天窗單元，非電氣化鐵路一般以施工區間為天窗單元。天窗分段是為了兼顧施工維修作業和運輸工作的連續性需求，對天窗單元進行的合理組合。天窗分段可以用車站集合進行表示，出現在相鄰兩個天窗分段中的車站稱為相鄰天窗分段的分界站。天窗分段會導致分界站出現兩個以上的天窗，形成天窗錯位，影響車站和線路能力利用。而天窗銜接正是為了協調不同天窗分段在分界站的起始時間，以減少天窗錯位對車站和線路能力的影響。可以說，天窗分段主要解決“在哪兒分”的問題，是從空間維度對天窗單元進行組合。而天窗銜接主要解決“在哪兒接”的問題，是研究橫向時間帶上不同天窗分段的配合。本質上講，天窗分段與銜接研究是一個二維時空組合優化問題。

2.2 符合說明

3 問題建模

3.1 模型假設

本文研究基于以下前提：

1)旅客列車運行方案已知；

2)天窗時間不能橫向分割；

3)天窗分段分界站的到發線數量充足；

4)時間以分鐘為單位，取值范圍為[0，1440)。

3.2 目標函數

天窗分段與銜接優化的主要目有兩個：一是減小天窗設置對列車運行的影響，二是盡可能縮短相鄰天窗分段的錯位時間。

本文定義如式(1)所示的示性函數來表征天窗設置對列車運行的影響，?di∈u，如果天窗時間與列車運行時間有交集，則稱天窗分段對該列車運行有影響，反之，則稱天窗分段對該列車運行無影響。

R(Tp，s，Mi)=1|Tp，s∩Mi≠?

R(Tp，s，Mi)=0|Tp，s∩Mi=?

(1)

則天窗分段方案u對列車運行的影響可表示為

(2)

圖1 天窗錯位時間

(3)

式(3)中，δ(s)表示分界站s可接受的天窗錯位時間閾值，則天窗分段方案u下任意兩個相鄰天窗分段錯位時間可表示為

綜上，本文的兩個目標函數可表示為

min{Z1(u，v)|?u∈U，v∈V}

(4)

min{Z2(u，v)|?u∈U，v∈V}

(5)

式(4)與式(5)表示遍歷所有可能的天窗分段及銜接方案組合，取其中對列車運行影響最小以及天窗分段錯位時間最短的方案即為最佳天窗分段及銜接方案。

3.3 約束條件

1)天窗分段完整性約束

天窗分段要求涵蓋線路上所有車站，并且除了分界站，其它車站只能屬于一個天窗分段。

{d1/sn1}∪{d2/sn2}∪…∪{de-1/sne-1}∪{de}=L

(6)

{d1/sn1}∩{d2/sn2}∩…∩{de-1/sne-1}∩{de}=?

(7)

2)天窗分段時間范圍約束

任意車站天窗開始時間與持續時間必須位于允許時間范圍內，并且分界站總的天窗占用時間不能超過該站總的天窗可用時間范圍。

(8)

|Mi|+|Mi+1|-(|Mi+1-Mi|)≤Ts

(9)

3)遍歷性約束

所有可能的天窗分段方案以及不同天窗分段的銜接方案都應該遍歷搜索一遍。

(10)

(11)

4)變量取值約束

R(Tp，s，Mi)∈{0，1}

(12)

φu，φv∈{0，1}

(13)

4 算法設計

4.1 雙目標轉化

上述模型是一個雙目標優化問題，采用線性加權法[8]將雙目標轉換為單目標進行求解。引進目標值權重系數ω1、ω2，且ω1+ω2=1，將上述模型轉化成單目標模型問題：

(14)

4.2 變量降維

對于一個由n個車站組成的線路而言，天窗分段與銜接問題的復雜度為O(((1440-Δt)/σ)·2n-2)。當車站數量較多時，問題的規模會以指數形式增長，造成組合爆炸現象。因此，有必要通過變量降維來降低問題求解的復雜度。

根據天窗分段與銜接問題的復雜度計算表達式，可以從兩個方面對該問題進行降維處理。一是減少車站數量n；二是降低搜索粒度σ。基于歷史列車運行圖資料分析可知，天窗分段往往發生在一些大站和銜接站，因此，可以根據線路車站的到發運量，停站列數，線路銜接情況等屬性，判定可能發生天窗分段的備選車站集，然后在備選車站集中進行迭代搜索，這樣可以大大降低搜索空間，提高搜索效率。另外，根據運行圖鋪畫要求，可以適當增大橫向搜索的時間粒度，減少搜索次數。

4.3 并行蟻群搜索算法

考慮到天窗分段與銜接問題的復雜性，一種可行的思路是采用分治思想，將原問題分解為多個規模較小的子問題，各個子問題可使用同一種算法求解，然后再做綜合優化。并行蟻群算法是體現“分治思想”的智能優化方法之一，本文采用并行蟻群算法進行求解，其關鍵步驟包括轉移概率計算、信息素更新和并行策略選取。

1)轉移概率計算

(15)

式(15)中，τij(t)為信息素強度；ηij為啟發式信息，是指天窗分段di選擇銜接天窗分段開始時間tj的啟發式期望度。0≤β≤1表示τij(t)和ηij在構造解時的作用程度。

2)信息素更新

信息素更新是蟻群算法的核心。本文采用最小最大螞蟻系統的思想[8]，只有迭代最優螞蟻才被允許釋放信息素，為了避免迭代停滯，將信息素的取值限制在區間[τmin，τmax]，其中τmax和τmin可根據文獻[9]中的方法確定。螞蟻在完成一次循環后，每條邊上的信息素濃度將依據下式更新

τij(t+1)=ρτij(t)+Δτij

(16)

式(16)中，ρ為信息素的揮發系數ρ<1，且；t為迭代次數；Δτij為本次迭代后信息素增量。計算出τij(t+1)后，還需判斷其值是否在區間[τmin，τmax]，因此，本文算法信息素更新原則如下

(17)

3)并行策略

在蟻群算法并行化時，選擇何種并行策略是由問題規模及運行環境決定的。本文選擇粗粒度并行策略[10]，該種策略將原蟻群劃分成若干個子群，每個子蟻群相互獨立地并發執行串行蟻群算法，經過指定次數的迭代后，各子蟻群間會交換若干信息，豐富各子蟻群的多樣性，防止未成熟收斂的發生。粗粒度并行策略的過程如圖2所示。

圖2 粗粒度并行策略

4.4 算法流程

應用并行蟻群算法進行天窗分段與銜接問題求解的算法描述如下：

Step1：初始化參數。確定螞蟻總數，子群個數以及各子群的螞蟻數目，并為每個螞蟻選擇一個初始的解構成，設定各子群內的初始信息素濃度為τij(0)，計算信息素的上下界τmin，τmax。將循環次數設定為0。

Step2：狀態轉移規則。每個螞蟻在其所在子群中使用偽隨機比例原則選擇下一個解的構成，并根據式(15)計算其轉移概率。

Step3：局部更新規則。每個螞蟻在構造一個解的過程中，根據局部更新規則更新解的各構成部分信息素濃度。

Step4：目標函數值評價。計算每個子群內各個螞蟻所得到的目標函數值，并比較其大小。

Step5：全局更新規則。在各個子群中全局更新只是對每次循環中得到最優解的螞蟻，全局更新依據式(16)—(17)進行。

Step6：子群間信息素交流。將更新后的信息素同時傳送給其它q-1個子群。

Step7：終止條件判定。如果滿足終止條件，則輸出全局最優解并結束程序；否則，轉向step2繼續執行。

圖3為并行蟻群算法流程圖，圖中，I為迭代次數，R為迭代次數上限。

圖3 并行蟻群算法流程圖

5 算例分析

以達萬鐵路為研究對象，驗證本文提出模型算法的有效性。達萬鐵路為單線鐵路，全長157km，共有18個車站，依次編號為1—18。根據路局天窗設置原則，需預留不少于90min的分段矩形天窗。綜合考慮車站等級、線路銜接、停站方案等因素，選定萬州，萬州西，三正，關龍橋，梁平，文化，葫蘆潭，亭子和達州9個車站作為可能的天窗分界站。根據達萬鐵路2018年列車開行方案，該線共運行22列各等級旅客列車。各類列車的權重系數見表1。

表1 不同種類列車權重值

利用MATLAB 7.12.0 編程實現并行蟻群算法，將蟻群平均分為4組，算法中螞蟻個數M=40，每個群組初始信息濃度設為τij(0)=0.01，ρ=0.8，β=0.5，時間粒度σ=5。算法迭代過程中，可行解收斂情況見圖4，可以看出，算法迭代到150次左右開始收斂，得到全局最優函數轉化值為143，耗時25s。達萬線天窗分段與銜接最優方案見表2。

圖4 算法收斂曲線圖

為進一步說明本文所提方法的有效性，將本文結果與2018年達萬線天窗設置情況(人工經驗編制)進行對比，本文方法將達萬線的天窗劃分為5個天窗分段，分別為萬州—三正、三正—梁平、梁平—開江、開江—亭子、亭子-達州，總的天窗錯位時間為120min。人工設置的結果共有8個天窗分段，總的天窗錯位時間為250min。可以看出，相較于人工經驗設置的結果，本文方法能夠有效減少分界站的天窗錯位時間，而且可以在較短時間內求得全局滿意解，能夠滿足計劃編制的實時性要求。

表2 天窗分段與銜接結果

6 結束語

我國鐵路貫通成網運營條件下，大量長途跨線列車對天窗設置的制約十分明顯，合理進行天窗分段與銜接對優化列車運行線時空布局，提高鐵路能力利用至關重要。本文基于列車開行方案給定情形，研究了既有線天窗分段與銜接優化問題，并設計了并行蟻群算法進行求解，最后以達萬鐵路實際數據為例驗證了本文提出模型及算法的有效性。本文研究未考慮貨物列車對天窗分段與銜接的影響，在今后研究中將繼續對這一問題進行深化。