李 濤 胡可昊 宋凱文 楊生仁

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

0 引 言

到發(fā)線的合理運用是客運車站行車作業(yè)的一項重要內(nèi)容，是車站編制階段計劃的關鍵工作之一。高效運用到發(fā)線不僅可以提高客運站的服務水平，而且還可以提高鐵路資源的利用效率?？瓦\車站一般按到發(fā)線的固定方案接發(fā)列車，但是實際中列車的運行往往受惡劣天氣、車輛以及設備故障等不確定因素的影響，造成列車實際到發(fā)時刻與圖定時刻產(chǎn)生差異，使到發(fā)線運用計劃與正常情況下有所不同。

鑒于到發(fā)線運用計劃的重要性，國內(nèi)外許多學者針對該問題進行了一系列頗有成效的研究。文獻[1-3]都建立了客運站到發(fā)線運用的0-1規(guī)劃模型，算法很好的實現(xiàn)了客運站到發(fā)線運用計劃的自動編制。文獻[4-6]把客運站到發(fā)線運用優(yōu)化的目標分成3個子目標進行考慮，采用智能算法進行求解。文獻[7-9]采用排序理論，建立車站到發(fā)線運用的排序模型。文獻[10-11]把到發(fā)線運用優(yōu)化問題描述為有權重的NPP，構造無向圖，采用分枝定界法對模型進行求解。文獻[12]使用禁忌搜索算法解決列車到發(fā)時刻確定條件下列車的最優(yōu)過站進路。文獻[13-14]對晚點下到發(fā)線運用問題進行研究，建立了混合整數(shù)規(guī)劃模型。文獻[15]以均衡使用到發(fā)線、列車到達時刻不確定性等為約束，建立帶柔性重疊時間窗的優(yōu)化模型，采用模擬退火算法求解。文獻[16]在列車到發(fā)時刻變動的前提下，分析列車進出站時可能會產(chǎn)生的交叉，建立滿足列車最小安全時間間隔的優(yōu)化模型，設計啟發(fā)式算法求解。文獻[17]統(tǒng)計了列車到發(fā)時刻不確定的均值和方差，建立滿足列車、咽喉以及股道三者耦合關系的模型，采用模擬退火算法求解。

上述文獻存在以下問題:如目標中未考慮設備使用的均衡性[1-3]、當問題規(guī)模比較大時，算法的實時性無法滿足[4，6]、現(xiàn)有研究大多是按圖定時刻對客運站到發(fā)線進行優(yōu)化，而對到發(fā)線運用方案中列車到發(fā)時刻不確定等因素未能充分考慮。本文在總結已有研究結果的基礎上，將列車實際到達時刻與計劃到達時刻差值描述為不確定變量，建立了客運站到發(fā)線運用優(yōu)化問題的不確定規(guī)劃模型，借助不確定理論將模型等價轉化為確定類模型。為了提高算法的運行效率以及搜索全局最優(yōu)解的能力，把遺傳算法（genetic algorithm，GA）和模擬退火算法（simulated annealing algorithm，SAA）結合起來，同時在模型中引入懲罰因子、改進選擇算子和適應度函數(shù)，設計ISAGA算法對確定模型進行求解。

1 問題描述

到發(fā)線的運用不僅關系著客運站的服務水平，而且還關系到鐵路資源的利用效率。到發(fā)線的運用要保證客運車站可以不間斷地接發(fā)列車，最大限度地利用車站每一條線路的能力，同時也要留有一定的余地。

在實際生產(chǎn)過程中，由于大雨、雪天氣的影響、車輛和設備的狀態(tài)等使列車實際到發(fā)時刻與圖定到發(fā)時刻有所差異，從而影響到發(fā)線的運用計劃，而現(xiàn)場工作人員為了能完成運輸任務，往往會不按技術規(guī)范去趕點完成作業(yè)，從而引發(fā)了許多安全事故。針對列車到發(fā)時刻的不確定性，由于樣本數(shù)據(jù)缺乏，將其視為不確定變量進行分析是有效的方法。本文借助不確定理論的方法，利用不確定變量表示列車實際到達時刻與計劃到達時刻差值的不確定性，以列車占用到發(fā)線時間最小和到發(fā)線運用的均衡性為優(yōu)化目標，以差值得到滿足而應達到的置信水平、列車占用到發(fā)線的唯一性等為約束條件，建立到發(fā)線運用的不確定規(guī)劃模型。

為了便于后續(xù)的研究，現(xiàn)對列車到發(fā)時刻不確定條件下鐵路客運站到發(fā)線優(yōu)化模型做如下假設。

假設1。列車計劃到達時刻為一確定的值，不考慮冗余。

假設2。站內(nèi)的到發(fā)線、信號機等設備能正常接發(fā)列車，站外的線路等設備使列車能正常運行。

