基于改進(jìn)魚群算法的城軌列車運(yùn)行均衡調(diào)整研究

楊艷娟,徐永能,董瑞超,景順利,姜建萍

(1.南京理工大學(xué) a.自動(dòng)化學(xué)院； b.瞬態(tài)物理國(guó)家重點(diǎn)實(shí)驗(yàn)室， 南京 210094；2.南京恩瑞特實(shí)業(yè)有限公司， 南京 211106)

隨著基于無(wú)線通信的CBTC(Communication Based Train Control System)系統(tǒng)在城市軌道交通列車上的應(yīng)用，促進(jìn)了列車控制技術(shù)的發(fā)展，在很大程度上縮短了列車的追蹤間隔。但是，列車在實(shí)際運(yùn)行過(guò)程中容易受到隨機(jī)干擾因素的影響，使得列車偏離計(jì)劃運(yùn)行圖。由于列車運(yùn)行間隔短，若前行列車晚點(diǎn)時(shí)間過(guò)長(zhǎng)時(shí)，可能導(dǎo)致列車運(yùn)行的大面積紊亂，導(dǎo)致列車群連帶晚點(diǎn)。因此，列車運(yùn)行自動(dòng)控制系統(tǒng)需要采取一定的調(diào)整措施，對(duì)偏離計(jì)劃運(yùn)行圖的列車進(jìn)行實(shí)時(shí)、高效地調(diào)整，使列車盡快恢復(fù)按圖定計(jì)劃運(yùn)行，達(dá)到保障城市軌道交通運(yùn)營(yíng)效率和服務(wù)水平的目的。

目前，針對(duì)城市軌道交通列車運(yùn)行調(diào)整已經(jīng)取得了豐富的研究成果，國(guó)內(nèi)外學(xué)者大多從構(gòu)建模型的角度出發(fā)，將列車調(diào)整問(wèn)題抽象為具體的數(shù)學(xué)模型[1-4]，并采用粒子群算法[5-7]、遺傳算法[8-11]、螢火蟲算法[12]等智能優(yōu)化算法對(duì)模型進(jìn)行求解。本研究從綜合考慮乘客出行體驗(yàn)和企業(yè)運(yùn)營(yíng)服務(wù)考核指標(biāo)的角度出發(fā)，以列車的總晚點(diǎn)時(shí)間和乘客延誤等待總時(shí)間最少為優(yōu)化目標(biāo)，建立城市軌道交通列車運(yùn)行均衡調(diào)整模型，并提出一種改進(jìn)人工魚群算法對(duì)模型進(jìn)行求解。

1 列車運(yùn)行均衡調(diào)整模型構(gòu)建

在構(gòu)建城市軌道交通列車運(yùn)行均衡調(diào)整模型時(shí)，本研究給出以下假設(shè)：

1) 列車晚點(diǎn)時(shí)間在ATR(Automatic Train Regulation，ATR)閾值內(nèi)，無(wú)需人工介入調(diào)整；

2) 列車晚點(diǎn)不包括改變列車運(yùn)行次序、增加/取消列車車次以及發(fā)生設(shè)備故障的情況；

3) 延誤只對(duì)發(fā)生初始延誤的后續(xù)列車有影響。

1.1 約束條件

城市軌道交通列車調(diào)整的約束條件是復(fù)雜且相對(duì)固定的，主要包括停站時(shí)間約束、區(qū)間運(yùn)行時(shí)間約束、追蹤間隔時(shí)間約束和到發(fā)車時(shí)間約束等四項(xiàng)約束[13-14]。

1) 停站時(shí)間約束

停站約束時(shí)間可以表示成：

(1)

其中，Ts min和Ts max分別表示列車li在車站sj的最小停站時(shí)間和最大停站時(shí)間。

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

為了保障乘客出行的安全性和舒適性，列車的運(yùn)行時(shí)間約束不僅對(duì)最小區(qū)間運(yùn)行時(shí)間進(jìn)行約束，也對(duì)最大區(qū)間運(yùn)行時(shí)間也進(jìn)行了約束，具體表示如下：

(2)

