基于改進螢火蟲算法的鐵路運行調(diào)度算法研究?

肖 云

（陜西能源職業(yè)技術(shù)學院 咸陽 712000）

1 引言

鐵路交通系統(tǒng)是我國運輸系統(tǒng)的重要組成部分，它為客運和貨運提供主要的運輸服務。交通運輸部門正在努力減少公路運輸達到降低交通污染的目的，同時適當增加鐵路使用量。與此同時，可用鐵路系統(tǒng)部分過飽和，造成了主要路段的調(diào)度困難。

鐵路運行調(diào)度通常被認為是一個工程難題，主要原因在于它的超大規(guī)模路網(wǎng)和數(shù)量巨大的火車之間的復雜關(guān)系。鐵路網(wǎng)與道路交通網(wǎng)絡一樣細，火車超車和相遇的選擇性非常有限，取決于可用的側(cè)軌、交換機、信號設(shè)施和火車的特點等多種因素。Chang，S-C，Sahin等針對鐵路調(diào)度提出了不同模型的優(yōu)化策略，包括優(yōu)化、排隊、仿真方法等［1～4］。

目前求解鐵路運行調(diào)度的方法主要有準確式算法、引導式算法和智能算法等［5～6］。準確式算法能夠得到待求問題的確切答案，缺點就是只能得出某些具體小問題的解［7］。引導式算法可以迅速得到所求問題的答案，缺點是答案不精確而且算法結(jié)構(gòu)復雜［8］。智能算法可以在較短時間內(nèi)得到較為可靠的答案，是一些生產(chǎn)調(diào)度問題的常用算法［9～10］。螢火蟲算法是一種近年來被發(fā)明的仿生智能算法，類似蟻群、遺傳等智能算法［11］。它是通過模擬螢火蟲發(fā)光的特性演變而來的一種計算方法，具有架構(gòu)簡便、并行處理能力強、收斂迅速等特點。多用于一些物流調(diào)配、經(jīng)濟預測等領(lǐng)域［12～13］，鐵路運行調(diào)度領(lǐng)域的應用尚未見于國內(nèi)文獻中。

本文的目的是對鐵路交通調(diào)度算法進行研究。通過分析螢火蟲算法的機理，提出改進型螢火蟲算法，在此基礎(chǔ)上應用算法求解鐵路運行調(diào)度問題，通過典型案例進行了仿真驗證，證明了算法的有效性，并將其與傳統(tǒng)調(diào)度進行了對比，利用改進螢火蟲算法的調(diào)度結(jié)果明顯優(yōu)于傳統(tǒng)調(diào)度方法。

2 原理

2.1 螢火蟲算法機理

螢火蟲算法（FA）是針對優(yōu)化問題的智能算法，它于2009 年由Yang 在劍橋大學提出［14］。該算法是受夜間螢火蟲閃爍行為的啟發(fā)，共三條規(guī)則。螢火蟲都是中性的，這就意味著任何螢火蟲都可以被其他較亮的螢火蟲吸引，這是螢火蟲算法的規(guī)則之一；第二條規(guī)則是螢火蟲的亮度是由編碼的目標函數(shù)確定的；第三條規(guī)則是吸引力與亮度成正比，但隨著距離的增加而減小，螢火蟲會朝著更亮的一方移動，如果沒有較亮的一方，它會隨機移動。

為了正確設(shè)計FA，需要定義兩個重要問題：光強的變化和吸引力的表述。從基本物理學中可以清楚地看出，光線的強度與距離的平方成反比。此外，當光通過介質(zhì)時，光強隨著距離變化的公式如下：

其中，r 為距離，λ 為吸收系數(shù)，I0為初始光強，I為變化光強。進一步細化可得到：

因為，計算1/(1+λr2)比e-λr2更容易，所以為了降低計算量，式（2）可改寫為

那么，螢火蟲的吸引力可以定義為

其中A0為r=0 時的吸引力。如果一只位于的螢火蟲比另一只位于x=(x1，x2，…，xn)的螢火蟲更亮，位于x 的螢火蟲將朝向x'。位于x 的螢火蟲的位置更新可用下面的公式表達：

其中α 是一個隨機參數(shù)，0 ≤α ≤1，ε 是一個隨機向量，根據(jù)文獻［15］，在實際應用中，取A0=1。

2.2 改進的螢火蟲算法

從螢火蟲算法的機理可知，最明亮的螢火蟲則是最優(yōu)解。如果這個最亮的螢火蟲向標準螢火蟲算法那樣隨機移動，它的亮度可能會隨著方向的改變而降低。這會導致迭代算法的性能下降。然而，如果允許最明亮的螢火蟲在其亮度提高的方向上移動，則不會在迭代過程中降低算法的性能。本文作如下改進，為了確定最亮螢火蟲的運動方向，首先隨機生成單位向量m，定義為u1，u2…um。然后在生成的向量中選擇一個方向U，如果螢火蟲向方向U 移動，最亮螢火蟲的亮度則增加。因此，最明亮的螢火蟲的運動可以描述如下：

其中α 是一個隨機步長。如果在隨機生成的解決方案中不存在這樣的方向，最亮的螢火蟲將保持其當前位置。此外，并不是對于每一個螢火蟲i 都取Ai0=1，而是基于螢火蟲的光強分配吸引力，吸引力又取決于目標函數(shù)，一種可能的方式是分配螢火蟲光強的比例。 假設(shè)位于x'的螢火蟲i 比位于x的螢火蟲j明亮。那么位于x 的螢火蟲將向螢火蟲i移動，但是A0由下公式得出：

