基于改進蟻群算法的客運站到發(fā)線運用優(yōu)化研究

王林杰

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

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

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

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

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

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

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

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

2.1 模型構建

設客運車站站臺集合為Q={1，2，…，q,…,u}，其q為車站站臺的編號順序，u為站臺數(shù)量總和；設列車集合P={1,2,…,p,…,m}，其中p為列車到站的編號順序，m為列車數(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)化是為了列車能夠正點、準時和安全地完成車站內的各項客運作業(yè)，在不影響其他線路和列車的作業(yè)計劃前提下，高效地完成路局下達的運輸生產任務，同時要考慮到旅客的滿意度，提高為旅客服務的質量。因此，為了使高鐵車站高效、安全地完成運輸生產任務，以所有在站列車占用到發(fā)線時間最優(yōu)和均衡使用到發(fā)線為目標。建模如下

(2)

2.3 條件約束

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

(1)某列車占用某條到發(fā)線，該列車不得轉入其他到發(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è)來減小交叉干擾。約束條件如下

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

(6)

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

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

(7)

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

(8)

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

3.1 AOC算法改進

(1)改進初始信息素。

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

(9)

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

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

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

(10)

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

(11)

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

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

(12)

其中：

(13)

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

(4)改進狀態(tài)轉移規(guī)律。

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

(14)

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

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

(15)

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

3.2 AOC算法流程

引入車站到發(fā)線時間片概念，改進的蟻群算法求解到發(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ā)線選擇。假設螞蟻k在t時刻上，此時列車在i到發(fā)線選擇節(jié)點上，利用公式(14)由τij和α計算出到下一到發(fā)線節(jié)點的選擇路徑，在t+1時刻上到發(fā)線節(jié)點選擇根據(jù)公式(14)計算出。

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

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

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

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

4 算例分析

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

圖1 改進蟻群算法收斂曲線

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

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

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

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

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

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

(3)到發(fā)線占用時間標準差。

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

5 結束語

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