基于改進(jìn)遺傳算法的客運(yùn)站到發(fā)線運(yùn)用優(yōu)化研究

李 濤，張杉基，孫建林，張 楊，賈 飛

LI Tao, ZHANG Shanji, SUN Jianlin, ZHANG Yang, JIA Fei

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

0 引言

到發(fā)線分配是客運(yùn)站行車作業(yè)的一項重要內(nèi)容，是車站階段計劃編制的關(guān)鍵工作之一。到發(fā)線的合理運(yùn)用不僅關(guān)系車站的正常運(yùn)輸生產(chǎn)和運(yùn)行圖的實現(xiàn)，還關(guān)系鐵路行車安全和列車運(yùn)行的經(jīng)濟(jì)效益。一般情況下，客運(yùn)站按照到發(fā)線的固定使用方案接發(fā)列車，而在實際運(yùn)營中，列車的運(yùn)行會受到惡劣天氣、車輛及設(shè)備故障、節(jié)假日客流高峰等因素的影響而發(fā)生晚點，需要調(diào)整原有的到發(fā)線運(yùn)用計劃，盡可能保證車站作業(yè)順利進(jìn)行。為此，到發(fā)線的運(yùn)用應(yīng)保證客運(yùn)站可以不間斷地接發(fā)列車，最大限度地利用車站到發(fā)線的能力，同時也需要留有一定的余地，避免高峰時段列車在站外停車等線導(dǎo)致的晚點傳播。因此，研究列車到發(fā)時刻波動情況下客運(yùn)站的到發(fā)線運(yùn)用問題，對客運(yùn)站到發(fā)線運(yùn)用計劃編制有非常重要的意義。

為了高效、合理地運(yùn)用到發(fā)線，保證接發(fā)車作業(yè)的效率，許多學(xué)者對到發(fā)線的運(yùn)用優(yōu)化進(jìn)行研究。部分研究[1-3]建立客運(yùn)站到發(fā)線運(yùn)用的0-1 規(guī)劃模型，實現(xiàn)客運(yùn)站到發(fā)線運(yùn)用計劃的自動編制，但均未考慮設(shè)備使用的均衡性。部分研究[4-6]把客運(yùn)站到發(fā)線運(yùn)用優(yōu)化的目標(biāo)分解為3 個子目標(biāo)，其中謝楚農(nóng)等[4]建立多目標(biāo)優(yōu)化模型，采用分枝定界法求解；林志安等[5]運(yùn)用捕食禁忌搜索求解；吳鵬等[6]統(tǒng)一多目標(biāo)函數(shù)的量綱，將多目標(biāo)優(yōu)化問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題，利用分枝定界算法求解。當(dāng)問題規(guī)模較大時，謝楚農(nóng)等[4]和吳鵬等[6]提出的方法無法滿足求解效率要求。劉偉等[7]統(tǒng)計列車實際到發(fā)時刻的均值和方差，建立滿足列車、咽喉及到發(fā)線耦合關(guān)系的模型，采用模擬退火算法求解。劉偉等[8]考慮安全約束，建立晚點情況下客運(yùn)站到發(fā)線分配模型，分析延誤時間與延誤列車數(shù)量的關(guān)系。部分研究[9-11]建立車站到發(fā)線運(yùn)用的排序模型。Billionnet[12]把到發(fā)線運(yùn)用優(yōu)化問題描述為有權(quán)重的NPP，構(gòu)造無向圖，采用分枝定界法求解。

這些研究大多是按圖定到發(fā)時刻對客運(yùn)站到發(fā)線運(yùn)用進(jìn)行優(yōu)化，對實際運(yùn)營中列車到發(fā)時刻波動的研究較少。按照圖定到發(fā)時刻計算得到的到發(fā)線運(yùn)用方案沒有充分考慮列車晚點的情況，魯棒性較差，在列車到發(fā)時刻不確定的場景下使用效果不佳，需要頻繁地調(diào)整車站到發(fā)線運(yùn)用計劃。因此，考慮列車到發(fā)時刻不確定性，運(yùn)用概率統(tǒng)計和不確定理論，統(tǒng)計得到實際運(yùn)營中列車到發(fā)時刻的波動范圍，建立客運(yùn)站到發(fā)線運(yùn)用優(yōu)化模型。借鑒模擬退火算法思想，改進(jìn)遺傳算法的選擇算子，避免算法過早收斂或過慢結(jié)束，同時提出交叉概率的自適應(yīng)確定方法，加快遺傳算法的收斂速度。該模型和算法可以實現(xiàn)有預(yù)見性地安排到發(fā)線運(yùn)用，減少交叉干擾產(chǎn)生的列車晚點，提高作業(yè)的安全性。

