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

徐虎

(西安鐵路職業技術學院 機電工程系， 西安 710016)

0 引言

鐵路運輸在我國經濟發展中發揮了巨大作用，隨著經濟的發展和社會的進步，對鐵路運輸提出更多要求，鐵路列車的合理調度對提高鐵路運輸能力、調度能力和組織能力具有重要意義。目前，列車調度是基于列車運行圖進行調度和調整的，由于隨機因素和不確定因素的影響，鐵路列車容易出現時刻偏差的問題，因此對列車進行優化調度和調整，可以實現列車的合理調度，在確保列車安全運行的前提下，使得鐵路運行列車上行時間差和下行時間誤差的總和最小。

1 改進的螢火蟲算法

螢火蟲算法[1](Firefly Algorithm，FA)是用螢火蟲個體模擬搜索空間的點，利用螢火蟲自身的趨光性，將尋優問題轉化成為尋找螢火蟲群體中亮度最大的螢火蟲。每次迭代，找到亮度最大的螢火蟲，通過螢火蟲之間的吸引和移動實現螢火蟲位置的更新。

螢火蟲i向亮度更強的螢火蟲j移動更新規則如[2]式(1)。

Xi=Xi+β(r)×(Xj-Xi)+αεi

(1)

與其他群智能算法類似，FA算法在算法尋優后期階段容易在局部最優或者全局最優附近反復振蕩，陷入局部最優，為改進局部最優問題，將慣性權重引入FA算法，提出一種改進的螢火蟲算法(Improved Firefly Algorithm，IFA)，慣性權重如式(2)[3]。

(2)

其中，wmax、wmin分別表示最大和最小權重；t、Tmax分別表示當前迭代次數和最大迭代次數。IFA算法的位置更新公式如式(3)。

Xi=wXi+β(r)×(Xj-Xi)+αεi

(3)

2 列車運行圖

列車運行圖是列車運行調度的基礎，通過坐標原理描述刻畫列車運行的時間和空間關系，通過列車運行圖可以直觀地顯示列車在各個車站通過或者停車的狀態，其規定了各次列車運行區間的順序，列車在區間運行時間，列車在每個車站到達、出發或通過時刻以及列車在車站的停靠時間和列車在折返站折返所需時間等[4]。

列車運行圖中如如圖1所示。

圖1 列車運行圖

橫坐標、豎直線和縱坐標分別表示時間、時分線和車站距離；橫直線和斜線分別表示站名線和列車運行線，前者表示各個車站到發線中心的位置，而后者是運行線和水平線的交點表示列車到站時間、發站時間和停站時間。

3 鐵路運行調度模型

鐵路運行調度的目的是在確保列車安全運行的前提下，使得鐵路運行列車上行時間差和下行時間誤差的總和最小。由于鐵路列車運行系統的連續性，當某個列車晚點時，為了保證鐵路列車的運行安全和降低晚點所產生的不利影響，列車調度中心需要對后續列車進行調度處理。為了將列車晚點產生的不利影響控制在很小的區間范圍內，因此列車運行調度優化的區間范圍也應該控制在很小的區間范圍內[5]。

3.1 編碼

為了便于問題的簡化和解決，列車運行時間采用整數編碼。例如，12:00:00的整數編碼結果為43 200。列車運行時間矩陣編碼形式如下：到站時間矩陣編碼為：[d11d12d13……d1n]，發車時間矩陣編碼為：[f11f12f13……f1n]。其中，[d11d12d13……d1n]和[f11f12f13……f1n]分別表示第1輛列車在第1站到第n站的到站時間和發車時間。

3.2 數學模型

為實現列車的合理調度，在確保列車安全運行的前提下，使得鐵路運行列車上行時間差和下行時間誤差的總和最小，鐵路列車調度的數學模型可表示為[6]：

(1) 列車到站和站點發車早晚點時間之差的絕對值之和最小，如式(4)。

(4)

(2) 列車到站和出發早晚點數量之和最小,如式(5)。

(5)

其中式(6)、式(7)。

(6)

(7)

當列車到站和離站時間誤差大于10 s時，列車晚點；反之，列車不晚點。

綜合上述分析，鐵路列車調度的數學模型可表示為[7-8]式(8)。

(8)

其中，λ1、λ2表示權重。

3.3 約束條件

(1) 發車時間：列車計劃發車時間不能遲于列車實際發車時間為式(9)。

(9)

(2) 列車停站時間：列車最小停站時間≤實際停站時間為式(10)。

(10)

其中，Tik(min)表示列車最小停站時間。

(3) 列車區間運行時間[9]：所用軌道交通停靠站中相鄰兩站點之間的軌道交通列車運行時間≥最小運行時間Tmin。如式(11)。

(11)

(4) 列車追蹤時間：相鄰兩列車的運行時間間隔≥規定的運行時間間隔ΔT，從而保證列車的行車安全,如式(12)。

(12)

3.4 算法步驟

基于IFA的鐵路運行調度優化流程如下：

Step1：讀取列車運行的計劃時刻表，包括列車到達時間和發車時間；

Step2：參數編碼；

Step3：初始化IFA算法參數：螢火蟲數量N、初始吸引度β0、步長因子α、螢火蟲初始位置X和最大迭代次數T；

Step4：計算各螢火蟲的亮度并進行排序：計算每個螢火蟲所對應的適應度f，將適應度f作為對應螢火蟲的亮度并排序，得到亮度最大的螢火蟲位置；

Step5：判斷迭代是否結束：如果算法達到最大迭代次數T，則算法轉到Step6，否則轉到Step7；

Step6：輸出亮度最大的螢火蟲位置及其亮度，得到最佳調度時間；

Step7：更新螢火蟲位置：根據公式(3)更新螢火蟲的位置。

4 實證分析

4.1 數據來源

為驗證本文算法的有效性和可靠性，選擇某地鐵1#線的時刻表為研究對象，共13個站點，以3輛列車上下行6個運行車次進行實證分析[10-11]，列車追蹤間隔時間為180 s，運行時刻表如表1所示。

每個站點最小停站時間和計劃停站時間分別為[170 25 25 25 35 25 25 25 25 25 25 25 25 110]和[180 30 30 30 40 30 30 30 30 30 30 30 30 120]。時間參數如表2所示。

4.2 結果分析

IFA算法參數設置如下：螢火蟲數量N=50、初始吸引度β0=1、步長因子α=0.5和最大迭代次數T=100，其優化結果如圖2所示。

將IFA與FA、PSO和GA算法進行對比，其對比結果如圖2所示。由圖2可知，IFA算法具有更快的收斂速度，效果優于FA、PSO和GA算法，避免陷入局部最優，同時提高收斂速度。優化結果如表3所示。

由表1和表2對比可知，列車上行至第3站時晚點200 s，通過IFA算法優化調整，列車下行至第12站時恢復正點。通過IFA算法優化調整列車調度，在保證列車安全運行的情況下，可以將列車晚點產生的不利影響控制在很小的區間范圍內。

表1 列車計劃時刻表

表2 時間參數

表3 優化結果

5 總結

為了實現鐵路列車的優化調度，將列車晚點產生的不利影響控制在較小的區間范圍內，將改進的螢火蟲算法引入鐵路列車調度優化數學模型，在合理的約束條件上，運用IFA算法進行優化求解。研究結果表明，通過IFA算法優化調整列車調度，在保證列車安全運行的情況下，可以將列車晚點產生的不利影響控制在很小的區間范圍內。

(a) IFA

(b) FA

(c) PSO

(d) GA