王林杰

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

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

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

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

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

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

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

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

2.1 模型構(gòu)建

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

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

(1)

2.2 優(yōu)化模型

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

(2)

2.3 條件約束

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

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

(3)

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

(4)

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

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

(5)

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

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

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

(6)

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

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

(7)

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

(8)

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

3.1 AOC算法改進(jìn)

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

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

(9)

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

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

信息素更新主要描繪了螞蟻分泌的化學(xué)物質(zhì)隨時(shí)間的變化規(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ā)式信息是與下個(gè)節(jié)點(diǎn)到終點(diǎn)的距離成反比，這樣有助于螞蟻選擇最優(yōu)的路徑。但是如果不考慮當(dāng)前位置和下個(gè)位置的狀況，螞蟻選擇的路徑不一定為最優(yōu)路徑，而且在算法搜索后期為了加快算法收斂速度，會(huì)影響啟發(fā)式信息對路徑選擇的指導(dǎo)作用。本文采用引入阻尼系數(shù)來改進(jìn)啟發(fā)式信息，如公式(12)所示

(12)

其中：

(13)

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

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

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

(14)

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

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

(15)

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

3.2 AOC算法流程

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

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

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

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

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時(shí)，可由當(dāng)前Lbest,NCmax,dSE通過公式(15)計(jì)算出q0。

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

4 算例分析

為了驗(yàn)證算法和模型的可行性，采用定西北站的運(yùn)行圖數(shù)據(jù)，選用高鐵客運(yùn)站9∶00～12∶00的數(shù)據(jù)來計(jì)算驗(yàn)證。在此時(shí)間段內(nèi)共有18列車在該站辦理旅客乘降作業(yè)，該站共有2條正線，4條到發(fā)線，2個(gè)站臺(tái)。其中第I，II號(hào)為正線，只辦理通過作業(yè)；第3，5號(hào)到發(fā)線接下行列車；第4，6號(hào)到發(fā)線接上行列車；1，2號(hào)站臺(tái)分別分布在4，6和3，4之間。因?yàn)樵撥囌旧舷滦械桨l(fā)線都是同等級(jí)的，所以本文中的列車占用到發(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代的時(shí)候找到最優(yōu)值?？梢钥闯龈倪M(jìn)的算法具有良好的收斂效果，可以滿足求解更加復(fù)雜的大規(guī)模尋優(yōu)問題。

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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