重載組合站列車組合方案隨機機會規劃模型及算法

董世鑫，魏玉光，張進川

(北京交通大學 交通運輸學院，北京 100044)

以大秦線為代表，我國重載鐵路在鐵路網中相對獨立，重載線路兩端銜接路網中其他線路，車流來源與去向較為復雜，從而形成了半封閉式重載鐵路。由于重載線路與其所銜接集疏線路牽引質量標準不一致，為充分利用重載線路能力，半封閉式重載線路在裝車端單獨設置列車組合站進行重車車列的組合作業和空車車列的分解作業[1]。重載鐵路裝車端組合站在重載運輸集疏運系統中發揮著極其重要的作用。

與我國不同，國外重載鐵路一般為專線運輸，普遍采用低密度、大載重、固定車底循環的運輸模式，線路利用率低，能力富裕，因此對于重載運輸組織的研究較少。國內學者從不同角度對重載鐵路運輸組織進行了研究。在重載鐵路車流組織方面，文獻[2]以組合時間最短、重載通道重車流量最大為目標，建立重載鐵路裝車端車流組織的多目標規劃模型，并從宏觀角度結合路網結構將其抽象成最小費用最大流問題求解。文獻[3]對重載鐵路裝車域的重車車流組合方案進行優化研究，以組合列車在總組合時間及走行時間最小為目標，建立多目標規劃模型。文獻[4]綜合考慮重載鐵路裝車端和卸車端空車回送，以空車空駛時間最短為目標，建立重載鐵路空車調整的規劃模型，并利用動態規劃方法求解。

在車站工作組織方面，文獻[5]以編組站為研究對象，引入“代價”的概念將編組站靜態配流問題轉換為運輸問題，并采用表上作業法求解。文獻[6]對湖東站的車流組織形式展開分析，構建湖東站重車流調整的0-1規劃模型，并利用網絡流算法求解模型。文獻[7]以在站停留時間和前方站分解時間最小為目標，構建確定環境下重載組合站的列車組合方案規劃模型，并設計表格法求解。然而在車站系統內存在諸多不確定因素，如列車到發時刻、車流信息以及各種作業時間等，為提高計劃的可靠性，有必要研究不確定條件下的計劃方案編制。文獻[8]運用隨機規劃方法，研究列車解編時間隨機變動情況下編組站階段計劃的優化編制問題。文獻[9]將編組站解編作業時間作為模糊變量，在給定置信水平下用變量的悲觀值表示不確定環境下的解編作業時間。

綜上，目前針對重載組合站的階段計劃優化研究較少且存在不足之處。由于組合方式的多樣化以及車站系統的不確定因素，重載列車的組合作業時間有所差異且存在不確定性，這時需要對不確定條件下的車流接續約束作具體討論，既有研究中僅考慮編組站階段計劃編制這一方面；另外，到發線數量約束以及重載列車的發車間隔調整等重載組合站應特殊討論的問題在既有研究中均未涉及。

在上述研究的基礎上，本文結合重載組合站組合作業特點引入組合模式變量，以組合列車在站停留時間和前方站分解作業時間最少為優化目標，在考慮組合規則、到發線數量、發車時間間隔調整以及不確定性條件下的車流接續等約束的基礎上，構建相應的隨機機會約束規劃模型，并借鑒行生成方法的優化思想，優先分解復雜的到發線數量約束，以解決到發線數量約束導致模型求解困難的問題，從而提高模型求解效率。

1 重載組合站組合作業特點分析

重載鐵路裝車端組合站以列為單位辦理重載列車組合作業和回送空車的分解作業，與既有線編組站“到、解、集、編、發”的作業流程存在較大差異。在重車方向，由于裝車點裝車能力限制和銜接集疏線路牽引質量標準差異，到達組合站的列車多為牽引質量相對較小的單元列車，如萬噸單元列車；同時也有少量到達的其他列車，如0.5萬t列車和2萬t組合列車。

