專業(yè)化分工粒子群優(yōu)化算法在地鐵列車運(yùn)行調(diào)整中的應(yīng)用

劉小玲，孫 波，薛 亮，2

（1.遼寧省交通高等?？茖W(xué)校 軌道交通工程系，遼寧 沈陽(yáng)110122；2.大連理工大學(xué) 交通運(yùn)輸學(xué)院，遼寧 大連116024）

運(yùn)輸調(diào)度工作是地鐵運(yùn)營(yíng)企業(yè)日常運(yùn)輸組織的中樞，它是地鐵能夠正常開(kāi)展行車組織工作任務(wù)的決定因素。當(dāng)運(yùn)營(yíng)過(guò)程中列車運(yùn)行偏離了計(jì)劃運(yùn)行圖時(shí)，就必須進(jìn)行列車運(yùn)行調(diào)整。地鐵系統(tǒng)是一個(gè)龐大而復(fù)雜的系統(tǒng)，要解決該系統(tǒng)的列車運(yùn)行調(diào)整問(wèn)題，使之盡快恢復(fù)運(yùn)行圖行車，有很多影響因素值得分析。目前，最優(yōu)化方法和智能計(jì)算方法是解決這類問(wèn)題的主要方法。采用最優(yōu)化方法時(shí)必須先對(duì)列車運(yùn)行調(diào)整問(wèn)題復(fù)雜的模型進(jìn)行簡(jiǎn)化，多項(xiàng)式計(jì)算量極其龐大，同時(shí)，導(dǎo)致最后結(jié)果與現(xiàn)實(shí)出現(xiàn)一定偏差。智能計(jì)算方法中最主要的是遺傳算法（GA）和粒子群優(yōu)化（PSO）算法。遺傳算法在智能優(yōu)化方法中應(yīng)用極為廣泛，它以生物進(jìn)化為原型，具有很好的收斂性，在計(jì)算精度要求時(shí)，計(jì)算時(shí)間少、魯棒性高，但在解決大規(guī)模計(jì)算量問(wèn)題時(shí)，它很容易陷入“早熟”。粒子群優(yōu)化由于其算法簡(jiǎn)單、無(wú)需梯度信息、參數(shù)少、易于實(shí)現(xiàn)等特點(diǎn)，在解決多目標(biāo)優(yōu)化、約束優(yōu)化、動(dòng)態(tài)優(yōu)化問(wèn)題上表現(xiàn)出良好的性能特征。然而，基本粒子群優(yōu)化算法在解決列車運(yùn)行調(diào)整問(wèn)題時(shí)，因?yàn)樵搯?wèn)題具有多個(gè)約束條件和龐大的搜索空間，因此基本PSO算法也因在其求解時(shí)易陷入死循環(huán)而很難得到最優(yōu)解?；趯I(yè)化分工策略的粒子群優(yōu)化算法（Division of Specialization PSO，DSPSO）是在PSO算法的基礎(chǔ)上，將基于專業(yè)化分工的策略引入PSO算法中，使算法的性能得到提高，能較好地適應(yīng)復(fù)雜的實(shí)際環(huán)境。本文針對(duì)地鐵列車運(yùn)行調(diào)整問(wèn)題提出一種基于專業(yè)化分工的粒子群算法，從而達(dá)到快速尋優(yōu)、提高求解質(zhì)量和收斂速度的目的。

1 算法描述

1.1 基本粒子群優(yōu)化算法

算法的基本原理描述如下:

一個(gè)群體由m個(gè)粒子組成，它以一定的速度在n維搜索空間中飛行，搜索時(shí)，每個(gè)粒子在考慮到了自己和群內(nèi)（或領(lǐng)域內(nèi)）其他粒子搜索到的歷史最好點(diǎn)的基礎(chǔ)上，進(jìn)行了位置（狀態(tài)，也就是解）的變化。

第i個(gè)粒子的位置表示為:Xi＝ （xi1，xi2，…，xin），（i＝1，2，…，m）。

第i個(gè)粒子的速度表示為:Vi＝ （vi1，vi2，…，vin），（i＝1，2，…，m）。

第i個(gè)粒子經(jīng)歷過(guò)的歷史最好點(diǎn)（最好適應(yīng)值）表示為:Pi＝ （pi1，pi2，…，pin），（i＝1，2，…，m）。

在給最小化問(wèn)題求解時(shí)，需要對(duì)應(yīng)較小的目標(biāo)函數(shù)值，才能得到較好的適應(yīng)值。因此，將目標(biāo)函數(shù)設(shè)為f（x），i粒子所經(jīng)過(guò)的當(dāng)前最好點(diǎn)表示為下式

