蔣靈明，倪少權(quán)

(1.西南交通大學(xué) 交通運輸與物流學(xué)院，四川 成都 611756；2.北京全路通信信號研究設(shè)計院集團有限公司，北京 100070)

鐵路作為高效、綠色的陸地交通方式,是中國、日本、韓國和歐洲等國家和地區(qū)的主要公共交通運輸方式。根據(jù)國際鐵路聯(lián)盟(UIC)發(fā)布的數(shù)據(jù)[1-2]:2017年全球鐵路里程、客運和貨運分別達(dá)到801 357 km、2 783億人·km和8 991億t·km。鐵路特別適用于重型、散裝和長途的大宗商品運輸,例如貨運鐵路分別占美國和中國總運輸份額的55%和50%[1]。而且,與公路運輸(例如卡車)相比,貨物列車平均減少了75%的溫室氣體排放與直接能耗[3]。

貨運鐵路網(wǎng)絡(luò)的輸運能力由速度、載重和運營效率決定。由于惡劣天氣、臨時限速、鐵路建設(shè)或維護、自然災(zāi)害甚至列車事故等原因,貨物列車的到達(dá)、出發(fā)和停留時間都會有所延誤。更嚴(yán)重的是,延誤會在一定范圍內(nèi)傳播,導(dǎo)致大面積列車延誤,降低運營效率[4]。本文重點關(guān)注原計劃列車時刻表面臨不同延誤干擾下貨物列車運營效率的提升,以實時或動態(tài)方式重新調(diào)度列車,使得延誤或成本降至最低。因此,列車運行計劃動態(tài)調(diào)整具有重要理論意義和應(yīng)用價值,已成為研究熱點[5-6]。

列車運行圖調(diào)整或運行動態(tài)調(diào)整是一個NP完全問題。如文獻(xiàn)[5-20]所述,列車運行圖調(diào)整的恢復(fù)模型和算法涉及數(shù)學(xué)規(guī)劃、啟發(fā)式算法[7-8]、智能算法等。采用啟發(fā)式算法的替代圖模型或整數(shù)線性規(guī)劃模型能夠得到有效解[5,9-10],但在處理大規(guī)模調(diào)度問題時面臨嚴(yán)峻挑戰(zhàn)。與此同時,遺傳算法、模擬退火法、粒子群優(yōu)化算法和神經(jīng)網(wǎng)絡(luò)等智能算法在優(yōu)化補償列車時刻表的延誤擾動方面也展現(xiàn)非凡實力[8,14-18]。

近年,作為一種先進(jìn)智能算法——強化學(xué)習(xí)[21-22]被廣泛應(yīng)用于鐵路交通管理中,如信號控制、列車調(diào)度或運行圖調(diào)整[23-29]。強化學(xué)習(xí)結(jié)合了動態(tài)規(guī)劃和有監(jiān)督學(xué)習(xí),適用于難以精確建模甚至無法數(shù)學(xué)建模的復(fù)雜環(huán)境。因此,強化學(xué)習(xí)是一種典型的無模型方法,它在獲取優(yōu)化的參數(shù)后,可以應(yīng)用于不同環(huán)境[21],具有優(yōu)良的泛化性。因此,強化學(xué)習(xí)算法(Q-learning等)已經(jīng)在研究高速鐵路(以下簡稱“高鐵”)、城際列車和地鐵的運行計劃動態(tài)調(diào)整中發(fā)揮了重要作用[30-43],包括來自斯洛文尼亞[31]、英國[32-33]、荷蘭[34-36]、印度[37-39]、韓國[40]和中國[41-43]的研究案例。