假設3。列車不會大面積晚點甚至停運。

2 模型建立

2.1 不確定理論知識

不確定理論為解決難以獲得精確信息的決策問題提供了數(shù)學基礎，它已經(jīng)被用于各個領域，劉寶碇[18]提出了不確定理論。

定義1。記不確定變量為ζ ，它的不確定分布表示為Φ(x)= M{ζ ≤x},x ∈R ，它的逆不確定分布為其反函數(shù)[19]，即Φ-1(x)。

在決策過程中，用不確定分布表示不確定變量，首先根據(jù)經(jīng)驗或專家意見估計不確定變量所服從的分布[19]，然后求出其逆不確定分布。如果不確定變量ζ 服從下面的正態(tài)不確定分布Φ(x) ，則其逆不確定分布為Φ-1(x)。

定理1[20]。設ζ 為一不確定變量，其不確定分布為Φ(x)，Φ(x)∈(0,1)，g(x,ζ)= h(x)- ζ ，當置信水平α ∈(0,1) 時，則有M{g(x,ζ)≤0} ≥α (M{g(x,ζ)≥0}≥α)，當且僅當h(x)≤fζ(α)（h(x)≥fζ(α)）。其中fζ(α)=Φ-1(1 - α)（ fζ(α)= Φ-1(α)）。

2.2 符號及變量定義

設某客運站到發(fā)線的集合為D ={1,2,…,j,…,m}，其中j 為第j 條到發(fā)線的編號，m 為到發(fā)線的總數(shù)；計劃階段到達客運站的列車集合L ={1,2,…,i,…,n}，其中，i 為列車i 到達車站的順序，n 為列車總數(shù)；P ={1,2,…,p,…,w}，其中p 為第p 類作業(yè)的編號，w 為作業(yè)類總數(shù)。

Ti為列車的計劃到達時刻，即列車運行圖規(guī)定時刻。

ΔT 為前后2列列車占用同1條股道時的最小安全時間間隔，本文中值取8 min。

cij 為列車i 占用到發(fā)線j 的權值，其權值的確定與呂紅霞[21]確定方法類似。

xij 為1，列車i 占用到發(fā)線j ；0，否則。

2.3 模型建立

目標函數(shù)從縮短旅客列車在到發(fā)線的停留時間和均衡使用到發(fā)線（用每條到發(fā)線占用時間總和與各到發(fā)線平均占用時間之差的標準差來衡量）2個方面考慮。因列車的出發(fā)時刻為列車到達時刻與列車占用到發(fā)線總時間的加和，所以可將研究的問題轉化為只考慮列車到達時刻不確定性下到發(fā)線的運用優(yōu)化。由于外界因素的無規(guī)律變化，使得列車到達時間充滿不確定性，本文采用機會約束的思想，將列車到達時刻的波動表示為波動滿足的機會達到一定的置信水平，從而得到魯棒性較高的到發(fā)線運用計劃，所建模型見式（1）～（11）。

式（1）為目標函數(shù)，表示旅客列車在到發(fā)線上的停留時間和到發(fā)線均衡使用的標準差之和最小。式（2）～（7）為約束條件，其中式（2）～（4）在任何情況下，列車只要占用到發(fā)線都必須遵循。式（4）保證同1條到發(fā)線上先后接發(fā)2列列車時的安全，最小安全時間間隔見圖1；式（5）表示列車到達時刻機會約束。列車i 實際到達時刻發(fā)生了波動，已不再是一個確定的值，其到達時刻是在一定置信度水平下的置信區(qū)間；式（6）表示交叉的疏解；式（7）表示同站臺換乘；式（8）～（11）為0-1變量。

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

2.4 確定性等價類模型

因為列車計劃到達時刻Ti為確定的值，而實際到達時刻受諸多因素的影響為一不確定的值，本文將的差值記為ζ ，ζ 為1個不確定變量，其不確定分布為Φζ、逆不確定分布為。將約束（5）進行化簡，得到式（12）和式（13），利用定義1 和定理1將式（12）和式（13）轉化為確定性等價類約束式（14）和式（15）。

通過上述分析，將原來的不確定機會約束規(guī)劃模型轉化為0-1 整數(shù)規(guī)劃的確定性等價類模型。與原來模型式（1）～（11）相比，上述模型只是將約束（5）替換成式（14）和式（15）。為了簡化，本文假設ζ服從正態(tài)不確定分布，則式（14）和式（15）對應的逆不確定分布見式（16）和式（17）。

3 求解算法

到發(fā)線的運用優(yōu)化已被證明屬于NP完全問題[9]，對該類問題的求解多采用智能算法。雖然本文考慮了列車到發(fā)時刻的不確定性，但是其占用到發(fā)線的過程仍和列車到發(fā)時刻固定時是一致的，所以仍可采用智能算法進行求解。本文考慮到SA 較強的魯棒性和局部搜索能力，將其與GA相結合，能更好的避免GA 的缺點，在此基礎上對選擇算子和適應度函數(shù)等做了進一步的改進，使設計的ISAGA算法能更好的提高運行效率和求解的質(zhì)量。