1 客運(yùn)站到發(fā)線運(yùn)用問題

1.1 問題假設(shè)

在列車到發(fā)時刻波動條件下，對鐵路客運(yùn)站到發(fā)線優(yōu)化模型作出以下假設(shè)：①列車在運(yùn)行過程中不發(fā)生鐵路交通事故及其他安全事件；②站內(nèi)的到發(fā)線、信號機(jī)等設(shè)備能正常接發(fā)列車，站外的線路等設(shè)備可以保證列車正常運(yùn)行；③列車運(yùn)行時間發(fā)生波動，不會使列車到達(dá)車站的次序發(fā)生變化；④不考慮大面積晚點以及列車停運(yùn)的情況。

1.2 列車到發(fā)時刻波動范圍

列車到發(fā)時刻服從的分布無法預(yù)先掌握，也很難對其分布作出準(zhǔn)確的假設(shè)，可以根據(jù)經(jīng)驗或?qū)＜业囊庖?，預(yù)測其大致的趨勢，再用已有的樣本數(shù)據(jù)對預(yù)測的分布形態(tài)進(jìn)行驗證?；诜菂?shù)檢驗方法，先采用數(shù)理統(tǒng)計方法，對一定時段內(nèi)的列車到發(fā)時間波動值(列車實際到達(dá)時刻與計劃到達(dá)時刻之差)進(jìn)行統(tǒng)計，根據(jù)該時段波動值出現(xiàn)的次數(shù)以及專家的意見，假設(shè)其可能服從的分布，然后運(yùn)用假設(shè)檢驗方法驗證假設(shè)的合理性，即驗證列車的到發(fā)時間波動是否服從該分布。如果假設(shè)檢驗不通過，則需要提出新的分布，再進(jìn)行假設(shè)檢驗，直到得到合適的分布函數(shù)為止。最后，運(yùn)用區(qū)間估計得出到發(fā)時刻的波動范圍。由于區(qū)間的長度、同等級列車的運(yùn)行速度相近，假設(shè)列車到發(fā)時刻的波動服從正態(tài)分布，假設(shè)問題的接受域為H0：列車i到達(dá)時刻的波動值服從正態(tài)分布，可以得到正態(tài)分布均值計算公式為

式中：為列車到達(dá)時刻波動值均值的估計值；n為研究階段內(nèi)相同等級的列車數(shù)量；i為列車序號；ti為第i列車的到達(dá)時刻波動值。

正態(tài)分布方差計算公式為

式中：為列車到達(dá)時刻波動值方差的估計值。

為提高統(tǒng)計的準(zhǔn)確性，規(guī)定在通常情況下，樣本容量n應(yīng)滿足n≥46。以到達(dá)時刻為例，用公式 ⑴ 和公式 ⑵ 分別計算列車到達(dá)時刻波動值的均值和方差，由此可以得到第i列車到達(dá)時刻波動值的正態(tài)分布估計，即ti～N(，)，然后用χ2檢驗進(jìn)行驗證。列車實際到達(dá)時刻與圖定時刻通常存在一定的偏差。列車的到達(dá)時刻在指定的偏差范圍內(nèi)，可以認(rèn)為其正點運(yùn)行，該情況可以用公式⑶ 表示。

式中：為列車實際到達(dá)時刻的估計值；Ti為列車計劃到達(dá)時刻；α為到達(dá)時刻偏差的允許范圍；β為偏差的置信度。

為了得到列車到達(dá)時刻的波動范圍，首先需要得到列車到達(dá)時刻波動值服從的分布函數(shù)，然后運(yùn)用區(qū)間估計，對一定置信度水平下的波動范圍進(jìn)行估計。在列車到達(dá)時刻的波動值服從正態(tài)分布的情況下，如果公式⑶成立，則列車i的實際到達(dá)時刻在一定置信度水平下的波動范圍可以用以下公式計算

式中：為對應(yīng)分布的分位點。

