基于列車到發(fā)時刻不確定的客運站到發(fā)線運用優(yōu)化研究*

李 濤 胡可昊 宋凱文 楊生仁

（蘭州交通大學(xué)交通運輸學(xué)院 蘭州730070）

0 引 言

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

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

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

1 問題描述

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

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

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

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

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

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

2 模型建立

2.1 不確定理論知識

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

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

在決策過程中，用不確定分布表示不確定變量，首先根據(jù)經(jīng)驗或?qū)＜乙庖姽烙嫴淮_定變量所服從的分布[19]，然后求出其逆不確定分布。如果不確定變量ζ 服從下面的正態(tài)不確定分布Φ(x) ，則其逆不確定分布為Φ-1(x)。

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

2.2 符號及變量定義

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

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

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

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

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

2.3 模型建立

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

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

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

2.4 確定性等價類模型

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

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

3 求解算法

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

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

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

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

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

3.1.2 改進(jìn)選擇算子

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

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

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

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

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

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

4 算 例

4.1 算例求解

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

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

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

圖3 列車到達(dá)時刻波動統(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 ℃，當(dāng)溫度低于10 ℃時，采用等步長下降，步長取1；λ = 0.9 ，ε = 3 × 10-4；α = 10，β = 0.04 。

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

分別用常規(guī)GA和ISAGA 算法給08:00—12:00到達(dá)的46 列列車分配到發(fā)線，運用MatlabR 2018a在Intel（R）Core（TM）i5-4210H CPU 2.90G Hz，內(nèi)存4G 的計算機上進(jìn)行求解，最后GA所得目標(biāo)函數(shù)值穩(wěn)定為58 843 min，迭代過程見圖5，ISAGA所得目標(biāo)函數(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 均衡性

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

進(jìn)一步計算，得

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

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

4.2.2 平均誤差

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

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

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

4.2.3 α取值

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

5 結(jié) 論

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

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

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

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