劉小玲，孫 波，薛 亮，2

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

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

1 算法描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

子群體S1:

子群體S2:

子群體S3:

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

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

2 建立模型

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

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

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

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

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

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

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

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

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

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

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

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

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

約束3:列車追蹤間隔時間

式中:ΔT為列車追蹤間隔時間。

約束4:最小站停時間

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

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

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

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

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

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

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

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

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

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

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

4 實 例

本文采用 Visual Basic 2012作為編程工具，選取數(shù)據(jù)為沈陽地鐵2號線某工作日三臺子站至白塔河路站這一區(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＝300，q1＝0.8，q2＝0.2。現(xiàn)考慮上行方向，該區(qū)段內(nèi)列車運(yùn)行時間從6:00～9:00，計劃運(yùn)行圖如圖1所示，以208次在岐山路站上行站臺出發(fā)時晚點(diǎn)130s為例，運(yùn)用DSPSO計算后的調(diào)整結(jié)果在時刻表編輯軟件Hustas上仿真模擬，得到調(diào)整后的列車運(yùn)行圖如圖2所示，208次的計劃時刻表和調(diào)整后時刻表如圖3、圖4所示。

圖1 計劃運(yùn)行

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

圖3 計劃時刻

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

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

5 結(jié)束語

由于地鐵列車運(yùn)行調(diào)整問題約束多，搜索空間大，可行解范圍小，因而總是難以獲得最優(yōu)解。因為列車運(yùn)行調(diào)整問題有如此特性，故本文為了求解該問題提出了DSPSO算法，即將粒子群體劃分為幾個子群體，充分利用子群體的優(yōu)勢，將子群體進(jìn)行專業(yè)化分工，他們之間通過信息交換來協(xié)調(diào)工作，各個子群體通過不同的進(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ī)應(yīng)用研究，2013（6）:1721－1723.

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

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

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