李 濤，韓建鵬

LI Tao, HAN Jianpeng

（蘭州交通大學(xué) 交通運(yùn)輸學(xué)院，甘肅 蘭州 730070）

0 引言

為了更好地完成運(yùn)輸任務(wù)，客運(yùn)站必須嚴(yán)格按照本站的作業(yè)計(jì)劃進(jìn)行作業(yè)，而階段計(jì)劃是車站作業(yè)計(jì)劃的核心，是對班計(jì)劃的分階段部署，也是編制調(diào)車作業(yè)計(jì)劃的主要依據(jù)[1]。到發(fā)線的合理運(yùn)用是客運(yùn)站行車作業(yè)的一項(xiàng)重要內(nèi)容，是車站編制階段計(jì)劃的關(guān)鍵工作之一。因此，建立鐵路客運(yùn)站到發(fā)線運(yùn)用優(yōu)化模型并且設(shè)計(jì)相應(yīng)的算法進(jìn)行求解，對客運(yùn)站編制到發(fā)線運(yùn)用計(jì)劃有非常重要的 意義。

為了高效、合理地運(yùn)用到發(fā)線，保證接發(fā)車作業(yè)的安全，許多學(xué)者對到發(fā)線的運(yùn)用優(yōu)化進(jìn)行了研究。呂紅霞等[2]根據(jù)客運(yùn)站作業(yè)的特點(diǎn)建立了客運(yùn)站到發(fā)線運(yùn)用的0-1 規(guī)劃模型，基于最小最大螞蟻的思想，設(shè)計(jì)蟻群算法對問題求解。高建[3]結(jié)合旅客列車在客運(yùn)站的作業(yè)特點(diǎn)，以出發(fā)旅客列車正點(diǎn)為目標(biāo)，同時考慮到發(fā)線的固定使用方案及高等級列車優(yōu)先，建立了客運(yùn)站到發(fā)線運(yùn)用的混合0-1 整數(shù)規(guī)劃模型，運(yùn)用模擬退火算法進(jìn)行求解。何林等[4]以均衡、合理運(yùn)用到發(fā)線為原則，建立了高速鐵路客運(yùn)站到發(fā)線運(yùn)用的0-1 規(guī)劃模型，采用遺傳算法求解。謝楚農(nóng)等[5]通過分析客運(yùn)站旅客列車到發(fā)技術(shù)作業(yè)，把研究問題分為方便旅客乘降、保證行車作業(yè)安全、有效使用車站既有設(shè)備3 個子目標(biāo)，建立到發(fā)線運(yùn)用優(yōu)化模型，采用分枝定界算法對模型進(jìn)行求解。林志安等[6]以行車交叉干擾最小、方便旅客乘降、均衡使用到發(fā)線為優(yōu)化目標(biāo)，建立到發(fā)線運(yùn)用優(yōu)化的整數(shù)規(guī)劃模型，設(shè)計(jì)了基于捕食策略的禁忌搜索算法對問題進(jìn)行求解。吳鵬等[7]以到發(fā)線的固定使用、均衡使用到發(fā)線、旅客走行距離最短為優(yōu)化目標(biāo)，建立多目標(biāo)0-1 規(guī)劃模型，利用功效系數(shù)法將多目標(biāo)同一量綱轉(zhuǎn)化為單目標(biāo)函數(shù)，利用LINGO 軟件進(jìn)行求解。青學(xué)江等[8]建立了區(qū)段站到發(fā)線運(yùn)用優(yōu)化模型，采用遺傳算法進(jìn)行求解。雖然模型考慮了多個方面，但是算法運(yùn)行時間為25min，不能滿足算法實(shí)時性的要求。張英貴等[9]引入時間窗、權(quán)重、有限度3 個參數(shù)和柔性理論，建立車站到發(fā)線運(yùn)用的柔性模型，求解采用解改進(jìn)策略和人—機(jī)交互式算法。Kroon 等[10]在已知車站布局和列車到發(fā)時間的前提下，從安全角度出發(fā)，將問題看成是節(jié)點(diǎn)裝箱問題，建立整數(shù)規(guī)劃模型，運(yùn)用特定的預(yù)處理規(guī)劃減小可行性問題的實(shí)例大小，采用動態(tài)規(guī)劃的方法進(jìn)行求解。目前，上述研究大部分是針對技術(shù)站到發(fā)線的運(yùn)用研究，而對客運(yùn)站到發(fā)線運(yùn)用的研究相對較少，考慮在呂紅霞等[2]、高建[3]、何林等[4]研究到發(fā)線固定使用方案的基礎(chǔ)上兼顧到發(fā)線的均衡使用，同時引入懲罰因子并改進(jìn)適應(yīng)度函數(shù)來提高運(yùn)行效率、加快模型收斂的速度。為了更好地實(shí)現(xiàn)車站作業(yè)智能化和算法的實(shí)時性，在謝楚農(nóng)等[5]、吳鵬等[7]、青學(xué)江等[8]研究的基礎(chǔ)上采用模擬退火遺傳算法對問題進(jìn)行求解。

