左義盟

(重慶交通大學(xué) 信息科學(xué)與工程學(xué)院,重慶 400074)

在鐵路系統(tǒng)中,經(jīng)常有各類異常事件影響列車正常運(yùn)行.以異常事件發(fā)生的位置分類,可以把它們分為發(fā)生在區(qū)間的異常事件與發(fā)生在車站的異常事件[1].這兩類異常事件中發(fā)生在區(qū)間上發(fā)生的異常事件造成的影響往往比在車站發(fā)生的異常事件更大,而在發(fā)生在區(qū)間的異常事件中,又以區(qū)間失效造成的影響更大.為了避免異常事件帶來更壞的影響,調(diào)度員需及時(shí)做出最優(yōu)或次優(yōu)的調(diào)整.調(diào)整涉及到的內(nèi)容有列車時(shí)刻表、乘務(wù)計(jì)劃與列車交路計(jì)劃,其中列車時(shí)刻調(diào)整是首要調(diào)整任務(wù)[2].

區(qū)間失效后的列車時(shí)刻調(diào)整問題及相關(guān)研究中使用的方法主要有啟發(fā)式算法、分支定界法、元啟發(fā)式算法與專業(yè)數(shù)學(xué)優(yōu)化軟件等,其中啟發(fā)式算法與分支定界法是最常使用的兩種方法[3].Josyula 等人把解空間表示為樹,并提出以深度優(yōu)先的搜索策略為基礎(chǔ)的順序啟發(fā)算法來快速遍歷樹[4].蘭澤康等人提出使用組合列生成算法與分支定界法的分支定價(jià)法求解基于列車路徑的整數(shù)規(guī)劃模型[5].Zhou 等人分別使用進(jìn)化算法與混沌螢火蟲算法獲得列車時(shí)刻調(diào)整方案[6].鄧念和占曙光等人主要研究了高速鐵路列車運(yùn)行實(shí)時(shí)調(diào)整問題,然后直接使用CPLEX 求解其構(gòu)建的模型[7,8];Hou 等研究地鐵系統(tǒng)發(fā)生異常狀況時(shí)如何調(diào)整列車,同樣使用CPLEX 求解[9].彭其淵等人則指出隨著列車和車站數(shù)的增加,模型求解呈指數(shù)型增長,直接求解十分困難,因此他們利用二階段啟發(fā)式算法結(jié)合CPLEX 求解[10].這些經(jīng)典的方法存在的問題是面對較大規(guī)模問題時(shí),求解時(shí)間較長,算法的實(shí)時(shí)性較低.為了提高算法的實(shí)時(shí)性,引入變鄰域下降算法(Variable Neighborhood Descend,VND)快速解決區(qū)間失效后的列車調(diào)整問題.

VND 是由變鄰域搜索算法(Variable Neighborhood Search,VNS)變化而來的一個算法框架,它以某種方式搜索解的鄰域.Shakibayifar 與Sheikholeslami 使用多目標(biāo)變鄰域搜索算法尋找列車調(diào)整問題的帕累托最優(yōu)集[11],本文則利用VND 的局部搜索能力,并定義適用于列車時(shí)刻調(diào)整的鄰域結(jié)構(gòu),結(jié)合禁忌表提出多階段變鄰域下降算法(Multi Stage Variable Neighborhood Descend,MSVND),高效地獲得不改變列車順序時(shí)的調(diào)整后的列車運(yùn)行時(shí)刻.

1 高速鐵路區(qū)間失效的列車時(shí)刻調(diào)整模型

雙線高速鐵路上的列車分向運(yùn)行,兩個運(yùn)行方向上的列車互不干擾.為了簡便起見,本文研究雙線高速鐵路某一個方向上區(qū)間失效后的列車時(shí)刻調(diào)整問題,線路上除了全程運(yùn)行的列車以外,還有只在線路上部分區(qū)間運(yùn)行的列車.

1.1 模型假設(shè)

(1)區(qū)間失效之前的所有列車活動都正常進(jìn)行;

(2)一旦區(qū)間失效,失效持續(xù)時(shí)間可以預(yù)測;

(3)剛好進(jìn)入失效區(qū)間的列車在區(qū)間等待區(qū)間恢復(fù);

(4)時(shí)間的最小單位為分鐘.

1.2 符號說明