3.1 模擬退火遺傳算法的關鍵步驟

3.1.1 適應度函數(shù)的選取

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

式（18）和式（19）中符號的含義與取值同文獻[22]。

3.1.2 改進選擇算子

常用賭輪選擇法作為選擇算子，雖然賭輪選擇法容易用程序實現(xiàn)，但是這種方法在計算過程中會產(chǎn)生過早收斂或過慢結束的現(xiàn)象。本文首先創(chuàng)建了2個種群大小均為N的空間，并把二者按其適應度的大小分別進行排序；然后把父代種群中1/4的最優(yōu)個體和子代種群中1/2 的最優(yōu)個體組合成一個新的種群，對新種群進行退火選擇[23]；最后從中間選取N 個個體組成新的父代，再進行后面的交叉和變異操作[23]。如果個體的適應度大小為f (i)，則個體i 被選中的概率為

式中，tk為當前狀態(tài)的退火溫度。

3.1.3 交叉算子自適應調(diào)整

遺傳算法中交叉概率pc 的取值對算法的收斂性和搜索速度有很大影響，大小選取不當會使算法進化緩慢，破壞種群的多樣性，使算法陷入局部最優(yōu)。因此，對交叉概率進行非線性的指數(shù)形式調(diào)整。

式中:K1=0.5，K2=0.9；favg為每代種群適應度的平均值；f ' 為當前要交叉的2 個個體中適應度較小的一個個體；fmin為每代種群中最小的適應度。

模擬退火遺傳算法的具體流程見圖2。

4 算 例

4.1 算例求解

為了驗證本文提出的算法和建立模型的準確性，從某客運站驗證的數(shù)據(jù)中選取某天08:00—12:00時的數(shù)據(jù)為例進行驗證。選取階段中到發(fā)的列車共46 列，該站共2 條正線，5 條到發(fā)線，其中3，5，7號到發(fā)線固定接發(fā)下行列車；4，6號到發(fā)線固定接發(fā)上行列車；正線I，II分別用于下、上行列車的不停站通過。為了驗證假設的分布，本文借助IBM SPSS Statistics 23 對該站7 月、8 月、9 月共3 個月（天氣影響和旅客周期性波動較大）進行統(tǒng)計分析，結果見圖3～4。

由圖3 可見，除了1 列車的時間波動外，其余列車到達時刻的波動是近似服從正態(tài)分布的。根據(jù)列車到達時刻波動的正態(tài)Q-Q圖可以看出數(shù)據(jù)與對角線基本重合，Q-Q圖提示該組數(shù)據(jù)服從正態(tài)分布，而且單樣本K-S 檢驗數(shù)據(jù)摘要中顯著性概率P = 0.177 ＞0.04 ,提示假設正態(tài)分布成立，且該分布的均值為0.78，標準差為5.723。

圖2 算法流程圖Fig. 2 Algorithm flowchart

圖3 列車到達時刻波動統(tǒng)計Fig. 3 Fluctuation statistics of train arrival time

本文中i,j,n,m,p 等變量的取值均為正整數(shù)。參數(shù)取值:種群大小 popsize =30；變異概率pm = 0.01 ；最大迭代次數(shù)U = 500 ；初始溫度t0= 100 ℃，當溫度低于10 ℃時，采用等步長下降，步長取1；λ = 0.9 ，ε = 3 × 10-4；α = 10，β = 0.04 。

圖4 列車到達時刻波動的正態(tài)Q-Q圖Fig. 4 Normal Q-Q diagram of train arrival time fluctuations

分別用常規(guī)GA和ISAGA 算法給08:00—12:00到達的46 列列車分配到發(fā)線，運用MatlabR 2018a在Intel（R）Core（TM）i5-4210H CPU 2.90G Hz，內(nèi)存4G 的計算機上進行求解，最后GA所得目標函數(shù)值穩(wěn)定為58 843 min，迭代過程見圖5，ISAGA所得目標函數(shù)值穩(wěn)定為48 781 min，迭代過程見圖6。通過整理迭代所得數(shù)據(jù)，得到到發(fā)線運用方案，見表1～2。

圖5 GA優(yōu)化收斂趨勢圖Fig. 5 Convergence trend diagram of GA optimization

圖6 ISAGA優(yōu)化收斂趨勢圖Fig. 6 Convergence trend diagram of ISAGA optimization

表1 GA 所得到發(fā)線運用方案Tab. 1 Application scheme of GA's arrival and departure lines

