離散螢火蟲算法在高速列車運(yùn)行調(diào)整中的應(yīng)用

段少楠，戴勝華

北京交通大學(xué) 電子信息工程學(xué)院，北京 100044

1 引言

列車運(yùn)行調(diào)整是鐵路行車指揮工作的基礎(chǔ)和核心[1]。列車在運(yùn)行過程中，不可避免地受到各種因素的影響使列車運(yùn)行偏離計劃線，擾亂行車秩序，影響行車效率。我國高速鐵路采用“高中速混跑”運(yùn)營模式，列車采取分級調(diào)整策略[2]，并且高速鐵路列車運(yùn)行速度快、行車密度大，對運(yùn)行調(diào)整的實(shí)時性和動態(tài)性提出了更高的要求，因此，需要采用科學(xué)的優(yōu)化方法對列車運(yùn)行圖進(jìn)行調(diào)整。

列車運(yùn)行調(diào)整是一類NP完全問題，目前求解這類問題的主要方法是最優(yōu)化方法和智能計算方法[3]。線性規(guī)劃、非線性規(guī)劃、混合整數(shù)規(guī)劃、分枝定界法、拉格朗日松弛法等最優(yōu)化方法都已在求解過程中得到應(yīng)用[4]。但采用最優(yōu)化算法解決列車運(yùn)行調(diào)整問題必須對復(fù)雜模型進(jìn)行簡化，因此計算結(jié)果與實(shí)際有較大偏差，且計算量極為龐大。解決這一問題常用的智能計算方法有遺傳算法、粒子群算法和普通啟發(fā)式算法等。遺傳算法雖然適用性強(qiáng)，計算效果較好，但是編碼相對復(fù)雜，運(yùn)算過程繁瑣且尋優(yōu)耗時多，求解速度慢。由于列車運(yùn)行調(diào)整約束眾多，搜索空間龐大，可行解范圍狹小，粒子群算法搜索緩慢易陷入死循環(huán)，難以得到最優(yōu)解[3]。普通的啟發(fā)式算法雖然計算量較小，但對全局最優(yōu)解的搜索能力不強(qiáng)，易陷入局部最優(yōu)解。

螢火蟲算法是模擬自然界中螢火蟲的發(fā)光特性而發(fā)展起來的一種新型智能優(yōu)化算法，具有較高的尋優(yōu)精度和收斂速度，是一種可行有效的優(yōu)化方法，為智能優(yōu)化提供了新思路[5]。本文針對運(yùn)行圖調(diào)整問題的特點(diǎn)，將標(biāo)準(zhǔn)螢火蟲算法進(jìn)行離散化處理，通過調(diào)整列車在給定站的發(fā)車次序來對列車運(yùn)行進(jìn)行調(diào)整。經(jīng)過計算對比，該算法可以準(zhǔn)確、快速地得到目標(biāo)函數(shù)最優(yōu)解。

2 模型建立

本次研究選擇雙線自動閉塞高速鐵路單一方向線路為研究目標(biāo)。為了反映列車在區(qū)間和車站內(nèi)晚點(diǎn)情況以及在程序設(shè)計中易于處理相關(guān)約束條件，將列車運(yùn)行圖的計劃線用到達(dá)和出發(fā)兩條線表示，并且以時間軸的形式給出，以分鐘為單位，到達(dá)線和出發(fā)線可以分成1 440個點(diǎn)[6]。如圖1所示。

2.1 變量定義

針對某一調(diào)度區(qū)段，對于列車調(diào)整模型給出如下定義：

（1）列車總列數(shù)為L。

（2）車站總數(shù)為N，則區(qū)間總數(shù)為K=N-1。

（3）Ai,k、Si,k分別為第 i(i∈{1 ,2,…,L})列車在第k(k∈{1 ,2,…,N})個車站的到達(dá)、出發(fā)時刻，則相應(yīng)的定義、為原定計劃時刻。

（5）列車等級優(yōu)先級為 μ(i),i∈{1 ,2,…,L} ，其值越大表明列車等級越高，優(yōu)先級越高，反之則優(yōu)先級越低。不同等級列車對應(yīng)的列車運(yùn)行調(diào)整權(quán)重為w(i),i∈{1 ,2,…,L}，不同等級列車在車站的作業(yè)時間為t(i),i∈{1 ,2,…,L}。不同等級的列車在車站k與車站k+1之間的最小運(yùn)行時間用表示，不同等級列車在車站k的最小作業(yè)時間用εi,k表示。

