黃俊生，廣曉平

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

0 引言

編組站是我國(guó)鐵路的運(yùn)輸樞紐，主要進(jìn)行列車(chē)解體和編組等技術(shù)作業(yè)；同時(shí)作為列車(chē)“加工車(chē)間”，其運(yùn)轉(zhuǎn)效率直接影響鐵路列車(chē)周轉(zhuǎn)效率。無(wú)論是客運(yùn)站還是技術(shù)站，到發(fā)線的高效運(yùn)用都是行車(chē)作業(yè)的核心環(huán)節(jié)[1]。到發(fā)線的運(yùn)用負(fù)荷，是反映車(chē)站到達(dá)場(chǎng)對(duì)運(yùn)行圖適應(yīng)能力的重要指標(biāo)之一[2]，同時(shí)到發(fā)線分配是否可行也是反映鐵路日常工作效率的指標(biāo)之一。由于到發(fā)線的運(yùn)用受不確定因素影響較多，如列車(chē)到發(fā)不確定[3]、技術(shù)作業(yè)時(shí)間不確定、車(chē)輛等級(jí)和種類(lèi)繁多[4]等，因而到發(fā)線的運(yùn)用研究更為復(fù)雜，構(gòu)建的目標(biāo)模型也具有多種形式。龍建成等[5]構(gòu)建以作業(yè)晚點(diǎn)時(shí)間最短、各進(jìn)路總走行時(shí)間最短的多目標(biāo)規(guī)劃模型；張英貴等[6]采用排序理論方法，構(gòu)建車(chē)站股道運(yùn)用的排序模型；劉偉等[3]根據(jù)列車(chē)到發(fā)不確定性，構(gòu)建車(chē)站咽喉利用和股道分配優(yōu)化模型。

由于該類(lèi)問(wèn)題多為NP問(wèn)題，因而大大增加了求解難度，此類(lèi)問(wèn)題的求解多采用啟發(fā)式進(jìn)化算法。郭莉等[7]運(yùn)用遺傳算法對(duì)到發(fā)線運(yùn)用進(jìn)行優(yōu)化；康柳江[8]運(yùn)用模擬退火算法計(jì)算福州站進(jìn)出站咽喉時(shí)間、股道占用分配等問(wèn)題。編組站到發(fā)線的運(yùn)用可看作特殊的柔性車(chē)間調(diào)度問(wèn)題[9]，列車(chē)加工順序?qū)?duì)股道運(yùn)用產(chǎn)生重要影響。

目前，同時(shí)考慮列車(chē)到達(dá)時(shí)刻不確定、到達(dá)場(chǎng)技術(shù)作業(yè)時(shí)間彈性、終到列車(chē)選擇股道多樣性及帶重疊時(shí)間窗4種隨機(jī)因素的研究較少。為進(jìn)一步提高編組站到發(fā)線的運(yùn)用效率，構(gòu)建帶柔性重疊時(shí)間窗約束、以股道最大占用時(shí)間最小化為目標(biāo)的非線性規(guī)劃模型，由于此類(lèi)問(wèn)題已被證明為NP-hard問(wèn)題[10]，為在有限時(shí)間資源內(nèi)搜尋到模型的滿意解，設(shè)計(jì)模擬退火算法對(duì)該模型進(jìn)行求解計(jì)算。

1 柔性和重疊時(shí)間窗

股道分配運(yùn)用問(wèn)題可以看作是傳統(tǒng)車(chē)間調(diào)度問(wèn)題的衍生，由于編組站到發(fā)線使用更靈活，因而股道分配運(yùn)用問(wèn)題有別于傳統(tǒng)車(chē)間調(diào)度問(wèn)題。終到列車(chē)股道分配問(wèn)題建立在柔性和列車(chē)到達(dá)有重疊時(shí)間窗的基礎(chǔ)上，考慮的柔性可以理解為完全柔性，有別于部分柔性和傳統(tǒng)問(wèn)題。完全柔性體現(xiàn)在列車(chē)到達(dá)時(shí)刻不確定，技術(shù)作業(yè)時(shí)間有彈性及終到列車(chē)選擇股道多樣性3個(gè)方面。因此，考慮完全柔性的股道分配更貼近編組站實(shí)際工作安排。完全柔性、部分柔性和傳統(tǒng)問(wèn)題區(qū)別如表1所示。

