城軌列車運行調(diào)整問題的模糊優(yōu)化設(shè)計研究

魏 倩,陳永剛

(蘭州交通大學(xué)自動化與電氣工程學(xué)院,蘭州 730070)

城軌列車運行調(diào)整問題的模糊優(yōu)化設(shè)計研究

魏 倩,陳永剛

(蘭州交通大學(xué)自動化與電氣工程學(xué)院,蘭州 730070)

城市軌道交通中列車運行的實時調(diào)整能保證系統(tǒng)的運營效率,因此對該問題進行研究很有必要。考慮到優(yōu)化目標(biāo)函數(shù)與約束條件的模糊性,建立了列車運行調(diào)整的模糊優(yōu)化設(shè)計數(shù)學(xué)模型。在模型求解過程中,首先基于Zimmermann對稱模型求解思想的容差法,將模糊優(yōu)化模型轉(zhuǎn)化為一系列確定性優(yōu)化模型,然后運用MATLAB中遺傳算法相關(guān)函數(shù)對模型進行求解。最后選取蘇州軌道交通1號線運營數(shù)據(jù)進行算法驗證,結(jié)果表明列車運行調(diào)整模糊優(yōu)化模型較之普通優(yōu)化模型的合理性和有效性。

城市軌道交通;運行調(diào)整;模糊優(yōu)化;遺傳算法

當(dāng)前我國城市軌道交通正處于快速發(fā)展階段,其客流量的增加和列車運行密度的增大對列車運行調(diào)整的質(zhì)量和效率提出了更高的要求,如何恰當(dāng)?shù)孛枋鰡栴}和設(shè)計相應(yīng)的算法是城軌行車指揮調(diào)度自動化的關(guān)鍵。

列車運行調(diào)整屬于高維數(shù)、非線性混合整數(shù)目標(biāo)優(yōu)化問題[1],國內(nèi)外許多學(xué)者對此問題提出了多種數(shù)學(xué)模型及優(yōu)化方法,奠定了列車運行調(diào)整問題進一步研究的基礎(chǔ)[2,3],目前線性規(guī)劃、非線性規(guī)劃、分枝定界法、遺傳算法[4]、專家系統(tǒng)[5]、粒子群算法[6]等各種優(yōu)化方法在列車運行調(diào)整問題上已進行了一定的應(yīng)用研究,但是在城軌列車運行調(diào)整方面使用的方法很少。列車在實際運行過程中,易受到包括來自環(huán)境、列車設(shè)備、線路條件等各種不確定因素的干擾,使得列車運行過程的多種約束參數(shù)具有模糊不確定性。傳統(tǒng)方法更多考慮的是確定變量環(huán)境下的優(yōu)化問題[7],無法適應(yīng)受不確定性因素影響的城軌實際運營環(huán)境。

為此,本文建立了列車運行調(diào)整模糊模型,使優(yōu)化模型更接近實際情況,并運用遺傳算法對該模型進行求解,可望得到更加合理的優(yōu)化解,從而為解決城軌列車運行調(diào)整問題提供一種新思路。

1 模糊優(yōu)化設(shè)計模型及其解法

1.1 模糊優(yōu)化設(shè)計模型

模糊環(huán)境下,多約束的非線性規(guī)劃模型可表示為

式中,x表示優(yōu)化模型的設(shè)計變量序列;z為綜合優(yōu)化目標(biāo)函數(shù);A∈Rm×n,b∈Rm,c∈Rn分別代表資源約束矩陣、資源擁有向量和系數(shù)向量。

1.2 基于Zimmermann對稱模型的容差法

定義第i個資源約束的最大容差為pi,資源約束的隸屬度為μ1,μ2,μ3,…,μm,考慮到求解方便,本文采用線性分布的隸屬函數(shù)

其隸屬函數(shù)示意如圖1所示。

圖1 約束條件隸屬函數(shù)示意

資源約束的水平截集λ可定義為

應(yīng)用Zimmermann對稱模型可以將式(1)轉(zhuǎn)化為帶有容差的形式[8]