2 客運(yùn)站到發(fā)線運(yùn)用優(yōu)化模型

2.1 符號及變量

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

為第i列車占用到發(fā)線的總時間，計算公式為

式中：為信號員或車站值班員開始為第i列車排列進(jìn)路，至列車完全停靠在到發(fā)線上所耗費的時間[4]，根據(jù)車站作業(yè)標(biāo)準(zhǔn)，為2 min；為列車從完全?？吭诘桨l(fā)線時起，至該列車從車站出發(fā)時刻止，列車在到發(fā)線上所停留的時間，其取值由圖定的列車到達(dá)時刻和出發(fā)時刻確定；為列車從出發(fā)時刻起，至該列車完全離開該進(jìn)路止所耗費的時間[4]，根據(jù)車站作業(yè)標(biāo)準(zhǔn)，為2 min[13]。

cij為列車i占用到發(fā)線j的權(quán)值，確定方法與呂紅霞[14]相同。Lij'為0-1 已知量，取值為1 時表示到發(fā)線j與到發(fā)線j'相鄰，共用同一個站臺，取值為0 時反之；Sii'為0-1 已知量，取值為1 時表示列車i與列車i'存在換乘關(guān)系，取值為0 時反之。和分別為第i列車的計劃到達(dá)和出發(fā)時刻。xij為0-1 變量，取值為1 時表示列車i占用到發(fā)線j，取值為0 時反之。hijp為0-1 變量，取值為1 時表示列車i占用到發(fā)線j時與作業(yè)p產(chǎn)生交叉干擾，取值為0 時反之。為列車i開始占用到發(fā)線的時刻；為列車i完全離開到發(fā)線的時刻。和分別為第i列車實際到達(dá)和出發(fā)時刻的估計值。

2.2 優(yōu)化模型

客運(yùn)站到發(fā)線運(yùn)用的優(yōu)化是合理安排列車到發(fā)線，使車站可以正點接發(fā)列車，避免列車由于等待到發(fā)線騰空造成的晚點，高效地完成運(yùn)輸生產(chǎn)任務(wù)。因此，客運(yùn)站到發(fā)線優(yōu)化模型的目標(biāo)函數(shù)包含縮短旅客列車在到發(fā)線的停留時間(所有到發(fā)線占用時間總和)和均衡使用到發(fā)線(到發(fā)線占用時間標(biāo)準(zhǔn)差)2 部分?？瓦\(yùn)站到發(fā)線運(yùn)用數(shù)學(xué)優(yōu)化模型如下。

公式 ⑹ 為目標(biāo)函數(shù)，表示所有到發(fā)線占用時間總和和到發(fā)線占用時間標(biāo)準(zhǔn)差之和最小。公式 ⑹ 至 ⑾ 為 約束 條件。公 式 ⑺ 至 ⑻ 表 示 在 任 何情況下，所有列車占用到發(fā)線時都必須遵循的約束。其中，公式 ⑺ 表示每列車必須且只能選擇1條到發(fā)線，該列車在出發(fā)之前不能轉(zhuǎn)移到其他到發(fā)線上；公式 ⑻ 保證同一條到發(fā)線上先后接發(fā)的2列車時的安全，避免2 種車站資源占用沖突情況，沖突示意圖如圖1 所示；公式 ⑼ 表示列車到達(dá)時刻機(jī)會約束。列車i實際到達(dá)時刻發(fā)生了波動，已不再是一個確定的值，其到達(dá)時刻是在一定置信度水平下的置信區(qū)間，約束中用其估計值；公式⑽表示交叉的疏解[13]，在同一個時間片[1]內(nèi)，接發(fā)列車的進(jìn)路不能有沖突(如列車的接發(fā)與機(jī)車出入段的交叉)，應(yīng)多組織平行作業(yè)來減少交叉干擾；公式⑾表示把存在換乘關(guān)系的列車安排在相鄰的站臺上[13]。

圖1 沖突示意圖Fig.1 Conflict diagram

因為列車進(jìn)站、出站作業(yè)時間以及在站停留時間幾乎都是固定的，且列車的到達(dá)時刻發(fā)生了波動，所以列車出發(fā)時刻的估計值可以用列車到達(dá)時間的估計值與列車占用到發(fā)線的總時間之和表示，即為此，公式 ⑻ 可以化簡為

