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

魏 倩,陳永剛

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

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

魏 倩,陳永剛

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

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

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

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

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

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

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

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

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

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

1.2 基于Zimmermann對(duì)稱模型的容差法

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

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

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

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

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

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

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

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

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

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

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

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

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

列車總晚點(diǎn)時(shí)間

總晚點(diǎn)列車數(shù)

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

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

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

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

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

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

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

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

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

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

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

圖3 遺傳編碼方式示意

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

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

4 應(yīng)用算例

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

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

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

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

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

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

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

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

5 結(jié)語(yǔ)

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

[1] 陳雍君,周磊山.基于序優(yōu)化方法的列車運(yùn)行調(diào)整算法研究[J].鐵道學(xué)報(bào),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)仕,金煒東.基于遺傳算法的單線列車運(yùn)行調(diào)整體系[J].西南交通大學(xué)學(xué)報(bào),2005,40(2):147-152.

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

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

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

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

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

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

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

[12]張智畯,于建華,邱清水.基于自適應(yīng)并行遺傳算法的結(jié)構(gòu)模糊動(dòng)力優(yōu)化[J].四川大學(xué)學(xué)報(bào),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

國(guó)家自然科學(xué)基金地區(qū)項(xiàng)目(61164010)

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