表2 ISAGA 所得到發(fā)線運用方案Tab. 2 Application scheme of ISAGA's arrival and departure lines

4.2 算例分析

4.2.1 均衡性

從算例結果可以看出，本文所設計的模型和算法可以滿足列車在車站的作業(yè)需要，可以使上行列車分布在4，6 股道，下行列車分布在3,5,7 股道；而車站值班員的方案沒能實現(xiàn)到發(fā)線分方向接發(fā)列車。根據(jù)本文對均衡性評價的定義分別計算車站值班員所用方案、常規(guī)GA 所得方案以及本文設計的ISAGA算法優(yōu)化所得方案的均衡度，見表3。

進一步計算，得

根據(jù)計算結果可知，運用常規(guī)GA 得到的到發(fā)線運用方案與車站值班員方案相比，到發(fā)線運用的均衡度提高了26.32%；運用本文設計的ISAGA 算法得到的到發(fā)線運用方案與車站值班員方案相比，均衡度提高了75.47%，與常規(guī)GA 得到方案相比，均衡度提高了49.15%。從最后目標值可以看出，ISAGA 所得的目標值比運用常規(guī)GA 所得的更優(yōu)；從優(yōu)化收斂趨勢圖可以看出，本文設計的ISAGA算法能夠有效的避免GA 陷入局部最優(yōu)解的缺陷，而且得到的解更接近最優(yōu)解。

表3 均衡度統(tǒng)計Tab. 3 Balance statistics min

4.2.2 平均誤差

為了進一步驗證算法和模型的準確性，盡量避免奇異數(shù)據(jù)對研究問題的影響，隨機在這3 個月中選取15 d 的數(shù)據(jù)進行統(tǒng)計分析。通過對得到的數(shù)據(jù)進行處理后，運用常規(guī)GA和設計的ISAGA算法對選取的15 d的數(shù)據(jù)進行到發(fā)線的分配，分別分析所得方案目標函數(shù)值和到發(fā)線運用均衡性的均值以及用這2 種算法進行求解得到優(yōu)化方案的均值，見表4。

表4 平均值統(tǒng)計Tab. 4 Average statistics

根據(jù)統(tǒng)計結果可知，運用ISAGA算法求得方案的目標值、均衡性依然是優(yōu)于運用常規(guī)GA 求得的方案。因此，算例中選取的數(shù)據(jù)可以驗證模型和算法的準確性，所選數(shù)據(jù)不具有特殊性。

4.2.3 α取值

根據(jù)文中數(shù)據(jù)分析所得標準差的值，結合約束（14）～（15），對約束中α的取值進行分析，其中α取0～10 之間的整數(shù)。通過計算發(fā)現(xiàn)當α取0～7 之間的整數(shù)時，能保證約束發(fā)揮作用；而取大于7的整數(shù)時，約束將不會成立。而文中給參數(shù)賦值時，α取5，剛好落入成立的區(qū)間，所以得到的結果是可行且有效的。

5 結 論

1） 針對列車到發(fā)時刻不確定下客運站到發(fā)線運用優(yōu)化問題，建立了帶有機會約束的整數(shù)規(guī)劃模型。以最小化列車占用到發(fā)線的時間和到發(fā)線運用的均衡性為優(yōu)化目標，并且借助軟件IBM SPSS Statistics 23 驗證了樣本數(shù)據(jù)的特征與前文中假設分布的一致性，可以較好的描述實際問題。

2） 借助改進適應度函數(shù)、選擇算子、交叉算子的模擬退火遺傳算法，有效的求解了模型。通過算例分析表明，該算法在解決列車到發(fā)時刻不確定條件下客運站到發(fā)線分配問題上是可行的，優(yōu)化所得的方案優(yōu)于現(xiàn)場方案和運用常規(guī)GA 所得方案，均衡性分別提高了75.47%和49.15%。運用設計的ISAGA算法求得的方案，在應對列車到發(fā)時刻不確定方面有較好的魯棒性，車站可以按照所得方案安排生產(chǎn)，從而保證車站作業(yè)的安全性。因為算法的改進，使得算法收斂速度較快，能夠滿足車站編制計劃實時性的要求，對車站作業(yè)智能化具有一定的意義。

3） 通過平均誤差分析結果看出，算例所選數(shù)據(jù)不是個例，能夠驗證模型和算法的準確性。運用設計的ISAGA算法所求方案的目標函數(shù)值、均衡性以及求解效果確實優(yōu)于常規(guī)GA 所求方案。通過α取值分析看出，計算時給參數(shù)的賦值是合理的。

4） 在建立到發(fā)線分配模型時，對問題進行了簡化，未考慮列車大面積晚點、列車停運，及不確定變量服從其他分布的情況。在后續(xù)可對列車晚點且密集到達后接發(fā)車進路的調(diào)整以及不確定變量服從其他分布的情況進行研究。