在上述研究工作的啟發(fā)下,本文首次提出基于多智能體強化學(xué)習(xí)(Multi-agent Reinforcement Learning, MARL)突破大規(guī)模貨物列車的運行計劃動態(tài)調(diào)整難題,具有開創(chuàng)性參考價值。一方面,貨物列車的規(guī)模(數(shù)量)遠(yuǎn)大于客運列車,其運行計劃動態(tài)調(diào)整更為關(guān)鍵。然而,相較于高鐵和地鐵已經(jīng)引入了多種智能型動態(tài)調(diào)整技術(shù)[30-43],貨物列車的動態(tài)調(diào)整仍然以傳統(tǒng)方法為主[44-50],且動態(tài)調(diào)整的效率具有一定局限性。另一方面,MARL在處理大規(guī)模貨物列車運行計劃動態(tài)調(diào)整問題上優(yōu)勢顯著,而傳統(tǒng)智能算法難以乃至不能實時或快速地處理。具體而言,貨物列車運行計劃動態(tài)調(diào)整將采用“多智能體”模式,而不是傳統(tǒng)的“單智能體”模式[51]。多智能體算法被廣泛應(yīng)用于AlphaGo、智能多機器人、道路交通信號控制和分布式系統(tǒng)控制[27-28,51],具有并行優(yōu)化和動態(tài)策略選擇的優(yōu)越性能。從原理上分析,MARL采用馬爾可夫博弈(或隨機博弈),引入了智能體之間交互(協(xié)作、沖突或組合)這一新自由度進(jìn)行決策優(yōu)化,而不是傳統(tǒng)單智能體強化學(xué)習(xí)算法(Single-agent Reinforcement Learning, SARL)的馬爾可夫決策過程。對應(yīng)地,區(qū)段網(wǎng)內(nèi)的貨物列車可以組合成多個智能體,分別與環(huán)境進(jìn)行交互,構(gòu)建多智能體模式,而單智能體模式則是由所有列車組成的一個公共智能體與環(huán)境進(jìn)行交互。因此,與單智能體算法相比,所提出的MARL的算法復(fù)雜度和計算時間呈現(xiàn)指數(shù)函數(shù)趨勢下降。

本文首先闡述貨物列車運行計劃動態(tài)調(diào)整場景、基于MARL的運行計劃動態(tài)調(diào)整算法,以及動態(tài)調(diào)整的實現(xiàn)過程;然后以包頭—神木貨運鐵路為案列,進(jìn)行模擬實驗,驗證運行計劃動態(tài)調(diào)整方法的性能與效率,并與傳統(tǒng)SARL進(jìn)行性能比較;最后進(jìn)行總結(jié)和討論。

1 面向貨物列車的多智體強化學(xué)習(xí)方法

1.1 場景描述

貨物列車運行動態(tài)調(diào)整的鐵路場景見圖1:由雙向運行(上行和下行方向)的單線軌道和4個車站(S1、S2、S3和S4)組成。由于貨物列車整車較長,兩個相鄰站點之間設(shè)置為一個站間閉塞分區(qū),共計3個站間閉塞分區(qū)。車站和站間閉塞分區(qū)的軌道都被定義為位置資源(詳見2.2節(jié)),并按“1,2,3,…,14”進(jìn)行編號排序。大多數(shù)情況下,貨物列車(G1和G3下行列車,G2和G4上行列車)按照原計劃時刻表在車站和站間閉塞分區(qū)之間有序運行。

圖1 貨物列車運行計劃動態(tài)調(diào)整的鐵路場景

為充分滿足鐵路運營的安全約束,對場景做以下近似理想合理約束:

(1)每列貨物列車被視為一個質(zhì)點,其位于車站軌道或站間閉塞分區(qū),而不會同時占用站間閉塞分區(qū)和車站的軌道。

(2)每個車站由多條并行軌道(到發(fā)線)組成,可容納列車數(shù)不超過并行軌道(到發(fā)線)數(shù)目。

(3)車站軌道和站間閉塞分區(qū)都必須滿足唯一的資源占用約束,以確保列車運行的安全性,即該資源在某時刻只能為空閑狀態(tài)或被一列列車占用。

(4)貨物列車在車站可提前一定時間發(fā)車,以有效補償延誤干擾,而客運列車或地鐵不允許。

(5)所有貨物列車的運行速度相同(例如,包頭—神木鐵路速度為80 km/h),不考慮速度差異。

1.2 基于MARL的列車運行動態(tài)調(diào)整的原理與步驟