表1 完全柔性、部分柔性和傳統(tǒng)問(wèn)題區(qū)別Tab.1 Difference among fully flexibility, partial flexibility and traditional problems

在編組站實(shí)際工作中，多列終到列車(chē)到達(dá)時(shí)刻和列車(chē)從股道清空時(shí)刻的時(shí)間窗存在互相重疊的現(xiàn)象。重疊時(shí)間窗是指2 (多)列終到列車(chē)的到達(dá)時(shí)刻和列車(chē)從股道清空時(shí)刻的時(shí)間窗存在重疊，若2(多)列列車(chē)一旦存在“重疊時(shí)間窗”關(guān)系，則2 (多)列列車(chē)在重疊時(shí)間窗內(nèi)不能占用同一股道。重疊時(shí)間窗關(guān)系如圖1所示。

圖1 重疊時(shí)間窗關(guān)系Fig.1 Relationship of overlapped time window

因此，以編組站終到列車(chē)為對(duì)象，以到發(fā)場(chǎng)股道為資源，構(gòu)建以股道最大占用時(shí)間最小化為目標(biāo)、帶柔性重疊時(shí)間窗約束的非線性規(guī)劃模型。

2 帶柔性重疊時(shí)間窗非線性規(guī)劃模型

2.1 變量定義

I為終到列車(chē)集合，任意列車(chē)i∈I，I= {i|i= 1，2，…，n}，n為某階段計(jì)劃內(nèi)編組站接進(jìn)的終到列車(chē)數(shù)量；J為編組站到發(fā)線股道集合，編組站內(nèi)到發(fā)場(chǎng)任意到發(fā)線j∈J，J= {j| 1，2，…，m}，m為編組站到發(fā)線數(shù)量。

為0-1變量，表示列車(chē)i在t時(shí)刻是否占用j股道，如果= 1則表示列車(chē)i在t時(shí)刻占用j股道，否則= 0；為列車(chē)i占用股道j的實(shí)際結(jié)束時(shí)刻；為列車(chē)i占用股道j的實(shí)際開(kāi)始時(shí)刻；為列車(chē)i占用股道j的計(jì)劃開(kāi)始時(shí)刻；pi為列車(chē)i在股道j的技術(shù)作業(yè)時(shí)間；Nj為股道使用均衡系數(shù)；，為偏差系數(shù)，> 1 對(duì)應(yīng)列車(chē)晚到，0 ＜＜ 1 對(duì)應(yīng)列車(chē)早到，> 1 表示技術(shù)作業(yè)時(shí)間延長(zhǎng)，0 ＜＜ 1表示技術(shù)作業(yè)時(shí)間縮短；Tmin為同一股道接近列車(chē)最小安全時(shí)間間隔，設(shè)為14 min；M為一個(gè)無(wú)窮大的數(shù)。

2.2 約束條件

（1）股道占用約束。同一股道在同一時(shí)刻只能由一列車(chē)占用或不占用，計(jì)算公式為

（2）列車(chē)占用股道約束。同一列車(chē)在同一時(shí)刻只能占用同一股道，計(jì)算公式為（3）重疊時(shí)間窗約束。重疊時(shí)間窗內(nèi)連續(xù)2趟列車(chē)不能占用同一股道，計(jì)算公式為

（4）股道占用最小時(shí)間間隔約束。最小安全時(shí)間間隔如圖2所示。前后2列車(chē)占用同一股道，應(yīng)保證后續(xù)列車(chē)i的接車(chē)時(shí)刻與前續(xù)列車(chē)i'從股道清空時(shí)刻之差大于最小安全時(shí)間間隔Tmin，否則= 0，計(jì)算公式為

圖2 最小安全時(shí)間間隔Fig.2 Minimum safety time interval

（5）股道使用均衡性約束。采用占用股道次數(shù)定義股道使用均衡性。為方便描述，將各到發(fā)線的占用次數(shù)與到發(fā)線平均占用次數(shù)之差的平方和定義為股道使用均衡性，Nj為股道使用均衡系數(shù)，計(jì)算公式為

已有研究[3]認(rèn)為股道使用均衡系數(shù)越小，股道使用均衡性越好；股道使用均衡系數(shù)越大，股道使用均衡性越差。

（6）終到列車(chē)實(shí)際到達(dá)與清空股道時(shí)刻。為表示列車(chē)實(shí)際到達(dá)時(shí)刻，引入偏差系數(shù)，該值可用于調(diào)整列車(chē)到達(dá)時(shí)刻，計(jì)算公式為

