王林杰

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

隨著我國高鐵的蓬勃發(fā)展，截止2020年9月，“八縱八橫”高鐵網(wǎng)絡(luò)主骨架已搭建七成，2020年底我國高鐵里程達(dá)到38 000 km。高速鐵路具有發(fā)車間隔小、作業(yè)時間短、作業(yè)過程簡單以及列車開行密度大、進(jìn)出站頻率高等特點，因此對車站客運服務(wù)質(zhì)量和列車正點率要求較高。到發(fā)線的運用直接關(guān)系著站場能力的利用，合理、高效地運用到發(fā)線能夠促進(jìn)客運站安全、順利地完成各項客運作業(yè)。

關(guān)于到發(fā)線的優(yōu)化問題有很多學(xué)者做了研究。部分研究把客運站優(yōu)化問題劃分為3個子目標(biāo)問題，其中謝楚農(nóng)等[1]建立了多目標(biāo)模型，并且使用分支定界法來求解模型；郭吉安等[2]建立以均衡運用到發(fā)線、縮短旅客走行距離和減小列車在站作業(yè)時間為多目標(biāo)的優(yōu)化模型。林志安[3]等用捕食禁忌搜索算法來求解模型。部分研究建立了0-1整數(shù)規(guī)劃的非線性客運站優(yōu)化模型，可以自動制定車站到發(fā)線的運用計劃，但沒有考慮到發(fā)線的均衡性問題。呂紅霞等[4]建立了0-1整數(shù)到發(fā)線優(yōu)化模型，并采用了蟻群算法求解。何林[5]等引用時間片理念，以旅客走行距離最小為目標(biāo)，規(guī)定了到發(fā)線權(quán)值大小，并以最大權(quán)值為目標(biāo)建立了車站到發(fā)線運用模型。李琦[6]以旅客服務(wù)質(zhì)量為目標(biāo)，通過使用自適應(yīng)克隆算法來優(yōu)化其模型。青學(xué)江等主要研究了區(qū)段站到發(fā)線的優(yōu)化問題，并采用遺傳算法來求解模型。李濤等通過改進(jìn)遺傳算法來解決高鐵客運站的到發(fā)線優(yōu)化模型，改進(jìn)算法達(dá)到了較好的效果。部分研究以優(yōu)化到發(fā)線的排序為目標(biāo)建立了優(yōu)化模型。

以上研究大多數(shù)是基于普通的優(yōu)化算法來求解的，這些方法求解過程復(fù)雜而且效率很低，無法解決更復(fù)雜的數(shù)學(xué)模型。也有部分研究是基于智能算法來優(yōu)化模型，但這些智能算法對于復(fù)雜的大規(guī)模模型，收斂速度較慢，針對一些特大規(guī)模的高鐵車站，無法實現(xiàn)客運站的智能化目標(biāo)。為了實現(xiàn)鐵路客運站作業(yè)智能化，通過改進(jìn)蟻群算法的初始信息素、信息素更新規(guī)則、啟發(fā)式信息和狀態(tài)轉(zhuǎn)移規(guī)律來解決大規(guī)模的優(yōu)化問題，算法收斂速度很快，能夠快速、高效、準(zhǔn)確地求解，找到較優(yōu)的到發(fā)線運用計劃。

1 列車占用到發(fā)線問題分析

到發(fā)線運用是指在一定時間內(nèi)，根據(jù)列車種類及作業(yè)性質(zhì)，考慮各種時間標(biāo)準(zhǔn)的限制并協(xié)調(diào)咽喉進(jìn)路，為圖定旅客列車分配合適的作業(yè)股道、停靠站臺并規(guī)定其相應(yīng)的占用時間安排每列車合理地使用到發(fā)線，保證所有列車都能夠按時完成作業(yè)計劃。因此到發(fā)線的使用需要滿足以下約束條件：(1)同一時間一條到發(fā)線只能接發(fā)1列車；(2)站臺兩側(cè)的到發(fā)線應(yīng)不同時安排其他列車在站作業(yè)；(3)占用同一到發(fā)線的相鄰列車應(yīng)該滿足的最小安全間隔要求；(4)有換乘關(guān)系的兩列車盡量安排在同站臺停靠；(5)為車站方便、高效的組織作業(yè)，應(yīng)該按照到發(fā)線的固定方案使用；(6)到發(fā)線使用時應(yīng)盡量減少交叉干擾。上述條件是鐵路安全作業(yè)的根本保障，在日常鐵路生產(chǎn)中必須滿足。