與SARL的“單智能體”模式不同,MARL采用“多個智能體”。為此,設(shè)計并定義兩個不同的智能體,分別涵蓋下行和上行貨物列車,且這兩個智能體與鐵路環(huán)境交互,觀察多個貨物列車的狀態(tài)(位置資源)和基礎(chǔ)設(shè)施資源(車站、軌道和站間閉塞分區(qū))的可用性。兩個智能體(下行和上行列車)之間的相互作用以及與環(huán)境的交互見圖2,每個智能體包含3個核心因素:狀態(tài)、動作和獎勵。MARL利用當(dāng)前狀態(tài)下的獎勵(貨物列車總延誤時間最小化)積累學(xué)習(xí)經(jīng)驗完成Q-table更新,引導(dǎo)多智能體不斷試錯學(xué)習(xí)并逐步收斂,在安全運行條件下以最優(yōu)動作(停止或前進(jìn))來最小化總延誤時間。

圖2 兩個智能體(下行和上行列車)之間的相互作用以及與環(huán)境的交互

在算法收斂和計算效率之間保持平衡的前提下,可以為特定場景設(shè)置更多智能體,而不僅局限于2個智能體。

圖2中:sd、su分別為所有下行、上行貨物列車的位置集;rd、ru分別為所有下行、上行貨物列車的獎勵函數(shù)矩陣;ad、au分別為所有下行、上行貨物列車的動作矩陣;A為耦合動作矩陣。

在MARL方法中,智能體的狀態(tài)、行動和獎勵定義如下:

(1)狀態(tài)定義為貨物列車在每個時刻的位置資源及占用,即車站到發(fā)線或站間閉塞分區(qū)。圖2中所有位置資源都按“1,2,3,…,14”進(jìn)行編碼和排序,每個智能體的狀態(tài)由該智能體所包括的多個貨物列車的位置集組成。

(2)動作定義為每列列車的兩個可用動作(“停車”或“行駛”)。當(dāng)考慮N列貨物列車(N/2列下行列車和N/2列上行列車)時,每個智能體都有2N/2個行動集。假設(shè)任一列車(重車或空車)都可以在車站停車或行駛,但在站間閉塞分區(qū)必須行駛。

(3) 獎勵定義為所有貨物列車延誤時間之和的倒數(shù)或者延誤時間平方之和的倒數(shù),即

( 1 )

或

( 2 )

由式( 1 )可知,每個智能體的獎勵隨著總延遲時間的減少而增加。當(dāng)所有智能體到達(dá)最終狀態(tài)時(即所有下行和上行列車都到達(dá)終點站),可以獲得獎勵。此外,還需設(shè)置一些懲罰機制,以促進(jìn)MARL算法的收斂。例如,當(dāng)?shù)鷷r間ti超過時間閾值而貨物列車未能全部到達(dá)終點站時,訓(xùn)練過程中斷且獎勵為負(fù)值。因此,獎勵函數(shù)進(jìn)一步改寫為

( 3 )

Tthreshold=Tspan+Tdelay+Tset

式中:ri為列車的獎勵函數(shù);β為放大常數(shù),用于調(diào)控算法收斂速度;Tthreshold為閾值;Tspan為第一列車出發(fā)時刻與最后一列車到達(dá)時刻之間的時間跨度;Tdelay為所有列車干擾延誤時間的總和;Tset為具體時間常數(shù)(設(shè)置為10 min)。另外,為避免局部最優(yōu)和縮短訓(xùn)練時間,將時間閾值設(shè)置為MARL算法每輪訓(xùn)練結(jié)束的標(biāo)志。

在場景描述和參數(shù)定義之后,進(jìn)一步闡述基于MARL的列車運行計劃動態(tài)調(diào)整的詳細(xì)過程。兩個智能體之間采用獨立學(xué)習(xí)和相互競爭的混合策略,因此采用Q-learning方法來獲得多個貨物列車之間的最優(yōu)動作(“停止”或“前進(jìn)”)策略。對應(yīng)于1.2小節(jié),定義的兩個智能體(下行和上行貨物列車)的3個關(guān)鍵因素(狀態(tài)、行為和獎勵)可以進(jìn)一步描述為