1鐵路客運(yùn)站到發(fā)線運(yùn)用優(yōu)化模型構(gòu)建

1.1 問題描述

隨著列車運(yùn)行速度和列車等級的提高，列車運(yùn)行圖不斷調(diào)整，列車開行密度增加，并且在車站的技術(shù)作業(yè)時間減少，為了按時按點(diǎn)的接發(fā)旅客列車，必須編制良好的作業(yè)計(jì)劃，而到發(fā)線的運(yùn)用又是客運(yùn)站行車作業(yè)的一項(xiàng)重要內(nèi)容。到發(fā)線的運(yùn)用優(yōu)化問題是一個具有時間和空間二維特性的組合優(yōu)化問題[11]，其合理運(yùn)用不僅關(guān)系車站的正常運(yùn)輸生產(chǎn)和運(yùn)行圖的實(shí)現(xiàn)，還關(guān)系到鐵路行車安全和列車運(yùn)行的經(jīng)濟(jì)效益。對一個客運(yùn)站來說，到發(fā)線運(yùn)用計(jì)劃是規(guī)定車站在某一階段內(nèi)到發(fā)場線路的具體使用計(jì)劃，為了方便車站值班員接發(fā)列車，到發(fā)線一般固定使用。到發(fā)線的運(yùn)用要保證客運(yùn)站可以不間斷地接發(fā)列車，最大限度地利用車站每一條線路的能力，同時也得留有一定的余地，避免高峰時段由于一列列車晚點(diǎn)而不能為其后列車安排進(jìn)路，使其后列車在進(jìn)站信號機(jī)外停車等線。如果某一時段列車到達(dá)強(qiáng)度超過車站的接發(fā)車能力或出現(xiàn)早晚點(diǎn)情況，這時將不能再按固定方案使用到發(fā)線，應(yīng)該按到發(fā)線的備用方案接發(fā)列車，將等級相對較高的列車和早點(diǎn)的列車接入滿足時間安全間隔的線路。盡量按照《車站行車工作細(xì)則》規(guī)定的固定方案接發(fā)列車，減少行調(diào)作業(yè)交叉。所有占用到發(fā)線的列車都應(yīng)遵循以下條件。

（1）同一時間內(nèi)一條到發(fā)線只可以接或發(fā)一列列車或不接列車。

（2）一條到發(fā)線一旦被某一列列車占用，直到出發(fā)，該列車中途不得轉(zhuǎn)到另一條到發(fā)線上。

（3）先后占用同一條到發(fā)線的2 列列車，必須滿足接發(fā)列車的最小安全時間間隔要求。

1.2 模型構(gòu)建

設(shè)某客運(yùn)站到發(fā)線的集合為D= {1，2，…，j，…，m}，其中j為第j條到發(fā)線的編號，m為到發(fā)線的總數(shù)；計(jì)劃階段到達(dá)客運(yùn)站的列車集合L= {1，2，…，i，…，n}，其中i為第i列列車到達(dá)車站的順序，n為列車總數(shù)。目標(biāo)函數(shù)從縮短旅客列車在到發(fā)線的停留時間和均衡使用到發(fā)線2 個方面考慮(用每條到發(fā)線占用時間總和與各到發(fā)線平均占用時間之差的方差來衡量)。

式中：xij為0-1 變量，xij= 1 表示列車i占用到發(fā)線j，否則xij= 0；tki為列車i開始占用到發(fā)線的時間；tei為列車i完全離開到發(fā)線的時間；為第i列列車占用到發(fā)線的總時間為信號員或值班員為第i列列車排列進(jìn)路以及列車完全?？吭诘桨l(fā)線上所耗費(fèi)的時間[5]；為列車從完全?？吭诘桨l(fā)線起至出發(fā)時刻止，列車在到發(fā)線上所耗費(fèi)的時間；為列車從出發(fā)時刻起至該列車完全離開該徑路止所耗費(fèi)的時間[5]。根據(jù)車站作業(yè)標(biāo)準(zhǔn)，和均取2min，由列車的到達(dá)時刻和出發(fā)時刻確定)；cij為列車i占用到發(fā)線j的權(quán)值大小，其權(quán)值的確定與呂紅霞[11]確定方法類似。

模型的約束條件如下。

（1）同一時間內(nèi)一條到發(fā)線只可以接或發(fā)一列列車或不接發(fā)列車。

（2）一條到發(fā)線一旦被某一列列車占用，直到出發(fā)，該列車中途不得轉(zhuǎn)到其他到發(fā)線上。