由于銜接線路眾多，到達組合站的重載列車數量較多且去向多樣，而組合站發車能力及重載線路通過能力有限，無法單獨將所有列車發出。為充分挖掘重載線路潛力，提高重載運輸能力，一般將小編組列車組合成大編組組合列車發出，而大編組列車則無需進行組合作業，在到發線上完成必要的技術作業后，直接選擇適當列車運行線上線運行。

通過分析重載組合站組合作業特點，列舉各種組合模式及其特點，見表1。其中m為組合模式；am、bm、cm為組合模式m下0.5、1.0、2.0萬t重載小列數量。

表1 組合模式表

表1中組合模式1、4、7為組合站常見的組合作業形式；組合模式3、5、6由于組合作業復雜，組合時間過長，在實際生產作業中已不再采用；組合模式2、8實際上并沒有進行組合作業，而是萬噸以上重載列車到達車站后進行必要的技檢作業后直接上線發車；組合模式9則為抽象意義上的組合模式，表示列車編入本階段站存車，因此重載小列數及組合大列質量均不確定。

不同于編組站在編組場進行編組作業，重載組合站的列車組合作業直接在到發線上進行，且一般不進行轉線作業。重載組合站到發線也相對特殊，到發線有效長較長，兩條到發線間夾一條機走線構成“三線一束”的形式，且到發線與機走線間設有腰岔。

對于列車占用到發線的起訖時間，需結合組合方案及各列車實際到發時間確定，如某出發列車占用到發線的時間段為編入該出發列車的單元小列中最早到站時刻起至該出發列車實際出發時刻止。在描述到發線數量對組合方案的影響時，本文以出發列車為研究對象，討論其占用到發線的時間沖突，同時為簡化列車之間占用到發線起訖時刻不同而產生的約束，引入時間片[10]的概念。

時間片定義：將本階段的時間劃分為幾段, 每段時間被多列車占用, 且這幾列車在占用到發線的時間上存在著交叉干擾, 不能使用同一條到發線，則每段時間就稱為一個時間片。時間片的劃分算法在文獻[10]中有詳細解釋，本文不再贅述。

2 模型構建

2.1 問題描述及模型假設

給定組合站到達單元重載列車的數量、編組內容、到達時刻信息，和出發組合列車的數量、出發時刻信息，以及組合站到發線類型及數量、各項技術作業時間標準等，重載組合站重載列車組合方案優化問題旨在合理分配到達單元列車，確定各重載列車單元的組合方案，同時保證所有重載列車在站停留時間及在前方站分解時間最少，加速機車車輛周轉。

本文基于如下假設：①組合站重車到達方向接車能力滿足要求；②機車設備供應充足，機車出入段不受影響；③列檢組能力充足。

2.2 符號與變量

2.3 約束條件

?i∈Dj∈F1m∈M1

(1)

式中：α為置信水平。

(2)組合規則約束。除站存車外，對于出發列車j，選擇不同的組合模式時，其所需的各類型重載小列數量需滿足表1中的關系，即

(2)

(3)

(4)

式中：am，bm和cm取值見表1。

(3)列車歸屬唯一約束。對于到達列車i，只能編入一列出發列車。

(5)

(4)組合模式唯一約束。對于出發列車j，只能選擇一種組合模式，且站存車f+1 只能選擇組合模式9。

(6)

(5)站存車組合約束。本文討論的在站組合作業均為本線組合，即列車到達組合站后無需轉線作業，因此上階段末的站存車之間無法組合編入同一出發列車。

pii′j=0 ?i,i′∈D0i≠i′ ?j∈F1

(7)

(8)

(9)

(10)

(11)

(12)

(8)到發線數量約束。在本階段任意時刻，重載列車占用各類型到發線的數量，不大于組合站可提供作業的各類型到發線數量。而通過引用前面時間片的概念，可將任意時刻描述為任一時間片內，從而簡化該約束。

(13)

(14)

(15)

(16)

式(14)～式(16)表示在第k個時間片內3種類型組合列車占用到發線數量不得超過可提供的相應類型到發線數量。

(9)邏輯約束。根據上述決策變量的定義，決策變量之間需滿足一系列的邏輯約束。

(17)