2 到發(fā)線運用優(yōu)化模型構(gòu)建

合理的到發(fā)線運用計劃有利于保證列車不間斷接發(fā)車，減少列車等待時間，合理分配車站設(shè)備能力，相互較少列車作業(yè)交叉干擾，保證列車順利、安全、高效地通過車站且快速、合理地完成旅客乘降作業(yè)。所以到發(fā)線的運用優(yōu)化可以從均衡使用車站設(shè)備、提高行車作業(yè)、提高旅客服務(wù)質(zhì)量3個方面為目標(biāo)進(jìn)行研究。

2.1 模型構(gòu)建

設(shè)客運車站站臺集合為Q={1，2，…，q,…,u}，其q為車站站臺的編號順序，u為站臺數(shù)量總和；設(shè)列車集合P={1,2,…,p,…,m}，其中p為列車到站的編號順序，m為列車數(shù)量的總和；設(shè)到發(fā)線集合K={1,2,…,k,…,n}，其中k為車站到發(fā)線的編號順序，n為到發(fā)線數(shù)量的總和。

列車占用到發(fā)線狀態(tài)用決策變量0-1來表示，xpk為到站列車p占用到發(fā)線的狀態(tài)，取值表示為

(1)

2.2 優(yōu)化模型

車站到發(fā)線運用計劃的優(yōu)化是為了列車能夠正點、準(zhǔn)時和安全地完成車站內(nèi)的各項客運作業(yè)，在不影響其他線路和列車的作業(yè)計劃前提下，高效地完成路局下達(dá)的運輸生產(chǎn)任務(wù)，同時要考慮到旅客的滿意度，提高為旅客服務(wù)的質(zhì)量。因此，為了使高鐵車站高效、安全地完成運輸生產(chǎn)任務(wù)，以所有在站列車占用到發(fā)線時間最優(yōu)和均衡使用到發(fā)線為目標(biāo)。建模如下

(2)

2.3 條件約束

根據(jù)到發(fā)線運用的基本原則與車站其他設(shè)備對其的限制，服從以下約束。

(1)某列車占用某條到發(fā)線，該列車不得轉(zhuǎn)入其他到發(fā)線上直至列車離開車站。約束條件如下

(3)

(2)同一時間一條到發(fā)線只能接發(fā)1列車。約束條件如下

(4)

(3)同一到發(fā)線接發(fā)相鄰列車時需滿足最小安全間隔時間。約束條件如下：

|x(p+1)kts(p+1)-xpktep|≥T

(5)

式中：T為相鄰列車占用同一到發(fā)線的最小安全間隔時間，本文取值為10 min。

(4)到發(fā)線使用時應(yīng)盡量減少交叉干擾。組織平行作業(yè)來減小交叉干擾。約束條件如下

xpk≤1-hpkjp=1,2,…,m;k=1,2,…,m

(6)

式中：當(dāng)p列車占用到發(fā)線k與其他作業(yè)j相互產(chǎn)生干擾時，hpkj=1，否則hpkj=0。

(5)有換乘關(guān)系的兩列車盡量安排在同站臺停靠。約束條件如下

(7)

(6)兩相鄰站臺同側(cè)到發(fā)線的列車應(yīng)當(dāng)滿足一定的時間間隔，防止旅客檢票進(jìn)站時兩流線相互干擾。約束條件如下

(8)

3 改進(jìn)蟻群優(yōu)化算法

3.1 AOC算法改進(jìn)

(1)改進(jìn)初始信息素。

基本AOC算法在初始階段信息素是一個定值，螞蟻在初始搜索時具有盲目性，會導(dǎo)致搜索時間加長。因此提出一種信息素改進(jìn)的方法，根據(jù)目前節(jié)點、下一節(jié)點與起點之間的位置距離計算初始信息值，公式如下

(9)

