段少楠，戴勝華

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

1 引言

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

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

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

2 模型建立

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

2.1 變量定義

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

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

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

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

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

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

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

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

2.3 約束條件

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

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

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

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

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

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

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

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

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

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

算法描述如下：

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

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

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

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

由于螢火蟲(chóng) j被螢火蟲(chóng)i吸引而向螢火蟲(chóng)i移動(dòng)，則螢火蟲(chóng) j的位置更新公式為：

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

3.2 算法離散化

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

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

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

為了避免螢火蟲(chóng)算法陷入局部最優(yōu)，需要在螢火蟲(chóng)移動(dòng)之后加入擾動(dòng)量。本文參考螢火蟲(chóng)算法在TSP問(wèn)題中的應(yīng)用，在搜索過(guò)程中采用變鄰域的擾動(dòng)機(jī)制，系統(tǒng)地改變螢火蟲(chó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)用離散螢火蟲(chóng)算法求解運(yùn)行圖調(diào)整問(wèn)題的基本步驟如下：

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

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

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

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

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

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

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

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

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

4 算例分析

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

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

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

該算例的已知條件如下：

有4種等級(jí)的14輛列車，對(duì)應(yīng)的等級(jí)矩陣為μ(i)=[2，2，2，3，3，4，4，4，4，4，1，1，1，1]。14輛車對(duì)應(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]。為了便于計(jì)算，設(shè)第一個(gè)站的第一列車發(fā)車時(shí)間為0，后續(xù)時(shí)間以“min”為單位。例如，按照計(jì)劃運(yùn)行圖，列車在5號(hào)站點(diǎn)計(jì)劃與實(shí)際到站時(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ā)時(shí)間間隔=6 min；各車站最小到達(dá)時(shí)間間隔=6 min；4種等級(jí)的列車在5個(gè)區(qū)間的最小運(yùn)行時(shí)間矩陣以及在6個(gè)站的最小作業(yè)時(shí)間矩陣分別為：

4.2 算例設(shè)計(jì)

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

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

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

表1 計(jì)劃時(shí)刻表

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

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

4.3 計(jì)算結(jié)果對(duì)比

4.3.1 啟發(fā)式算法

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

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

4.3.2 離散螢火蟲(chóng)算法

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

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

4.3.3 結(jié)果分析

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

5 結(jié)束語(yǔ)

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