彭其淵， 寧 佳， 魯工圓

(1. 西南交通大學(xué) 交通運(yùn)輸與物流學(xué)院， 四川 成都 610031； 2. 綜合交通運(yùn)輸智能化國(guó)家地方聯(lián)合工程實(shí)驗(yàn)室， 四川 成都 610031)

大型高鐵客運(yùn)站位于高鐵網(wǎng)絡(luò)的重要節(jié)點(diǎn)，通常銜接多條高鐵線路并配備動(dòng)車段；站內(nèi)列車作業(yè)過程種類多樣、運(yùn)行進(jìn)路及列車接續(xù)關(guān)系錯(cuò)綜復(fù)雜，其車站作業(yè)對(duì)于所銜接各條線路的列車運(yùn)行均有很大影響，且受到干擾后的決策質(zhì)量可能影響多條線路的運(yùn)營(yíng)效率。為更好保障高鐵網(wǎng)絡(luò)中列車安全、有序運(yùn)行，有必要重點(diǎn)研究大型高鐵客運(yùn)站的到發(fā)線運(yùn)用調(diào)整問題。

大型高鐵客運(yùn)站到發(fā)線運(yùn)用調(diào)整問題考慮在列車運(yùn)行晚點(diǎn)或車站設(shè)備故障等干擾情況下，如何通過調(diào)整到發(fā)線運(yùn)用方案及列車到發(fā)時(shí)刻，減小干擾對(duì)車站作業(yè)及列車運(yùn)行的影響，以期盡快恢復(fù)正常秩序。該問題的解決方法需滿足以下幾個(gè)方面要求：

(1) 實(shí)時(shí)性要求 方法應(yīng)能夠在足夠短的時(shí)間內(nèi)得到調(diào)整方案；

(2) 可執(zhí)行性要求 方案應(yīng)能以盡量小的調(diào)整量盡快恢復(fù)車站作業(yè)及列車運(yùn)行秩序；

(3) 安全性要求 方案應(yīng)滿足車站間隔時(shí)間、無進(jìn)路沖突等安全要求。

縱觀國(guó)內(nèi)外學(xué)者關(guān)于到發(fā)線運(yùn)用問題的研究，主要針對(duì)列車到發(fā)時(shí)刻確定條件下的到發(fā)線運(yùn)用計(jì)劃編制問題，而針對(duì)干擾情況下的到發(fā)線運(yùn)用調(diào)整的研究相對(duì)較少。雖然兩者在研究對(duì)象、優(yōu)化目標(biāo)和優(yōu)化頻次三個(gè)方面有所不同[1]，但進(jìn)路沖突疏解均為二者需要解決的一個(gè)關(guān)鍵問題，前者的既有研究成果具有一定的借鑒意義。文獻(xiàn)[2]通過引入“時(shí)間片”的概念，簡(jiǎn)化到發(fā)線占用相容性約束，并設(shè)計(jì)最小最大螞蟻算法求解。文獻(xiàn)[3]將問題轉(zhuǎn)化為加權(quán)節(jié)點(diǎn)包裝問題，并利用分支定界算法求解。以上兩篇文獻(xiàn)均需預(yù)先計(jì)算出所有的相容進(jìn)路集合，算法的復(fù)雜度隨著問題規(guī)模的增大急劇增加。文獻(xiàn)[4-5]將列車的接發(fā)車進(jìn)路和到發(fā)線拼接成過站徑路，考慮道岔和到發(fā)線的占用時(shí)間窗構(gòu)造相容性約束，并設(shè)計(jì)模擬退火算法求解。文獻(xiàn) [6]通過構(gòu)造列車作業(yè)時(shí)間窗沖突圖，利用沖突識(shí)別、值排序以及BT搜索3個(gè)步驟進(jìn)行求解。

