帶柔性重疊時間窗編組站終到列車到發(fā)線優(yōu)化研究

黃俊生，廣曉平

（蘭州交通大學 交通運輸學院，甘肅 蘭州 730070）

0 引言

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

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

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

1 柔性和重疊時間窗

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

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

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

圖1 重疊時間窗關系Fig.1 Relationship of overlapped time window

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

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

2.1 變量定義

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

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

2.2 約束條件

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

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

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

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

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

已有研究[3]認為股道使用均衡系數越小，股道使用均衡性越好；股道使用均衡系數越大，股道使用均衡性越差。

（6）終到列車實際到達與清空股道時刻。為表示列車實際到達時刻，引入偏差系數，該值可用于調整列車到達時刻，計算公式為

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

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

2.3 目標函數

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

2.4 模擬退火算法

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

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

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

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

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

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

3 算例分析

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

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

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

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

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

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

3.1 算例1

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

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

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

3.2 算例2

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

參照文獻[2,8]列車到發(fā)時間不確定的判斷依據，到發(fā)時間偏差系數的波動范圍設定為0.9≤≤1.1；根據實際工作經驗，實際技術作業(yè)時間應在原技術作業(yè)時間上小幅度擺動，因此，技術作業(yè)時間偏差系數的波動范圍設定為0.9≤≤1.1；均衡系數設定為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ā)生早到(晚到)或技術時間延長(縮短)的終到列車均在隨機條件下進行設定。

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

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

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

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

3.3 算例3

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

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

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

4 結束語

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