終到列車(chē)實(shí)際從股道清空時(shí)刻等于終到列車(chē)實(shí)際到達(dá)時(shí)刻加上實(shí)際技術(shù)作業(yè)時(shí)間。為體現(xiàn)彈性技術(shù)作業(yè)時(shí)間，引入偏差系數(shù)，用于調(diào)整技術(shù)作業(yè)時(shí)間。

（7）股道占用時(shí)間。股道占用時(shí)間由3部分組成，分別是終到列車(chē)到達(dá)技術(shù)作業(yè)使用時(shí)間ti1，終到列車(chē)等待列車(chē)檢查作業(yè)時(shí)間ti2，終到列車(chē)等待解體作業(yè)時(shí)間ti3。

2.3 目標(biāo)函數(shù)

由于編組站站線資源緊張，應(yīng)盡可能保證到發(fā)線能力富足，且合理分配股道，使到發(fā)線最大占用時(shí)間最小化，提高股道資源使用率，進(jìn)而減少維修成本，優(yōu)化目標(biāo)函數(shù)為

2.4 模擬退火算法

帶柔性重疊時(shí)間窗的終到列車(chē)股道應(yīng)用問(wèn)題屬于柔性車(chē)間調(diào)度問(wèn)題的衍生，屬于NP-hard問(wèn)題，使用傳統(tǒng)數(shù)值計(jì)算方法解決此類(lèi)問(wèn)題將很難在有限時(shí)間內(nèi)得到滿意解。江秀等[11]列舉了解決此大類(lèi)問(wèn)題的常用智能算法有遺傳算法、蟻群算法、禁忌搜索算法、模擬退火算法等；Zhu等[12]設(shè)計(jì)了基于agent的啟發(fā)式算法對(duì)車(chē)站線路進(jìn)行調(diào)度優(yōu)化。由于列車(chē)占用股道資源的起始時(shí)刻和占用股道資源的時(shí)間均不確定，使得合理調(diào)配股道資源模型的求解存在較大困難。因此，結(jié)合模型復(fù)雜性、多樣性和特殊性的特點(diǎn)，選用模擬退火算法求解此問(wèn)題。

模擬退火算法參照固體物理退火過(guò)程，當(dāng)溫度較高，分子運(yùn)動(dòng)劇烈，分子內(nèi)能增大隨著溫度降低，分子也逐漸停止運(yùn)動(dòng)，趨于有序。因此，使用該算法求解大型組合類(lèi)[1]NP問(wèn)題能夠避免求解結(jié)果陷入局部最優(yōu)解，而使最終結(jié)果趨于全局最優(yōu)。

模型中的為0-1決策變量，因而算例的模擬退火算法采用該編碼方式表示列車(chē)與股道的關(guān)系。結(jié)合已構(gòu)建的帶柔性重疊時(shí)間窗模型的特點(diǎn)，設(shè)計(jì)模擬退火優(yōu)化算法具體流程步驟如下。

步驟1：①輸入初始溫度T、降溫系數(shù)α、最小時(shí)間間隔，設(shè)定外部循環(huán)閾值outIteration、內(nèi)部循環(huán)閾值inIteration；②產(chǎn)生初始解 ，初始解為初始股道分配方案，判斷初始解是否滿足公式⑴—⑸的約束條件，不滿足則重新生成，直到滿足約束條件；計(jì)算f(i)，f(i)表示初始股道分配方案對(duì)應(yīng)的股道占用總時(shí)間，并且設(shè)定a= 1，b= 1。

步驟2：①如果達(dá)到內(nèi)部循環(huán)停止條件，轉(zhuǎn)步驟3；②否則，父代通過(guò)交換某列車(chē)的股道得到新的子代解，兩父代通過(guò)交叉產(chǎn)生2個(gè)新的解，判斷是否滿足公式⑴—⑸的約束條件,不滿足則重新生成，直到滿足約束條件；③取其中一個(gè)子代解j，計(jì)算f(j)，f(j)表示新股道分配方案對(duì)應(yīng)的股道占用總時(shí)間，如果f(j) -f(i) ＜ 0，則表示新的分配方案目標(biāo)值優(yōu)于初始解目標(biāo)值，則i=j；如果f(j) -f(i) > 0，則計(jì)算exp (- (f(j) -f(i)) /T)，如果存在exp (- (f(j) -f(i)) /T) >rand(0，1)，則以概率的形式讓i=j，b=b+ 1，轉(zhuǎn)①。