以上文獻(xiàn)均為針對(duì)到發(fā)線運(yùn)用計(jì)劃編制問題進(jìn)行的研究，由于列車到發(fā)時(shí)刻固定，故在約束進(jìn)路沖突時(shí)，均未考慮列車占用先后關(guān)系；另外，到發(fā)線運(yùn)用實(shí)時(shí)調(diào)整要求算法收斂速度快，計(jì)算效率高，上述研究成果中所涉及的算法難以滿足強(qiáng)時(shí)效性的要求。針對(duì)到發(fā)線運(yùn)用調(diào)整問題，文獻(xiàn)[1]提出了一種基于滾動(dòng)時(shí)域的到發(fā)線動(dòng)態(tài)調(diào)整策略；文獻(xiàn)[7-8]采用模擬人工調(diào)度的方法，逐一為各列車安排到發(fā)線及接發(fā)車進(jìn)路，并通過調(diào)整后行列車的到發(fā)時(shí)刻疏解沖突；文獻(xiàn)[9]建立了2個(gè)線性規(guī)劃模型，通過逐次求解兩模型得到多個(gè)到發(fā)線調(diào)整方案，通過方案比選確定最終方案；文獻(xiàn)[10]運(yùn)用現(xiàn)代排序理論，設(shè)計(jì)自律優(yōu)化算法及三步算法，實(shí)現(xiàn)股道運(yùn)用的實(shí)時(shí)調(diào)整；文獻(xiàn)[11]針對(duì)到發(fā)線異常下的咽喉區(qū)利用優(yōu)化問題，通過引入“虛擬列車”，建立非線性優(yōu)化模型，并設(shè)計(jì)遺傳算法求解，但其計(jì)算效率仍無法滿足實(shí)時(shí)性要求。

綜上，目前針對(duì)干擾下的到發(fā)線運(yùn)用調(diào)整研究較少，既有研究的有待完善之處主要體現(xiàn)在：干擾情況下，僅通過調(diào)整到發(fā)線可能無法實(shí)現(xiàn)沖突疏解，這時(shí)就需要對(duì)列車的到發(fā)時(shí)刻進(jìn)行調(diào)整，而既有研究中絕大多數(shù)未考慮這一方面；既有調(diào)整算法難以滿足實(shí)時(shí)性要求，且基于滾動(dòng)時(shí)域和模擬人工調(diào)度的方法極有可能加劇晚點(diǎn)傳播，難以保證求解質(zhì)量；另外，大部分現(xiàn)有研究在構(gòu)建進(jìn)路沖突約束時(shí)僅考慮了一次解鎖，缺乏針對(duì)不同解鎖方式下進(jìn)路沖突關(guān)系的統(tǒng)一性描述。

本文針對(duì)大型高鐵客運(yùn)站到發(fā)線運(yùn)用調(diào)整問題，在將咽喉區(qū)進(jìn)路和到發(fā)線組合成過站徑路的前提下，首先，以列車實(shí)際到發(fā)時(shí)刻和過站徑路選擇為決策，構(gòu)建混合整數(shù)線性規(guī)劃模型，該模型可適用于不同的進(jìn)路解鎖方式；其次，將問題分解為到發(fā)線運(yùn)用方案編制子問題和列車到發(fā)時(shí)刻調(diào)整子問題，分別設(shè)計(jì)分支定界算法和同步調(diào)整算法求解，并在此基礎(chǔ)上提出了到發(fā)線運(yùn)用調(diào)整優(yōu)化的算法框架；最后設(shè)計(jì)算例對(duì)模型及算法的有效性進(jìn)行驗(yàn)證。

1 到發(fā)線運(yùn)用方案調(diào)整模型的建立

令某干擾情況下需要進(jìn)行到發(fā)線運(yùn)用方案調(diào)整的時(shí)間段(下文簡(jiǎn)稱“調(diào)整階段”)為[T0,Tn]，列車集為K={1,2,…,n}，列車按照在站作業(yè)方式的不同，分為始發(fā)列車、終到列車、通過列車、停站列車和立折列車[12]。不同類型的列車，在不同的進(jìn)路解鎖方式下，占用各軌道電路的起訖時(shí)刻不同。

為方便問題描述，本文從運(yùn)輸組織的角度，使用了如下占用時(shí)間的定義，即?k∈K。

為便于模型構(gòu)建，在保證模型對(duì)實(shí)際問題描述的準(zhǔn)確性的基礎(chǔ)上，對(duì)上述各時(shí)刻進(jìn)行進(jìn)一步預(yù)處理，這里分別以停站列車和通過列車為例進(jìn)行說明，見圖1，其他類型列車與停站列車類似，不再贅述。

所有的列車過站徑路必須彼此相容，具體體現(xiàn)在以下兩個(gè)方面：一是到發(fā)線占用相容性，即一條到發(fā)線同時(shí)最多只能被一列列車占用；二是咽喉區(qū)進(jìn)路占用相容性，保證列車占用咽喉區(qū)進(jìn)路時(shí)不能存在時(shí)空沖突。