（3）同一條到發(fā)線上接發(fā)相鄰列車時須滿足最小安全時間間隔的要求[11]，最小安全時間間隔如圖1 所示。

圖1 最小安全時間間隔Fig.1 Minimum safe interval

具體約束如下。

式中：T為前后兩列列車占用同一條到發(fā)線時，后續(xù)列車i+ 1 接車時刻與前車i完全離開該股道的最小安全時間間隔，文中T值取10 min。

（4）交叉的疏解[12]。在同一個時間片[2]內(nèi)，接發(fā)列車的進(jìn)路不能有沖突(如列車的接發(fā)與機(jī)車出入段的交叉)，應(yīng)多組織平行作業(yè)來減少交叉干擾，具體約束如下。

式中：當(dāng)列車i占用到發(fā)線j時與作業(yè)p產(chǎn)生交叉干擾時hijp= 1，否則取hijp= 0。

（5）如果存在換乘的列車，應(yīng)盡可能將其安排在相鄰的站臺上[13]，具體約束如下。

式中：為0-1 變量，= 1 表示到發(fā)線j與到發(fā)線j′相鄰，共用一個站臺，反之則在不同站臺[13]；為0-1 變量，= 1 表示列車i與列車i′存在換乘關(guān)系，反之則不存在[13]。

（6）行包作業(yè)量大的列車應(yīng)接入靠近有行包通道的站臺。

式中：Hi,B= 1 為列車有行包、郵政作業(yè)，反之Hi,B= 0；Sj,B= 1 為到發(fā)線靠近行包、郵政通道，反之，Sj,B= 0；M取值為10。

2案例求解算法

在實(shí)際生產(chǎn)中，出于對車站生產(chǎn)指揮的需要，因而對算法的實(shí)時性要求較高。而到發(fā)線的運(yùn)用優(yōu)化已被證明屬于NP 完全問題[14]，對該類問題的求解目前還沒有確認(rèn)的多項(xiàng)式時間算法，因而增加了求解的難度，故此類問題多采用啟發(fā)式算法求解。雖然遺傳算法擁有強(qiáng)大的全局最優(yōu)解搜索能力，但局部搜索能力差，容易造成早熟，不能保證算法快速收斂；模擬退火算法具有較強(qiáng)的魯棒性，其以一種概率的方式進(jìn)行搜索，局部搜索能力強(qiáng)，但把握搜索過程的能力不強(qiáng)，過程中還會遺失最優(yōu)解，從而使模擬退火算法的能力不高，因而采用模擬退火遺傳算法來提高運(yùn)行效率和求解質(zhì)量。

2.1 模擬退火遺傳算法的關(guān)鍵步驟

（1）染色體編碼。染色體的長度由車站到發(fā)線的數(shù)量確定，對車站在編制計(jì)劃階段到達(dá)的旅客列車按時間先后進(jìn)行排序，用空格表示列車，空格對應(yīng)的下標(biāo)為相應(yīng)列車的編號，空格中的數(shù)字表示所占股道。

（2）適應(yīng)度函數(shù)的選取。適應(yīng)度函數(shù)求取的是極大值，并且適應(yīng)度函數(shù)要非負(fù)。根據(jù)實(shí)際問題來考慮目標(biāo)函數(shù)的取值，并且在目標(biāo)函數(shù)中加入懲罰系數(shù)，然后把處理后的目標(biāo)函數(shù)作為該算法的適應(yīng)度函數(shù)，使求解過程中2 列及以上列車在一個時間片內(nèi)占用同一到發(fā)線的個體以較小的機(jī)會生存 下來。

式中：fm(x)是當(dāng)前輸入空間的個體最大值；E[f(x)]是目標(biāo)函數(shù)的均值；這里用fm(x)和E[f(x)]之差的歐式范數(shù)再加上E[f(x)]作為Cmax的取值；C為懲罰系數(shù)，當(dāng)有2 列及以上列車在一個時間片內(nèi)占用同一到發(fā)線時，C= 1，否則C= 1 / 1 000。

（3）初始溫度的選取 。生成初始種群pop(0)后，設(shè)該種群中最大的目標(biāo)函數(shù)值為fmax，最小目標(biāo)函數(shù)值為fmin。初始溫度t0由t0= -Δf/ lnnc確定，其中-Δf=fmax－fmin，nc為初始接受概率，0 ＜nc＜ 1，如nc= 0.8，nc= 0.9 等。

（4）溫度下降方法 。用tk+1=λtk來控制整個算法的終止，其中tk是前一狀態(tài)的溫度。模擬退火遺傳算法的最終溫度為1 且最大迭代次數(shù)超過給定的次數(shù)U。給定一個比較小的ε和U，當(dāng)溫度tk≤ε且l＞U時，算法終止。

2.2 算法流程

