李 濤，韓建鵬

LI Tao, HAN Jianpeng

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

0 引言

為了更好地完成運(yùn)輸任務(wù)，客運(yùn)站必須嚴(yán)格按照本站的作業(yè)計(jì)劃進(jìn)行作業(yè)，而階段計(jì)劃是車(chē)站作業(yè)計(jì)劃的核心，是對(duì)班計(jì)劃的分階段部署，也是編制調(diào)車(chē)作業(yè)計(jì)劃的主要依據(jù)[1]。到發(fā)線(xiàn)的合理運(yùn)用是客運(yùn)站行車(chē)作業(yè)的一項(xiàng)重要內(nèi)容，是車(chē)站編制階段計(jì)劃的關(guān)鍵工作之一。因此，建立鐵路客運(yùn)站到發(fā)線(xiàn)運(yùn)用優(yōu)化模型并且設(shè)計(jì)相應(yīng)的算法進(jìn)行求解，對(duì)客運(yùn)站編制到發(fā)線(xiàn)運(yùn)用計(jì)劃有非常重要的 意義。

為了高效、合理地運(yùn)用到發(fā)線(xiàn)，保證接發(fā)車(chē)作業(yè)的安全，許多學(xué)者對(duì)到發(fā)線(xiàn)的運(yùn)用優(yōu)化進(jìn)行了研究。呂紅霞等[2]根據(jù)客運(yùn)站作業(yè)的特點(diǎn)建立了客運(yùn)站到發(fā)線(xiàn)運(yùn)用的0-1 規(guī)劃模型，基于最小最大螞蟻的思想，設(shè)計(jì)蟻群算法對(duì)問(wèn)題求解。高建[3]結(jié)合旅客列車(chē)在客運(yùn)站的作業(yè)特點(diǎn)，以出發(fā)旅客列車(chē)正點(diǎn)為目標(biāo)，同時(shí)考慮到發(fā)線(xiàn)的固定使用方案及高等級(jí)列車(chē)優(yōu)先，建立了客運(yùn)站到發(fā)線(xiàn)運(yùn)用的混合0-1 整數(shù)規(guī)劃模型，運(yùn)用模擬退火算法進(jìn)行求解。何林等[4]以均衡、合理運(yùn)用到發(fā)線(xiàn)為原則，建立了高速鐵路客運(yùn)站到發(fā)線(xiàn)運(yùn)用的0-1 規(guī)劃模型，采用遺傳算法求解。謝楚農(nóng)等[5]通過(guò)分析客運(yùn)站旅客列車(chē)到發(fā)技術(shù)作業(yè)，把研究問(wèn)題分為方便旅客乘降、保證行車(chē)作業(yè)安全、有效使用車(chē)站既有設(shè)備3 個(gè)子目標(biāo)，建立到發(fā)線(xiàn)運(yùn)用優(yōu)化模型，采用分枝定界算法對(duì)模型進(jìn)行求解。林志安等[6]以行車(chē)交叉干擾最小、方便旅客乘降、均衡使用到發(fā)線(xiàn)為優(yōu)化目標(biāo)，建立到發(fā)線(xiàn)運(yùn)用優(yōu)化的整數(shù)規(guī)劃模型，設(shè)計(jì)了基于捕食策略的禁忌搜索算法對(duì)問(wèn)題進(jìn)行求解。吳鵬等[7]以到發(fā)線(xiàn)的固定使用、均衡使用到發(fā)線(xiàn)、旅客走行距離最短為優(yōu)化目標(biāo)，建立多目標(biāo)0-1 規(guī)劃模型，利用功效系數(shù)法將多目標(biāo)同一量綱轉(zhuǎn)化為單目標(biāo)函數(shù)，利用LINGO 軟件進(jìn)行求解。青學(xué)江等[8]建立了區(qū)段站到發(fā)線(xiàn)運(yùn)用優(yōu)化模型，采用遺傳算法進(jìn)行求解。雖然模型考慮了多個(gè)方面，但是算法運(yùn)行時(shí)間為25min，不能滿(mǎn)足算法實(shí)時(shí)性的要求。張英貴等[9]引入時(shí)間窗、權(quán)重、有限度3 個(gè)參數(shù)和柔性理論，建立車(chē)站到發(fā)線(xiàn)運(yùn)用的柔性模型，求解采用解改進(jìn)策略和人—機(jī)交互式算法。Kroon 等[10]在已知車(chē)站布局和列車(chē)到發(fā)時(shí)間的前提下，從安全角度出發(fā)，將問(wèn)題看成是節(jié)點(diǎn)裝箱問(wèn)題，建立整數(shù)規(guī)劃模型，運(yùn)用特定的預(yù)處理規(guī)劃減小可行性問(wèn)題的實(shí)例大小，采用動(dòng)態(tài)規(guī)劃的方法進(jìn)行求解。目前，上述研究大部分是針對(duì)技術(shù)站到發(fā)線(xiàn)的運(yùn)用研究，而對(duì)客運(yùn)站到發(fā)線(xiàn)運(yùn)用的研究相對(duì)較少，考慮在呂紅霞等[2]、高建[3]、何林等[4]研究到發(fā)線(xiàn)固定使用方案的基礎(chǔ)上兼顧到發(fā)線(xiàn)的均衡使用，同時(shí)引入懲罰因子并改進(jìn)適應(yīng)度函數(shù)來(lái)提高運(yùn)行效率、加快模型收斂的速度。為了更好地實(shí)現(xiàn)車(chē)站作業(yè)智能化和算法的實(shí)時(shí)性，在謝楚農(nóng)等[5]、吳鵬等[7]、青學(xué)江等[8]研究的基礎(chǔ)上采用模擬退火遺傳算法對(duì)問(wèn)題進(jìn)行求解。