文獻(xiàn)[13]在考慮了列車占用先后關(guān)系的基礎(chǔ)上，建立了敵對(duì)進(jìn)路的疏解約束。文獻(xiàn)[14]引入“沖突度”的概念計(jì)算不同解鎖方式下的敵對(duì)進(jìn)路解鎖時(shí)間。令進(jìn)路β與進(jìn)路α的沖突度為γβ,α，則進(jìn)路β開始占用γβ,α?xí)r間后，才能開始準(zhǔn)備進(jìn)路α的占用。在上述兩篇文獻(xiàn)的基礎(chǔ)上，考慮不同類型列車接發(fā)車時(shí)占用咽喉區(qū)的開始時(shí)刻不同，?k,h∈K，?ρi∈Rk，?ρj∈Rh，Rh={ρj|j=1,2,…,λh}(λh表示列車h的可行過站徑路有λh條)令ωk表示列車k是否為通過列車，若是取1，否則取0，定義以下4類進(jìn)路沖突度：

( 1 )

( 2 )

( 3 )

( 4 )

除此之外，對(duì)于?k,h∈K，?ρi∈Rk，?ρj∈Rh，定義如下參數(shù)及0-1變量。

表1 模型0-1變量定義

表2 模型相關(guān)參數(shù)定義

到發(fā)線運(yùn)用方案調(diào)整模型的約束條件如下：

(1) ?k∈K，上述各占用時(shí)間的起訖時(shí)刻及實(shí)際到發(fā)時(shí)刻之間的關(guān)系如下

( 5 )

( 6 )

( 7 )

( 8 )

( 9 )

(10)

(2) 到發(fā)線相容性約束，對(duì)于?k,h∈K，且k≠h，?ρi∈Rk，?ρj∈Rh

(11)

(12)

(3) 咽喉區(qū)進(jìn)路占用相容性約束，對(duì)于?k,h∈K，且k≠h，?ρi∈Rk，?ρj∈Rh：

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(4) 徑路可用性約束：以到發(fā)線故障為例，保證列車占用某條到發(fā)線時(shí)該到發(fā)線處于可用狀態(tài)，即對(duì)于?k∈K，?ρi∈Rk

(21)

(22)

xk,i≤θk,i

(23)

(5) ?k∈K，列車k的實(shí)際到達(dá)(出發(fā))時(shí)刻不得早于圖定到達(dá)(出發(fā))時(shí)刻，且其在到發(fā)線上的停留時(shí)間不得少于最小停留時(shí)間要求，即

(24)

(25)

(26)

(6) 每1列車只能選擇1條過站徑路，即?k∈K

(27)

在滿足以上約束的條件下，模型的優(yōu)化目標(biāo)為：一是對(duì)車站作業(yè)秩序的影響最小，即盡可能少的調(diào)整到發(fā)線運(yùn)用方案，并盡量滿足到發(fā)線固定使用方案，其體現(xiàn)在盡量選擇權(quán)重ck,i較大的徑路，即

(28)

式中:ck,i為列車k選擇徑路ρi的權(quán)重。其值越大表示該選擇對(duì)車站作業(yè)秩序影響越小，若與圖定到發(fā)線運(yùn)用方案相同，ck,i=1；若與圖定方案不同，但符合到發(fā)線固定使用方案，ck,i=q1；若與圖定方案不同，且不符合固定使用方案，ck,i=q2，0

二是列車總晚點(diǎn)時(shí)分最少，即

(29)

考慮到在現(xiàn)場(chǎng)實(shí)際中，當(dāng)列車運(yùn)行晚點(diǎn)或車站設(shè)備故障時(shí)，為避免列車晚點(diǎn)在路網(wǎng)中的傳播，應(yīng)優(yōu)先考慮保證列車總晚點(diǎn)時(shí)分最少，故將上述雙目標(biāo)轉(zhuǎn)化為單目標(biāo)為

maxZ=Z1-αZ2

(30)

式中：α為一足夠大的罰因子。該處理方法借鑒了文獻(xiàn)[4]中的相關(guān)思路，以實(shí)現(xiàn)到發(fā)線運(yùn)用調(diào)整方案中列車總晚點(diǎn)時(shí)分最少前提下對(duì)車站作業(yè)秩序影響最小的目標(biāo)。

