肖 云

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

1 引言

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

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

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

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

2 原理

2.1 螢火蟲算法機理

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

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

其中，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ù)，一種可能的方式是分配螢火蟲光強的比例。 假設位于x'的螢火蟲i 比位于x的螢火蟲j明亮。那么位于x 的螢火蟲將向螢火蟲i移動，但是A0由下公式得出：

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

3 基于改進螢火蟲算法的鐵路運行調度

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

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

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

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

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

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

3.2 調度算法流程

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

圖2 改進FA調度鐵路運輸流程

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

4 仿真實驗

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

4.1 第一個測試問題

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

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

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

圖3 第一個測試問題的仿真結果

4.2 第二個測試問題

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

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

圖4 第二個測試問題的仿真結果

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

5 結語

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