1鐵路客運(yùn)站到發(fā)線(xiàn)運(yùn)用優(yōu)化模型構(gòu)建

1.1 問(wèn)題描述

隨著列車(chē)運(yùn)行速度和列車(chē)等級(jí)的提高，列車(chē)運(yùn)行圖不斷調(diào)整，列車(chē)開(kāi)行密度增加，并且在車(chē)站的技術(shù)作業(yè)時(shí)間減少，為了按時(shí)按點(diǎn)的接發(fā)旅客列車(chē)，必須編制良好的作業(yè)計(jì)劃，而到發(fā)線(xiàn)的運(yùn)用又是客運(yùn)站行車(chē)作業(yè)的一項(xiàng)重要內(nèi)容。到發(fā)線(xiàn)的運(yùn)用優(yōu)化問(wèn)題是一個(gè)具有時(shí)間和空間二維特性的組合優(yōu)化問(wèn)題[11]，其合理運(yùn)用不僅關(guān)系車(chē)站的正常運(yùn)輸生產(chǎn)和運(yùn)行圖的實(shí)現(xiàn)，還關(guān)系到鐵路行車(chē)安全和列車(chē)運(yùn)行的經(jīng)濟(jì)效益。對(duì)一個(gè)客運(yùn)站來(lái)說(shuō)，到發(fā)線(xiàn)運(yùn)用計(jì)劃是規(guī)定車(chē)站在某一階段內(nèi)到發(fā)場(chǎng)線(xiàn)路的具體使用計(jì)劃，為了方便車(chē)站值班員接發(fā)列車(chē)，到發(fā)線(xiàn)一般固定使用。到發(fā)線(xiàn)的運(yùn)用要保證客運(yùn)站可以不間斷地接發(fā)列車(chē)，最大限度地利用車(chē)站每一條線(xiàn)路的能力，同時(shí)也得留有一定的余地，避免高峰時(shí)段由于一列列車(chē)晚點(diǎn)而不能為其后列車(chē)安排進(jìn)路，使其后列車(chē)在進(jìn)站信號(hào)機(jī)外停車(chē)等線(xiàn)。如果某一時(shí)段列車(chē)到達(dá)強(qiáng)度超過(guò)車(chē)站的接發(fā)車(chē)能力或出現(xiàn)早晚點(diǎn)情況，這時(shí)將不能再按固定方案使用到發(fā)線(xiàn)，應(yīng)該按到發(fā)線(xiàn)的備用方案接發(fā)列車(chē)，將等級(jí)相對(duì)較高的列車(chē)和早點(diǎn)的列車(chē)接入滿(mǎn)足時(shí)間安全間隔的線(xiàn)路。盡量按照《車(chē)站行車(chē)工作細(xì)則》規(guī)定的固定方案接發(fā)列車(chē)，減少行調(diào)作業(yè)交叉。所有占用到發(fā)線(xiàn)的列車(chē)都應(yīng)遵循以下條件。

（1）同一時(shí)間內(nèi)一條到發(fā)線(xiàn)只可以接或發(fā)一列列車(chē)或不接列車(chē)。