此目標(biāo)函數(shù)保證了當(dāng)列車運(yùn)行晚點(diǎn)或車站設(shè)備故障時(shí)，為避免列車晚點(diǎn)在路網(wǎng)中的傳播，優(yōu)先考慮固定列車到發(fā)時(shí)刻不變，調(diào)整其到發(fā)線運(yùn)用方案；若仍無法疏解徑路沖突，再調(diào)整其到發(fā)時(shí)刻。這與現(xiàn)場(chǎng)生產(chǎn)中車站到發(fā)線運(yùn)用調(diào)整邏輯相符。

2 到發(fā)線運(yùn)用方案調(diào)整模型的求解

2.1 模型的分解

上述所建立的模型為混合整數(shù)線性規(guī)劃模型(MILP)，模型中決策變量及約束條件的數(shù)目均較大，若直接利用優(yōu)化軟件求解，對(duì)于大規(guī)模算例，運(yùn)算效率緩慢。這是由于每?jī)蓷l徑路間均存在一組到發(fā)線相容性約束以及咽喉區(qū)進(jìn)路占用相容性約束，這兩組約束的存在是為了疏解徑路沖突?？紤]到徑路沖突疏解的措施有以下兩種：調(diào)整到發(fā)線運(yùn)用方案以及調(diào)整列車到發(fā)時(shí)刻。為優(yōu)先保證列車運(yùn)行秩序，對(duì)于存在徑路沖突的列車，首先考慮在列車到發(fā)時(shí)刻固定不變的前提下調(diào)整其到發(fā)線；若仍存在徑路沖突，再對(duì)該部分沖突列車的到發(fā)時(shí)刻及到發(fā)線進(jìn)行同步調(diào)整?；诖?，將原問題分解為以下2個(gè)子問題：

子問題1 到發(fā)線運(yùn)用方案編制子問題。在固定列車到發(fā)時(shí)刻的基礎(chǔ)上，考慮到發(fā)線的固定使用方案、圖定到發(fā)線運(yùn)用方案、所有可行過站徑路的可用性以及每?jī)蓷l徑路間的相容性關(guān)系，制定總權(quán)重最大的過站徑路選擇方案。該子問題的模型M1如下

(31)

模型M1的最優(yōu)解為具有相容過站徑路且徑路選擇總權(quán)重最大的列車集。雖然模型M1總是有解的，但所得方案并不一定能實(shí)現(xiàn)調(diào)整階段內(nèi)所有列車的到發(fā)線分配，這時(shí)就需要對(duì)無法分配到發(fā)線的該部分列車集進(jìn)行到發(fā)時(shí)刻調(diào)整，即子問題2。

子問題2 列車到發(fā)時(shí)刻調(diào)整子問題。在求解子問題1得到的徑路選擇方案的基礎(chǔ)上，對(duì)無法分配到發(fā)線的該部分列車集進(jìn)行到發(fā)時(shí)刻及到發(fā)線的同步調(diào)整，在保證列車總晚點(diǎn)時(shí)分最少的前提下，實(shí)現(xiàn)徑路沖突疏解。該子問題的模型M2為

M2 式(29)

s.t. 式( 5 )～式(27)

(32)

可以看出，對(duì)于模型M1，列車到發(fā)時(shí)刻已知，其核心決策變量為徑路選擇0-1變量，各占用時(shí)間的起訖時(shí)刻可由徑路選擇方案及到發(fā)時(shí)刻綜合決定，因此后文將設(shè)計(jì)高效分支定界算法進(jìn)行求解；模型M2僅應(yīng)用于仍存在徑路沖突的部分列車集，求解規(guī)模較小，可直接利用商業(yè)優(yōu)化軟件求解。

基于此，下面將分別針對(duì)這兩個(gè)子問題設(shè)計(jì)分支定界算法及同步調(diào)整算法進(jìn)行求解，并在此基礎(chǔ)上，進(jìn)一步提出原問題的求解算法框架。

2.2 分支定界算法

由于在子問題1中，列車到發(fā)時(shí)刻固定，則列車占用每條可行過站徑路的相關(guān)起訖時(shí)刻也固定，進(jìn)一步每條徑路是否可用以及每?jī)蓷l徑路間的相容性關(guān)系固定。