式中:S包括所有基礎(chǔ)設(shè)施資源(車站軌道和站間閉塞分區(qū)),按順序列為貨物列車的可執(zhí)行位置;A為由兩個智能體的2N/2+2N/2=2(1+N/2)個單獨操作所組成的動作集,假設(shè)下行列車和下行列車的數(shù)量(N/2)相同。同樣場景下,單智體模式的SARL方法卻具有2N個獨立的動作。

經(jīng)過對比,不難發(fā)現(xiàn):MARL方法的復(fù)雜度由O(2N)降到O[2(1+N/2)]。假設(shè)面向22列貨物列車(第3節(jié)),MARL的算法復(fù)雜性或計算時間降低為SARL計算時間的約1‰(即1/1 024)。因此,該MARL方法能夠高效、實時地完成貨物列車的運行計劃動態(tài)調(diào)整任務(wù),特別是大規(guī)模動態(tài)調(diào)整。

此外,每個智能體的動作通過ε貪婪策略進(jìn)行決策,以ε為探索率決定執(zhí)行動作的概率,即

( 4 )

( 5 )

式中:μ(t,ai|si)表示第i個智能體(i=d或u)在時間t和狀態(tài)si下目標(biāo)動作集合;A(t,si)為在時間t狀態(tài)si的所有可能動作集;rand為標(biāo)準(zhǔn)正態(tài)分布;a*為與時刻t時狀態(tài)si中最大值Q對應(yīng)的動作;其余參數(shù)見表1。

由式( 5 )可知:隨著訓(xùn)練片段的增加,ε逐漸減小并接近于零,即隨著訓(xùn)練代數(shù)增加,智能體傾向于使用學(xué)習(xí)經(jīng)驗,從而產(chǎn)生最優(yōu)動作集。

Q-learning通?；跔顟B(tài)和動作來構(gòu)造Q-table的更新規(guī)則。在基于MARL的列車運行計劃動態(tài)調(diào)整過程中,狀態(tài)由列車數(shù)量(N)、車站數(shù)量(M)和時間跨度Tspan組成,所有狀態(tài)的數(shù)量達(dá)到MN×Tspan。因此,Q-table中元素數(shù)量增加到MN×Tspan×2(1+N/2)。隨著列車規(guī)模增加,Q-table中的元素數(shù)量呈現(xiàn)出爆炸性增長。為降低復(fù)雜度,結(jié)合時間和動作構(gòu)建Q-table,則第i個智能體的Q-table為

Qi(t+Δt,ai)=Qi(t,ai)+