（7）定義布爾變量ψi,k表明列車通過車站的作業(yè)類型。

2.2 目標(biāo)函數(shù)

對調(diào)整策略的優(yōu)劣進(jìn)行評價有多種標(biāo)準(zhǔn)，這是由于列車晚點(diǎn)情況是有差異的，運(yùn)行調(diào)整策略也需要做出相應(yīng)的變動[7]。本文選擇按站調(diào)整的方式，以每個車站的列車發(fā)車順序?yàn)樽兓?，選擇列車在調(diào)整站點(diǎn)的下一站加權(quán)到達(dá)晚點(diǎn)時間最小為目標(biāo)函數(shù)。

2.3 約束條件

為保障行車安全及運(yùn)輸效率，列車運(yùn)行調(diào)整的范圍要受到車站最小作業(yè)時間、最小區(qū)間運(yùn)行時間、列車到達(dá)間隔、列車出發(fā)間隔等約束[8]，具體描述如下所示：

（1）越行條件：只有滿足以下條件，列車 j才可以越行列車i（其中i為前車，j為后車）：

（2）列車在兩站之間的運(yùn)行時間，需滿足列車在區(qū)間的最小運(yùn)行時分，且考慮列車的起、停附加時間：

（3）若列車在車站停車，作業(yè)時間不得小于規(guī)定的在該車站的最小作業(yè)時間：

（4）所有列車發(fā)車時間不得早于固定的發(fā)車時間；

（5）在同一個車站，前后兩列車的到達(dá)、出發(fā)時間間隔要滿足最小到達(dá)、出發(fā)時間間隔的約束[3]。

3 離散螢火蟲優(yōu)化算法

3.1 標(biāo)準(zhǔn)螢火蟲算法

2008年，Yang通過對螢火蟲個體相互吸引和移動過程的研究，提出了一種新型群體智能優(yōu)化算法，即螢火蟲算法（Firefly Algorithm，F(xiàn)A）[9]。

螢火蟲算法將搜索空間中的點(diǎn)模擬成自然界的螢火蟲個體，將搜索和優(yōu)化的過程模擬成螢火蟲個體之間的吸引和移動過程，用求解問題的目標(biāo)函數(shù)值來表示螢火蟲當(dāng)前位置的優(yōu)劣，將個體的優(yōu)勝劣汰過程類比為搜索和優(yōu)化過程中用較好可行解取代較差可行解的迭代過程。算法涉及兩個關(guān)鍵因素：螢火蟲的發(fā)光亮度和相互吸引度。螢火蟲發(fā)光亮度取決于自身所在位置的目標(biāo)值，發(fā)光亮的螢火蟲會吸引發(fā)光弱的螢火蟲向它移動，最終大多數(shù)螢火蟲會聚集在最亮的螢火蟲附近。發(fā)光越亮的螢火蟲對周圍螢火蟲的吸引度越高，若發(fā)光亮度一樣，則螢火蟲做隨機(jī)運(yùn)動。吸引度與距離成反比，即距離越大吸引度越小[10]。

算法描述如下：

首先建立螢火蟲i的絕對亮度Ii和目標(biāo)函數(shù)值之間的關(guān)系，一般直接用目標(biāo)函數(shù)值來代表螢火蟲的絕對亮度，即：

假設(shè)螢火蟲i絕對亮度大于螢火蟲 j，則螢火蟲 j被螢火蟲i吸引而向螢火蟲i移動。螢火蟲i對螢火蟲j的吸引力βi,j為：

其中，β0為最大吸引力，通常為1；γ為光吸收系數(shù)，γ∈[0 . 01,100]；ri,j為螢火蟲i到螢火蟲 j的笛卡爾距離，即：

其中d為變量的維數(shù)。

由于螢火蟲 j被螢火蟲i吸引而向螢火蟲i移動，則螢火蟲 j的位置更新公式為：

其中t為迭代次數(shù)；Xi、Xj為螢火蟲i和 j所處的空間位置；α為步長因子，是[0 , 1]上的常數(shù)；εj是均勻分布的隨機(jī)數(shù)向量，用于加大搜索區(qū)域，避免過早陷入局部最優(yōu)[11]。