其中，Tr min和Tr max分別表示列車的最小區(qū)間運(yùn)行時(shí)間和最大區(qū)間運(yùn)行時(shí)間。

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

為了保障安全性，防止相鄰列車發(fā)生追尾事件，規(guī)定列車追蹤間隔時(shí)間約束如下：

(3)

其中:Tg min表示列車間的最小追蹤間隔；Tfd min表示相鄰列車到發(fā)最小間隔。

4) 到發(fā)車時(shí)間約束

為防止發(fā)生延誤的列車對(duì)前面的列車產(chǎn)生影響，盡快實(shí)現(xiàn)“按圖行車”，提高調(diào)整效率，對(duì)列車到發(fā)車時(shí)間進(jìn)行約束，保證不會(huì)出現(xiàn)早于計(jì)劃時(shí)間到發(fā)車的情況：

(4)

1.2 優(yōu)化目標(biāo)

列車的總晚點(diǎn)時(shí)間可以表示為各列車到達(dá)各車站的晚點(diǎn)時(shí)分和各列車從各車站出發(fā)的晚點(diǎn)時(shí)間之和受晚點(diǎn)影響的列車數(shù)Nl和到發(fā)時(shí)間線數(shù)Ns的改進(jìn)公式：

(5)

(6)

其中：tdelay為列車晚點(diǎn)時(shí)間；Tyz為列車追蹤間隔冗余時(shí)間；Tyr為區(qū)間運(yùn)行冗余時(shí)間；N和M分別車站總數(shù)和列車總數(shù)；n和m表示發(fā)生延誤的車站和列車；a為延誤類型標(biāo)志，a=0表示列車到達(dá)延誤，a=1表示列車發(fā)車延誤；ceil(x)和floor(x) 函數(shù)分別表示x趨近于正無(wú)窮的整數(shù)和趨近于負(fù)無(wú)窮大的整數(shù)。列車總晚點(diǎn)時(shí)間最小函數(shù)可以表示成：

(7)

由于存在列車到發(fā)車約束條件，所以上述公式可以簡(jiǎn)化為：

(8)

晚點(diǎn)時(shí)域內(nèi)乘客等待總時(shí)間最小函數(shù)表示如下：

(9)

(10)

城市軌道交通列車運(yùn)行均衡調(diào)整優(yōu)化目標(biāo)函數(shù)用列車總晚點(diǎn)時(shí)間最小函數(shù)和晚點(diǎn)時(shí)域內(nèi)乘客等待總時(shí)間最小函數(shù)的加權(quán)和表示如下：

F=α1×F1+α2×F2=

(11)

其中，α1和α2分別為總晚點(diǎn)時(shí)間最小函數(shù)和晚點(diǎn)時(shí)域內(nèi)乘客等待總時(shí)間最小函數(shù)的權(quán)重值，滿足α1+α2=1。

2 人工魚群優(yōu)化算法

2003年，李曉磊博士提出了人工魚群算法[15]，它是一種模擬自然魚群行為的智能優(yōu)化算法，是一種自上而下的尋優(yōu)結(jié)構(gòu)，其基本行為包括覓食、聚群、追尾和隨機(jī)，逐步聚集在食物濃度最大的地方，通過(guò)模仿自然魚的行為更快地找到全局最優(yōu)值。為了兼顧列車自動(dòng)調(diào)整優(yōu)化效果與求解時(shí)間，本研究采用改進(jìn)的人工魚群算法對(duì)上述模型進(jìn)行求解。

2.1 行為描述

假設(shè)有fishnum條魚，每條魚的狀態(tài)Xi={x1,x2,…,xm},(i=1,2,…,fishnum)為待尋優(yōu)變量，食物濃度f(wàn)(Xi)為適應(yīng)度函數(shù)，人工魚之間距離dij=||Xi-Xj||,visual為人工魚的視野，step為人工魚的步長(zhǎng)，δ為人工魚擁擠度因子，try_number為嘗試次數(shù)。

在城市軌道交通列車運(yùn)行調(diào)整模型中，目標(biāo)函數(shù)F>0恒成立，因此可以得到人工魚群的食物濃度函數(shù)：