群體中所有粒子經(jīng)歷過(guò)的最好點(diǎn)由Pg（t）表示，即為種群全局最好位置。則

有了上述定義，Kennedy和Eberhart兩人提出了基本粒子群算法的位置和速度進(jìn)化方程，可表示如下

式中:1≤i≤m，1≤j≤n，t為循環(huán)迭代次數(shù)；c1為“認(rèn)知”加速常數(shù)；c2為“社會(huì)”加速常數(shù)；r1，r2為（0，1）間相互獨(dú)立的隨機(jī)數(shù)。

1.2 基于專業(yè)化分工策略的粒子群優(yōu)化算法

基于專業(yè)化分工策略的粒子群優(yōu)化算法（DSPSO）的群體是基于“開(kāi)采者”和“搜索者”的不同專業(yè)化分工而劃分的。DSPSO是在基本粒子群優(yōu)化算法的基礎(chǔ)上將粒子群的群體優(yōu)勢(shì)充分發(fā)揮，并加以利用，使之在復(fù)雜的環(huán)境中能更好地適應(yīng)。

基于專業(yè)化分工的粒子群優(yōu)化算法具體描述如下:

將m個(gè)粒子組成的群體分成子群體S1（開(kāi)采者1）、S2（開(kāi)采者2）、S3（搜索者），各子群體包含的粒子數(shù)分別為m1，m2，m3，m＝m1＋m2＋m3。每一個(gè)子群體對(duì)應(yīng)一個(gè)進(jìn)化方程，S1子群體的進(jìn)化方程收斂速度較快，作用是使局部尋優(yōu)能力得到提升；S2子群體的進(jìn)化方程是c1＝0時(shí)的“社會(huì)模型”；S3子群體的進(jìn)化方程作用是全局搜索。具體的進(jìn)化方程如下

子群體S1:

子群體S2:

子群體S3:

1.3 基于專業(yè)化分工策略的粒子群優(yōu)化算法優(yōu)勢(shì)分析

文獻(xiàn)［4］中對(duì)幾種改進(jìn)的粒子群優(yōu)化算法進(jìn)行對(duì)比分析，一是基于專業(yè)化分工策略的PSO（DSPSO）、基于線性遞減權(quán)策略的PSO（LDWPSO）和經(jīng)典PSO（CPSO）三種算法對(duì)經(jīng)典函數(shù)Sphere和Griewank的尋優(yōu)性能進(jìn)行測(cè)試，試驗(yàn)結(jié)果表明，基于專業(yè)化分工策略的粒子群優(yōu)化算法在尋優(yōu)精度和搜索快速上都優(yōu)于其余兩種方法；二是DSPSO、保持粒子活性的改進(jìn)PSO（IPSO）和具有局部參數(shù)的PSO（LPSO）三種算法對(duì)經(jīng)典函數(shù)Sphere和Griewank的性能進(jìn)行測(cè)試，試驗(yàn)結(jié)果表明，DSPSO較其余兩種算法在全局和局部尋優(yōu)能力上均有較為優(yōu)異的表現(xiàn)，同時(shí)兼具較小計(jì)算量、勿須判斷比較、固定參數(shù)、易于實(shí)現(xiàn)的優(yōu)勢(shì)。

2 建立模型

列車運(yùn)行調(diào)整的意思是在某個(gè)區(qū)段和時(shí)間內(nèi)，列車運(yùn)行秩序發(fā)生混亂，列車實(shí)際運(yùn)行偏離了運(yùn)行圖計(jì)劃時(shí)，通過(guò)調(diào)整的方式使列車運(yùn)行盡快恢復(fù)至計(jì)劃運(yùn)行圖。在城市軌道交通系統(tǒng)中，一般來(lái)說(shuō)，列車等級(jí)相同，各站的上、下行停站時(shí)間固定，運(yùn)行過(guò)程中沒(méi)有會(huì)讓和越行，因此，在建立列車運(yùn)行調(diào)整模型前，相關(guān)定義表示如下:

設(shè)某線路上有一包括M個(gè)車站的區(qū)段，該區(qū)段內(nèi)有N列（N1表示上行列車的數(shù)量，N2表示下行列車的數(shù)量，N1＋N2＝N）車運(yùn)行，D實(shí)際ij、F實(shí)際ij分別表 示 第i（i∈ ｛1，2，…，N｝）列 車 在 第j（j∈｛1，2，…，M｝）個(gè) 車 站 的 實(shí) 際 到 達(dá)、出 發(fā) 時(shí) 刻，D計(jì)劃ij、F計(jì)劃ij分別表示第i（i∈｛1，2，…，N｝）列車在第j（j∈｛1，2，…，M）｝）個(gè)車站的計(jì)劃到達(dá)、出發(fā)時(shí)刻。

