基于PSO算法的城市軌道交通運(yùn)行調(diào)度優(yōu)化研究

劉欣昊

中南大學(xué) 交通運(yùn)輸工程學(xué)院,湖南 長(zhǎng)沙 410083

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

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

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

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

2 列車(chē)運(yùn)行圖

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

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

3.1 建立模型

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

3.2 編碼

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

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

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

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

3.3 數(shù)學(xué)模型

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

（1）列車(chē)到站早晚點(diǎn)時(shí)間和站點(diǎn)發(fā)車(chē)早晚點(diǎn)時(shí)間之差的二者絕對(duì)值之和最小。

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

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

公式（5）和公式（6）中，當(dāng)列車(chē)到站和離站時(shí)間誤差＜10 s時(shí)，列車(chē)不晚點(diǎn)；反之，列車(chē)晚點(diǎn)。

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

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

3.4 約束條件

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

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

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

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

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

3.5 算法步驟

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

Step 1：讀取列車(chē)運(yùn)行的計(jì)劃時(shí)刻表，包括列車(chē)到達(dá)時(shí)間和發(fā)車(chē)時(shí)間；

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

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

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

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

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

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

4 實(shí)證分析

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

圖1 不同時(shí)間段進(jìn)站人數(shù)分布圖Fig.1 Distribution of checkin population at different periods

表1 列車(chē)計(jì)劃時(shí)刻表Table 1 Train schedule timetable

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

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

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

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

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

4.2 收斂速度分析

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

圖2 收斂速度對(duì)比圖Fig.2 Comparison of convergence speeds

5 結(jié)論

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

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

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

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

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

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

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

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

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

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