1) 覓食行為：假設(shè)人工魚在t時(shí)刻的位置為Xi，在視野內(nèi)隨機(jī)選擇狀態(tài)Xj,如果f(Xi)

在城市軌道交通列車運(yùn)行調(diào)整模型中，對(duì)前進(jìn)條件的要求較為嚴(yán)格，本研究提出改進(jìn)的覓食行為Matlab偽代碼如下：

functiony=AF_prey(Xi)

fori=1∶trynumber

Xj=Xi+Rand*visual;

iff(Xi)

if judge(Xnew)==1

y=Xnew

break;

else

continue;

end

else

continue;

end

end

end

其中：judge(Xnew)為判斷Xnew是否滿足約束條件的函數(shù)，如果滿足約束條件，置1；反之，置0。

2) 聚群行為：假設(shè)人工魚在t時(shí)刻的位置為Xi，計(jì)算視野內(nèi)滿足dijδf(Xi)，則Xi向Xc方向按式(12)得到Xnew，判斷Xnew是否滿足要求，如果滿足則Xnew為下一個(gè)狀態(tài)；否則執(zhí)行覓食行為。

(12)

3) 追尾行為：假設(shè)人工魚在t時(shí)刻的位置為Xi，搜索視野內(nèi)滿足dijδf(Xi),則按式(13)得到Xnew，判斷Xnew是否滿足要求，如果滿足則Xnew為下一個(gè)狀態(tài)；否則執(zhí)行覓食行為。

(13)

4) 隨機(jī)行為：假設(shè)人工魚在t時(shí)刻的位置為Xi，當(dāng)覓食行為重復(fù)try_number次后，仍不滿足約束條件則執(zhí)行隨機(jī)行為：

Xnew=Xi+Rand*step

if judge(Xnew)==1

y=Xnew;

else

y=Xi;

2.2 求解流程

本研究應(yīng)用改進(jìn)的人工魚群算法，對(duì)列車運(yùn)行的出發(fā)時(shí)間和到達(dá)時(shí)間進(jìn)行調(diào)整，求解目標(biāo)函數(shù)值最優(yōu)下的各列列車在各個(gè)站臺(tái)的合理到發(fā)時(shí)問(wèn)，具體求解流程如下：

步驟1參數(shù)初始化。初始化列車運(yùn)行圖XR、列車總數(shù)M、車站總數(shù)N、列車追蹤間隔冗余時(shí)間Tyz、區(qū)間運(yùn)行冗余時(shí)間Tyr和列車各約束條件Ts min、Ts max、Tr min、Tr max、Tg min和Tfd min，輸入列車晚點(diǎn)時(shí)間tdelay；

其中:

步驟2人工魚群參數(shù)初始化。初始化人工魚群種群數(shù)目fishnum、人工魚視野visual、人工魚步長(zhǎng)step、人工魚擁擠度因子δ、嘗試次數(shù)try_number和最大迭代次數(shù)Maxgen；

步驟3根據(jù)式(5)和式(6)計(jì)算晚點(diǎn)時(shí)域參數(shù)；

步驟4根據(jù)晚點(diǎn)時(shí)域參數(shù)，初始化人工魚的狀態(tài)Xi(i=1,2,…,fishnum)，并計(jì)算對(duì)應(yīng)的食物濃度f(wàn)(Xi);

其中

由于城市軌道交通列車運(yùn)行調(diào)整模型約束條件復(fù)雜，因此為了保證初始化的人工魚的狀態(tài)Xi有足夠可行解，提出以下初始化規(guī)則：

行規(guī)則：

Xi(ii,jj+1)=Xi(ii,jj)+Tg min+k*rand

列規(guī)則：

Xi(ii+1,jj)=Xi(ii,jj)+Ts min+k*rand

Xi(ii,jj)為到達(dá)線

Xi(ii+1,jj)=Xi(ii,jj)+Tr min+k*rand

Xi(ii,jj)為出發(fā)線