設(shè)運(yùn)算函數(shù)為kji（即列車晚點(diǎn)的標(biāo)志函數(shù)），如下式表示

在最短的時(shí)間內(nèi)將晚點(diǎn)列車的數(shù)量和晚點(diǎn)時(shí)間影響降到最小是列車運(yùn)行調(diào)整問(wèn)題最根本的目標(biāo)，達(dá)到此目標(biāo)就能使列車盡快的恢復(fù)運(yùn)行圖行車。故而，將該問(wèn)題數(shù)學(xué)模型的兩個(gè)優(yōu)化目標(biāo)表示如下

目標(biāo)1（即F1）:最小的晚點(diǎn)列車總時(shí)間

目標(biāo)2（即F2）:最小的晚點(diǎn)列車總數(shù)目

本文以上述兩個(gè)目標(biāo)最小為優(yōu)化目標(biāo)，建立模型，其目標(biāo)函數(shù)表示如下

式中:q1為晚點(diǎn)時(shí)間的加權(quán)因子；q2為晚點(diǎn)列車數(shù)量的加權(quán)因子。

列車運(yùn)行調(diào)整旨在使偏離計(jì)劃運(yùn)行圖的列車盡快恢復(fù)計(jì)劃運(yùn)行圖運(yùn)行，與目標(biāo)函數(shù)F表示的意義一致，即使多目標(biāo)優(yōu)化問(wèn)題的加權(quán)和最小。應(yīng)用DSPSO算法來(lái)求解列車運(yùn)行調(diào)整這個(gè)多目標(biāo)優(yōu)化問(wèn)題時(shí)，若其適應(yīng)度函數(shù)的適應(yīng)值越小，則體現(xiàn)出來(lái)的是其列車晚點(diǎn)總數(shù)量和總時(shí)間也就越少，從而晚點(diǎn)列車的實(shí)際到達(dá)、出發(fā)時(shí)刻也就越接近計(jì)劃運(yùn)行圖的到達(dá)、出發(fā)時(shí)刻，故本文將適應(yīng)度函數(shù)fitness（f）定為F，表示如下

鑒于實(shí)際地鐵列車運(yùn)行的獨(dú)特性質(zhì)，故將其約束條件表示如下:

約束1:區(qū)間運(yùn)行時(shí)間

式中:Qi，j＋1為第i站至第j間最小區(qū)間運(yùn)行時(shí)分。

約束2:發(fā)車時(shí)間

約束3:列車追蹤間隔時(shí)間

式中:ΔT為列車追蹤間隔時(shí)間。

約束4:最小站停時(shí)間

式中:MTij為列車i在j站的最小站停時(shí)間。

3 基于專業(yè)化分工策略的粒子群優(yōu)化算法求解列車運(yùn)行調(diào)整問(wèn)題

本文采用基于專業(yè)化分工的粒子群優(yōu)化算法對(duì)列車運(yùn)行調(diào)整問(wèn)題模型進(jìn)行求解，詳細(xì)的算法步驟描述如下:

第1步:在初始化范圍內(nèi)，對(duì)粒子群進(jìn)行隨機(jī)初始化，包括各粒子的隨機(jī)速度和位置、粒子群群體的規(guī)模和數(shù)目；

第2步:計(jì)算各粒子的適應(yīng)值，對(duì)于各粒子，設(shè)定其個(gè)體最優(yōu)值Pi，同時(shí)得到種群全局最優(yōu)值Pg；

第3步:相關(guān)參數(shù)的設(shè)置，即系數(shù)q1，q2，各子群體具有的粒子數(shù)m1，m2，m3，最大迭代次數(shù)T；

第4步:分別按照式（5）、（6）、（7）及（4）更新各子群體的粒子位置和速度，通過(guò)進(jìn)化（即迭代）得到粒子群群體新個(gè)體；

第5步:按照式（12）對(duì)各粒子適應(yīng)值進(jìn)行評(píng)價(jià)，比較其適應(yīng)值與初始的個(gè)體最優(yōu)值Pi，若更好，則將其作為當(dāng)前最優(yōu)值Pi；

第6步:將得到的所有最優(yōu)值Pi和Pg進(jìn)行比較后，對(duì)Pg進(jìn)行更新；

第7步:如沒(méi)有達(dá)到終止條件，則轉(zhuǎn)到第3步；如達(dá)到終止條件，則搜索結(jié)束，將得到全局歷史最好結(jié)果輸出；

第8步:將最優(yōu)值所對(duì)應(yīng)的列車到達(dá)和出發(fā)時(shí)刻輸出，從而得到列車運(yùn)行調(diào)整的最終方案。

