基于PSO算法的城市軌道交通運行調度優化研究

劉欣昊

中南大學 交通運輸工程學院,湖南 長沙 410083

隨著經濟的發展和社會的進步，城市軌道交通作為新型的交通工具得到廣泛重視和發展，其具有方便、安全、快捷、準時、節能和污染較小的優點[1]。由于城市軌道交通的快速發展，列車自動控制系統在軌道交通列車控制中得到廣泛應用，該系統不但可以協助列車調度人員進行列車調度管理，同時進行列車的實時運行監控，確保行車安全，有效提高列車調度效率和降低列車運行成本和管理成本。列車調度主要是基于列車運行圖行駛的，由于存在的隨機因素和不確定性的影響，在實際運行過程中，列車會經常出現偏離列車時刻表的情況，因此需進行列車運行自動調整，實現列車的正點運行和調度。

1 粒子群算法（Particle Swarm Algorithm，PSO）

粒子群算法是受鳥群覓食行為啟發而提出的群搜索算法，其位置xid和速度Vid更新公式如公式（1）和公式（2）所示[2]：

其中，w表示慣性權值；c1、c2表示學習因子，一般取c1=c2=2；r1、r2表示(0，1)之間的隨機數；pid、pgd分別表示個體最優位置和全局最優位置；Vi為每個粒子的移動速度，Vi∈[-Vmax,Vmax]，Vmax為常數。

2 列車運行圖

列車運行圖是指運用坐標原理描述列車在軌道線路運行的時間、空間關系，直觀地顯示出在各車站停車或通過、在各區間運行狀態的一種圖解形式[3]。列車運行圖是軌道交通列車運行的基礎，其規定了每個軌道交通列車車次所占用區間的順序相關信息，主要包括軌道交通列車在各個站點的到站時間、離站時間和停站時間以及列車上行和下行所需的時間。

3 軌道交通運行調度模型

3.1 建立模型

城市軌道交通運行調度的目的是在保證軌道交通列車運行安全的情況下，保證軌道交通列車上行和下行的時間誤差總和最小。由于城市軌道列車運行系統具有連續性，為了保證列車的行駛安全，因此當某個列車的晚點時，列車調度中心將對后續的列車進行運行調度，確保運行安全，同時減小因列車晚點所帶來的不利影響。為了將列車晚點所帶來的不利影響限制在較小的范圍內，因此列車運行調度優化的區間范圍也應限制在較小的范圍內[4]。

3.2 編碼

為了方便問題解決，本文采用整數編碼方式對列車運行時間進行編碼。例如12:00:00的整數編碼結果為43200。矩陣編碼形式如下：

到站時間編碼結果：[d11d12d13…d1n]

發車時間編碼結果：[f11f12f13…f1n]

其中，[d11d12d13…d1n]表示第1輛列車在第1站到第n站的到站時間；[f11f12f13…f1n]表示第1輛列車在第1站到第n站的發車時間。

3.3 數學模型

為實現列車的合理調度，在保證軌道交通列車運行安全的情況下，保證軌道交通列車上行和下行的時間誤差總和最小，本文軌道交通調度數學模型的目標函數選擇如下[5]：

（1）列車到站早晚點時間和站點發車早晚點時間之差的二者絕對值之和最小。

其中，n1、n2分別表示上行列車數和下行列車數；d′i;k、di;k分別表示列車實際到站時間和計劃到站時間；f′i;k、fi;k分別表示列車實際離站時間和計劃離站時間。

（2）列車到站早晚點數量和出發早晚點數量之和最小。

公式（5）和公式（6）中，當列車到站和離站時間誤差＜10 s時，列車不晚點；反之，列車晚點。

通過綜合分析，軌道交通列車調度的數學模型可表示為[6]：

公式（7）中，λ1、λ2表示權重。

3.4 約束條件

（1）列車停站時間約束：列車最小停站時間應小于等于實際停站時間。

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

（2）列車追蹤時間約束：相鄰兩列車的運行時間間隔應大于等于規定的運行時間間隔ΔT，從而保證列車的行車安全。

（3）發車時間約束：列車實際發車時間不能早于列車計劃發車時間。

