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

董世鑫，魏玉光，張進川

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

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

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

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

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

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

1 重載組合站組合作業(yè)特點分析

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

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

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

表1 組合模式表

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

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

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

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

2 模型構(gòu)建

2.1 問題描述及模型假設(shè)

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

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

2.2 符號與變量

2.3 約束條件

?i∈Dj∈F1m∈M1

(1)

式中：α為置信水平。

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

(2)

(3)

(4)

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

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

(5)

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

(6)

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

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

(7)

(8)

(9)

(10)

(11)

(12)

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

(13)

(14)

(15)

(16)

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

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

(17)

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

(18)

?i∈Dj∈F1m∈M1

(19)

2.4 目標函數(shù)

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

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

(20)

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

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

(21)

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

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

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

本文將隨機機會約束轉(zhuǎn)換為其相應(yīng)等價的確定性約束[11]。

定理：令ξ為隨機變量，其分布函數(shù)為Φ，若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)≥ξ]≥α可轉(zhuǎn)換為Pr(Kα≥ξ)=α，此時Kα=inf[K|K=Φ-1(α)]。

?i∈Dj∈F1m∈M1

(22)

(2)線性化轉(zhuǎn)換

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

?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)

綜合考慮，總目標函數(shù)為：

(28)

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

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

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

借鑒行生成[12]的思想，先松弛到發(fā)線數(shù)量約束式，得到子問題Md2，此時子問題松弛為線性混合整數(shù)規(guī)劃模型，可調(diào)用商業(yè)求解器GUROBI求解，求解子問題并判斷該解是否滿足到發(fā)線數(shù)量約束，若不滿足，則添加相應(yīng)約束，從而減少原問題約束的數(shù)量與復雜度，最終求得較優(yōu)解?；谇懊娣治?，算法流程如下：

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

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

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

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

Step5若不存在到發(fā)線占用沖突，則輸出結(jié)果，終止算法。

4 算例分析

(1)參數(shù)說明及原始數(shù)據(jù)

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

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

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

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

表3 到達列車車流數(shù)據(jù)

表4 出發(fā)列車圖定出發(fā)時刻

(2)優(yōu)化求解

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

表5 子問題初次優(yōu)化時間片劃分結(jié)果

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

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

根據(jù)各列車占用到發(fā)線起訖時間，時間片劃分結(jié)果見表8，此時各時間片內(nèi)列車均滿足到發(fā)線數(shù)量約束。

表6 迭代優(yōu)化過程對比

表7 重載組合站最終優(yōu)化組合方案

表8 最終優(yōu)化方案時間片劃分結(jié)果

(3)結(jié)果分析

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

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

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

5 結(jié)束語

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

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