大型高鐵客運站到發線運用調整模型及算法

彭其淵， 寧 佳， 魯工圓

(1. 西南交通大學 交通運輸與物流學院， 四川 成都 610031； 2. 綜合交通運輸智能化國家地方聯合工程實驗室， 四川 成都 610031)

大型高鐵客運站位于高鐵網絡的重要節點，通常銜接多條高鐵線路并配備動車段；站內列車作業過程種類多樣、運行進路及列車接續關系錯綜復雜，其車站作業對于所銜接各條線路的列車運行均有很大影響，且受到干擾后的決策質量可能影響多條線路的運營效率。為更好保障高鐵網絡中列車安全、有序運行，有必要重點研究大型高鐵客運站的到發線運用調整問題。

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

(1) 實時性要求 方法應能夠在足夠短的時間內得到調整方案；

(2) 可執行性要求 方案應能以盡量小的調整量盡快恢復車站作業及列車運行秩序；

(3) 安全性要求 方案應滿足車站間隔時間、無進路沖突等安全要求。

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

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

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

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

1 到發線運用方案調整模型的建立

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

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

為便于模型構建，在保證模型對實際問題描述的準確性的基礎上，對上述各時刻進行進一步預處理，這里分別以停站列車和通過列車為例進行說明，見圖1，其他類型列車與停站列車類似，不再贅述。

所有的列車過站徑路必須彼此相容，具體體現在以下兩個方面：一是到發線占用相容性，即一條到發線同時最多只能被一列列車占用；二是咽喉區進路占用相容性，保證列車占用咽喉區進路時不能存在時空沖突。

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

( 1 )

( 2 )

( 3 )

( 4 )

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

表1 模型0-1變量定義

表2 模型相關參數定義

到發線運用方案調整模型的約束條件如下：

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

( 5 )

( 6 )

( 7 )

( 8 )

( 9 )

(10)

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

(11)

(12)

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

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(20)

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

(21)

(22)

xk,i≤θk,i

(23)

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

(24)

(25)

(26)

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

(27)

在滿足以上約束的條件下，模型的優化目標為：一是對車站作業秩序的影響最小，即盡可能少的調整到發線運用方案，并盡量滿足到發線固定使用方案，其體現在盡量選擇權重ck,i較大的徑路，即

(28)

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

二是列車總晚點時分最少，即

(29)

考慮到在現場實際中，當列車運行晚點或車站設備故障時，為避免列車晚點在路網中的傳播，應優先考慮保證列車總晚點時分最少，故將上述雙目標轉化為單目標為

maxZ=Z1-αZ2

(30)

式中：α為一足夠大的罰因子。該處理方法借鑒了文獻[4]中的相關思路，以實現到發線運用調整方案中列車總晚點時分最少前提下對車站作業秩序影響最小的目標。

此目標函數保證了當列車運行晚點或車站設備故障時，為避免列車晚點在路網中的傳播，優先考慮固定列車到發時刻不變，調整其到發線運用方案；若仍無法疏解徑路沖突，再調整其到發時刻。這與現場生產中車站到發線運用調整邏輯相符。

2 到發線運用方案調整模型的求解

2.1 模型的分解

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

子問題1 到發線運用方案編制子問題。在固定列車到發時刻的基礎上，考慮到發線的固定使用方案、圖定到發線運用方案、所有可行過站徑路的可用性以及每兩條徑路間的相容性關系，制定總權重最大的過站徑路選擇方案。該子問題的模型M1如下

(31)

模型M1的最優解為具有相容過站徑路且徑路選擇總權重最大的列車集。雖然模型M1總是有解的，但所得方案并不一定能實現調整階段內所有列車的到發線分配，這時就需要對無法分配到發線的該部分列車集進行到發時刻調整，即子問題2。

子問題2 列車到發時刻調整子問題。在求解子問題1得到的徑路選擇方案的基礎上，對無法分配到發線的該部分列車集進行到發時刻及到發線的同步調整，在保證列車總晚點時分最少的前提下，實現徑路沖突疏解。該子問題的模型M2為

M2 式(29)

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

(32)

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

基于此，下面將分別針對這兩個子問題設計分支定界算法及同步調整算法進行求解，并在此基礎上，進一步提出原問題的求解算法框架。

2.2 分支定界算法

由于在子問題1中，列車到發時刻固定，則列車占用每條可行過站徑路的相關起訖時刻也固定，進一步每條徑路是否可用以及每兩條徑路間的相容性關系固定。

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

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

(33)

(34)

(35)

(36)

(37)

(38)

(39)

(40)

(41)

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

(42)