（2）一條到發(fā)線(xiàn)一旦被某一列列車(chē)占用，直到出發(fā)，該列車(chē)中途不得轉(zhuǎn)到另一條到發(fā)線(xiàn)上。

（3）先后占用同一條到發(fā)線(xiàn)的2 列列車(chē)，必須滿(mǎn)足接發(fā)列車(chē)的最小安全時(shí)間間隔要求。

1.2 模型構(gòu)建

設(shè)某客運(yùn)站到發(fā)線(xiàn)的集合為D= {1，2，…，j，…，m}，其中j為第j條到發(fā)線(xiàn)的編號(hào)，m為到發(fā)線(xiàn)的總數(shù)；計(jì)劃階段到達(dá)客運(yùn)站的列車(chē)集合L= {1，2，…，i，…，n}，其中i為第i列列車(chē)到達(dá)車(chē)站的順序，n為列車(chē)總數(shù)。目標(biāo)函數(shù)從縮短旅客列車(chē)在到發(fā)線(xiàn)的停留時(shí)間和均衡使用到發(fā)線(xiàn)2 個(gè)方面考慮(用每條到發(fā)線(xiàn)占用時(shí)間總和與各到發(fā)線(xiàn)平均占用時(shí)間之差的方差來(lái)衡量)。

式中：xij為0-1 變量，xij= 1 表示列車(chē)i占用到發(fā)線(xiàn)j，否則xij= 0；tki為列車(chē)i開(kāi)始占用到發(fā)線(xiàn)的時(shí)間；tei為列車(chē)i完全離開(kāi)到發(fā)線(xiàn)的時(shí)間；為第i列列車(chē)占用到發(fā)線(xiàn)的總時(shí)間為信號(hào)員或值班員為第i列列車(chē)排列進(jìn)路以及列車(chē)完全?？吭诘桨l(fā)線(xiàn)上所耗費(fèi)的時(shí)間[5]；為列車(chē)從完全?？吭诘桨l(fā)線(xiàn)起至出發(fā)時(shí)刻止，列車(chē)在到發(fā)線(xiàn)上所耗費(fèi)的時(shí)間；為列車(chē)從出發(fā)時(shí)刻起至該列車(chē)完全離開(kāi)該徑路止所耗費(fèi)的時(shí)間[5]。根據(jù)車(chē)站作業(yè)標(biāo)準(zhǔn)，和均取2min，由列車(chē)的到達(dá)時(shí)刻和出發(fā)時(shí)刻確定)；cij為列車(chē)i占用到發(fā)線(xiàn)j的權(quán)值大小，其權(quán)值的確定與呂紅霞[11]確定方法類(lèi)似。

模型的約束條件如下。

（1）同一時(shí)間內(nèi)一條到發(fā)線(xiàn)只可以接或發(fā)一列列車(chē)或不接發(fā)列車(chē)。

（2）一條到發(fā)線(xiàn)一旦被某一列列車(chē)占用，直到出發(fā)，該列車(chē)中途不得轉(zhuǎn)到其他到發(fā)線(xiàn)上。

（3）同一條到發(fā)線(xiàn)上接發(fā)相鄰列車(chē)時(shí)須滿(mǎn)足最小安全時(shí)間間隔的要求[11]，最小安全時(shí)間間隔如圖1 所示。

圖1 最小安全時(shí)間間隔Fig.1 Minimum safe interval

具體約束如下。

式中：T為前后兩列列車(chē)占用同一條到發(fā)線(xiàn)時(shí)，后續(xù)列車(chē)i+ 1 接車(chē)時(shí)刻與前車(chē)i完全離開(kāi)該股道的最小安全時(shí)間間隔，文中T值取10 min。

（4）交叉的疏解[12]。在同一個(gè)時(shí)間片[2]內(nèi)，接發(fā)列車(chē)的進(jìn)路不能有沖突(如列車(chē)的接發(fā)與機(jī)車(chē)出入段的交叉)，應(yīng)多組織平行作業(yè)來(lái)減少交叉干擾，具體約束如下。

式中：當(dāng)列車(chē)i占用到發(fā)線(xiàn)j時(shí)與作業(yè)p產(chǎn)生交叉干擾時(shí)hijp= 1，否則取hijp= 0。

（5）如果存在換乘的列車(chē)，應(yīng)盡可能將其安排在相鄰的站臺(tái)上[13]，具體約束如下。