3.2 算法離散化

標(biāo)準(zhǔn)螢火蟲算法采用笛卡爾距離，適用于連續(xù)空間中的尋優(yōu)，本文通過優(yōu)化列車發(fā)車順序來得到目標(biāo)函數(shù)最優(yōu)解，屬于組合優(yōu)化問題，因此需要對算法進(jìn)行離散化處理，主要從距離計算、移動方式和擾動機(jī)制三方面進(jìn)行改動。

對于每一個需要優(yōu)化的站點(diǎn)，用總加權(quán)到站晚點(diǎn)時間的倒數(shù)作為螢火蟲的絕對亮度，每個螢火蟲表示本站所有列車的一種可能的發(fā)車順序，如Xi=[1 , 2,3,4,5]。在離散螢火蟲算法中，使用漢明距離來度量兩個螢火蟲序列之間的距離，即序列中相同位置元素不同的個數(shù)。例如Xi=[1 , 2,3,4,5]，Xj=[1 , 2,4,3,5]，其漢明距離為2。對于兩個相互吸引的螢火蟲個體，在進(jìn)行移動時需要先將其相同位置元素相同的值對應(yīng)保存下來，對兩者元素不相同的位置，每次生成一個[0,1]區(qū)間內(nèi)的隨機(jī)數(shù)r，如果r＜β，則該位置取亮度高的螢火蟲的元素，否則取亮度低的螢火蟲的元素，其中β為螢火蟲之間的吸引力。如果所選取元素和前面已選元素重復(fù)，則先將該位置留空，直到序列全部選擇完畢，再將剩余未選擇元素，依次分配給這些留空的位置[12]。

3.3 變鄰域擾動機(jī)制

為了避免螢火蟲算法陷入局部最優(yōu)，需要在螢火蟲移動之后加入擾動量。本文參考螢火蟲算法在TSP問題中的應(yīng)用，在搜索過程中采用變鄰域的擾動機(jī)制，系統(tǒng)地改變螢火蟲的鄰域，從而拓展搜索范圍[13]。

根據(jù)運(yùn)行圖調(diào)整的求解特點(diǎn)，文中應(yīng)用了兩種鄰域結(jié)構(gòu)：

（1）Insert鄰域，在解序列中隨機(jī)選取不同車次的列車x和y，其中x＜y，把列車x的發(fā)車次序插入列車y的發(fā)車次序之后，得到新的次序排列。例如Xi=[1,2,3,4,5]，隨機(jī)得到x=2，y=4，則調(diào)整之后Xi=[1,3,4,2,5]。

（2）Swap鄰域，在解序列中隨機(jī)選擇不同車次的列車x和y，互換這兩次列車的發(fā)車次序。例如Xi=[1,2,3,4,5]，隨機(jī)得到x=2，y=4，則調(diào)整之后Xi=[1,4,3,2,5]。

3.4 算法流程

應(yīng)用離散螢火蟲算法求解運(yùn)行圖調(diào)整問題的基本步驟如下：

步驟1按站進(jìn)行查詢，對比實(shí)際到站時間和計劃到站時間，得到首次晚點(diǎn)車站k和首次晚點(diǎn)列車序號i。

步驟2針對該存在晚點(diǎn)情況的車站，初始化算法基本參數(shù)，包括螢火蟲數(shù)目m、光強(qiáng)吸收系數(shù)γ、最大迭代次數(shù)Tmax。隨機(jī)初始化每只螢火蟲的初始解序列，即保持正點(diǎn)列車發(fā)車順序不變，對首次晚點(diǎn)列車及其后所有列車的發(fā)車順序進(jìn)行隨機(jī)設(shè)置。

步驟3按照約束條件（1）對每只螢火蟲對應(yīng)的發(fā)車次序進(jìn)行重新調(diào)整，然后按照調(diào)整后的發(fā)車順序和約束條件（3）、（4）、（5）計算所有列車在該車站的實(shí)際發(fā)車時間 Si,k,i∈{1,2,…,L}。