為形象描述徑路相容性關系，構建列車沖突圖[14]：將所有的可行過站徑路抽象為頂點v(如頂點vk,i表示列車k的徑路ρi)，相應的權重ck,i抽象為頂點權重ωk,i，徑路間的相容關系抽象為頂點間的無向弧(當兩徑路相容時，對應兩頂點間存在無向弧)。

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

(43)

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

通過對列車過站徑路所做的特定選擇構造一棵狀態空間樹，樹的節點反映了對某一列列車的過站徑路所做的特定選擇。樹的根代表了問題求解前的初始狀態，第一層節點代表了列車1的徑路選擇方案，第二層節點代表了列車2的徑路選擇方案，以此類推。

令L表示狀態空間樹中存儲的節點集合，L={P(Xp)|p=1,2,…}，其中每一個節點均可表示為六元組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屬于組合優化問題，狀態空間樹規模較大，傳統的分支定界收斂較慢，為保證在不犧牲解的質量的前提下，提高算法的收斂速度，通過設置“前探”策略與“檢查”機制，提出了一種高效的剪枝規則。改進后的分支定界算法流程如下：

Step1初始步。計算該子問題的上界UB，計算式見式(47)。將x0初始化為空集，E0中每個元素初始化為1，產生根節點P(X0)=(0,?,0,UB,E0,?)，則L={P(X0)}，當前最優解x*=?，u*=0。轉Step2。

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

(47)

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

Step3分枝。在節點PS(X)的基礎上，為列車(dS+1)選擇徑路，共產生(λdS+1+1)個節點，記LD={P(Xp)|p=1,2,…,λdS+1+1}。其中，對于?p=1,2,…,λdS+1，節點P(Xp)表示選擇徑路ρp；而當p=λdS+1+1時，節點P(Xp)表示不為列車(dS+1)選擇任何一條過站徑路。轉Step4。

Step4定界。計算集合LD中每一節點P(Xp)的dp、xp、up、UBp、Ep。對于每一個節點P(Xp)：

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

(3) 若dp

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

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

Step5可行解。更新當前的最優解，即令x*=xp，u*=up，并從集合LD中移除節點P(Xp)。

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

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

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

(48)

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

(49)

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

(50)

將節點PS(X)從集合L中移除，令L=L∪LD，轉Step2。

2.3 同步調整算法

通過對子問題1的求解，可以得到列車到發時刻固定條件下對車站作業秩序影響最小的最優徑路選擇方案。若該方案實現了對調整階段內所有列車的到發線分配，則原問題已得到最優解；否則，需要對仍存在徑路沖突的列車進行到發時刻及到發線同步調整，以疏解徑路沖突。

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

同步調整算法流程如下：

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

Step3同步調整。對于集合J中每一個調整列車集，調用模型M2進行沖突疏解。由于每個調整列車集中包含的列車數目較少，模型的求解時間也較短。

2.4 到發線運用調整優化算法框架

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

Step1根據列車運行圖信息、圖定到發線運用方案、車站站型圖、設備故障信息、到發線固定使用方案等，生成每列列車的可行過站徑路集，并初始化每列列車占用每條徑路的相關起訖時刻等。轉Step2。

Step2調用改進分支定界算法求解徑路選擇方案。若該方案實現了調整階段內所有列車的到發線分配，則已得到對車站作業秩序影響最小的到發線運用調整方案，且列車按照圖定到發時刻運行，算法結束；否則，轉Step3。

Step3根據Step2得到的無法分配到發線的列車集合，調用同步調整算法進一步疏解徑路沖突。轉Step4。

Step4更新每列列車的到發時刻，并重新計算徑路相容性關系。轉Step2。

3 算例分析

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

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

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

表3 干擾場景下列車信息調整匯總表

編號類型最小停站時間/s圖定方案調整方案到達時刻出發時刻到發線停站時間/s到達時刻出發時刻到發線停站時間/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 結束語

大型高鐵客運站到發線運用調整具有實時性、可執行性、安全性等要求，干擾情況下如何快速生成調整方案以盡快恢復車站作業及列車運行的正常秩序，對于保障高鐵網絡中列車安全、有序運行具有重要意義。

針對該問題，本文在構建了到發線運用調整優化的混合整數線性規劃模型的基礎上，提出了一種基于分支定界的算法框架，其關鍵技術包括：(1)根據問題的特點，將問題分解為2個子問題，簡化了問題的計算復雜度；(2)針對傳統分支定界收斂速率問題，提出了一種基于“前探”策略與“檢查”機制的高效剪枝規則；(3)通過構建列車沖突圖，引入頂點“權重度”的概念，提出了一種高質量的上界計算方法，并以此改進了算法終止規則；(4)同步調整算法針對規模縮減的調整列車集，通過求解線性規劃模型，實現到發線與到發時刻的同步調整。

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