某高速鐵路的運(yùn)行指定方向列車的軌道與車站組成有向圖GA=(S,R),其中S={s1,s2,···,sN}是按指定方向排序的車站集合,R={(s1,s2),(s2,s3)···,(sN?1,sN)}是軌道區(qū)間的集合,(si,si+1)表示車站si至車站si+1的軌道區(qū)間,N是線路上的辦理客運(yùn)業(yè)務(wù)的車站數(shù)量.

在GA上運(yùn)行的列車集合為T={t1,t2,···,tM},其中M是列車的數(shù)量.T中的任意一列列車t在GA上運(yùn)行的第一個車站與最后一個車站分別為與,其圖定到發(fā)時(shí)刻與調(diào)整后的到發(fā)時(shí)刻分別為:

Ot與Xt都有 2N個值,從索引1 至索引 2N依次為車站s1至車站sN的到站時(shí)刻與出站時(shí)刻.如果列車t不在某車站運(yùn)行,那么其對應(yīng)的到站與出站時(shí)刻的值為0.相應(yīng)地,E={e1,e2,e3,e4,···,e2N?1,e2N}依次是列車在車站s1至車站sN的進(jìn)站附加時(shí)間、出站附加時(shí)間;G={g1,g2,g3,g4,···,g2N?1,g2N}依次是列車在車站s1至車站sN的最小到站間隔時(shí)間、最小出站間隔時(shí)間.

表1 參數(shù)與變量符號及說明

1.3 模型構(gòu)建

1.3.1 基本模型

以最小化列車在各車站的總晚點(diǎn)時(shí)間為目標(biāo),可以構(gòu)建列車運(yùn)行調(diào)整的基本模型如下:

式(1)是列車時(shí)刻調(diào)整的目標(biāo);式(2)表示區(qū)間失效之前;列車按照計(jì)劃時(shí)刻運(yùn)行;式(3)表示列車在計(jì)劃停站的車站的出站時(shí)刻不早于其計(jì)劃出站時(shí)刻;式(4)限定列車的區(qū)間運(yùn)行時(shí)分;式(5)限定若列車在車站s停站,則其停站時(shí)間不能小于最小停站時(shí)間,若列車在車站s不停車,則列車的停站時(shí)間為0;式(6)表示列車的停站選擇約束,在其計(jì)劃停站的車站必須停站.

1.3.2 其他約束

除了單列列車的約束條件以外,還有列車之間因?yàn)榛ハ嘤绊懚枳袷氐囊恍┘s束條件.

(1)出發(fā)間隔時(shí)間與到達(dá)間隔時(shí)間約束

式(7)表示任意兩列列車在車站的到站與出站間隔時(shí)間都滿足最小間隔時(shí)間約束.

(2)出發(fā)與到達(dá)間隔時(shí)間約束

式(8)表示兩列列車占用車站相同軌道需要滿足最小發(fā)到間隔時(shí)間.

(3)車站能力約束

式(9)表示列車t在到達(dá)車站s的時(shí)候,車站s應(yīng)有能力為列車t提供服務(wù).

(4)列車越行約束

式(10)表示列車t與t′在某站的出站時(shí)刻之差與在前一車站的到站時(shí)刻之差應(yīng)同正負(fù),其意義是列車不能在區(qū)間越行.

2 多階段變鄰域下降算法

2.1 初始解

在獲得初始解之前,根據(jù)列車的所有圖定時(shí)刻是否在r1之 前把列車分為需調(diào)整的列車集合T1與不需調(diào)整的列車集合,其中T1的列車數(shù)量為M1.在需調(diào)整的列車集合T1中有兩類車直接導(dǎo)致線路上的列車受到影響,一類是在r1及 之前的某時(shí)刻進(jìn)入?yún)^(qū)間(s0,)且未在r2前離開的列車,另一類是在時(shí)間段(r1,r2)到達(dá)車站s0的列車,分別如圖1中實(shí)斜線與虛斜線所示,并令它們分別組成集合T0與T0′.如果沒有上述兩類列車,所有的列車能夠按照各自的圖定時(shí)刻運(yùn)行.如果有這兩類列車的任意一種,則需要調(diào)整列車集合T1中列車的時(shí)刻,并且需調(diào)整的時(shí)刻是大于r1的時(shí)刻.令(It,Jt)為列車集合T1中 任意一列列車t的圖定到發(fā)時(shí)刻中大于r1的時(shí)刻的起止索引,It與Jt分別是大于r1的時(shí)刻的最小索引與最大索引.例如某列車在車站s0與車站sN之間的所有時(shí)刻都需調(diào)整,它的起止索引為(1,2N).