其中，k是初始化參數(shù)，根據(jù)列車晚點(diǎn)時(shí)間tdelay不同而調(diào)整。在進(jìn)行初始化時(shí)，先初始化人工魚的狀態(tài)的第一行和第一列，然后按照行規(guī)則和列規(guī)則分別計(jì)算下一行的各個(gè)數(shù)據(jù)，對(duì)比選擇既滿足行規(guī)則和列規(guī)則的計(jì)算結(jié)果，判斷結(jié)果是否滿足到發(fā)車約束，如果滿足則初始化成功；否則，選擇相應(yīng)的原到發(fā)車時(shí)間代替不滿足約束的數(shù)據(jù)。

步驟5對(duì)人工魚的狀態(tài)Xi按食物濃度f(wàn)(Xi)降序排列，并設(shè)定全局最優(yōu)pbest(X1)=f(X1)；

步驟6按照人工魚的4種行為對(duì)人工魚的狀態(tài)Xi進(jìn)行更新，并選擇食物濃度最大的行為更新結(jié)果作為人工魚的狀態(tài)Xi；

步驟7判斷是否滿足結(jié)束條件，如果滿足，進(jìn)行步驟8；否則，轉(zhuǎn)到步驟5繼續(xù)執(zhí)行；

步驟8對(duì)人工魚的狀態(tài)Xi按食物濃度f(wàn)(Xi)降序排列，并輸出調(diào)整的列車運(yùn)行時(shí)刻以及對(duì)應(yīng)的全局最優(yōu)解pbest(X1)；

步驟9算法結(jié)束。

算法流程如圖1所示。

圖1 人工魚群算法求解流程框圖

3 實(shí)例仿真

3.1 基本參數(shù)

南京地鐵3號(hào)線全長(zhǎng)44.9 km，其中地下段42.5 km、高架段2.4 km，共有林場(chǎng)站到秣周東路29座站臺(tái)，本研究算法選擇三號(hào)線勝太西路站到新莊站路段早高峰(7∶15∶48—8∶24∶07)期間運(yùn)行的8列車，構(gòu)造列車計(jì)劃時(shí)刻表。列車區(qū)間運(yùn)行參數(shù)以及魚群算法相關(guān)參數(shù)如表1所示。

表1 列車區(qū)間運(yùn)行參數(shù)以及魚群算法參數(shù)

3.2 魚群算法仿真

為了驗(yàn)證算法的適用性和有效性，假設(shè)第4輛車在經(jīng)過(guò)南京南站時(shí)由于隨機(jī)因素發(fā)生晚點(diǎn)，根據(jù)式(5)和式(6)，受晚點(diǎn)影響列車數(shù)Nl和到發(fā)時(shí)間線數(shù)Ns與追蹤間隔冗余時(shí)間Tyz有關(guān)系，故分別選取小于追蹤間隔冗余時(shí)間的晚點(diǎn)時(shí)間、大于1倍追蹤間隔冗余時(shí)間的晚點(diǎn)時(shí)間和大于2倍追蹤間隔冗余時(shí)間的晚點(diǎn)時(shí)間。

1) 當(dāng)晚點(diǎn)時(shí)間小于追蹤間隔冗余時(shí)間Tyz時(shí)，假設(shè)tdelay=40 s，根據(jù)式(5)和式(6)可以確定晚點(diǎn)時(shí)域受影響列車Nl=1和受影響到發(fā)時(shí)間線數(shù)Ns=5，根據(jù)魚群算法得到的適應(yīng)度收斂圖和列車最優(yōu)調(diào)整方案如圖2和圖3所示。

圖2 tdelay=40 s時(shí)魚群收斂曲線

圖3 tdelay=40 s時(shí)列車最優(yōu)調(diào)整方案曲線

從圖2可以看出，改進(jìn)魚群算法的收斂曲線在前50代收斂速度較快，當(dāng)經(jīng)過(guò)60代之后收斂曲線接近水平，算法優(yōu)化結(jié)果為列車總晚點(diǎn)時(shí)間F1=53.055 6 s、列車晚點(diǎn)時(shí)域內(nèi)乘客總等待時(shí)間F2=84 526 s；從圖3可以看出，列車在南京南站到站晚點(diǎn)40 s時(shí)，經(jīng)過(guò)本站發(fā)車時(shí)間調(diào)整，在明發(fā)廣場(chǎng)站就調(diào)整回列車計(jì)劃運(yùn)行圖，調(diào)整效率較高。