α[ri-Qi(t,ai)+γgmaxQi(t,:)

( 6 )

式中:Δt為時間步長;ri為第i個智能體在狀態(tài)si執(zhí)行動作ai而獲得的獎勵。maxQi(t,:)為時刻t的最大Q值。表1和算法1詳細(xì)給出了的MARL的參數(shù)定義和算法步驟。

算法1基于MARL的列車運行動態(tài)調(diào)整算法

輸入:α,β,T_table,Q_table,max_episode,S_matrix,delay_time,delay_point;

輸出:opt_plan;

輸入(Train_environment,Q_table,episode)

1: forepisode=1:max_episode

2: 輸入(t,states,done)給上下行智能體;

3: while !done do

4: foragent_i:

5:state_i=states(i);

6: [action_i,res_i] =get_act_res(t,state_i);

7:actions= [train_i],ress= [res_i];

8:check_action_res(actions,ress);

9: [states_,rewards,done] =step(t,states,

actions,ress);

10: foragent_i:

11:Q(t,action_i,agent_i) =

12:Q(t,action_i,agent_i) +α[reward_i+γmaxQ(t,action_i,agent_i)];

13:t=t+ 1;

14:states=states_;

15: end

16:opt_plan=greedy(Q_table);

17:plot(opt_plan);

18: end

2 基于多智體強化學(xué)習(xí)的貨物列車運行計劃動態(tài)調(diào)整案例

2.1 包頭—神木鐵路中等規(guī)模的動態(tài)調(diào)整

萬南場—東勝區(qū)段貨物列車運行計劃動態(tài)調(diào)整場景見圖3,這是包頭—神木煤炭貨運鐵路主干部分。該區(qū)段由91.4 km的雙向單線軌道組成,設(shè)有9個車站和8個站間閉塞分區(qū)。對應(yīng)地,萬南場—東勝區(qū)段可構(gòu)建69個位置資源,由車站軌道(到發(fā)線)和站間閉塞分區(qū)組成;計劃期間共有22列貨物列車,上行和下行各為11列。

為比較MARL與SARL的性能,首先研究一個中等規(guī)模貨物列車的運行動態(tài)調(diào)整。中等規(guī)模貨物列車運行動態(tài)調(diào)整的3種算法(MARL、SARL和FIFO)性能比較見表2,如表2所示,選取1列或3列列車晚點場景下的5種延誤擾動條件,并進(jìn)行動態(tài)調(diào)整測試。本文聚焦延誤擾動(表2)為決策者已知的場景下,利用MARL與SARL方法實現(xiàn)貨物列車的運行動態(tài)調(diào)整。

表2 中等規(guī)模貨物列車運行動態(tài)調(diào)整的3種算法性能比較

本文采用通用計算機(AMD Ryzen 7 5800X 8核3.79 GHz CPU和64GB RAM)完成貨物列車運行動態(tài)調(diào)整程序的測試。如表2所示,MARL方法的收斂迭代均為250次以內(nèi),且對所有擾動條件下的優(yōu)化調(diào)整均收斂有效。進(jìn)一步選擇兩種擾動情景進(jìn)行詳細(xì)分析,見表3。如圖4(a)和圖4(b)所示,在兩種擾動條件下(一列和三列延誤),MARL方法收斂穩(wěn)定后的最佳總延誤時間分別為721 min和1 686 min。值得指出的是:圖4(a)和圖4(b)中迭代過程中產(chǎn)生了比最終收斂結(jié)果更小的延誤時間。這是因為將時間閾值設(shè)置為MARL算法每輪訓(xùn)練結(jié)束的標(biāo)志,以避免局部最優(yōu)和縮短訓(xùn)練時間。在每輪訓(xùn)練中,當(dāng)訓(xùn)練時間超過時間閾值且存在列車未到達(dá)終點站時,訓(xùn)練被強制停止而未到達(dá)終點站的列車不計算終點站的延誤時間,因此出現(xiàn)最終收斂結(jié)果的更小延誤時間,這些更小延誤時間不能作為動態(tài)調(diào)整的有效解。

表3 中等規(guī)模貨物列車運行動態(tài)調(diào)整的延誤擾動條件

圖4 中等規(guī)模貨物列車的MARL方法收斂結(jié)果和動態(tài)調(diào)整前后的貨物列車運行圖

圖4(c)和圖4(d)展示了兩種擾動條件下經(jīng)過列車運行動態(tài)調(diào)整后的時間表。不難看出,兩種條件下動態(tài)調(diào)整獲得的時間表均滿足唯一的資源占用約束。因此,實驗結(jié)果表明MARL方法能夠有效處理大規(guī)模的運行動態(tài)調(diào)整。

為了驗證MARL方法處理貨物列車運行動態(tài)調(diào)整的高效率,同時采用了SARL方法來處理表2中的延時擾動問題。與圖4所示的擾動情景(1列延誤列車和3列延誤列車)相同,SARL方法處理重新調(diào)度后的時刻表見圖5。顯然,對于不同的擾動條件,MARL和SARL方法都可獲得相同總延誤時間。

圖5 中等規(guī)模下貨物列車的SARL方法收斂結(jié)果和動態(tài)調(diào)整前后的貨物

更進(jìn)一步,表2提供了MARL和SARL方法之間的全面性能比較,例如計算時間、操作集和內(nèi)存需求。與MARL相比,SARL方法的動作集增加了27倍,達(dá)到 65 536。 因而SARL計算時間高達(dá)675 min甚至更多,而MARL的計算時間大幅度減少到5～6 min,不到SARL的1%。顯然,MARL方法極大地提升了計算效率,這種優(yōu)勢對于3.2節(jié)中的大規(guī)模的動態(tài)調(diào)整更為明顯。

此外,引入先進(jìn)先出(FIFO)算法以提供更加全面的性能比較,它對延誤列車采用整體平移策略,不能通過超車方式進(jìn)行調(diào)整。與FIFO算法相比,MARL方法的總延遲時間降低了44%～86%。

2.2 包頭—神木段大規(guī)模貨物列車運行動態(tài)調(diào)整

為了在更大范圍內(nèi)驗證運行計劃動態(tài)調(diào)整能力,利用MARL方法對全部22列貨物列車進(jìn)行動態(tài)調(diào)整,即下行和上行方向各11列貨物列車。

同樣,在上述鐵路環(huán)境下,選擇了1列和3列延誤列車的兩種擾動條件。大規(guī)模貨物列車(22列)運行計劃動態(tài)調(diào)整的收斂結(jié)果如圖6(a)和6(b)所示。經(jīng)過250或300次訓(xùn)練后,最佳總延遲時間分別為721、 1 689 min,兩種干擾條件見表4。相應(yīng)地,圖6(c)和圖6(d)顯示了兩種延誤擾動下經(jīng)動態(tài)調(diào)整優(yōu)化后的列車時刻表。兩種擾動條件下,受延誤影響的22列列車在計劃動態(tài)調(diào)整后的時刻表仍滿足對資源占用的唯一約束。

表4 大規(guī)模動態(tài)調(diào)整下(22列)延誤擾動條件

圖6 大規(guī)模貨物列車(22列)的MARL方法收斂結(jié)果和動態(tài)調(diào)整前后的貨物列車運行圖

根據(jù)表5和圖6的統(tǒng)計與分析結(jié)果,MARL方法能夠有效解決延誤干擾下大規(guī)模貨物列車的運行計劃動態(tài)調(diào)整,并得到最小總延誤時間。然而,若采用SARL替換MARL來實施動態(tài)調(diào)整,動作集從4 096(即212)指數(shù)上升至4 294 967 296(即222),此時該通用計算機已經(jīng)無法在短時間內(nèi)完成優(yōu)化過程。根據(jù)表2和表5對此時SARL所需的計算時間和內(nèi)存進(jìn)行預(yù)測:該通用計算機需要耗時3 469 d(即4 995 600 min),幾乎難以完成任務(wù)。這一結(jié)論與2.2節(jié)的理論分析是一致的:MARL使得算法復(fù)雜度從O(2N)到O[2(1+N/2)]成指數(shù)趨勢級降低,因而計算效率以2(N/2-1)倍顯著提高。

表5 大規(guī)模貨物列車(22列)運行動態(tài)調(diào)整的MARL與SARL性能比較

值得指出的是,若采用高性能計算服務(wù)器可以進(jìn)一步減少大規(guī)模列車運行計劃動態(tài)調(diào)整下的MARL計算時間(例如僅需幾分鐘),提供實時模式服務(wù)。然而,此時SARL方法仍需數(shù)十、數(shù)百小時,依舊無法完成以實時或快速的大規(guī)模貨物列車運行動態(tài)調(diào)整任務(wù)。

3 結(jié)論

針對大規(guī)模貨物列車運行動態(tài)調(diào)整問題,本文提出了一種高計算效率的MARL方法。頗具創(chuàng)意的是,該MARL方法將上行和下行貨物列車設(shè)計為兩個不同的智能體,從而使其算法復(fù)雜度比單智能體算法大幅度。以包頭—神木貨運鐵路為例,在處理22列貨物列車和9個車站的大規(guī)模動態(tài)調(diào)整案例,該MARL方法能夠獲得穩(wěn)定收斂的最小總延誤時間和可行的列車運行調(diào)整方案。但由于所需計算時間巨大,傳統(tǒng)SARL方法不可能在短時間內(nèi)完成大規(guī)模運行計劃動態(tài)調(diào)整任務(wù)。因此,本文提出的基于MARL方法的貨物列車運行計劃動態(tài)調(diào)整有望為大運量、復(fù)雜網(wǎng)絡(luò)的鐵路貨物列車調(diào)度問題提供一種有效和有力的解決方案,從而顯著提高貨運鐵路的運營效率。