由于進(jìn)路沖突度僅能描述咽喉區(qū)進(jìn)路間的相容性關(guān)系，為進(jìn)一步描述列車過站徑路間的相容性關(guān)系，引入“徑路相容性”：令ak,i,h,j表示列車k的徑路ρi與列車h的徑路ρj是否相容，相容取1，不相容取0。若兩條徑路存在到發(fā)線占用不相容或咽喉區(qū)進(jìn)路占用不相容，即式(33)～式(41)中至少有一個(gè)成立時(shí)，ak,i,h,j=0；相反，若式(33)～式(41)均不成立，則這兩條徑路彼此相容，ak,i,h,j=1。

(1) 到發(fā)線占用相容性判定條件

(33)

(34)

(35)

(36)

(37)

(38)

(39)

(40)

(41)

若列車k的徑路ρi不可用，則對(duì)于?h∈K，?ρj∈Rh，令ak,i,h,j=0，ah,j,k,i=0；另外，由于1列列車最多只能占用1條過站徑路，結(jié)合后續(xù)算法的需要，令

(42)

為形象描述徑路相容性關(guān)系，構(gòu)建列車沖突圖[14]：將所有的可行過站徑路抽象為頂點(diǎn)v(如頂點(diǎn)vk,i表示列車k的徑路ρi)，相應(yīng)的權(quán)重ck,i抽象為頂點(diǎn)權(quán)重ωk,i，徑路間的相容關(guān)系抽象為頂點(diǎn)間的無向弧(當(dāng)兩徑路相容時(shí)，對(duì)應(yīng)兩頂點(diǎn)間存在無向弧)。

類比頂點(diǎn)“度”的概念，引入頂點(diǎn)“權(quán)重度”：根據(jù)頂點(diǎn)vk,i與其他頂點(diǎn)的連接關(guān)系，若將該頂點(diǎn)入選完備子圖(此時(shí)該子圖僅包含這一個(gè)頂點(diǎn))，則完備子圖可能達(dá)到的最大權(quán)重，稱為頂點(diǎn)vk,i的權(quán)重度，記為udk,i，計(jì)算式為

(43)

子問題1轉(zhuǎn)化為：在列車沖突圖頂點(diǎn)的所有排列中，求其中具有最大權(quán)重的頂點(diǎn)集合，使得集合中任意兩個(gè)頂點(diǎn)間有且僅有一條邊。類比最大團(tuán)問題(Maximum Clique Problem，MCP)[15]，該問題具有以下特征：(1)頂點(diǎn)賦有權(quán)重；(2)目標(biāo)為求具有最大權(quán)重的完備子圖；(3)頂點(diǎn)與弧的數(shù)目均較多，但隸屬于同一列車的頂點(diǎn)，最多只能有一個(gè)頂點(diǎn)入選可行解。下面將結(jié)合這些特征，設(shè)計(jì)分支定界算法。

通過對(duì)列車過站徑路所做的特定選擇構(gòu)造一棵狀態(tài)空間樹，樹的節(jié)點(diǎn)反映了對(duì)某一列列車的過站徑路所做的特定選擇。樹的根代表了問題求解前的初始狀態(tài)，第一層節(jié)點(diǎn)代表了列車1的徑路選擇方案，第二層節(jié)點(diǎn)代表了列車2的徑路選擇方案，以此類推。

令L表示狀態(tài)空間樹中存儲(chǔ)的節(jié)點(diǎn)集合，L={P(Xp)|p=1,2,…}，其中每一個(gè)節(jié)點(diǎn)均可表示為六元組P(Xp)=(dp,xp,up,UBp,Ep,Lp)

up=∑vk,i∈xpωk,i

(44)

{ωh,j×min{ak,i,h,j|vk,i∈xp}|ρj∈Rh}

(45)

(46)

考慮到子問題1屬于組合優(yōu)化問題，狀態(tài)空間樹規(guī)模較大，傳統(tǒng)的分支定界收斂較慢，為保證在不犧牲解的質(zhì)量的前提下，提高算法的收斂速度，通過設(shè)置“前探”策略與“檢查”機(jī)制，提出了一種高效的剪枝規(guī)則。改進(jìn)后的分支定界算法流程如下：

Step1初始步。計(jì)算該子問題的上界UB，計(jì)算式見式(47)。將x0初始化為空集，E0中每個(gè)元素初始化為1，產(chǎn)生根節(jié)點(diǎn)P(X0)=(0,?,0,UB,E0,?)，則L={P(X0)}，當(dāng)前最優(yōu)解x*=?，u*=0。轉(zhuǎn)Step2。

UB=min{max{udk,i|ρi∈Rk}|k∈K}

(47)