步驟4根據(jù)列車在車站k的實(shí)際發(fā)車時間Si,k和計劃發(fā)車時間確定晚點(diǎn)列車，在車站k和k+1之間的區(qū)間，晚點(diǎn)列車按照最小區(qū)間運(yùn)行時分運(yùn)行，其余列車正常運(yùn)行，最后按照約束條件（2）、（5）計算得到所有列車在k+1站的實(shí)際到站時間Ai,k+1,i∈{1,2,…,L}。

步驟5 根據(jù)w(i),i∈{1,2,…,L}、Ai,k+1,i∈{1,2,…,L}計算調(diào)整后的每個發(fā)車順序?qū)?yīng)的函數(shù)值，并按照吸引和移動原則進(jìn)行移動。

步驟6對移動后的螢火蟲進(jìn)行變鄰域搜索，選擇兩種鄰域中的一種進(jìn)行隨機(jī)擾動，重復(fù)執(zhí)行n次，選擇目標(biāo)函數(shù)值最優(yōu)的位置作為螢火蟲的當(dāng)前位置。

步驟7對更新后的所有螢火蟲的目標(biāo)函數(shù)值進(jìn)行排序，并與當(dāng)前最優(yōu)解進(jìn)行比較，如果更優(yōu)則更新最優(yōu)解。

步驟8如果最優(yōu)解滿足結(jié)束條件，則跳出循環(huán)，輸出本站的調(diào)整結(jié)果，對下一站點(diǎn)進(jìn)行調(diào)整，否則跳到步驟5繼續(xù)搜索。

步驟9如果調(diào)整執(zhí)行到最后一個車站或者最優(yōu)解為0則調(diào)整結(jié)束，否則對下一個車站繼續(xù)步驟2。

4 算例分析

4.1 數(shù)據(jù)整理

為了驗(yàn)證離散螢火蟲算法的先進(jìn)性，本文選取文獻(xiàn)[14]提供的算例，利用本文所提出的算法對文獻(xiàn)[14]中的算例進(jìn)行重新計算，將得到的結(jié)果與文獻(xiàn)[14]提出的啟發(fā)式算法進(jìn)行對比。

文獻(xiàn)[14]算例中計劃運(yùn)行時刻表如表1所示。針對晚點(diǎn)情況設(shè)定了3個參數(shù)：首次晚點(diǎn)發(fā)生的區(qū)間m，該區(qū)間初始晚點(diǎn)的列車n以及列車晚點(diǎn)時間s。這里的晚點(diǎn)時間表示的是列車在區(qū)間運(yùn)行過程中的實(shí)際運(yùn)行時分比計劃運(yùn)行時分多出的部分。本次算例，設(shè)置m=3，n=6，s=25。采用文獻(xiàn)[14]中提到的啟發(fā)式算法得到的晚點(diǎn)發(fā)生后的列車運(yùn)行時刻表如表2所示。

該算例的已知條件如下：

有4種等級的14輛列車，對應(yīng)的等級矩陣為μ(i)=[2，2，2，3，3，4，4，4，4，4，1，1，1，1]。14輛車對應(yīng)權(quán)重為w(i)=[0.3，0.3，0.3，0.2，0.2，0.1，0.1，0.1，0.1，0.1，0.4，0.4，0.4，0.4]。為了便于計算，設(shè)第一個站的第一列車發(fā)車時間為0，后續(xù)時間以“min”為單位。例如，按照計劃運(yùn)行圖，列車在5號站點(diǎn)計劃與實(shí)際到站時間分別為：=[109，115，121，156，162，204，210，216，222，228，261，267，273，279]，Ai,5=[109，115，121，156，162，221，227，233，239，245，261，267，273，279]。各車站最小出發(fā)時間間隔=6 min；各車站最小到達(dá)時間間隔=6 min；4種等級的列車在5個區(qū)間的最小運(yùn)行時間矩陣以及在6個站的最小作業(yè)時間矩陣分別為：

4.2 算例設(shè)計

列車運(yùn)行圖調(diào)整有按站調(diào)整和按車調(diào)整兩種方式，本文以及文獻(xiàn)[14]均是采用按站調(diào)整的方法，即重新設(shè)置經(jīng)過某個車站的所有列車的到達(dá)時刻與出發(fā)時刻，通過區(qū)間的調(diào)整冗余度來降低晚點(diǎn)列車所受到的影響[15]。