式中：為0-1 變量，= 1 表示到發(fā)線(xiàn)j與到發(fā)線(xiàn)j′相鄰，共用一個(gè)站臺(tái)，反之則在不同站臺(tái)[13]；為0-1 變量，= 1 表示列車(chē)i與列車(chē)i′存在換乘關(guān)系，反之則不存在[13]。

（6）行包作業(yè)量大的列車(chē)應(yīng)接入靠近有行包通道的站臺(tái)。

式中：Hi,B= 1 為列車(chē)有行包、郵政作業(yè)，反之Hi,B= 0；Sj,B= 1 為到發(fā)線(xiàn)靠近行包、郵政通道，反之，Sj,B= 0；M取值為10。

2案例求解算法

在實(shí)際生產(chǎn)中，出于對(duì)車(chē)站生產(chǎn)指揮的需要，因而對(duì)算法的實(shí)時(shí)性要求較高。而到發(fā)線(xiàn)的運(yùn)用優(yōu)化已被證明屬于NP 完全問(wèn)題[14]，對(duì)該類(lèi)問(wèn)題的求解目前還沒(méi)有確認(rèn)的多項(xiàng)式時(shí)間算法，因而增加了求解的難度，故此類(lèi)問(wèn)題多采用啟發(fā)式算法求解。雖然遺傳算法擁有強(qiáng)大的全局最優(yōu)解搜索能力，但局部搜索能力差，容易造成早熟，不能保證算法快速收斂；模擬退火算法具有較強(qiáng)的魯棒性，其以一種概率的方式進(jìn)行搜索，局部搜索能力強(qiáng)，但把握搜索過(guò)程的能力不強(qiáng)，過(guò)程中還會(huì)遺失最優(yōu)解，從而使模擬退火算法的能力不高，因而采用模擬退火遺傳算法來(lái)提高運(yùn)行效率和求解質(zhì)量。

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

（1）染色體編碼。染色體的長(zhǎng)度由車(chē)站到發(fā)線(xiàn)的數(shù)量確定，對(duì)車(chē)站在編制計(jì)劃階段到達(dá)的旅客列車(chē)按時(shí)間先后進(jìn)行排序，用空格表示列車(chē)，空格對(duì)應(yīng)的下標(biāo)為相應(yīng)列車(chē)的編號(hào)，空格中的數(shù)字表示所占股道。

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

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

（3）初始溫度的選取 。生成初始種群pop(0)后，設(shè)該種群中最大的目標(biāo)函數(shù)值為fmax，最小目標(biāo)函數(shù)值為fmin。初始溫度t0由t0= -Δf/ lnnc確定，其中-Δf=fmax－fmin，nc為初始接受概率，0 ＜nc＜ 1，如nc= 0.8，nc= 0.9 等。

（4）溫度下降方法 。用tk+1=λtk來(lái)控制整個(gè)算法的終止，其中tk是前一狀態(tài)的溫度。模擬退火遺傳算法的最終溫度為1 且最大迭代次數(shù)超過(guò)給定的次數(shù)U。給定一個(gè)比較小的ε和U，當(dāng)溫度tk≤ε且l＞U時(shí)，算法終止。

2.2 算法流程

步驟1：給定種群大小popsize，k= 0；初始溫度tk=t0，隨機(jī)產(chǎn)生群體pop(k)并檢驗(yàn)解的可行性；求各解的適應(yīng)度F(s)，并找出最優(yōu)適應(yīng)度F(s*)，最優(yōu)解s*=s。

步驟2：進(jìn)行選擇、交叉、變異操作，并檢查解的可行性。

步驟3：計(jì)算最優(yōu)適應(yīng)度F(s*)與新解所對(duì)應(yīng)適應(yīng)度的差ΔF，然后根Metropolic 準(zhǔn)則判斷是否接受新解，如果ΔF≥0，則接受s作為新的解；如果ΔF≤0，以概率接受s作為新的解。判斷l(xiāng)≤U是否滿(mǎn)足，如果滿(mǎn)足，轉(zhuǎn)步驟2；如果不滿(mǎn)足，轉(zhuǎn)步驟4。

步驟4：tk＜ε是否滿(mǎn)足，如果滿(mǎn)足，轉(zhuǎn)步驟6；如果不滿(mǎn)足，轉(zhuǎn)步驟5。

步驟5：tk+1=λtk，k=k+ 1，轉(zhuǎn)步驟2。