Step2選擇節(jié)點(diǎn)。若L=?，停止，x*為最優(yōu)徑路選擇方案，u*為相應(yīng)的總權(quán)重；否則，從L中選擇具有最大深度、當(dāng)前最佳、最有希望(即上界最大)的一個(gè)節(jié)點(diǎn)，記為PS(X)=(dS,xS,uS,UBS,ES,LS)。轉(zhuǎn)Step3。

Step3分枝。在節(jié)點(diǎn)PS(X)的基礎(chǔ)上，為列車(dS+1)選擇徑路，共產(chǎn)生(λdS+1+1)個(gè)節(jié)點(diǎn)，記LD={P(Xp)|p=1,2,…,λdS+1+1}。其中，對(duì)于?p=1,2,…,λdS+1，節(jié)點(diǎn)P(Xp)表示選擇徑路ρp；而當(dāng)p=λdS+1+1時(shí)，節(jié)點(diǎn)P(Xp)表示不為列車(dS+1)選擇任何一條過站徑路。轉(zhuǎn)Step4。

Step4定界。計(jì)算集合LD中每一節(jié)點(diǎn)P(Xp)的dp、xp、up、UBp、Ep。對(duì)于每一個(gè)節(jié)點(diǎn)P(Xp)：

(2) 若dp=n，說明已搜索到一個(gè)可行解：若up>u*，說明up是比當(dāng)前最優(yōu)解u*更好的解，轉(zhuǎn)Step5；否則，轉(zhuǎn)Step6。

(3) 若dp

(4) 若dpu*且p≤λdp，設(shè)置“前探”策略，對(duì)集合LD中所有有希望的可行節(jié)點(diǎn)P(Xq)(q=1,2,…,p-1)進(jìn)行遍歷，轉(zhuǎn)Step7。

待集合LD中每一個(gè)節(jié)點(diǎn)P(Xp)均計(jì)算、判斷完畢，“檢查”被選擇節(jié)點(diǎn)PS(X)，若其待檢查節(jié)點(diǎn)集合LS≠?，對(duì)LS中所有的待檢查節(jié)點(diǎn)PS(Xg)進(jìn)行遍歷，轉(zhuǎn)Step8。

Step5可行解。更新當(dāng)前的最優(yōu)解，即令x*=xp，u*=up，并從集合LD中移除節(jié)點(diǎn)P(Xp)。

若u*=UB，說明可行解x*與u*一定為該問題的最優(yōu)解，停止；否則遍歷集合L中的所有節(jié)點(diǎn)，?P(Xf)∈L，若UBf≤u*，轉(zhuǎn)Step6。

Step6剪枝。從集合LD中移除節(jié)點(diǎn)P(Xp)，或者從集合L中移除節(jié)點(diǎn)P(Xf)。

(1) 若rh,j=rdp,p，則

(48)

(2) 若rh,j=rdp,q，則

(49)

(3) 若rh,j≠rdp,p，且rh,j≠rdp,q，則

(50)

將節(jié)點(diǎn)PS(X)從集合L中移除，令L=L∪LD，轉(zhuǎn)Step2。

2.3 同步調(diào)整算法

通過對(duì)子問題1的求解，可以得到列車到發(fā)時(shí)刻固定條件下對(duì)車站作業(yè)秩序影響最小的最優(yōu)徑路選擇方案。若該方案實(shí)現(xiàn)了對(duì)調(diào)整階段內(nèi)所有列車的到發(fā)線分配，則原問題已得到最優(yōu)解；否則，需要對(duì)仍存在徑路沖突的列車進(jìn)行到發(fā)時(shí)刻及到發(fā)線同步調(diào)整，以疏解徑路沖突。

令通過求解子問題1，仍無法分配到發(fā)線的列車集合為K′。?k∈K′，為疏解列車k與其他列車間的徑路沖突，可能需要調(diào)整到發(fā)時(shí)刻及到發(fā)線的列車集合記為Jk，稱為調(diào)整列車集。

同步調(diào)整算法流程如下：

Step2合并調(diào)整列車集。?k,h∈K′，且k≠h，若Jk∩Jh≠?，則令Jk=Jk∪Jh，刪除集合Jh。

Step3同步調(diào)整。對(duì)于集合J中每一個(gè)調(diào)整列車集，調(diào)用模型M2進(jìn)行沖突疏解。由于每個(gè)調(diào)整列車集中包含的列車數(shù)目較少，模型的求解時(shí)間也較短。

