劉小玲，孫 波，薛 亮，2

（1.遼寧省交通高等專科學校 軌道交通工程系，遼寧 沈陽110122；2.大連理工大學 交通運輸學院，遼寧 大連116024）

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

1 算法描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

子群體S1:

子群體S2:

子群體S3:

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

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

2 建立模型

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

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

設運算函數(shù)為kji（即列車晚點的標志函數(shù)），如下式表示

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

目標1（即F1）:最小的晚點列車總時間

目標2（即F2）:最小的晚點列車總數(shù)目

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

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

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

鑒于實際地鐵列車運行的獨特性質，故將其約束條件表示如下:

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

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

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

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

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

約束4:最小站停時間

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

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

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

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

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

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

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

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

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

第7步:如沒有達到終止條件，則轉到第3步；如達到終止條件，則搜索結束，將得到全局歷史最好結果輸出；

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

4 實 例

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

圖1 計劃運行

圖2 調整后運行

圖3 計劃時刻

圖4 調整后時間

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

5 結束語

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

［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］ 王瑞峰，孔維珍，詹生正.雜交粒子群算法在列車運行調整中的應用研究［J］.計算機應用研究，2013（6）:1721－1723.

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

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

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