步驟3：①如果達(dá)到外部循環(huán)停止條件，終止運(yùn)算；②否則，轉(zhuǎn)步驟2，a=a+ 1。

3 算例分析

參數(shù)設(shè)置：模擬退火算法外部循環(huán)設(shè)置為1 000次，內(nèi)部循環(huán)為5次，初始溫度為100℃，降溫系數(shù)為0.85，最小時(shí)間間隔設(shè)為14 min。

為驗(yàn)證模型的正確性和合理性，現(xiàn)以某三級(jí)六場(chǎng)編組站接進(jìn)終到列車(chē)為例進(jìn)行驗(yàn)算。該編組站下行到達(dá)場(chǎng)有12條股道，其中1股為正線，不進(jìn)行接發(fā)列車(chē)作業(yè)，2-12股道可進(jìn)行接發(fā)列車(chē)作業(yè)。為降低算例復(fù)雜性，終到列車(chē)接進(jìn)股道不受其他種類(lèi)列車(chē)的影響。編組站下行到達(dá)場(chǎng)股道布置如圖3所示。

圖3 編組站下行到達(dá)場(chǎng)股道布置Fig.3 Tracks arrangement of downward receiving yard

經(jīng)統(tǒng)計(jì)，終到列車(chē)技術(shù)作業(yè)時(shí)間均值統(tǒng)計(jì)如表2所示。

表2 終到列車(chē)技術(shù)作業(yè)時(shí)間均值統(tǒng)計(jì) minTab.2 Average technical operation time of arriving trains

以某天下行到達(dá)終到列車(chē)接車(chē)計(jì)劃為例，經(jīng)統(tǒng)計(jì)得到該天下行終到列車(chē)的計(jì)劃接入到發(fā)線時(shí)刻和列車(chē)計(jì)劃從到發(fā)線清空時(shí)刻，其中5號(hào)和6號(hào)列車(chē)、10號(hào)和11號(hào)列車(chē)、14號(hào)和15號(hào)列車(chē)、21號(hào)和22號(hào)列車(chē)接入到發(fā)線時(shí)刻和從到發(fā)線清空時(shí)刻存在重疊時(shí)間窗關(guān)系，階段計(jì)劃接近列車(chē)時(shí)刻和計(jì)劃清空股道時(shí)刻如表3所示。

3.1 算例1

編組站到發(fā)線占用計(jì)劃安排是在不考慮列車(chē)發(fā)生意外條件下對(duì)股道進(jìn)行的初始安排，因此，算例1優(yōu)化不考慮列車(chē)早到、晚到、或技術(shù)作業(yè)延長(zhǎng)(縮短)等情況。結(jié)合編組站到發(fā)線占用計(jì)劃安排特點(diǎn)，以某天到發(fā)線初始占用計(jì)劃安排為例，運(yùn)用模擬退火算法對(duì)原始股道分配方案進(jìn)行優(yōu)化，優(yōu)化前后的股道分配對(duì)比如表4所示。

相較于到發(fā)線占用計(jì)劃安排，優(yōu)化后股道總占用時(shí)間由149 min減少至109 min，股道總使用時(shí)間減少了40 min。進(jìn)一步得到算例中股道占用時(shí)間迭代曲線如圖4所示。

表3 階段計(jì)劃接近列車(chē)時(shí)刻和計(jì)劃清空股道時(shí)刻Tab.3 Time of approaching trains and empty tracks under periodic plan

3.2 算例2

到發(fā)線占用計(jì)劃安排并未考慮編組站終到列車(chē)實(shí)際到達(dá)時(shí)間和實(shí)際技術(shù)作業(yè)時(shí)間的不確定性，一旦發(fā)生列車(chē)晚點(diǎn)等意外情況，將對(duì)編組站正常作業(yè)產(chǎn)生嚴(yán)重影響，為提高到發(fā)線分配的魯棒性，考慮部分終到列車(chē)早到、晚到或有技術(shù)作業(yè)延長(zhǎng)或縮短的復(fù)雜情況，對(duì)原始股道占用計(jì)劃安排進(jìn)行優(yōu)化。