其中I0' 是螢火蟲i在r=0時的光強，I0是螢火蟲j在r=0時的光強，I0≠0。通過調(diào)整A0，則可以有效縮短迭代步長，提高運算效率。

3 基于改進螢火蟲算法的鐵路運行調(diào)度

3.1 鐵路運行調(diào)度數(shù)學描述

鐵路運行調(diào)度的核心問題是如何解決占用沖突，當兩列或更多列車想要同時占用同一部分鐵路網(wǎng)絡時，則為占用沖突。鐵路網(wǎng)通常分為幾個區(qū)塊（即單獨的軌道區(qū)段），每個區(qū)塊一般只能容納一列火車，以維持所需要的安全等級（稱為線路阻塞）。因為線路阻塞，不允許兩列火車靠得太近。要解決沖突，不僅要考慮到處在沖突中的兩列火車，而且還要考慮其對周圍其他火車的影響，因為沖突可能是相互依賴的?？紤]的因素主要包括網(wǎng)絡結(jié)構(gòu)、流量和數(shù)量火車類型。

雙向（雙向交通）單軌道的鐵路線路阻塞如圖1 所示。當火車1 從站5 出發(fā)時，暫時發(fā)生故障并延遲。鐵路運輸中不允許兩列火車同時使用一個火車站（即火車站4 和火車站5 之間），由于火車1的時間表錯亂從而導致火車2 必須延遲，圓圈表示只能遵循違背最初設(shè)定的火車的時間表。相反，火車2 必須等待火車1 這會導致其他的沖突，并可能延誤第3 和第4 列火車，具體取決于調(diào)度算法如何解決。

圖1 鐵路運輸網(wǎng)中站1與站7之間的火車“時間-距離”示意

基于上述問題，最優(yōu)調(diào)度方案就是尋找一個解，使得當前鐵路網(wǎng)中相關(guān)火車干擾最小化，即堵塞延遲時間最短。一個典型的最小化問題可以用下式表示：

其中S 為鐵路網(wǎng)中10 列火車的“時間-距離”的集合。 f(x)為S中的最小值，調(diào)度算法的目的就是尋找一個x*（x*∈S）使得f(x*)≤f(x)。

3.2 調(diào)度算法流程

基于改進的FA 尋找x*的算法流程如圖2 所示。

圖2 改進FA調(diào)度鐵路運輸流程

根據(jù)圖2 算法流程，得到的x*即為最優(yōu)解，表示圖1鐵路網(wǎng)中10輛火車的堵塞時間最小，即為最優(yōu)調(diào)度。

4 仿真實驗

本文選擇兩個測試問題來測試改進螢火蟲算法對鐵路運行調(diào)度的效果，并與標準螢火蟲算法進行對比。測試問題為隨機和多模態(tài)。對于每個測試問題，隨機生成相同的初始解集，其吸收系數(shù)λ等于2，改進的螢火蟲算法的局部搜索隨機方向的數(shù)量是10，迭代次數(shù)設(shè)置為500。

4.1 第一個測試問題

假設(shè)圖1中火車運行滿足函數(shù)關(guān)系式：

其中x1為發(fā)生故障的火車，x2為受x1干擾最大的火車，f1即為堵塞時間最小值。兩列火車的堵塞會影響前后兩個站點的鐵路運輸，那么有-2 ≤x1，x2≤2。這是眾所周知的基準最優(yōu)化問題之一，具有許多局部最優(yōu)性。利用改進后的螢火蟲算法和標準螢火蟲算法來尋找最小f1（絕對值），結(jié)果如圖3所示。

運行程序后，使用標準螢火蟲算法和改進后的螢火蟲算法得到的解決方案分別為-0.1239和-0.0001，顯然改進后的螢火蟲算法得到的解更好，而且改進螢火蟲算法迭代步數(shù)更少，表明其收斂速度快。

圖3 第一個測試問題的仿真結(jié)果

4.2 第二個測試問題

又假設(shè)圖1中火車運行滿足函數(shù)關(guān)系式：

其中x1為發(fā)生故障的火車，x2為受x1干擾最大的火車，要堵塞時間短，換言之就是受干擾的火車離故障火車距離遠，f2即為距離最大值。同樣，兩列火車的堵塞會影響前后兩個站點的鐵路運輸，那么有-2 ≤x1，x2≤2。這是一個全局解決方案的優(yōu)化問題。利用改進后的螢火蟲算法和標準螢火蟲算法來尋找最大f2，結(jié)果如圖4所示。

圖4 第二個測試問題的仿真結(jié)果

根據(jù)仿真結(jié)果，標準螢火蟲算法得出的結(jié)果為0.9782，而改進后的螢火蟲算法得出的結(jié)果為1，顯然改進后螢火蟲算法得到的結(jié)果更優(yōu)，而且其迭代步數(shù)也更少。

5 結(jié)語

本文在分析螢火蟲機理的基礎(chǔ)上，通過隨機生成方向，指引最亮的螢火蟲朝此方向移動，如果在隨機生成的方向中找不到這樣的方向，它將保持在當前位置，同時計算每個螢火蟲此時的吸引力，達到改進螢火蟲算法的目的。然后解釋了鐵路運行調(diào)度的數(shù)學描述，在此基礎(chǔ)上，針對鐵路運輸中的常見堵塞問題，假設(shè)了兩個函數(shù)關(guān)系，利用改進螢火蟲算法和標準螢火蟲算法分別尋找最優(yōu)解，仿真結(jié)果表明改進的螢火蟲算法比標準螢火蟲算法迭代次數(shù)少，得到的解更優(yōu)，驗證了改進螢火蟲算法應用在鐵路運行調(diào)度中的效果，為鐵路運輸領(lǐng)域的應用提供理論算法依據(jù)。