4 實(shí) 例

本文采用 Visual Basic 2012作為編程工具，選取數(shù)據(jù)為沈陽(yáng)地鐵2號(hào)線某工作日三臺(tái)子站至白塔河路站這一區(qū)段為例，該區(qū)段內(nèi)車站數(shù)目M＝18，列車數(shù)目N＝26，上行列車數(shù)N1＝13，下行列車數(shù)N2＝13。粒子數(shù)目設(shè)定為m＝30，各子群數(shù)m1＝6，m2＝9，m3＝15，迭代次數(shù)終止值為T(mén)＝300，q1＝0.8，q2＝0.2?，F(xiàn)考慮上行方向，該區(qū)段內(nèi)列車運(yùn)行時(shí)間從6:00～9:00，計(jì)劃運(yùn)行圖如圖1所示，以208次在岐山路站上行站臺(tái)出發(fā)時(shí)晚點(diǎn)130s為例，運(yùn)用DSPSO計(jì)算后的調(diào)整結(jié)果在時(shí)刻表編輯軟件Hustas上仿真模擬，得到調(diào)整后的列車運(yùn)行圖如圖2所示，208次的計(jì)劃時(shí)刻表和調(diào)整后時(shí)刻表如圖3、圖4所示。

圖1 計(jì)劃運(yùn)行

圖2 調(diào)整后運(yùn)行

圖3 計(jì)劃時(shí)刻

圖4 調(diào)整后時(shí)間

由圖3和圖4分析208次列車在各站的到達(dá)、出發(fā)時(shí)刻，可以看出當(dāng)其運(yùn)行到岐山路站上行站臺(tái)時(shí)，其實(shí)際出發(fā)時(shí)間比計(jì)劃晚了130s，即由7:07:42～7:09:52。此時(shí)經(jīng)基于專業(yè)化分工的粒子群優(yōu)化算法計(jì)算，并根據(jù)其結(jié)果調(diào)整后，列車在滿足各項(xiàng)約束條件的前提下，在運(yùn)行過(guò)程中就逐步縮小了晚點(diǎn)時(shí)間，直至其在奧體中心站上行站臺(tái)發(fā)車時(shí)晚點(diǎn)0s，已正點(diǎn)運(yùn)行，即恢復(fù)計(jì)劃運(yùn)行圖運(yùn)行。由此可見(jiàn)，DSPSO算法在求解列車運(yùn)行調(diào)整問(wèn)題時(shí)能較快地解決晚點(diǎn)現(xiàn)象，且收斂速度快，求解質(zhì)量高，避免了延遲傳播。

5 結(jié)束語(yǔ)

由于地鐵列車運(yùn)行調(diào)整問(wèn)題約束多，搜索空間大，可行解范圍小，因而總是難以獲得最優(yōu)解。因?yàn)榱熊囘\(yùn)行調(diào)整問(wèn)題有如此特性，故本文為了求解該問(wèn)題提出了DSPSO算法，即將粒子群體劃分為幾個(gè)子群體，充分利用子群體的優(yōu)勢(shì)，將子群體進(jìn)行專業(yè)化分工，他們之間通過(guò)信息交換來(lái)協(xié)調(diào)工作，各個(gè)子群體通過(guò)不同的進(jìn)化方程，各司其職，使得收斂速度得到提高，從而獲得更具可行性的結(jié)果。

［1］ 汪定偉，王俊偉，王洪峰，等.智能優(yōu)化方法［M］.北京:高等教育出版社，2007.

［2］ Lars Junghans，Nicholas Darde.Hybrid single objective genetic algorithm coupled with the simulated annealing optimization method for building optimization［J］.Energy and Buildings，2015，1（86）:651－662.

［3］ 王瑞峰，孔維珍，詹生正.雜交粒子群算法在列車運(yùn)行調(diào)整中的應(yīng)用研究［J］.計(jì)算機(jī)應(yīng)用研究，2013（6）:1721－1723.

［4］ 李洪亮，侯朝楨，周邵生.一種高效的改進(jìn)粒子群優(yōu)化算法［J］.計(jì)算機(jī)工程與應(yīng)用，2008，44（1）:14－16.

［5］ 高立群，任蘋(píng)，李楠.基于混沌粒子群算法的高速旅客列車優(yōu)化調(diào)度［J］.東北大學(xué)學(xué)報(bào):自然科學(xué)版，2007（2）:176－192.

［6］ 楊東，江雨星，宋巖.城市軌道交通列車開(kāi)行方案優(yōu)化模型研究［J］.交通科技與經(jīng)濟(jì)，2014，16（5）:38－42.