黃俊生，廣曉平

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

0 引言

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

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

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

1 柔性和重疊時間窗

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

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

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

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

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

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

2.1 變量定義

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

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

2.2 約束條件

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

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

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

圖2 最小安全時間間隔Fig.2 Minimum safety time interval

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

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

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

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

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

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

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

2.4 模擬退火算法

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

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

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

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

步驟2：①如果達(dá)到內(nèi)部循環(huán)停止條件，轉(zhuǎn)步驟3；②否則，父代通過交換某列車的股道得到新的子代解，兩父代通過交叉產(chǎn)生2個新的解，判斷是否滿足公式⑴—⑸的約束條件,不滿足則重新生成，直到滿足約束條件；③取其中一個子代解j，計(jì)算f(j)，f(j)表示新股道分配方案對應(yīng)的股道占用總時間，如果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è)為14 min。

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

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

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

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

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

3.1 算例1

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

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

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

3.2 算例2

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

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

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

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

為降低求解復(fù)雜性，列車早到(晚到)與技術(shù)時間延長(縮短)并不同時出現(xiàn)在同一列終到列車上；且發(fā)生早到(晚到)或技術(shù)時間延長(縮短)的終到列車均在隨機(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ì)劃安排條件下，股道總占用時間為189 min，優(yōu)化后股道總占用時間為125 min，股道總使用時間減少了64 min，股道的使用效率得到有效提高。

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

3.3 算例3

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

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

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

4 結(jié)束語

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