列車運行圖天窗分段與銜接優(yōu)化技術研究

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

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

1 引言

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

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

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

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

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

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

2 問題分析與描述

2.1 問題分析

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

2.2 符合說明

3 問題建模

3.1 模型假設

本文研究基于以下前提：

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

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

3)天窗分段分界站的到發(fā)線數(shù)量充足；

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

3.2 目標函數(shù)

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

本文定義如式(1)所示的示性函數(shù)來表征天窗設置對列車運行的影響，?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下任意兩個相鄰天窗分段錯位時間可表示為

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

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)天窗分段時間范圍約束

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

(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 雙目標轉(zhuǎn)化

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

(14)

4.2 變量降維

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

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

4.3 并行蟻群搜索算法

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

1)轉(zhuǎn)移概率計算

(15)

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

2)信息素更新

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

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

(16)

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

(17)

3)并行策略

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

圖2 粗粒度并行策略

4.4 算法流程

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

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

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

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

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

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

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

Step7：終止條件判定。如果滿足終止條件，則輸出全局最優(yōu)解并結(jié)束程序；否則，轉(zhuǎn)向step2繼續(xù)執(zhí)行。

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

圖3 并行蟻群算法流程圖

5 算例分析

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

表1 不同種類列車權重值

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

圖4 算法收斂曲線圖

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

表2 天窗分段與銜接結(jié)果

6 結(jié)束語

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