2.4 到發(fā)線運(yùn)用調(diào)整優(yōu)化算法框架

通過上述討論，將原問題分解為2個(gè)子問題，并分別提出了其求解算法。兩個(gè)算法之間的聯(lián)系如下：改進(jìn)分支定界算法為同步調(diào)整算法生成無法分配到發(fā)線的列車集合，同步調(diào)整算法為改進(jìn)分支定界算法更新徑路相容性關(guān)系。原問題的求解步驟如下：

Step1根據(jù)列車運(yùn)行圖信息、圖定到發(fā)線運(yùn)用方案、車站站型圖、設(shè)備故障信息、到發(fā)線固定使用方案等，生成每列列車的可行過站徑路集，并初始化每列列車占用每條徑路的相關(guān)起訖時(shí)刻等。轉(zhuǎn)Step2。

Step2調(diào)用改進(jìn)分支定界算法求解徑路選擇方案。若該方案實(shí)現(xiàn)了調(diào)整階段內(nèi)所有列車的到發(fā)線分配，則已得到對(duì)車站作業(yè)秩序影響最小的到發(fā)線運(yùn)用調(diào)整方案，且列車按照?qǐng)D定到發(fā)時(shí)刻運(yùn)行，算法結(jié)束；否則，轉(zhuǎn)Step3。

Step3根據(jù)Step2得到的無法分配到發(fā)線的列車集合，調(diào)用同步調(diào)整算法進(jìn)一步疏解徑路沖突。轉(zhuǎn)Step4。

Step4更新每列列車的到發(fā)時(shí)刻，并重新計(jì)算徑路相容性關(guān)系。轉(zhuǎn)Step2。

3 算例分析

以某大型高鐵客運(yùn)站為例，車站站型圖見圖2，共設(shè)有12條到發(fā)線，其中1～6道用于接發(fā)下行列車，7～12道用于接發(fā)上行列車。車站銜接A,B,C,D,E共5個(gè)方向，并配備有動(dòng)車段。咽喉區(qū)進(jìn)路采用分段解鎖，假設(shè)所有列車均由基本進(jìn)路接發(fā)，不考慮變通進(jìn)路，則共有67條接發(fā)車進(jìn)路，各進(jìn)路占用時(shí)間取值由列車長(zhǎng)度、列車速度及進(jìn)路長(zhǎng)度等因素綜合確定。到發(fā)線占用最小安全間隔時(shí)間為180 s。車站10:00:00—12:00:00時(shí)段內(nèi)到發(fā)84列高速列車，其中始發(fā)列車17列、終到列車14列、停站列車42列、立折列車11列。限于篇幅，各列車詳細(xì)到發(fā)信息未予展示。

車站到發(fā)線運(yùn)用計(jì)劃的圖定方案見圖3。設(shè)置干擾場(chǎng)景包括以下3個(gè)干擾：(1)列車6晚點(diǎn)2 min到達(dá)；(2)5道在10:30:00—10:40:00時(shí)段發(fā)生故障，不可占用；(3)列車44晚點(diǎn)5 min到達(dá)。根據(jù)本文構(gòu)建的模型及算法，在處理器為Intel Core i7 3.6 GHz、內(nèi)存為16.0 GB的計(jì)算機(jī)上，運(yùn)用C#編程，并調(diào)用CPLEX 12.6.3求解其中的模型M2，徑路選擇權(quán)重q1取0.8，q2取0.5，獲得干擾場(chǎng)景下車站到發(fā)線運(yùn)用調(diào)整方案見圖4，圖中每個(gè)矩形表示一列列車的到發(fā)線占用，水平方向的長(zhǎng)度表示持續(xù)時(shí)間，矩形右邊的數(shù)字表示列車編號(hào)，深顏色矩形表示產(chǎn)生到發(fā)線運(yùn)用方案調(diào)整或者到發(fā)時(shí)刻調(diào)整的列車，淺顏色矩形表示沒有發(fā)生任何調(diào)整的列車。對(duì)應(yīng)的總權(quán)重Z1為81.9，列車總晚點(diǎn)時(shí)間為320 s，程序運(yùn)行時(shí)間為1.33 s。

