劉欣昊

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

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

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

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

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

2 列車運行圖

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

3 軌道交通運行調(diào)度模型

3.1 建立模型

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

3.2 編碼

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

到站時間編碼結(jié)果：[d11d12d13…d1n]

發(fā)車時間編碼結(jié)果：[f11f12f13…f1n]

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

3.3 數(shù)學模型

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

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

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

（2）列車到站早晚點數(shù)量和出發(fā)早晚點數(shù)量之和最小。

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

通過綜合分析，軌道交通列車調(diào)度的數(shù)學模型可表示為[6]：

公式（7）中，λ1、λ2表示權(quán)重。

3.4 約束條件

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

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

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

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

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

3.5 算法步驟

基于PSO的城市軌道交通運行調(diào)度優(yōu)化的算法步驟如下：

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

Step 2：參數(shù)編碼；

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

Step 4：根據(jù)軌道交通列車調(diào)度的數(shù)學模型公式（7）計算粒子個體的適應(yīng)度，計算出局部最優(yōu)粒子和全局最優(yōu)粒子的位置和最優(yōu)值；

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

Step 6：計算適應(yīng)度，并進行位置更新和速度更新；

Step 7：若gen＞Iteration，保存最優(yōu)解；反之gen=gen+1，轉(zhuǎn)到Step 4。

4 實證分析

為驗證本文算法的有效性，以某地鐵2#線的時刻表為研究對象，設(shè)置有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 不同時間段進站人數(shù)分布圖Fig.1 Distribution of checkin population at different periods

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

表2 時間參數(shù)Table 2 Time parameters

4.1 優(yōu)化結(jié)果分析

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

表3 優(yōu)化結(jié)果Table 3 Optimization results

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

4.2 收斂速度分析

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

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

5 結(jié)論

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

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

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

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

[4]蔣 琦.城市軌道交通CBTC系統(tǒng)列車調(diào)度策略優(yōu)化研究[D].北京:北京交通大學,2012

[5]肖 楓.基于模糊神經(jīng)網(wǎng)絡(luò)的城市軌道交通行車間隔時間優(yōu)化研究[D].重慶:重慶交通大學,2013

[6]邢 雪.基于粒子群算法的城市接駁公交網(wǎng)絡(luò)優(yōu)化調(diào)度方法[J].北京工業(yè)大學學報,2016,42(9):1385-1391

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

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

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