基于改進蟻群算法的客運站到發(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整數規(guī)劃的非線性客運站優(yōu)化模型，可以自動制定車站到發(fā)線的運用計劃，但沒有考慮到發(fā)線的均衡性問題。呂紅霞等[4]建立了0-1整數到發(fā)線優(yōu)化模型，并采用了蟻群算法求解。何林[5]等引用時間片理念，以旅客走行距離最小為目標，規(guī)定了到發(fā)線權值大小，并以最大權值為目標建立了車站到發(fā)線運用模型。李琦[6]以旅客服務質量為目標，通過使用自適應克隆算法來優(yōu)化其模型。青學江等主要研究了區(qū)段站到發(fā)線的優(yōu)化問題，并采用遺傳算法來求解模型。李濤等通過改進遺傳算法來解決高鐵客運站的到發(fā)線優(yōu)化模型，改進算法達到了較好的效果。部分研究以優(yōu)化到發(fā)線的排序為目標建立了優(yōu)化模型。

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

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

到發(fā)線運用是指在一定時間內，根據列車種類及作業(yè)性質，考慮各種時間標準的限制并協調咽喉進路，為圖定旅客列車分配合適的作業(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為站臺數量總和；設列車集合P={1,2,…,p,…,m}，其中p為列車到站的編號順序，m為列車數量的總和；設到發(fā)線集合K={1,2,…,k,…,n}，其中k為車站到發(fā)線的編號順序，n為到發(fā)線數量的總和。

列車占用到發(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 條件約束

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

(9)

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

(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ā)式信息對路徑選擇的指導作用。本文采用引入阻尼系數來改進啟發(fā)式信息，如公式(12)所示

(12)

其中：

(13)

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

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

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

(14)

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

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

(15)

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

3.2 AOC算法流程

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

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

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

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

Step4：啟發(fā)式信息和信息素的更新。當完整的到發(fā)線路徑被建立后，將對啟發(fā)式信息和信息素更新，將Δτij(t),ρ,1-ρ根據基本算法公式更新信息素，再根據公式(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 算例分析

為了驗證算法和模型的可行性，采用定西北站的運行圖數據，選用高鐵客運站9∶00～12∶00的數據來計算驗證。在此時間段內共有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，最大迭代次數NCmax=100，信息素啟發(fā)式因子α=0.8，期望啟發(fā)式因子β=2.5。常數Q=200。算法在matlab2016b中求解，最終最優(yōu)解穩(wěn)定在6 967.56。由于0-1整數規(guī)劃為離散型函數，目標值的收斂曲線如圖1所示。模型收斂速度很快，在第51代的時候找到最優(yōu)值。可以看出改進的算法具有良好的收斂效果，可以滿足求解更加復雜的大規(guī)模尋優(yōu)問題。

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

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

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

從該算例的結果可以看出，在目標函數最優(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整數非線性規(guī)劃模型，且采用改進蟻群算法進行求解，最后根據算例結果可以看出模型和算法能夠快速地找到滿足條件的方案。但目前是根據列車運行圖的圖定時間來研究的，沒有考慮列車正晚點的影響，而且未考慮特殊情況下因出現大客流而導致列車密集到達的情況，該模型無法提供到發(fā)線運用計劃的臨時調整，在后期的研究中可以深入探究。