由圖3與圖4對(duì)比分析得：(1)由于列車44運(yùn)行延誤，導(dǎo)致其發(fā)車進(jìn)路與列車47的發(fā)車進(jìn)路產(chǎn)生時(shí)間沖突，為疏解沖突將列車47的停站時(shí)間延長(zhǎng)120 s，同時(shí)為保證列車44與列車60先后占用2道的間隔時(shí)間不少于180 s，將列車60的到發(fā)時(shí)刻均向后推遲100 s。(2)由于5道在10:30:00—10:40:00時(shí)段內(nèi)不可用，導(dǎo)致下行方向列車22和列車28被迫借用上行7道，進(jìn)而迫使列車10與列車11交換到發(fā)線。列車22和列車28由于車站布置圖的限制無法占用8道。(3)由于列車6運(yùn)行延誤，使得列車2被迫變更到發(fā)線至6道，進(jìn)而導(dǎo)致下行方向列車5被迫借用上行7道。其余列車的到發(fā)線運(yùn)用方案及到發(fā)時(shí)刻均保持不變。產(chǎn)生到發(fā)線運(yùn)用方案調(diào)整或者到發(fā)時(shí)刻調(diào)整的列車見表3?？梢钥闯?，該調(diào)整方案滿足實(shí)時(shí)性、安全性及可執(zhí)行性的要求，且能優(yōu)先保證列車運(yùn)行秩序，通過調(diào)整到發(fā)線運(yùn)用方案確保列車正點(diǎn)運(yùn)行。

表3 干擾場(chǎng)景下列車信息調(diào)整匯總表

編號(hào)類型最小停站時(shí)間/s圖定方案調(diào)整方案到達(dá)時(shí)刻出發(fā)時(shí)刻到發(fā)線停站時(shí)間/s到達(dá)時(shí)刻出發(fā)時(shí)刻到發(fā)線停站時(shí)間/s效用2下行34010:09:2010:15:00434010:09:2010:15:0063400.85下行14010:07:3010:09:50614010:07:3010:09:5071400.56下行12010:02:3010:04:30412010:04:3010:06:3041201.010上行94010:09:2010:25:00794010:09:2010:25:0089400.811上行34010:14:2010:20:00834010:14:2010:20:0073400.822下行45010:27:3010:35:00545010:27:3010:35:0074500.528下行12010:39:4010:41:40512010:39:4010:41:4071200.544下行42010:59:4011:06:40242011:04:4011:11:4024201.047下行36011:05:4011:11:40136011:05:4011:13:4014801.060下行27011:14:5011:19:20227011:16:3011:21:0022701.0

4 結(jié)束語

大型高鐵客運(yùn)站到發(fā)線運(yùn)用調(diào)整具有實(shí)時(shí)性、可執(zhí)行性、安全性等要求，干擾情況下如何快速生成調(diào)整方案以盡快恢復(fù)車站作業(yè)及列車運(yùn)行的正常秩序，對(duì)于保障高鐵網(wǎng)絡(luò)中列車安全、有序運(yùn)行具有重要意義。

針對(duì)該問題，本文在構(gòu)建了到發(fā)線運(yùn)用調(diào)整優(yōu)化的混合整數(shù)線性規(guī)劃模型的基礎(chǔ)上，提出了一種基于分支定界的算法框架，其關(guān)鍵技術(shù)包括：(1)根據(jù)問題的特點(diǎn)，將問題分解為2個(gè)子問題，簡(jiǎn)化了問題的計(jì)算復(fù)雜度；(2)針對(duì)傳統(tǒng)分支定界收斂速率問題，提出了一種基于“前探”策略與“檢查”機(jī)制的高效剪枝規(guī)則；(3)通過構(gòu)建列車沖突圖，引入頂點(diǎn)“權(quán)重度”的概念，提出了一種高質(zhì)量的上界計(jì)算方法，并以此改進(jìn)了算法終止規(guī)則；(4)同步調(diào)整算法針對(duì)規(guī)?？s減的調(diào)整列車集，通過求解線性規(guī)劃模型，實(shí)現(xiàn)到發(fā)線與到發(fā)時(shí)刻的同步調(diào)整。

算例分析表明：該算法能夠有效解決到發(fā)線運(yùn)用方案與列車到發(fā)時(shí)刻同步調(diào)整問題、不同進(jìn)路解鎖方式下的進(jìn)路沖突疏解問題，并在上述前提下，快速生成隨機(jī)干擾下大型高鐵客運(yùn)站到發(fā)線運(yùn)用實(shí)時(shí)調(diào)整方案，所得方案與圖定運(yùn)用計(jì)劃偏差較小，可操作性強(qiáng)。