（4）列車區間運行時間約束：所用軌道交通停靠站中相鄰兩站點之間的軌道交通列車運行時間應大于等于最小運行時間Tmin。

3.5 算法步驟

基于PSO的城市軌道交通運行調度優化的算法步驟如下：

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

Step 2：參數編碼；

Step 3：設定PSO算法的種群大小popsize，最大迭代次數Iteration，學習因子c1，c2，根據優化變量的取值范圍，隨機生成初始化種群；

Step 4：根據軌道交通列車調度的數學模型公式（7）計算粒子個體的適應度，計算出局部最優粒子和全局最優粒子的位置和最優值；

Step 5：更新粒子速度和位置；

Step 6：計算適應度，并進行位置更新和速度更新；

Step 7：若gen＞Iteration，保存最優解；反之gen=gen+1，轉到Step 4。

4 實證分析

為驗證本文算法的有效性，以某地鐵2#線的時刻表為研究對象，設置有13個站點，以3輛列車上下行6個運行車次進行仿真實驗[7,8]，列車追蹤間隔時間為180 s，其運行時刻表如表1所示。該地鐵運行線路的非工作日和工作日不同時間段進站客流分布圖分別如圖1和圖2所示。每個站點計劃停站時間分別為[180 30 30 30 40 30 30 30 30 30 30 30 30 120]，最小停站時間分別為[170 25 25 25 35 25 25 25 25 25 25 25 25 110]。

圖1 不同時間段進站人數分布圖Fig.1 Distribution of checkin population at different periods

表1 列車計劃時刻表Table 1 Train schedule timetable

表2 時間參數Table 2 Time parameters

4.1 優化結果分析

PSO算法[9]的種群大小為20，最大迭代次數為100，學習因子c1=c2=2，其優化結果如表3所示：

表3 優化結果Table 3 Optimization results

通過表1和表2對比分析可知，軌道交通列車上行到第3站時晚點200 s，經過PSO算法的優化調整，列車下行至第12站時恢復正點。通過PSO算法優化調度，可以保證列車的正常運行，同時可以進行實時調整，確保列車晚點時間在較小的范圍內。

4.2 收斂速度分析

為驗證PSO算法的收斂速度，將其與GWO、SCA、MFO、ALO、MVO、WOA、GA和DE算法進行對比，其收斂結果對比如圖2所示，通過對比可知，PSO算法收斂速度最快。

圖2 收斂速度對比圖Fig.2 Comparison of convergence speeds

5 結論

針對軌道交通列車運行存在運行早晚點的問題，在保證軌道交通列車運行安全的情況下，確保軌道交通列車上行和下行的時間誤差總和最小，將PSO算法引入軌道交通運行調度，在構建數學模型和約束條件的基礎上，運用PSO算法優化求解。研究結果表明，通過PSO算法優化調度，可以保證列車的正常運行，同時可以進行實時調整，確保列車晚點時間在較小的范圍內。

[1]雷 敏,楊萬里,彭曉波,等.基于改進簡化粒子群算法的含DG的配電網無功優化[J].華北電力大學學報:自然科學版,2015,42(1):39-44

[2]李 錦,王聯國.基于細菌覓食優化算法的城市軌道交通調度優化[J].計算機工程與科學,2017,39(3):586-592

[3]季一木,柴博周,楊羅坤,等.基于TD-LTE的軌道交通集群調度系統[J].計算機工程,2017,43(6):296-300

[4]蔣 琦.城市軌道交通CBTC系統列車調度策略優化研究[D].北京:北京交通大學,2012

[5]肖 楓.基于模糊神經網絡的城市軌道交通行車間隔時間優化研究[D].重慶:重慶交通大學,2013

[6]邢 雪.基于粒子群算法的城市接駁公交網絡優化調度方法[J].北京工業大學學報,2016,42(9):1385-1391

[7]李 軒,張 鑫.基于地鐵公司和乘客滿意度最大化的軌道交通列車開行優化方案[J].交通科技與經濟,2015,17(1):69-72

[8]婁建峰,高岳林,李 飛,等.基于改進粒子群算法的云計算任務調度算法[J].微電子學與計算機,2016,33(8):112-116

[9]周麗娟,王春影.基于粒子群優化算法的云計算資源調度策略研究[J].計算機科學,2015,42(6):279-281