基于變鄰域下降的列車運行時刻調整算法①

左義盟

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

在鐵路系統中,經常有各類異常事件影響列車正常運行.以異常事件發生的位置分類,可以把它們分為發生在區間的異常事件與發生在車站的異常事件[1].這兩類異常事件中發生在區間上發生的異常事件造成的影響往往比在車站發生的異常事件更大,而在發生在區間的異常事件中,又以區間失效造成的影響更大.為了避免異常事件帶來更壞的影響,調度員需及時做出最優或次優的調整.調整涉及到的內容有列車時刻表、乘務計劃與列車交路計劃,其中列車時刻調整是首要調整任務[2].

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

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

1 高速鐵路區間失效的列車時刻調整模型

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

1.1 模型假設

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

(2)一旦區間失效,失效持續時間可以預測;

(3)剛好進入失效區間的列車在區間等待區間恢復;

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

1.2 符號說明

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

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

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

表1 參數與變量符號及說明

1.3 模型構建

1.3.1 基本模型

以最小化列車在各車站的總晚點時間為目標,可以構建列車運行調整的基本模型如下:

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

1.3.2 其他約束

除了單列列車的約束條件以外,還有列車之間因為互相影響而需遵守的一些約束條件.

(1)出發間隔時間與到達間隔時間約束

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

(2)出發與到達間隔時間約束

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

(3)車站能力約束

式(9)表示列車t在到達車站s的時候,車站s應有能力為列車t提供服務.

(4)列車越行約束

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

2 多階段變鄰域下降算法

2.1 初始解

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

圖1 直接導致線路上列車受影響的兩類列車

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

2.2 多階段變鄰域下降算法

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

(1)鄰域結構

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

因為運行時刻在前的列車影響運行時刻在后的列車、運行位置在前方的列車影響運行位置在后方的列車,優先平移運行時刻與運行位置在前方的列車可以加快鄰域搜索.因此列車集合T1對應的整體平移鄰域結構集合N _T1中鄰域結構按照列車的起始索引與索引對應的時刻排序.

(2)禁忌表

在對列車集合T1中的列車進行鄰域搜索的過程中,當某列車恢復到其圖定時刻時,將該列車加入到禁忌表中,在禁忌表中的列車不再進行鄰域搜索.

(3)約束條件

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

基于前述鄰域結構、禁忌表與約束條件設計的第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 中的列車數量;T1

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

算法1 中步驟2 至17 調整T1中所有列車直至它們在對應的鄰域結構中沒有更優解.其中步驟3 至13 按照指定規則依次調整T1的一列列車,步驟5 至11 循環調整列車tk,如果列車的新時刻能滿足約束條件就一直搜索其鄰域,否則就跳出循環;步驟12 至14 表示列車tk調整后的時刻與原計劃時刻相等時,將列車加入到禁忌表中.

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

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

(1)鄰域結構

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

(2)禁忌表

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

(3)約束條件

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

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

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

(1)鄰域結構

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

(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 列車集合 中元素個數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 對應的鄰域結構Xtm′10 if 滿足各種約束條件 then Xtm:=Xtm′11 12 else then 13 change=False 14 end 15 end 16 end T3 17 until 在列車集合 中的任意列車的任意鄰域中搜索都不能獲得更優解.

2.2.4 調整階段

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

3 實例分析

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

3.1 數據準備

西成客運專線上行方向辦理客運業務的車站共有22 個,車站將線路劃分為21 個區間.當日上線運營的列車有89 列,其中44 列全程運行,其余45 列只在西成客運專線某段運行.

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

3.2 實驗及對比分析

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

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

由表2中目標值與CPLEX 求解目標值進行比較可以看出,M-S VND 得到的列車運行時調整結果與CPLEX 得到的結果差別較小.在計算時間方面,CPLEX計算時間只有(寧強南至漢中,16:00,20)的計算時間小于3 小時,其余場景在使用CPLEX 求解時在3 小時內都未完成求解.與MSVND 相比,CPLEX 求解耗費的計算時間太多,反應了MSVND 在計算時間方面優秀的性能.

4 結論與展望

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

表2 列車運行時刻調整結果