圖1 直接導(dǎo)致線路上列車受影響的兩類列車

本文使用右移法獲得算法的初始解,該方法把圖定的大于r1的所有時(shí)刻加上某時(shí)間長度,相當(dāng)于大于r1的所有時(shí)刻在列車運(yùn)行圖上整體向右移動了某時(shí)間長度.假設(shè)集合T0中的列車到達(dá)車站的時(shí)刻最早為r1,集合T0′中的列車從s0出 站的時(shí)刻最早為r1,則右移的時(shí)間長度如下:

2.2 多階段變鄰域下降算法

2.2.1 第1 階段變鄰域下降算法

(1)鄰域結(jié)構(gòu)

為列車集合T1中的每列列車t定義一個與其圖定時(shí)刻Ot等長的整體平移鄰域結(jié)構(gòu)Nt,在其起止索引(It,Jt)范圍內(nèi)的值為?1,其余值為0,例如某列車從車站s0到車站sN的全部時(shí)刻都需調(diào)整,其鄰域結(jié)構(gòu)為{?1,?1,?1,?1,…,?1,?1},其意義是列車t所有需調(diào)整的時(shí)刻在列車運(yùn)行圖中都整體向左平移1 分鐘.

因?yàn)檫\(yùn)行時(shí)刻在前的列車影響運(yùn)行時(shí)刻在后的列車、運(yùn)行位置在前方的列車影響運(yùn)行位置在后方的列車,優(yōu)先平移運(yùn)行時(shí)刻與運(yùn)行位置在前方的列車可以加快鄰域搜索.因此列車集合T1對應(yīng)的整體平移鄰域結(jié)構(gòu)集合N _T1中鄰域結(jié)構(gòu)按照列車的起始索引與索引對應(yīng)的時(shí)刻排序.

(2)禁忌表

在對列車集合T1中的列車進(jìn)行鄰域搜索的過程中,當(dāng)某列車恢復(fù)到其圖定時(shí)刻時(shí),將該列車加入到禁忌表中,在禁忌表中的列車不再進(jìn)行鄰域搜索.

(3)約束條件

列車圖定時(shí)刻Ot隱式地包含了列車安全運(yùn)行的約束條件,在列車時(shí)刻整體平移的過程中不需要檢驗(yàn)鄰域中的解是否滿足模型中的所有約束條件,只需遵守式(3),式(7),式(9)就能保證列車安全運(yùn)行.

基于前述鄰域結(jié)構(gòu)、禁忌表與約束條件設(shè)計(jì)的第1 階段多鄰域下降算法的偽代碼如算法1.

算法1.第1 階段多鄰域下降算法輸入:,X=(Xt1,Xt2,···,XtM1),N_T1=(N_t1,N_t2,···,N_tM1)1 Tabu:=? 2 repeat 3 for k=1 to M1 4 change=True 5 while change do Xtk′:=N_tk(Xtk)6 Xtk′7 if 滿足各種約束條件 then Xtk:=Xtk′8 9 else then 10 change=False 11 end Xtk=Otk 12 if then Tabu:=Tabu∪tk 13 14 end 15 end 16 M1:=在列車集合 中但不在禁忌表Tabu 中的列車數(shù)量;T1

17 until 某列車在第1 次沒有更優(yōu)解與第2 次沒有更優(yōu)解之間其他列車也沒有更優(yōu)解.

算法1 中步驟2 至17 調(diào)整T1中所有列車直至它們在對應(yīng)的鄰域結(jié)構(gòu)中沒有更優(yōu)解.其中步驟3 至13 按照指定規(guī)則依次調(diào)整T1的一列列車,步驟5 至11 循環(huán)調(diào)整列車tk,如果列車的新時(shí)刻能滿足約束條件就一直搜索其鄰域,否則就跳出循環(huán);步驟12 至14 表示列車tk調(diào)整后的時(shí)刻與原計(jì)劃時(shí)刻相等時(shí),將列車加入到禁忌表中.