式中,z0、z1分別表示約束條件伸縮到最大范圍和未伸縮時的解。這樣原模型就轉(zhuǎn)化為含有m+1個約束的確定性優(yōu)化模型,求解模型得到的設(shè)計方案Xλ可稱為“具有λ約束水平的優(yōu)化設(shè)計”。λ取不同的值,即可得到不同的最優(yōu)點,但最優(yōu)方案只有1個。

2 城軌列車運行調(diào)整的模糊優(yōu)化設(shè)計

2.1 符號定義和基本假設(shè)

定義:設(shè)區(qū)段內(nèi)車站數(shù)為m,上線列車數(shù)為n;集合S={si|i=1,2,…m}為設(shè)計區(qū)段內(nèi)車站集;Q={qi| i=1,2,…m-1}為區(qū)間集;L={lk|k=1,2,…n}為計劃期內(nèi)待調(diào)整的列車集;d*i,k、f*i,k分別為列車lk在車站si的計劃到、發(fā)時分;di,k、fi,k分別為列車lk在車站si的實際到、發(fā)時分;Ri,k為列車lk在區(qū)間[si,si+1]的最小運行時分;Ti,k為列車lk在車站si的最小停站時間;Tz為追蹤運行的最小行車間隔時間;定義sgn(a,b)函數(shù)如下

本文只考慮城軌客運列車的運營情況,假設(shè)列車等級為同一等級;鑒于城市軌道交通的車站技術(shù)設(shè)備及線路條件特性,約束條件僅考慮區(qū)間運行時間、停站時間、行車間隔存在模糊性,微觀層面不進行模糊松弛處理。其中約束條件中的區(qū)間運行時間按列車平均運行速度計算,設(shè)定列車在各車站的停站時間相等。

2.2 列車運行調(diào)整的確定優(yōu)化設(shè)計模型

由上述分析可知,模糊優(yōu)化設(shè)計模型可通過基于Zimmermann對稱模型的容差法轉(zhuǎn)化為確定性優(yōu)化模型,因此,關(guān)鍵在于確定性優(yōu)化模型的構(gòu)建與求解。

城軌列車運行調(diào)整問題通常使用的優(yōu)化準(zhǔn)則有最小列車總晚點時間、最少總晚點列車數(shù)等[9]。這兩個優(yōu)化目標(biāo)的數(shù)學(xué)描述可表示如下。

列車總晚點時間

總晚點列車數(shù)

本文將該雙目標(biāo)的規(guī)劃模型轉(zhuǎn)為單目標(biāo)規(guī)劃模型,以列車總晚點時間及總晚點列車數(shù)加權(quán)和最小作為優(yōu)化目標(biāo)[10],對二者賦予權(quán)重ω(0＜ω≤1),ω體現(xiàn)了列車運行調(diào)整時的偏重度。建立的列車運行調(diào)整的確定優(yōu)化設(shè)計模型如下

2.3 列車運行調(diào)整模糊優(yōu)化設(shè)計

對上述確定優(yōu)化模型的約束條件進行模糊化處理,給約束條件一個松弛條件,分別為模糊約束條件中的區(qū)間運行時分、列車停站時分及列車追蹤間隔時間設(shè)置容差值CR、CT、CTz,則約束松弛到最大限時的模型為

各模糊約束的取值從完全許用到完全不許用的中間過渡過程用線性隸屬函數(shù)來描述。限于篇幅,僅給出區(qū)間運行時分的模糊隸屬度函數(shù),公式表示為

其隸屬度函數(shù)的示意如圖2所示。

圖2 列車區(qū)間運行時間模糊約束隸屬度函數(shù)示意

基于上述約束條件和參數(shù)的模糊性,需要對優(yōu)化的目標(biāo)也進行模糊處理,可用公式表示為

將目標(biāo)函數(shù)及約束函數(shù)的隸屬函數(shù)表達(dá)式代入公式(4)中,即得

采用遺傳算法求此模型的最優(yōu)解(x*,λ*)為最大隸屬度λ*的模糊決策x*。求得的x*表示調(diào)整后的最優(yōu)列車到、發(fā)站時分,該最優(yōu)解既能降低列車晚點的影響,使列車運行盡快從無序到有序,又較好地保證了列車運行的安全性。