式中：dSE為從起點到終點的距離；dSi為從出發(fā)點到目前節(jié)點的距離；dij為目前節(jié)點到下一節(jié)點的距離；djE為下一節(jié)點到終點的距離；α0為常數(shù)；C為下一節(jié)點的集合。從上面公式可以看出當(dāng)分母越小，信息素越大。為了避免算法在初始時盲目搜索，改善搜索效率，提出了根據(jù)相互位置關(guān)系設(shè)定初始信息素的不均衡分布。

(2)改進(jìn)信息素更新規(guī)則。

信息素更新主要描繪了螞蟻分泌的化學(xué)物質(zhì)隨時間的變化規(guī)律。蟻群在完成一次搜索循環(huán)后進(jìn)行更新路徑。全部的螞蟻完成迭代后，所有的路徑信息素都將更新，可以在所有的路徑上找到最差結(jié)果與最優(yōu)結(jié)果，如公式(10)所示，由當(dāng)前結(jié)果可以對后續(xù)的迭代進(jìn)行指導(dǎo)。最差的解將可以對其表述處理，加快了算法的收斂速度。

(10)

式中：Lbest為目前最優(yōu)路徑的長度；Lworst為目前最差路徑的長度；為了防止算法停止，將信息素的范圍設(shè)定為[τmin,τmax]，如公式(11)所示

(11)

(3)改進(jìn)啟發(fā)式信息。

基本AOC算法的啟發(fā)式信息是與下個節(jié)點到終點的距離成反比，這樣有助于螞蟻選擇最優(yōu)的路徑。但是如果不考慮當(dāng)前位置和下個位置的狀況，螞蟻選擇的路徑不一定為最優(yōu)路徑，而且在算法搜索后期為了加快算法收斂速度，會影響啟發(fā)式信息對路徑選擇的指導(dǎo)作用。本文采用引入阻尼系數(shù)來改進(jìn)啟發(fā)式信息，如公式(12)所示

(12)

其中：

(13)

式中：NCmax為迭代次數(shù)的最大設(shè)定值，NC為目前的迭代次數(shù)。

(4)改進(jìn)狀態(tài)轉(zhuǎn)移規(guī)律。

使用偽隨機狀態(tài)轉(zhuǎn)移規(guī)律來改善算法質(zhì)量和搜索效率。假設(shè)在t時刻螞蟻k在i節(jié)點，那么螞蟻k在t+1時刻的節(jié)點位置為

(14)

式中：q0為狀態(tài)轉(zhuǎn)移規(guī)律的轉(zhuǎn)換率，取值在0-1之間；q為隨機自然數(shù)，當(dāng)q≤q0時，下個節(jié)點的位置直接由啟發(fā)式信息和最大的信息素濃度值來確定。

隨機選擇模式的概率與確定性選擇由q0直接決定。采用自適應(yīng)計算q0的算法，q0的值由迭代次數(shù)Nc和最優(yōu)路徑的長度Lbest來計算，如公式(15)所示

(15)

式中：b為0-1之間的常數(shù)；N0為迭代次數(shù)閾值。

3.2 AOC算法流程

引入車站到發(fā)線時間片概念，改進(jìn)的蟻群算法求解到發(fā)線運用流程如下：

Step1：參數(shù)初始化。包含的參數(shù)有螞蟻數(shù)量m、算法最大迭代次數(shù)NCmax、起始位置S、蟻群信息素強度Q、信息素啟發(fā)式因子α、期望啟發(fā)式因子β等。m取100，NCmax取100，Q取200。

Step2：算初始信息素。常數(shù)α0取0.5，將dsi,dij,djE分別代入基本算法公式中計算。

Step3：到發(fā)線選擇。假設(shè)螞蟻k在t時刻上，此時列車在i到發(fā)線選擇節(jié)點上，利用公式(14)由τij和α計算出到下一到發(fā)線節(jié)點的選擇路徑，在t+1時刻上到發(fā)線節(jié)點選擇根據(jù)公式(14)計算出。

Step4：啟發(fā)式信息和信息素的更新。當(dāng)完整的到發(fā)線路徑被建立后，將對啟發(fā)式信息和信息素更新，將Δτij(t),ρ,1-ρ根據(jù)基本算法公式更新信息素，再根據(jù)公式(12)更新啟發(fā)式信息。