2.2.2 第2 階段變鄰域下降算法

第2 階段的算法流程與第1 階段一致,區(qū)別只是第2 階段調(diào)整區(qū)間失效后仍在車站s1與s0之間運(yùn)行的列車.假設(shè)這些列車組成集合T2′,令列車集合T2′中的列車調(diào)整的起止索引為其中

(1)鄰域結(jié)構(gòu)

為列車集合T2′中的每列列車t定義一個與Ot等長的部分平移鄰域結(jié)構(gòu),在索引范圍內(nèi)的值為–1,其余則為0.

(2)禁忌表

如果T2′中的列車t在其調(diào)整的起止索引范圍(,)內(nèi)恢復(fù)圖定時(shí)刻,將列車t加入到第2 階段禁忌表中,在第2 階段鄰域搜索中不再搜索該列車.

(3)約束條件

第2 階段變鄰域下降算法需要遵守式(3),式(5),式(7)–式(9)表示的約束條件.

2.2.3 第3 階段變鄰域下降算法

第3 階段調(diào)整的列車是T2中不在第2 階段禁忌表中的列車或在禁忌表中而其終止索引Jt≥2?s0?2引的列車,假設(shè)它們組成集合T3,T3中列車數(shù)量為M3,其中的列車t需要調(diào)整時(shí)刻的起止索引為如果列車t在第2 階段禁忌表中而其終止索引Jt≥2?s0?1,那么列車t的起止索引更新為 (2?s0?1,Jt),其余列車的起止索引不變.

(1)鄰域結(jié)構(gòu)

為列車集合T3中的每列列車t定義一系列與Ot等長的鄰域結(jié)構(gòu).如果列車t的起始索引對應(yīng)的是到達(dá)時(shí)刻,為該列車定義一個到達(dá)平移鄰域結(jié)構(gòu),該索引對應(yīng)的值為?1,其余值為0;然后定義÷2個發(fā)到平移鄰域結(jié)構(gòu),這些鄰域結(jié)構(gòu)分別在索引等對應(yīng)位置取值為?1,其余取0.如果列車t的起始索引對應(yīng)的是出發(fā)時(shí)刻,則直接定義÷2個發(fā)到平移鄰域結(jié)構(gòu),它們分別在索引等對應(yīng)位置取值為?1,其余取值為0.因此列車集合T3中的列車t具有一個鄰域結(jié)構(gòu)集合 N _t,集合中至少有一個鄰域結(jié)構(gòu).

(2)約束條件

第3 階段變鄰域下降算法需要遵守式(3),式(5),式(7)–式(9)表示的約束條件.

第3 階段變鄰域下降算法的偽代碼如算法2.

算法2.第3 階段多鄰域下降算法輸入:X=(Xt1,Xt2,···,XtM3),N_T3=(N_t1,N_t2,···,N_tN3)k:=min(I3t1,I3t2,···,I3tM3) t1,t2,···,tM3∈T 1 2 repeat s=?(k+1)÷2? sN 3 for to Ts3:=T3 I3t≤2×s≤J3t 4 中索引 的列車組成的集合Ms3:=Ts3 5 列車集合 中元素個數(shù)Ms3 6 for m=1 to 7 change=True 8 while change do Xtm′:=N_tsm(Xtm)tm∈Ts3 9,N_tsm N_tm 為 中車站s 對應(yīng)的鄰域結(jié)構(gòu)Xtm′10 if 滿足各種約束條件 then Xtm:=Xtm′11 12 else then 13 change=False 14 end 15 end 16 end T3 17 until 在列車集合 中的任意列車的任意鄰域中搜索都不能獲得更優(yōu)解.

2.2.4 調(diào)整階段

本階段針對列車t在某車站s原計(jì)劃不停車而調(diào)整后到達(dá)時(shí)刻與出發(fā)時(shí)刻不同的情況.若滿足條件的列車t在車站s的出發(fā)時(shí)刻與到達(dá)時(shí)刻之差大于等于hs+es×2+es×2?1且滿足其他約束條件,令其在車站s的停站計(jì)劃為1;否則,令到達(dá)時(shí)刻與到達(dá)時(shí)刻等于它們兩個時(shí)刻之間最小的且滿足約束條件的時(shí)刻.

3 實(shí)例分析