3 遺傳算法求解模糊優(yōu)化模型

本文使用遺傳算法作為優(yōu)化引擎求解上述模糊優(yōu)化模型。根據(jù)模型的特點,定義適應(yīng)度函數(shù)時,對約束條件采用無參數(shù)的罰函數(shù)方式進行處理。列車運行調(diào)整問題實質(zhì)是重新確定列車時刻表的過程,因此采用整數(shù)編碼方式,用從午夜零點到某個時刻所經(jīng)過的秒數(shù)來代表某個時刻[11],例如:30656代表上午08∶ 30∶56。遺傳編碼時將水平截集因子λ與設(shè)計變量一起編碼形成染色體串,相當(dāng)于范圍在0～1之間的新增設(shè)計變量附加在染色體串的末尾[12],則染色體編碼長度為2mn+1。編碼時為使λ的數(shù)量級與設(shè)計變量統(tǒng)一,在λ前乘一個放縮系數(shù)a=105,具體的編碼格式如圖3所示。

圖3 遺傳編碼方式示意

上述列車運行調(diào)整問題的模糊優(yōu)化設(shè)計求解步驟如圖4所示。

圖4 模糊優(yōu)化求解步驟示意

4 應(yīng)用算例

本算例來源于蘇州軌道交通1號線運營數(shù)據(jù)[13]。選擇2012年5月18日8時30分至9時30分文化博覽中心至鐘南街區(qū)段的實際運營數(shù)據(jù),按上述算法步驟進行仿真。設(shè)計區(qū)段內(nèi)有6個車站,其中鐘南街站為折返站,列車折返時間為180 s。根據(jù)既定運行計劃,該時間段內(nèi)上線列車有8列。假設(shè)區(qū)段內(nèi)車次號為24100503的列車在8時39分56秒到達(dá)時代廣場站后因自身設(shè)備故障導(dǎo)致晚點120 s,需進行相應(yīng)的運行調(diào)整。優(yōu)化時設(shè)定權(quán)重ω=0.5,遺傳算法求解時種群規(guī)模N=100,交叉概率Pc=0.7,變異概率Pm= 0.001。求解步驟如下。

(1)根據(jù)確定優(yōu)化模型式(8),設(shè)定列車平均運行速度35 km/h,行車間隔560 s,停站時間40 s,應(yīng)用遺傳算法求得約束條件不進行松弛時的目標(biāo)函數(shù)值z1= 1 387,遺傳算法的運行結(jié)果如圖5(a)所示。

(2)將約束條件松弛到最大,設(shè)定列車平均運行速度39.3 km/h,行車間隔540 s,停站時間30 s,使用遺傳算法對模型式(9)求解得目標(biāo)函數(shù)值z0=1 107,遺傳算法的運行結(jié)果如圖5(b)所示。

(3)將優(yōu)化結(jié)果z1、z0代入模糊優(yōu)化設(shè)計模型式(12)中,經(jīng)遺傳算法求得目標(biāo)函數(shù)Z=100 000λ的值為79 640,即最優(yōu)約束水平λ*=0.796 4,即在列車平均運行速度為36.8 km/h,列車停站時間為37 s,行車間隔時間為549 s時為最優(yōu)調(diào)整結(jié)果。遺傳算法的運行結(jié)果如圖6所示。

圖5 確定約束條件下經(jīng)50代后解的收斂情況

圖6 模糊約束條件下經(jīng)100代后解的收斂情況

經(jīng)表1的優(yōu)化結(jié)果對比可發(fā)現(xiàn),雖然約束條件松弛到最大的時候總晚點時間最小,調(diào)整結(jié)果最優(yōu),但是此時的列車平均運行速度、行車間隔、停站時間均處于極限值,實際運行過程中會存在極大風(fēng)險。而在考慮約束條件的模糊性后,雖然比最高平均運行速度運行時的優(yōu)化結(jié)果要差一些,但是比約束無松弛情況下的總晚點時間少,優(yōu)化結(jié)果好。這樣以微弱放松約束條件值,減少了系統(tǒng)損耗度,并使列車運行安全性得到了一定保證,達(dá)到了理想的結(jié)果。