步驟1：給定種群大小popsize，k= 0；初始溫度tk=t0，隨機(jī)產(chǎn)生群體pop(k)并檢驗(yàn)解的可行性；求各解的適應(yīng)度F(s)，并找出最優(yōu)適應(yīng)度F(s*)，最優(yōu)解s*=s。

步驟2：進(jìn)行選擇、交叉、變異操作，并檢查解的可行性。

步驟3：計(jì)算最優(yōu)適應(yīng)度F(s*)與新解所對應(yīng)適應(yīng)度的差ΔF，然后根Metropolic 準(zhǔn)則判斷是否接受新解，如果ΔF≥0，則接受s作為新的解；如果ΔF≤0，以概率接受s作為新的解。判斷l(xiāng)≤U是否滿足，如果滿足，轉(zhuǎn)步驟2；如果不滿足，轉(zhuǎn)步驟4。

步驟4：tk＜ε是否滿足，如果滿足，轉(zhuǎn)步驟6；如果不滿足，轉(zhuǎn)步驟5。

步驟5：tk+1=λtk，k=k+ 1，轉(zhuǎn)步驟2。

步驟6：輸出最優(yōu)結(jié)果。

2.3 算例求解

為了驗(yàn)證文中提出的算法和建立模型的準(zhǔn)確性，算例選取客運(yùn)站8 : 00—12 : 00 的數(shù)據(jù)進(jìn)行驗(yàn)證。選取階段中到發(fā)的列車共46 列，該站共2 條正線，5 條到發(fā)線，其中 3，5，7 號到發(fā)線固定接發(fā)下行列車；4，6 號到發(fā)線固定接發(fā)上行列車；正線I、II 分別用于下、上行列車的不停站通過。文中i，j，n，m，p等變量的取值均為正整數(shù)。參數(shù)取值：種群規(guī)模popsize= 30；交叉概率pc= 0.75；變異概率pm= 0.01；最大迭代次數(shù)U= 500；初始溫度t0= 100，當(dāng)溫度低于10 時，采用等步長下 降[15]，步 長 取1；nc= 0.8，λ= 0.9，ε= 3×10-6。運(yùn)用MatlabR 2018a 進(jìn)行求解，最后目標(biāo)函數(shù)值穩(wěn)定為31 018 min，通過整理迭代所得數(shù)據(jù)，得到到發(fā)線運(yùn)用計(jì)劃，到發(fā)線運(yùn)用方案如表1 所示。

從算例結(jié)果可以看出，文中所設(shè)計(jì)的模型和算法可以滿足列車在車站的作業(yè)需要，使上行列車分布在4，6 股道，下行列車分布在3，5，7 股道；而車站值班員的方案中將一列上行始發(fā)的列車接入了3 道，沒實(shí)現(xiàn)分方向接發(fā)列車。根據(jù)上文對均衡性評價(jià)的定義，均衡度為然后分別計(jì)算車站值班員的方案和優(yōu)化所得方案的均衡度，均衡度統(tǒng)計(jì)如表2 所示。

表1 到發(fā)線運(yùn)用方案Tab.1 Operation plan for arrival and departure tracks

表2 均衡度統(tǒng)計(jì)Tab.2 Balance degree statistics

3研究結(jié)論

通過對鐵路客運(yùn)站到發(fā)線運(yùn)用優(yōu)化進(jìn)行研究，較全面地考慮了到發(fā)線分配的影響因素，建立了到發(fā)線運(yùn)用優(yōu)化模型，并根據(jù)模型特點(diǎn)設(shè)計(jì)模擬退火遺傳算法進(jìn)行求解，最后通過算例對模型和算法進(jìn)行驗(yàn)證，得到以下研究結(jié)論。

（1）考慮到發(fā)線固定使用方案的同時，兼顧到發(fā)線運(yùn)用的均衡性，所得方案不僅可以保證行車安全，而且可以使列車均衡的占用到發(fā)線，從而提高車站設(shè)備的利用效率。

（2）綜合考慮模擬退火算法和遺傳算法的優(yōu)點(diǎn)和不足，設(shè)計(jì)模擬退火遺傳算法對問題進(jìn)行求解，并且在適應(yīng)度函數(shù)中加入懲罰因子，有效地求解了模型。算例表明，該算法在解決到發(fā)線運(yùn)用優(yōu)化問題上是可行的，收斂速度較快，能夠滿足車站編制計(jì)劃實(shí)時性的要求，這對車站作業(yè)智能化具有一定意義。

（3）按圖定到發(fā)時刻對到發(fā)線運(yùn)用優(yōu)化進(jìn)行研究，由于各種不確定因素使得列車到發(fā)時刻與圖定時刻有所差異，因而在后續(xù)研究中可對列車到發(fā)時刻不確定的情況進(jìn)行研究。