步驟6：輸出最優(yōu)結(jié)果。

2.3 算例求解

為了驗(yàn)證文中提出的算法和建立模型的準(zhǔn)確性，算例選取客運(yùn)站8 : 00—12 : 00 的數(shù)據(jù)進(jìn)行驗(yàn)證。選取階段中到發(fā)的列車(chē)共46 列，該站共2 條正線(xiàn)，5 條到發(fā)線(xiàn)，其中 3，5，7 號(hào)到發(fā)線(xiàn)固定接發(fā)下行列車(chē)；4，6 號(hào)到發(fā)線(xiàn)固定接發(fā)上行列車(chē)；正線(xiàn)I、II 分別用于下、上行列車(chē)的不停站通過(guò)。文中i，j，n，m，p等變量的取值均為正整數(shù)。參數(shù)取值：種群規(guī)模popsize= 30；交叉概率pc= 0.75；變異概率pm= 0.01；最大迭代次數(shù)U= 500；初始溫度t0= 100，當(dāng)溫度低于10 時(shí)，采用等步長(zhǎng)下 降[15]，步 長(zhǎng) 取1；nc= 0.8，λ= 0.9，ε= 3×10-6。運(yùn)用MatlabR 2018a 進(jìn)行求解，最后目標(biāo)函數(shù)值穩(wěn)定為31 018 min，通過(guò)整理迭代所得數(shù)據(jù)，得到到發(fā)線(xiàn)運(yùn)用計(jì)劃，到發(fā)線(xiàn)運(yùn)用方案如表1 所示。

從算例結(jié)果可以看出，文中所設(shè)計(jì)的模型和算法可以滿(mǎn)足列車(chē)在車(chē)站的作業(yè)需要，使上行列車(chē)分布在4，6 股道，下行列車(chē)分布在3，5，7 股道；而車(chē)站值班員的方案中將一列上行始發(fā)的列車(chē)接入了3 道，沒(méi)實(shí)現(xiàn)分方向接發(fā)列車(chē)。根據(jù)上文對(duì)均衡性評(píng)價(jià)的定義，均衡度為然后分別計(jì)算車(chē)站值班員的方案和優(yōu)化所得方案的均衡度，均衡度統(tǒng)計(jì)如表2 所示。

表1 到發(fā)線(xiàn)運(yùn)用方案Tab.1 Operation plan for arrival and departure tracks

表2 均衡度統(tǒng)計(jì)Tab.2 Balance degree statistics

3研究結(jié)論

通過(guò)對(duì)鐵路客運(yùn)站到發(fā)線(xiàn)運(yùn)用優(yōu)化進(jìn)行研究，較全面地考慮了到發(fā)線(xiàn)分配的影響因素，建立了到發(fā)線(xiàn)運(yùn)用優(yōu)化模型，并根據(jù)模型特點(diǎn)設(shè)計(jì)模擬退火遺傳算法進(jìn)行求解，最后通過(guò)算例對(duì)模型和算法進(jìn)行驗(yàn)證，得到以下研究結(jié)論。

（1）考慮到發(fā)線(xiàn)固定使用方案的同時(shí)，兼顧到發(fā)線(xiàn)運(yùn)用的均衡性，所得方案不僅可以保證行車(chē)安全，而且可以使列車(chē)均衡的占用到發(fā)線(xiàn)，從而提高車(chē)站設(shè)備的利用效率。

（2）綜合考慮模擬退火算法和遺傳算法的優(yōu)點(diǎn)和不足，設(shè)計(jì)模擬退火遺傳算法對(duì)問(wèn)題進(jìn)行求解，并且在適應(yīng)度函數(shù)中加入懲罰因子，有效地求解了模型。算例表明，該算法在解決到發(fā)線(xiàn)運(yùn)用優(yōu)化問(wèn)題上是可行的，收斂速度較快，能夠滿(mǎn)足車(chē)站編制計(jì)劃實(shí)時(shí)性的要求，這對(duì)車(chē)站作業(yè)智能化具有一定意義。

（3）按圖定到發(fā)時(shí)刻對(duì)到發(fā)線(xiàn)運(yùn)用優(yōu)化進(jìn)行研究，由于各種不確定因素使得列車(chē)到發(fā)時(shí)刻與圖定時(shí)刻有所差異，因而在后續(xù)研究中可對(duì)列車(chē)到發(fā)時(shí)刻不確定的情況進(jìn)行研究。