對于列車到達(dá)時刻的機(jī)會約束，根據(jù)列車到達(dá)時間波動范圍的確定方法，將其轉(zhuǎn)化為以下對列車到達(dá)時刻進(jìn)行估計的約束

3 改進(jìn)遺傳算法

3.1 改進(jìn)遺傳算法流程

到發(fā)線的運(yùn)用優(yōu)化已經(jīng)被證明屬于NP 完全問題[11]，對該類問題的求解目前還沒有被證明的多項式時間算法，求解的難度較大，因而此類問題多采用智能算法求解。雖然考慮了列車到發(fā)時刻波動的置信區(qū)間，同時加入了機(jī)會約束，但是列車占用到發(fā)線的過程和圖定到發(fā)時刻下列車占用到發(fā)時刻的過程呈現(xiàn)一致性，因而采用智能算法求解仍然可行。因此，在常規(guī)遺傳算法中融入模擬退火(Simulated Annealing，SA)的思想，對適應(yīng)度函數(shù)和交叉算子進(jìn)行改進(jìn)，采用改進(jìn)的遺傳算法進(jìn)行求解，較好地解決經(jīng)典遺傳算法易早熟和局部搜索能力差的缺點，提高了運(yùn)行效率和求解質(zhì)量。改進(jìn)遺傳算法流程圖如圖2 所示。

圖2 改進(jìn)遺傳算法流程圖Fig.2 Improved genetic algorithm

3.2 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)求取的是極大值，并且適應(yīng)度函數(shù)的值大于或等于0。根據(jù)實際問題的特性，以目標(biāo)函數(shù)的取值作為適應(yīng)度的計算依據(jù)，并且在目標(biāo)函數(shù)中加入懲罰系數(shù)，得到以下適應(yīng)度計算公式

其中

式中：fm(x)是當(dāng)前輸入空間個體的最大值；E[f(x)]是目標(biāo)函數(shù)的均值；用fm(x)和E[f(x)]之差的歐氏范數(shù)再加上E[f(x)]作為Cmax的取值；C為懲罰系數(shù)，當(dāng)有2 列及以上列車在一個時間片內(nèi)占用同一到發(fā)線時，C= 1，否則C= 1/1000[13]。

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

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

式中：tk= 1 / ln (kt0+ 1)為當(dāng)前狀態(tài)的退火溫度；t0為初始溫度；k= 1，2，…。

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

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

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

圖3 列車到達(dá)時刻波動直方圖Fig.3 Train arrival time fluctuation histogram

4 算例分析

4.1 模型求解

為了驗證改進(jìn)遺傳算法和建立模型的準(zhǔn)確性，選取某客運(yùn)站8 : 00—12 : 00 的數(shù)據(jù)進(jìn)行驗證。該站共2 條正線，5 條到發(fā)線，其中3，5，7 號到發(fā)線固定接發(fā)下行列車；4，6 號到發(fā)線固定接發(fā)上行列車；正線I，II 分別用于下、上行列車的不停站通過。選取階段中到發(fā)的列車共46 列。種群大小為30；變異概率pm= 0.01；最大迭代次數(shù)U=500；初始溫度t0= 100，當(dāng)溫度低于10 時，采用等步長下降[17]，步長取1。

通過統(tǒng)計數(shù)據(jù)可知，由于客運(yùn)站7—9 月雨水較多，而且鐵路旅客運(yùn)輸周期性波動明顯，對車站的行車作業(yè)有較大的影響，也對車站工作計劃的魯棒性要求較高。為此，統(tǒng)計這3 個月的數(shù)據(jù)來驗證改進(jìn)遺傳算法和模型的合理性。經(jīng)統(tǒng)計，得到某站7—9 月8 : 00—12 : 00 的46 列列車的波動時間，通過假設(shè)檢驗的內(nèi)容可以得到列車到發(fā)時刻的分布，借助IBM SPSS Statistics 23 進(jìn)行驗證，樣本的均值為0.78，標(biāo)準(zhǔn)差為5.723。列車到達(dá)時刻波動直方圖如圖3 所示。