對于每一個車站，如果所有列車進(jìn)站時間及站內(nèi)作業(yè)時間已知，一旦確定各個列車的發(fā)車順序，即可知道每列車的發(fā)車時間。將發(fā)車時間和計劃發(fā)車時間進(jìn)行比較之后得到晚點(diǎn)列車車次，然后晚點(diǎn)的列車通過在區(qū)間的快速運(yùn)行來減少或者消除晚點(diǎn)，最終使運(yùn)行圖恢復(fù)計劃狀態(tài)。

本次研究的目標(biāo)函數(shù)是調(diào)整站點(diǎn)的下一站加權(quán)到達(dá)晚點(diǎn)時間最小。本次算例選取6個站中的某一個站，例如利用第5站的到站時間計算第5站的發(fā)車順序然后得到第5站的發(fā)車時間和第6站的到達(dá)時間。其他站的情況類似，在文章中不再贅述。

表1 計劃時刻表

表2 啟發(fā)式算法調(diào)整結(jié)果

表3 啟發(fā)式算法和螢火蟲算法在第五站的計算結(jié)果

4.3 計算結(jié)果對比

4.3.1 啟發(fā)式算法

通過表1和表2對比可得，在第5站共有5輛列車發(fā)生晚點(diǎn)，需要在該站點(diǎn)對發(fā)車順序進(jìn)行調(diào)整使得在6號站點(diǎn)總加權(quán)晚點(diǎn)時間最小。按照文獻(xiàn)[14]中提出的啟發(fā)式算法的計算結(jié)果如表3所示。

根據(jù)第5站計劃發(fā)車次序和實(shí)際發(fā)車次序，可以看到為了降低晚點(diǎn)時間，高優(yōu)先級的11、12、13、14號列車對低優(yōu)先級的8、9、10號列車進(jìn)行了站內(nèi)越行。目標(biāo)函數(shù)為6號站點(diǎn)的加權(quán)到達(dá)晚點(diǎn)時間，由實(shí)際到達(dá)時間和計劃到達(dá)時間計算得到。

4.3.2 離散螢火蟲算法

由于高等級的列車可以站內(nèi)越行低等級的列車，因此在5號站點(diǎn)對列車的發(fā)車次序進(jìn)行改變可以得到不同的目標(biāo)函數(shù)值。利用離散螢火蟲算法對解空間進(jìn)行搜索可以得到最優(yōu)的發(fā)車順序。

算法參數(shù)設(shè)置：螢火蟲數(shù)目m=30，最大迭代次數(shù)Tmax=20，最大吸引力β0=1，光強(qiáng)吸收系數(shù)γ=1，變鄰域搜索中兩種鄰域選用概率相同，均為0.5，變鄰域搜索執(zhí)行次數(shù)n=4，得到計算結(jié)果如表3所示。

4.3.3 結(jié)果分析

通過表3的對比，可以看到使用離散螢火蟲算法計算之后，高等級的11、12、13、14號列車只對9、10號列車進(jìn)行了站內(nèi)越行，而沒有對晚點(diǎn)20 min的8號低等級列車進(jìn)行越行。該算法計算得到的目標(biāo)函數(shù)值優(yōu)于普通啟發(fā)式算法，準(zhǔn)確找到的問題的最優(yōu)解。為了驗(yàn)證算法的穩(wěn)定性，作者還對該算例使用離散螢火蟲算法進(jìn)行多次計算，結(jié)果表明計算結(jié)果均可以在較少的迭代次數(shù)內(nèi)達(dá)到收斂，得到該問題的最優(yōu)解。

5 結(jié)束語

本文針對列車運(yùn)行調(diào)整這類特殊的NP完全問題，建立對應(yīng)的數(shù)學(xué)模型，通過對標(biāo)準(zhǔn)螢火蟲算法進(jìn)行改進(jìn)，提出一種離散的螢火蟲算法（DFA）對列車運(yùn)行調(diào)整模型進(jìn)行求解。采用Matlab編程，通過對比普通啟發(fā)式算法和離散螢火蟲算法的目標(biāo)函數(shù)值，發(fā)現(xiàn)離散螢火蟲算法收斂速度快、目標(biāo)函數(shù)的最優(yōu)解精度高，從而證明了該算法對解決列車運(yùn)行調(diào)整問題具有一定優(yōu)勢。