2) 當(dāng)晚點(diǎn)時(shí)間大于追蹤間隔冗余時(shí)間Tyz時(shí)，假設(shè)tdelay=80 s，根據(jù)式(5)和式(6)可以確定晚點(diǎn)時(shí)域受影響列車Nl=2和受影響到發(fā)時(shí)間線數(shù)Ns=10，應(yīng)用改進(jìn)魚群算法得到的適應(yīng)度收斂圖和列車最優(yōu)調(diào)整方案如圖4和圖5所示。

圖4 tdelay=80 s時(shí)魚群收斂曲線

圖5 tdelay=80 s時(shí)列車最優(yōu)調(diào)整方案曲線

從圖4可以看出，改進(jìn)魚群收斂曲線在前20代收斂速度較快，當(dāng)經(jīng)過(guò)30代之后收斂曲線接近水平，算法優(yōu)化結(jié)果為列車總晚點(diǎn)時(shí)間F1=389.849 6 s、列車晚點(diǎn)時(shí)域內(nèi)乘客總等待時(shí)間F2=168 180 s；從圖5可以看出，由于列車在南京南站到站晚點(diǎn)80s大于間隔冗余時(shí)間Tyz，所以后續(xù)列車也受到影響，相繼偏離計(jì)劃運(yùn)行圖，在經(jīng)過(guò)改進(jìn)魚群算法調(diào)整后，延誤的車輛均較快調(diào)整到列車計(jì)劃運(yùn)行圖。

3) 為了驗(yàn)證改進(jìn)魚群算法對(duì)列車發(fā)生程度較大的晚點(diǎn)的調(diào)整能力，假設(shè)tdelay=130 s，同理計(jì)算得到晚點(diǎn)時(shí)域受影響列車Nl=3和受影響到發(fā)時(shí)間線數(shù)Ns=15，根據(jù)魚群算法得到的適應(yīng)度收斂圖和列車最優(yōu)調(diào)整方案如圖6和圖7所示。

圖6 tdelay=130 s時(shí)魚群收斂曲線

圖7 tdelay=130 s時(shí)列車最優(yōu)調(diào)整方案曲線

從圖6可以看出，改進(jìn)魚群算法的收斂曲線在前60代收斂速度較快，當(dāng)經(jīng)過(guò)60代之后收斂曲線接近水平，算法優(yōu)化結(jié)果為列車總晚點(diǎn)時(shí)間F1=1 344.8 s、列車晚點(diǎn)時(shí)域內(nèi)乘客總等待時(shí)間F2=8.884 4×105s；從圖7可以看出，在經(jīng)過(guò)改進(jìn)魚群算法調(diào)整后，發(fā)生較大程度晚點(diǎn)的列車也能較快地調(diào)整到列車計(jì)劃運(yùn)行圖，減少了列車間的延誤傳播。

4 結(jié)論

針對(duì)城市軌道交通列車運(yùn)行調(diào)整問(wèn)題，本研究建立了列車運(yùn)行均衡調(diào)整模型；將列車運(yùn)行調(diào)整的多約束條件作為人工魚群的前進(jìn)條件，提出了改進(jìn)人工魚群算法；選取南京地鐵三號(hào)線的列車運(yùn)行數(shù)據(jù)，分別對(duì)晚點(diǎn)時(shí)間40 s、80 s和 130 s 進(jìn)行仿真，形成最優(yōu)調(diào)整方案。仿真結(jié)果表明，改進(jìn)的人工魚群算法可以滿足城市軌道交通列車運(yùn)行調(diào)整的實(shí)時(shí)調(diào)整要求，具有優(yōu)良的適應(yīng)性和高效性，減少了列車間的延誤傳播，保障了列車運(yùn)行效率和客運(yùn)服務(wù)質(zhì)量。