以西成客運(yùn)專線上行方向?yàn)槔?根據(jù)2019年7月某日上線運(yùn)行的列車進(jìn)行實(shí)例分析.算法基于Python3.6實(shí)現(xiàn),所有實(shí)驗(yàn)都使用CPU 為Intel(R)Core(TM)i7-7500U 2.70 GHz,內(nèi)存為8 GB 的計(jì)算機(jī)完成.

3.1 數(shù)據(jù)準(zhǔn)備

西成客運(yùn)專線上行方向辦理客運(yùn)業(yè)務(wù)的車站共有22 個,車站將線路劃分為21 個區(qū)間.當(dāng)日上線運(yùn)營的列車有89 列,其中44 列全程運(yùn)行,其余45 列只在西成客運(yùn)專線某段運(yùn)行.

算例的其他參數(shù)按如下規(guī)則設(shè)置.兩列列車同一車站的到達(dá)間隔時(shí)間與出發(fā)間隔時(shí)間都為2 分鐘,車站使用相同到發(fā)線的發(fā)到間隔約束時(shí)間為3 分鐘.青川站的起停附加時(shí)間為3 分鐘,其余車站的起停附加時(shí)間為2 分鐘.

3.2 實(shí)驗(yàn)及對比分析

實(shí)驗(yàn)設(shè)置4 種基本失效場景,4 種場景由兩類失效區(qū)間(綿陽至青蓮,寧強(qiáng)南至漢中)與兩類失效開始時(shí)刻(10:00,16:00)兩兩組合而成,每種失效場景下又分別對應(yīng)20,60,120 分鐘3 類失效持續(xù)時(shí)間.此外,使用CPLEX 獲得上述多種失效場景下的列車停止結(jié)果并進(jìn)行對比分析.CPLEX 求解時(shí)間設(shè)置為3 小時(shí),其余保持默認(rèn)設(shè)置,不包含約束條件(8).由MSVND 與CPLEX 獲得的列車調(diào)整結(jié)果如表2所示.

由表2可以看出,MSVND 在獲得列車調(diào)整結(jié)果上展示了優(yōu)秀的效率.相同失效區(qū)間與失效開始時(shí)刻下,計(jì)算時(shí)間隨著失效持續(xù)時(shí)間增加而增加.在所有失效場景中(寧強(qiáng)南至漢中,10:00,120)的計(jì)算時(shí)間最長,共20.765 s;失效持續(xù)時(shí)間為20 s 的場景的最長計(jì)算時(shí)間是 3.322 s.此外,從表2可以看出第一階段計(jì)算時(shí)間占比都大于60%,且失效持續(xù)時(shí)間為20 與60 分鐘時(shí),該占比大于80%.

由表2中目標(biāo)值與CPLEX 求解目標(biāo)值進(jìn)行比較可以看出,M-S VND 得到的列車運(yùn)行時(shí)調(diào)整結(jié)果與CPLEX 得到的結(jié)果差別較小.在計(jì)算時(shí)間方面,CPLEX計(jì)算時(shí)間只有(寧強(qiáng)南至漢中,16:00,20)的計(jì)算時(shí)間小于3 小時(shí),其余場景在使用CPLEX 求解時(shí)在3 小時(shí)內(nèi)都未完成求解.與MSVND 相比,CPLEX 求解耗費(fèi)的計(jì)算時(shí)間太多,反應(yīng)了MSVND 在計(jì)算時(shí)間方面優(yōu)秀的性能.

4 結(jié)論與展望

將多階段變鄰域下降算法應(yīng)用到區(qū)間失效后的列車運(yùn)行時(shí)刻調(diào)整問題,實(shí)驗(yàn)證明算法調(diào)整的結(jié)果與全局最優(yōu)結(jié)果相比沒有差距,同時(shí)其計(jì)算時(shí)間又有顯著的提升,表明了算法在列車運(yùn)行時(shí)刻調(diào)整問題中的有效性與實(shí)時(shí)性.第一階段快速確定哪些列車恢復(fù)到圖定時(shí)刻,可以結(jié)合其他方法對未恢復(fù)到圖定時(shí)刻的列車進(jìn)行調(diào)整,減少其他方法直接調(diào)整的范圍.

表2 列車運(yùn)行時(shí)刻調(diào)整結(jié)果