表1 設(shè)計變量及優(yōu)化結(jié)果對比

5 結(jié)語

針對傳統(tǒng)城軌列車運行調(diào)整優(yōu)化設(shè)計的局限性,建立了該類問題的模糊優(yōu)化設(shè)計模型,并采用基于Zimmermann對稱模型的容差法和遺傳算法進行求解,先通過確定模型求取到一個可行的范圍,之后再通過模糊優(yōu)化模型尋求一個較優(yōu)的調(diào)整策略,得到的優(yōu)化結(jié)果既考慮了列車的晚點情況,又可保證列車運行的安全性及減小設(shè)備損耗值,即更貼近實際的最優(yōu)調(diào)整策略。

[1] 陳雍君,周磊山.基于序優(yōu)化方法的列車運行調(diào)整算法研究[J].鐵道學(xué)報,2010,32(3):1-8.

[2] Cordeau J F,Toth P,Vigo D.A survey of optimization models for train routing and scheduling[J].Transportation Science,1998,32(4): 988-1005.

[3] Andrea D'Ariano,Dario Pacciarelli,Macro Pranzo.A branch and bound algorithm for scheduling trains in a railway network[J]. European Journal of Operational Research,2007,183(2):643-657.

[4] 章優(yōu)仕,金煒東.基于遺傳算法的單線列車運行調(diào)整體系[J].西南交通大學(xué)學(xué)報,2005,40(2):147-152.

[5] 程宇,秦作睿.列車運行調(diào)整專家系統(tǒng)的研究[J].鐵道學(xué)報, 1992,14(2):42-50.

[6] 陳世明,賴毅平,江冀海.面向列車運行調(diào)整問題的粒子群算法研究[J].計算機應(yīng)用研究,2010,27(12):4460-4463.

[7] 謝金鑫.基于模糊優(yōu)化方法的高速列車運行調(diào)整問題研究[D].北京交通大學(xué),2011.

[8] 程利軍.Fuzzy資源約束非線性規(guī)劃的一個有效解法[J].曲阜師范大學(xué)學(xué)報,2000,26(3):32.

[9] 李曉艷.基于Petri網(wǎng)模型的城市軌道交通列車運行調(diào)整方法研究[D].北京:北京交通大學(xué),2009.

[10]張亦南.基于GA的列車自動調(diào)整算法在CBTC系統(tǒng)中的應(yīng)用研究[D].北京:北京交通大學(xué),2008.

[11]王宏剛,張琦,王建英,等.基于遺傳算法的高速鐵路行車調(diào)整模型[J].中國鐵道科學(xué),2006,27(3):96-100.

[12]張智畯,于建華,邱清水.基于自適應(yīng)并行遺傳算法的結(jié)構(gòu)模糊動力優(yōu)化[J].四川大學(xué)學(xué)報,2009,41(1):68-73.

Study on Fuzzy Optimization Design for Train Operation Adjustment in Urban Rail Transit

WEI Qian,CHEN Yong-gang
(School of Automation and Electrical Engineering,Lanzhou Jiaotong University,Lanzhou 730070,China)

Real time adjusting on the train's running in urban rail transit can assure the operation efficiency of the whole system,so the research on this problem is very important.A fuzzy optimization model was established for train operation adjustment,considering the fuzzy characteristics of object function and restriction conditions.During the process of model solving,firstly,the tolerance method was adopted to transfer the fuzzy optimization model to a series of determined optimization model,which is based on Zimmermann symmetric model solution idea.Then the correlation functions of genetic algorithm in MATLAB were used to solve the model.Finally,the practical calculation example of the Suzhou Urban Rail Transit Line 1 was used to prove that the fuzzy optimization model for train operation adjustment is more practicable and more efficient than the normal optimization model.

urban rail transit;operation adjustment;fuzzy optimization;genetic algorithms

U231+.6

A

1004-2954(2013)03-0125-04

20120731;

20120810

國家自然科學(xué)基金地區(qū)項目(61164010)

魏 倩(1987—),女,碩士研究生,E-mail:weiqianok@ qq.com。