pii′j=xijxi′j?i∈D?j,j′∈F1

(18)

?i∈Dj∈F1m∈M1

(19)

2.4 目標函數

為加快重載機車車輛周轉，降低運營成本，提高運輸質量，在滿足上述約束條件下，模型的優化目標為：

一是重載列車在組合站總停留時間最小，考慮到不同重載列車車輛數差異，引入車輛權重更好地闡述列車在站停留時間。

(20)

式中：wi為到達列車i的車輛數權重，1萬t、1.5萬t、2萬t重載列車的車輛數權重分別為1.0、1.5及2.0。

二是去向不同的單元小列組合而成的重載組合列車在前方卸車端分解站的分解作業時間最小。

(21)

式中：aii′為0-1變量，若單元小列i與i′的去向不同，則aii′=1；否則為0；t分解為重載組合列車在前方分解站的分解作業時間，min。

2.5 隨機機會約束和非線性約束處理

(1)隨機機會約束轉換為確定性約束

本文將隨機機會約束轉換為其相應等價的確定性約束[11]。

定理：令ξ為隨機變量，其分布函數為Φ，若g(x)可表示為g(x,ξ)=h(x)-ξ，則Pr[g(x,ξ)≥0]≥α，當且僅當h(x)≥Kα，其中Kα=inf[K|K=Φ-1(α)]。

證明：由條件可知，Pr[g(x,ξ)≥0]≥α可表示為Pr[h(x)≥ξ]≥α；同時對于任意的α必然存在Kα使得Pr(Kα≥ξ)=α,即Φ(Kα)=α。則當且僅當h(x)≥Kα時，Pr[h(x)≥ξ]≥α可轉換為Pr(Kα≥ξ)=α，此時Kα=inf[K|K=Φ-1(α)]。

?i∈Dj∈F1m∈M1

(22)

(2)線性化轉換

式(17)和式(18)為非線性約束，可將其轉換為等價線性約束

?i∈Dj∈Fm∈M1

(23)

pii′j≤xijpii′j≤xi′jpii′j≥xij+xi′j-1

?i,i′∈D?j∈F1

(24)

(25)

(26)

Tij≥-M·xij?i∈Dj∈F1

(27)

綜合考慮，總目標函數為：

(28)

由此得到重載組合站組合方案優化模型Md1,包括目標函數式(28)，約束式(2)～式(16)、式(19)、式(22)～式(24)和式(26)～式(27)。

3 基于行生成的模型分解算法

從模型性質分析，模型Md1為非線性混合整數規劃模型，其中到發線數量約束涉及到時間維度上的占用沖突，為模型中的復雜約束，嚴重限制求解效率及精準度。

借鑒行生成[12]的思想，先松弛到發線數量約束式，得到子問題Md2，此時子問題松弛為線性混合整數規劃模型，可調用商業求解器GUROBI求解，求解子問題并判斷該解是否滿足到發線數量約束，若不滿足，則添加相應約束，從而減少原問題約束的數量與復雜度，最終求得較優解。基于前面分析，算法流程如下：

Step1S為模型Md1中到發線數量約束，C為其他所有約束，暫不考慮模型中到發線數量約束，令S=?，得到子問題Md2(C,S)。

Step2調用求解器求解子問題Md2(C,S)，如果不可行，則原問題不可行，終止算法；否則輸出組合方案和列車到發時刻，轉下一步。

Step3根據組合方案和列車到發時刻，求得每列出發列車占用到發線時間段，并結合時間片劃分算法[11]，將本階段劃分為多個時間片，轉下一步。

Step4依次檢查各個時間片內列車數量是否滿足約束式(14)～式(16)，其中各時間片內下階段站存車按重量類型分配至1.5萬t或2萬t到發線。一旦存在某個時間片不滿足，則將該時間片對應約束添加至S，轉Step2。

Step5若不存在到發線占用沖突，則輸出結果，終止算法。

4 算例分析

(1)參數說明及原始數據