Step5：全局更新信息素。當(dāng)蟻群中所有的螞蟻搜索完成一次后，找出此迭代過程中的最差和最優(yōu)到發(fā)線路徑，然后由基本算法公式和式(10)調(diào)整最優(yōu)和最差到發(fā)線上的信息素。

Step6：自適應(yīng)調(diào)整q0。當(dāng)Nc大于N0時，可由當(dāng)前Lbest,NCmax,dSE通過公式(15)計算出q0。

Step7：搜索結(jié)束。判斷是否滿足最優(yōu)條件，如滿足，輸出最優(yōu)解；否則將禁忌清單清除，使得Nc=Nc+1，轉(zhuǎn)到step3繼續(xù)計算。

4 算例分析

為了驗證算法和模型的可行性，采用定西北站的運行圖數(shù)據(jù)，選用高鐵客運站9∶00～12∶00的數(shù)據(jù)來計算驗證。在此時間段內(nèi)共有18列車在該站辦理旅客乘降作業(yè)，該站共有2條正線，4條到發(fā)線，2個站臺。其中第I，II號為正線，只辦理通過作業(yè)；第3，5號到發(fā)線接下行列車；第4，6號到發(fā)線接上行列車；1，2號站臺分別分布在4，6和3，4之間。因為該車站上下行到發(fā)線都是同等級的，所以本文中的列車占用到發(fā)線的權(quán)值cpk都設(shè)為1。蟻群規(guī)模為m=100，最大迭代次數(shù)NCmax=100，信息素啟發(fā)式因子α=0.8，期望啟發(fā)式因子β=2.5。常數(shù)Q=200。算法在matlab2016b中求解，最終最優(yōu)解穩(wěn)定在6 967.56。由于0-1整數(shù)規(guī)劃為離散型函數(shù)，目標(biāo)值的收斂曲線如圖1所示。模型收斂速度很快，在第51代的時候找到最優(yōu)值?？梢钥闯龈倪M(jìn)的算法具有良好的收斂效果，可以滿足求解更加復(fù)雜的大規(guī)模尋優(yōu)問題。

圖1 改進(jìn)蟻群算法收斂曲線

通過整理數(shù)據(jù)得到該站的到發(fā)線運用計劃，列車序號是根據(jù)列車的到站時間先后排列的，如表1所示。

表1 客運站9∶00～12∶00的到發(fā)線運用計劃

從該算例的結(jié)果可以看出，在目標(biāo)函數(shù)最優(yōu)的情況下上行列車均勻分布在4，6股道，下行列車均勻分布在3，5股道上，上下行列車均勻的分布在每條股道上，達(dá)到了到發(fā)線的均衡使用要求。主要用到發(fā)線占用率、占用時長標(biāo)準(zhǔn)差和各占用時間來評價到發(fā)線適應(yīng)性指標(biāo)。

表2 各到發(fā)線在9∶00～12∶00的占用累積時間

(1)到發(fā)線占用率。

(2)各條到發(fā)線在9∶00～12∶00的平均被使用時間。

(3)到發(fā)線占用時間標(biāo)準(zhǔn)差。

從上面計算的各項指標(biāo)結(jié)果可以看出，每條到發(fā)線的利用效率比較高。模型和算法能夠滿足列車在車站按時按點地完成作業(yè)，用改進(jìn)的蟻群算法可以快速地找到滿足條件最優(yōu)方案，為將來新建車站制定到發(fā)線運用計劃提供一種參考方法。

5 結(jié)束語

在已有研究的基礎(chǔ)上，采用相應(yīng)的模型和算法來研究車站到發(fā)線運用計劃，建立了以均衡使用到發(fā)線和列車在到發(fā)線停留時間最短為目標(biāo)的0-1整數(shù)非線性規(guī)劃模型，且采用改進(jìn)蟻群算法進(jìn)行求解，最后根據(jù)算例結(jié)果可以看出模型和算法能夠快速地找到滿足條件的方案。但目前是根據(jù)列車運行圖的圖定時間來研究的，沒有考慮列車正晚點的影響，而且未考慮特殊情況下因出現(xiàn)大客流而導(dǎo)致列車密集到達(dá)的情況，該模型無法提供到發(fā)線運用計劃的臨時調(diào)整，在后期的研究中可以深入探究。