由圖3 可知，除了1 列車的時間波動以外，其余列車到達(dá)時刻的波動是近似服從正態(tài)分布的。運(yùn)用單樣本柯爾莫哥諾夫-斯米爾諾夫檢驗(K-S檢驗)對文中的假設(shè)進(jìn)行驗證，得到列車到達(dá)時刻波動的正態(tài)Q-Q 圖如圖4 所示；列車到達(dá)時刻波動的假設(shè)檢驗摘要如表1 所示。

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

表1 列車到達(dá)時刻波動的假設(shè)檢驗摘要Tab.1 Summary of hypothesis test for the train arrival time fluctuation

由圖4 可知，數(shù)據(jù)與對角線基本重合，Q—Q 圖提示該組數(shù)據(jù)服從正態(tài)分布；而單樣本K—S 檢驗數(shù)據(jù)摘要中顯著性概率0.177 ＞ 0.05，決策為“保留原假設(shè)”，即列車到達(dá)時刻的波動值服從正態(tài)分布。從現(xiàn)場得知，該客運(yùn)站高速列車的正點率是96%，因而該站列車正點到發(fā)的置信度為96%，從而得到列車到達(dá)時刻的波動范圍[-1.73，1.76]，取整后為[-2 min，2 min]。利用改進(jìn)遺傳算法為8 : 00—12 : 00 到達(dá)的列車分配到發(fā)線，運(yùn)用MATLAB 2018a在Intel Core i5-4210H CPU (2.90 GHz)，內(nèi)存4G 的計算機(jī)上求解，得到穩(wěn)定的目標(biāo)函數(shù)值為49 969 min。改進(jìn)遺傳算法優(yōu)化收斂趨勢如圖5 所示；到發(fā)線運(yùn)用方案如表2 所示。

圖5 改進(jìn)遺傳算法優(yōu)化收斂趨勢Fig.5 Improved genetic algorithm optimizes the convergence trend

表2 到發(fā)線運(yùn)用方案Tab.2 Scheme for arrival-departure tracks utilization

4.2 結(jié)果分析

（1）均衡性分析。從算例結(jié)果可以看出，所設(shè)計的模型和算法可以滿足列車在車站的作業(yè)需要，上行列車分布在4，6 股道，下行列車分布在3，5，7 股道。根據(jù)均衡性評價的定義，均衡度的計算公式為

根據(jù)公式 ⒆，分別計算車站值班員用的方案和優(yōu)化模型得到的到發(fā)線運(yùn)用方案均衡度如表3所示。

（2）波動誤差分析。隨機(jī)選取15 列列車，根據(jù)計算得到的波動值，計算列車的最早到達(dá)時刻和最晚到達(dá)時刻。波動下列車最早和最晚到達(dá)時刻如表4 所示。由表4 可知，列車在波動范圍內(nèi)占用到發(fā)線的估計最早到達(dá)時刻或最晚到達(dá)時刻與實際到達(dá)時刻的誤差ΔT1= 41 min；而不考慮列車到達(dá)時刻波動的列車到達(dá)時刻誤差ΔT2= 61 min。比較考慮波動與不考慮波動下到達(dá)時刻的誤差值可知，考慮列車到達(dá)時刻波動能更好的描述列車的實際到達(dá)時刻，波動誤差值減少了33%。

5 研究結(jié)論

（1）可以通過預(yù)估列車早晚點到達(dá)時間，提前調(diào)整到發(fā)線運(yùn)用計劃，更好地保證車站作業(yè)的安全性。改進(jìn)后算法收斂速度較快，能夠滿足車站編制計劃實時性的要求，對車站作業(yè)智能化具有一定的意義。

（2）借助改進(jìn)適應(yīng)度函數(shù)、選擇算子、交叉算子的遺傳算法，可以有效地求解到發(fā)線運(yùn)用模型。算例分析表明，改進(jìn)的遺傳算法用于解決列車到發(fā)時刻波動條件下客運(yùn)站到發(fā)線分配問題是可行的。優(yōu)化所得的方案優(yōu)于車站值班員的運(yùn)用方案，均衡性提高了82.42%，波動誤差減少了33%。

（3）在建立到發(fā)線分配模型時對問題進(jìn)行了簡化，未考慮列車大面積晚點及密集到達(dá)的情況，還應(yīng)對列車晚點且密集到達(dá)后接發(fā)車進(jìn)路的調(diào)整以及調(diào)整后列車晚點的二次傳播進(jìn)行深入研究。