參照文獻(xiàn)[2,8]列車(chē)到發(fā)時(shí)間不確定的判斷依據(jù)，到發(fā)時(shí)間偏差系數(shù)的波動(dòng)范圍設(shè)定為0.9≤≤1.1；根據(jù)實(shí)際工作經(jīng)驗(yàn)，實(shí)際技術(shù)作業(yè)時(shí)間應(yīng)在原技術(shù)作業(yè)時(shí)間上小幅度擺動(dòng)，因此，技術(shù)作業(yè)時(shí)間偏差系數(shù)的波動(dòng)范圍設(shè)定為0.9≤≤1.1；均衡系數(shù)設(shè)定為Nj= 2.9。

表4 優(yōu)化前后的股道分配對(duì)比Tab.4 Comparison of tracks allocation before and after optimization

圖4 股道占用時(shí)間迭代曲線圖Fig.4 Iteration graph of occupation time of tracks

為降低求解復(fù)雜性，列車(chē)早到(晚到)與技術(shù)時(shí)間延長(zhǎng)(縮短)并不同時(shí)出現(xiàn)在同一列終到列車(chē)上；且發(fā)生早到(晚到)或技術(shù)時(shí)間延長(zhǎng)(縮短)的終到列車(chē)均在隨機(jī)條件下進(jìn)行設(shè)定。

經(jīng)計(jì)算，優(yōu)化前后股道分配方案比較如表5所示。

表5 優(yōu)化前后股道分配方案比較Tab. 5 Comparison of tracks allocation before and after optimization

經(jīng)計(jì)算，在到發(fā)線占用計(jì)劃安排條件下，股道總占用時(shí)間為189 min，優(yōu)化后股道總占用時(shí)間為125 min，股道總使用時(shí)間減少了64 min，股道的使用效率得到有效提高。

結(jié)合算例1和算例2可知，優(yōu)化前到發(fā)線占用時(shí)間由149 min增加至189 min，增加了40 min；優(yōu)化后到發(fā)線占用時(shí)間由109 min增加至125 min，增加了16 min。模型優(yōu)化了編組站到發(fā)線對(duì)外界的干擾的適應(yīng)性，因而股道分配的魯棒性得到提高。

3.3 算例3

股道均衡系數(shù)越大，即占用某股道的次數(shù)越多，股道使用的均衡性越差。算例1和算例2的股道均衡系數(shù)均設(shè)定為Nj= 2.9，算例3對(duì)列車(chē)正常到達(dá)下的股道均衡系數(shù)進(jìn)行靈敏度分析。不同均衡系數(shù)下優(yōu)化前后股道總占用時(shí)間對(duì)比如表6所示。

表6 不同均衡系數(shù)下優(yōu)化前后股道總占用時(shí)間對(duì)比Tab.6 Comparison of occupation time of tracks before and after optimization under different balanced parameters

由表6可知，優(yōu)化后的股道總占用時(shí)間明顯降低，且股道不均衡系數(shù)對(duì)終到列車(chē)占用到發(fā)線總時(shí)間影響較小，在編組站到發(fā)線運(yùn)能緊張的情況下，增加某股道使用頻次不會(huì)對(duì)到發(fā)線占用總時(shí)間產(chǎn)生顯著影響。

4 結(jié)束語(yǔ)

編組站到發(fā)線運(yùn)用計(jì)劃直接優(yōu)化目標(biāo)是在減少列車(chē)進(jìn)路交叉前提下，保證不間斷接發(fā)列車(chē)，因而編組站到發(fā)線優(yōu)化研究，可以有效保證編組站進(jìn)行日常有序技術(shù)作業(yè)。在研究過(guò)程中，引入柔性重疊時(shí)間窗，建立以股道占用最大時(shí)間最小化為目標(biāo)的非線性規(guī)劃模型。仿真算例1和算例2得到的優(yōu)化方案提高了到發(fā)線利用率和到發(fā)線分配的魯棒性，表明所構(gòu)建的模型和算法具有可行性和合理性，算例3的結(jié)論認(rèn)為增加某股道的使用頻次可以緩解編組站到發(fā)線運(yùn)能緊張的狀況?？紤]到列車(chē)等級(jí)和列車(chē)種類(lèi)也會(huì)對(duì)股道分配產(chǎn)生影響，如何在更復(fù)雜的條件下分配編組站到發(fā)線還需要進(jìn)一步的研究。