以湖東站某階段計劃編制為例，除站存車外，重載列車到達技術作業時間和出發技術作業時間均為30 min，組合列車在前方站分解作業時間為45 min，重載車輛在站最大停留時間為240 min，本階段編制結束時刻為07:00，重載列車包括A、B、C、D和E 5個去向，1.0、1.5、2.0萬t重載列車到發線數量分別為3、6、8條。

假定重載組合站不同組合模式下的組合作業時間服從正態分布，見表2，取置信水平α為0.90。

表2 不同組合模式下組合時間

到達列車車流數據見表3，編號1和2的到達列車為上階段末的站存車，其到達時刻取本階段編制開始時刻；出發列車圖定出發時刻見表4，編號18的出發列車為本階段末的站存車，其出發時刻取本階段編制結束時刻。

表3 到達列車車流數據

表4 出發列車圖定出發時刻

(2)優化求解

在Core 2.30 GHz & RAM 8 GB & Windows 10個人計算機上，采用Matlab2016b編程計算，調用GUROBI求解器對模型進行求解，得到子問題Md2初次優化的組合方案，根據組合方案確定各列車占用到發線起訖時間，由此得到時間片劃分結果見表5。

表5 子問題初次優化時間片劃分結果

由表5可知，時間片A1(與A2)明顯不滿足到發線數量約束，需要添加時間片A1(與A2)所對應的到發線數量約束到子問題Md2中，之后繼續迭代求解，直至得到滿足到發線數量約束的最終優化解，總求解耗時在10 min以內，迭代優化過程見表6。

最終優化組合方案見表7，編號18的出發列車為本階段站存車，包括1列0.5萬t和1列1萬t重載小列，本階段重載列車在站停留時間為5 457.5 min，在前方卸車站需要進行2次分解作業，總時間消耗為5 547.5 min。

根據各列車占用到發線起訖時間，時間片劃分結果見表8，此時各時間片內列車均滿足到發線數量約束。

表6 迭代優化過程對比

表7 重載組合站最終優化組合方案

表8 最終優化方案時間片劃分結果

(3)結果分析

分析上述結果可知，在迭代過程中列車總時間消耗與站存車數量逐步增加，最終優化組合方案與子問題初次優化結果對比，重載列車總時間消耗增加72 min，站存車增加1列0.5萬t重載小列。

究其原因，在不考慮到發線數量約束的情況下，為實現在站停留時間最小的目標，重載列車盡可能以2萬t的大載重組合方式組合發車，但由于組合站2萬t到發線數量的限制，因此必須對組合方案進行調整。而迭代優化過程實際即為調整部分組合列車的組合順序，通過犧牲部分重載列車在站停留時間，或者減少本階段出發車輛數，盡可能地減少本階段2萬t組合列車數量，以滿足到發線數量約束。

現場工作基于組合站“先到先組，先到先發”的原則盡管能確定可行的組合方案，但組合列車需在前方站進行10次分解作業，總時間消耗增加到5 999 min；同時未能考慮到發線數量的限制，導致列車組合方案不夠均衡，致使部分重載列車被迫晚點到站。相比于現場“先到先組，先到先發”的作業原則，優化組合方案使得重載列車總時間消耗降低7.5%，且組合方案更加均衡，能更好地適應重載運輸需求。

5 結束語

基于隨機規劃理論，考慮車流接續、發車時間間隔調整和到發線數量等約束，構建包含隨機機會約束的重載組合站組合方案優化模型，并借鑒行生成算法的思路求解模型，為重載組合站組合方案編制提供指導意義。

本文利用基于行生成的模型分解方法處理到發線數量約束時，在合理的限制時間內，可獲得接近于最優解的滿意解，在組合站復雜多變的作業環境下，滿意解也能夠滿足作業要求。同時，未考慮本階段組合方案對后續階段計劃的影響，以及車流不準確等隨機因素，因而得到的組合方案可靠性仍有待提升，而在實際生產作業中，為提高方案可靠性，可動態地更新車流信息以進行組合方案實時調整更新。此外，針對到發線數量約束的其他處理方式以及列車到達時間和車流信息的不確定性，后續筆者將作進一步的研究。