強(qiáng)化學(xué)習(xí)算法在高速鐵路運(yùn)營調(diào)度中的應(yīng)用

吳 越，袁志明，代學(xué)武，崔東亮，程麗娟，岳 鵬

（1. 東北大學(xué) 流程工業(yè)綜合自動化國家重點(diǎn)實(shí)驗(yàn)室，沈陽 110819；2. 中國鐵道科學(xué)研究院集團(tuán)有限公司 通信信號研究所，北京 100081）

目前，我國已建成世界上規(guī)模最大的高速鐵路（簡稱：高鐵）網(wǎng)。截至2020年底，我國高鐵營業(yè)里程達(dá)3.79萬km，占世界高鐵總里程的69%[1]。隨著列車開行數(shù)量的持續(xù)增長和通達(dá)范圍的不斷拓展，跨線運(yùn)行列車增多，行車密度不斷提高，運(yùn)行計(jì)劃調(diào)整日趨復(fù)雜，對高鐵調(diào)度提出了更高的要求。現(xiàn)階段的調(diào)度集中系統(tǒng)已在一定程度上降低了工作人員的勞動強(qiáng)度，實(shí)現(xiàn)了列車運(yùn)行監(jiān)視、到發(fā)點(diǎn)自動采集、調(diào)度命令網(wǎng)絡(luò)下達(dá)等功能，但階段計(jì)劃的自動調(diào)整一般為順延，只能處理簡單的晚點(diǎn)情況，沒有充分考慮更好的調(diào)整方案。因此，利用計(jì)算機(jī)優(yōu)化和人工智能等技術(shù)手段為調(diào)度員提供輔助決策支持是智能高鐵調(diào)度技術(shù)的一個發(fā)展方向。

由于傳統(tǒng)的運(yùn)籌學(xué)方法在求解調(diào)度問題時需要構(gòu)建準(zhǔn)確的數(shù)學(xué)模型。而高密度繁忙線路的行車約束條件復(fù)雜，有些約束條件（如股道運(yùn)用約束等）難以采用等式或不等式構(gòu)建準(zhǔn)確的數(shù)學(xué)描述。因此，通常需要對模型和約束進(jìn)行簡化[2]，導(dǎo)致所求得的調(diào)度方案可行性偏低。但隨著人工智能技術(shù)的發(fā)展，以強(qiáng)化學(xué)習(xí)為代表的多階段決策優(yōu)化算法可通過與環(huán)境的大量交互學(xué)習(xí)得到待求解問題的特征，并獲得較優(yōu)解。因此，采用強(qiáng)化學(xué)習(xí)方法的運(yùn)行計(jì)劃智能調(diào)整，可克服傳統(tǒng)運(yùn)籌學(xué)方法的建模難問題，通過與環(huán)境的交互，學(xué)習(xí)復(fù)雜的約束條件，獲得具有較好可行性的高鐵調(diào)度方案。因此，本文研究如何運(yùn)用強(qiáng)化學(xué)習(xí)求解高鐵調(diào)度問題，從而快速、準(zhǔn)確地調(diào)整列車運(yùn)行計(jì)劃[3]。

近年來涌現(xiàn)出較多針對基于強(qiáng)化學(xué)習(xí)的列車調(diào)度方法的研究。文獻(xiàn)[4]提出將強(qiáng)化學(xué)習(xí)方法的Q學(xué)習(xí)算法應(yīng)用于高鐵運(yùn)行計(jì)劃調(diào)整問題，并以3站2區(qū)間3車的小規(guī)模場景驗(yàn)證了Q學(xué)習(xí)算法在高鐵運(yùn)行計(jì)劃調(diào)整問題中的可行性，但其實(shí)驗(yàn)場景較小，沒有討論決策鏈較長時學(xué)習(xí)效率、收斂速度和收斂結(jié)果不理想的問題；文獻(xiàn)[5]將環(huán)境的狀態(tài)定義為相對位置關(guān)系，相對關(guān)系的狀態(tài)通過減小狀態(tài)空間的規(guī)模來提高算法的收斂速度，但該狀態(tài)包含的信息量過少，對環(huán)境的表征不夠充分，影響了算法的收斂結(jié)果；文獻(xiàn)[6]進(jìn)一步研究了Q學(xué)習(xí)算法在高鐵運(yùn)行計(jì)劃調(diào)整應(yīng)用中的狀態(tài)所包含環(huán)境元素對求解質(zhì)量和收斂性的影響。上述文獻(xiàn)使用的目標(biāo)函數(shù)均較為簡單，難以滿足行車密度增加導(dǎo)致的復(fù)雜調(diào)度需求。

本文針對Q學(xué)習(xí)的學(xué)習(xí)過程獎勵更新緩慢和簡單目標(biāo)函數(shù)無法反應(yīng)到發(fā)線使用情況的問題，基于累積式資格跡，設(shè)計(jì)多步獎勵更新機(jī)制，并在目標(biāo)函數(shù)中引入股道運(yùn)用計(jì)劃，設(shè)計(jì)面向高鐵運(yùn)行計(jì)劃調(diào)整的Q(λ)學(xué)習(xí)算法，其學(xué)習(xí)效率更高、收斂速度更快、收斂結(jié)果更好。

1 考慮股道運(yùn)用約束的高鐵運(yùn)行計(jì)劃調(diào)整問題

1.1 高鐵運(yùn)行計(jì)劃調(diào)整問題描述

高鐵運(yùn)行計(jì)劃調(diào)整問題是在一個時間區(qū)間內(nèi)，固定已經(jīng)發(fā)生的列車時刻點(diǎn)，對尚未發(fā)生的部分結(jié)合基本運(yùn)輸組織計(jì)劃進(jìn)行調(diào)整，包括調(diào)整列車的到發(fā)時間和車站使用的股道資源[7]。該問題涉及的到發(fā)時間和資源的定義如圖1所示。

圖1 到發(fā)時間和資源示意

其中，ai,j和di,j分別為列車i在車站j的實(shí)際到達(dá)時間和發(fā)車時間；Sj為 第j個車站的車站名；Tj-1為車站Sj-1與Sj之 間的站間區(qū)間資源名；SjIG、Sj3G、Sj5G等為車站j的股道資源編號。ai,j和di,j即為高鐵運(yùn)行計(jì)劃調(diào)整問題待求解的決策變量。

1.2 高鐵運(yùn)行計(jì)劃調(diào)整問題的目標(biāo)函數(shù)設(shè)計(jì)

高鐵運(yùn)行計(jì)劃調(diào)整問題通常采用的目標(biāo)函數(shù)是最小化總晚點(diǎn)時間，則在給定時間區(qū)間下的n輛列車、m個車站的目標(biāo)函數(shù)為

其中，和分別為列車i在車站j的圖定到達(dá)時間和發(fā)車時間。

隨著高鐵行車密度的日益增加，車站到發(fā)線使用率更高，使得列車群的約束日益復(fù)雜。如不按照股道運(yùn)用計(jì)劃安排行車，極易導(dǎo)致接發(fā)車進(jìn)路重新排程，增加工作量和潛在安全風(fēng)險(xiǎn)，且需旅客臨時更換乘車站臺，影響服務(wù)質(zhì)量。因此，單純用總晚點(diǎn)時間作為目標(biāo)函數(shù)，不能全面反映繁忙線路高密度行車下調(diào)度方案的性能優(yōu)劣。綜上，本文提出在目標(biāo)函數(shù)中引入股道運(yùn)用計(jì)劃，以提高調(diào)度方案的實(shí)用性。

設(shè)ta和td為列車i在車站j的到達(dá)和發(fā)車時間的晚點(diǎn)量，G?i,j為列車i在車站j使用的計(jì)劃股道，Gi,j為列車i在車站j使用的實(shí)際股道，是待求解的決策變量。考慮股道運(yùn)用約束的高鐵運(yùn)行調(diào)整包括兩方面：（1）列車使用的股道應(yīng)與計(jì)劃股道盡可能一致；（2）調(diào)度的到發(fā)時間與計(jì)劃到發(fā)時間應(yīng)盡可能一致。因此，引入股道運(yùn)用計(jì)劃的目標(biāo)函數(shù)為

其中：

該目標(biāo)函數(shù)盡可能保證列車群在到發(fā)時間和股道運(yùn)用上與原計(jì)劃一致，以實(shí)現(xiàn)在總晚點(diǎn)時間相差不大的情況下，優(yōu)先選擇臨時變更到發(fā)線次數(shù)少的調(diào)度方案。通過引入該目標(biāo)函數(shù)，可增大總晚點(diǎn)時間相差不大而股道運(yùn)用不同的調(diào)度方案的差異性。

綜上，將兩部分目標(biāo)函數(shù)合并，得到本文設(shè)計(jì)的綜合目標(biāo)函數(shù)為

公式(3)的目標(biāo)函數(shù)綜合考慮了總晚點(diǎn)時間和股道運(yùn)用計(jì)劃，能夠更好地反應(yīng)調(diào)度方案能夠恢復(fù)列車既定計(jì)劃的程度，總晚點(diǎn)時間越小，股道運(yùn)用計(jì)劃重合度越高，則目標(biāo)函數(shù)值越小，調(diào)度方案越好。

2 高鐵運(yùn)行計(jì)劃調(diào)整中Q(λ)學(xué)習(xí)算法的應(yīng)用

將傳統(tǒng)的強(qiáng)化學(xué)習(xí)方法Q學(xué)習(xí)算法應(yīng)用于決策鏈較長的高鐵運(yùn)行計(jì)劃調(diào)整問題時，該算法的單步獎勵更新機(jī)制會因過長的決策鏈導(dǎo)致學(xué)習(xí)過程獎勵更新緩慢，需要更多的學(xué)習(xí)回合數(shù)，才能得到有效獎勵值，影響算法的學(xué)習(xí)效率、收斂速度和收斂結(jié)果。本文提出的Q(λ)學(xué)習(xí)算法是在已有的Q學(xué)習(xí)算法基礎(chǔ)上，通過優(yōu)化獎勵函數(shù)，設(shè)計(jì)啟發(fā)式動作空間，增加累積式資格跡，以優(yōu)化Q學(xué)習(xí)算法在高鐵運(yùn)行計(jì)劃調(diào)整問題中的收斂速度和求解效果。

2.1 獎勵函數(shù)的設(shè)計(jì)

在高鐵運(yùn)行計(jì)劃調(diào)整問題中，一般要在所有列車終到或駛離本調(diào)度區(qū)段后，才能得到全面、準(zhǔn)確的性能指標(biāo)來評價一個調(diào)度方案的好壞。基于此種特點(diǎn)，本文將強(qiáng)化學(xué)習(xí)算法每個回合中間過程的獎勵設(shè)為零[8]，將回合終止?fàn)顟B(tài)的獎勵設(shè)為目標(biāo)函數(shù)的倒數(shù)。結(jié)合公式（3）定義獎勵函數(shù)為

其中，μ為獎勵的可調(diào)增益因子；t為決策鏈的決策時刻；tend為終止時刻，即所有列車都完成行駛的時刻。

2.2 狀態(tài)和動作設(shè)計(jì)

2.2.1 高鐵環(huán)境狀態(tài)定義

在高鐵運(yùn)營中，鐵路網(wǎng)的上下行是分開的，互不干擾，所以本文均以下行的環(huán)境為例進(jìn)行說明。以圖1為例，其下行資源集合的定義為

其中，奇數(shù)子集為某一車站的下行股道資源集合，每個元素均由車站名稱和股道編號組成；偶數(shù)子集為某一站間區(qū)間資源的集合。

高鐵調(diào)度環(huán)境的表現(xiàn)形式與決策時刻所有列車的位置及其下一資源的占用情況密切相關(guān)，因此，n輛列車的列車群在決策時刻t的狀態(tài)為

其中，ri,t為列車i在決策時刻t所處位置對應(yīng)的資源，ri,t∈?；si,t為列車i在t時刻的下一資源占用情況，si,t=1 表示未占用，si,t=0表示已占用。

2.2.2 智能體的動作定義

智能體是Q(λ)學(xué)習(xí)算法產(chǎn)生動作的映射。本文的智能體每次需要決策列車群的全部列車是否切換資源，將每輛列車的動作視作一個域Xi=(0,1)，其中，1表示切換資源的動作，0表示保持資源不變的動作，n輛列車的動作域依次為X1、X2、 ··· 、Xn，對應(yīng)的動作空間為

動作空間的每個動作向量是一個n元組，其通項(xiàng)為

其中，i=1,2,···,n，k=1,2,···,2n；ai表 示列車i的動作，其取值為0或1。

公式（8）為n輛列車的原始動作空間 ，其維數(shù)是 2n，但其中大部分動作向量產(chǎn)生的調(diào)度方案較差，甚至無解。直接用其進(jìn)行學(xué)習(xí)，會導(dǎo)致強(qiáng)化學(xué)習(xí)算法的學(xué)習(xí)效率低下、收斂緩慢。因此，需對動作空間進(jìn)行預(yù)處理，通過啟發(fā)式規(guī)則，預(yù)選出較好的動作向量。

（1） 規(guī)則1：股道資源沖突

在列車進(jìn)站時，如果當(dāng)前列車的計(jì)劃股道資源被占用，且當(dāng)前車站不存在可臨時調(diào)整的股道資源，則該列車不可切換資源。設(shè) Ω1為目標(biāo)列車在決策時刻t存在股道資源沖突的動作向量的集合。

（2） 規(guī)則2：咽喉區(qū)段沖突

在切換資源時，如果多輛車同時駛?cè)牖蝰傠x同一車站，則會在咽喉區(qū)段產(chǎn)生沖突。設(shè) Ω2為目標(biāo)列車在決策時刻t存在咽喉區(qū)段沖突的動作向量集合。

將啟發(fā)式規(guī)則1和規(guī)則2判斷的不合理動作向量取并集，并與原始動作空間的全集取補(bǔ)集，即可得啟發(fā)式動作空間為

2.3 基于累積式資格跡的經(jīng)驗(yàn)更新機(jī)制

累積式資格跡[9]通過記錄歷史決策的狀態(tài)—動作向量對 (St,At)出現(xiàn)的次數(shù)和出現(xiàn)時間的遠(yuǎn)近，來反映智能體決策的傾向性和時效性。將已有的歷史決策構(gòu)成一張二維表，即累積式資格跡表，狀態(tài)向量S為行索引，動作向量A為 列索引， (S,A)在表中對應(yīng)的元素為信度值，其更新方式為

其中，γ為獎勵折扣因子；λ為資格跡衰減因子。在每個決策時刻t，都需要對完整的資格跡表進(jìn)行更新。

累積式資格跡通過記錄智能體歷史決策的信息，來獲取其決策的頻度和逐新度，使智能體的決策信息更具全局性。

Q(λ)學(xué)習(xí)在高鐵運(yùn)行計(jì)劃調(diào)整問題中利用環(huán)境評價性指標(biāo)的反饋信號來優(yōu)化狀態(tài)值函數(shù)，該值函數(shù)為一張二維表，即Q表。其行索引為狀態(tài)S，列索引為動作A， 元素值為某一 (S,A)對應(yīng)的累積獎勵。通過逐漸減小Q表的真實(shí)值與估計(jì)值之間的偏差，實(shí)現(xiàn)獎勵最大化[10]，決策時刻t的偏差為

其中，rt為智能體與 (St,At)所對應(yīng)的即時獎勵；為t時刻后繼狀態(tài)向量St+1在Q表對應(yīng)行的最大Q值。累積式資格跡Q值的更新方式為

其中，Qt(S,A)為t時刻 (S,A)對應(yīng)的Q值；α為學(xué)習(xí)率。

不同于采用單步更新策略的Q學(xué)習(xí)，Q(λ)學(xué)習(xí)通過引入累積式資格跡進(jìn)行回溯，實(shí)現(xiàn)多步更新，有效解決因決策鏈較長導(dǎo)致的學(xué)習(xí)過程獎勵更新緩慢問題，提高了學(xué)習(xí)效率和收斂速度。

3 算法實(shí)現(xiàn)

綜上所述，本文設(shè)計(jì)的面向高鐵運(yùn)行計(jì)劃智能調(diào)整的Q(λ)學(xué)習(xí)算法的基本流程如圖2所示。

圖2 Q(λ)學(xué)習(xí)算法的基本流程

（1）初始化Q(λ)學(xué)習(xí)的基本參數(shù)：最大迭代次數(shù)N、α、γ、λ、值函數(shù)表Q、資格跡表Tr、計(jì)劃時刻表T和資源列表 ?。加載高鐵交互環(huán)境的數(shù)據(jù)：事件隊(duì)列、狀態(tài)列表等。

（2）由晚點(diǎn)事件獲取其對應(yīng)的狀態(tài)向量S0，初始化Q表、資格跡表Tr和當(dāng)前回合數(shù)n=0。

（3）每個回合開始前，將Tr清零。

（4）獲取決策時刻t的狀態(tài)St，再根據(jù)經(jīng)典的動作選擇策略（ε貪婪策略）在由公式（9）生成的啟發(fā)式動作空間中選擇動作At，該動作控制高鐵交互環(huán)境的列車運(yùn)行，進(jìn)而產(chǎn)生后繼狀態(tài)St+1。

（5）由公式（4）得到的獎勵值，根據(jù)公式（11）計(jì)算t時刻的偏差，根據(jù)公式（10）更新Tr的信度值，再根據(jù)公式（12）更新Q表的Q值，隨后更新當(dāng)前狀態(tài)St=St+1。

（6）判斷St是否為終止?fàn)顟B(tài)，即所有列車是否完成行駛。如果沒有完成行駛，則返回（4），否則執(zhí)行下一步。

（7）更新當(dāng)前回合數(shù)n=n+1，判斷其是否大于最大迭代次數(shù)。如果不大于，則返回（3），否則完成學(xué)習(xí)，輸出得到的高鐵運(yùn)行計(jì)劃調(diào)整方案。

4 試驗(yàn)分析

4.1 仿真案例

本文選取京滬（北京—上海）鐵路繁忙區(qū)段的濟(jì)南西站—蚌埠南站在11:00～16:00時段的下行列車群作為實(shí)驗(yàn)案例，其間各站的站場規(guī)模如表1所示。

表1 京滬線濟(jì)南西到蚌埠南站場規(guī)模表

試驗(yàn)案例使用的時刻表基于京滬鐵路的真實(shí)運(yùn)營案例，8站、7區(qū)間、20輛列車，共320個到發(fā)時間點(diǎn)，計(jì)劃運(yùn)行圖如圖3所示。

圖3 試驗(yàn)案例計(jì)劃運(yùn)行圖

4.2 算法性能對比實(shí)驗(yàn)

基于4.1節(jié)濟(jì)南西站—蚌埠南站的高鐵調(diào)度環(huán)境，分別使用Q學(xué)習(xí)和Q(λ)學(xué)習(xí)算法對列車突發(fā)晚點(diǎn)情況進(jìn)行調(diào)度。Q學(xué)習(xí)算法的基本參數(shù)為α=0.3，γ=0.8，μ=100，N=700；Q(λ) 學(xué)習(xí)算法的基本參數(shù)為α=0.3，γ=0.7，λ=0.8，μ=100，N=700。列車群的突發(fā)晚點(diǎn)設(shè)置為G321在濟(jì)南西站晚到5 min，G117在泰安站晚到12 min。

使用上述設(shè)置采用不同的隨機(jī)數(shù)種子進(jìn)行100次獨(dú)立實(shí)驗(yàn)，2個算法的學(xué)習(xí)過程如圖4和圖5所示，對比結(jié)果如圖6所示。

圖4 Q學(xué)習(xí)算法的學(xué)習(xí)過程示意

圖5 Q(λ)學(xué)習(xí)算法的學(xué)習(xí)過程示意

圖6 學(xué)習(xí)過程的總晚點(diǎn)時間的收斂曲線及其波動范圍（100次獨(dú)立實(shí)驗(yàn)）

圖6 中，Q(λ)學(xué)習(xí)的收斂曲線始終位于Q學(xué)習(xí)收斂曲線的下方，表明在相同的回合處，Q(λ)學(xué)習(xí)具有更好的學(xué)習(xí)效果；Q(λ) 學(xué)習(xí)400回合時已收斂到較好的調(diào)度方案，總晚點(diǎn)時間78 min，而Q學(xué)習(xí)700回合時的調(diào)度方案總晚點(diǎn)時間仍為85 min，這表明Q學(xué)習(xí)在有限的學(xué)習(xí)次數(shù)下未能收斂到較好結(jié)果。在圖5（b）和圖4（b）中，Q(λ)學(xué)習(xí)和Q學(xué)習(xí)的Q表增量分別在400和600回合處開始趨近于0，這表明前者的Q表能夠更快的收斂；在圖5（c）和圖4（c）中，Q(λ)學(xué)習(xí)和Q學(xué)習(xí)完全調(diào)度達(dá)到各自最優(yōu)結(jié)果的5%誤差范圍內(nèi)的起始位置分別是255和450回合處，也表明前者的收斂速度更快，學(xué)習(xí)效率更高。綜上，Q(λ)學(xué)習(xí)算法在學(xué)習(xí)效率、收斂速度和收斂結(jié)果上均優(yōu)于傳統(tǒng)的強(qiáng)化學(xué)習(xí)方法Q學(xué)習(xí)算法。

先來先服務(wù)（FCFS，F(xiàn)irst Come First Service）的調(diào)度策略與調(diào)度員進(jìn)行運(yùn)行計(jì)劃調(diào)整的過程十分相似，因此，本文用FCFS的調(diào)整結(jié)果近似人工調(diào)度的結(jié)果，設(shè)置列車G117在濟(jì)南西站晚點(diǎn)20 min，分別用Q(λ)學(xué)習(xí)算法和FCFS進(jìn)行運(yùn)行計(jì)劃調(diào)整，運(yùn)行計(jì)劃調(diào)整方案如圖7、圖8所示。

圖8中，基于FCFS的調(diào)度策略，G117晚點(diǎn)20 min，早于G7，所以先服務(wù)G117，迫使其緊鄰的列車向后順延，產(chǎn)生橫向和縱向的晚點(diǎn)傳播，在滿足高鐵行車安全的前提下，最終得到的調(diào)整方案影響了7輛列車在7個區(qū)間約60 min的行駛。而圖7中，由于Q(λ)學(xué)習(xí)能充分利用已有經(jīng)驗(yàn)，讓G117再晚3 min發(fā)車，先服務(wù)G7，使G7和G169沒有受到干擾，即沒有產(chǎn)生列車運(yùn)行干擾的橫向傳播，接著G169在棗莊站受到G119的影響，晚到1 min，在下一站又恢復(fù)原計(jì)劃，最終得到的調(diào)整方案只影響了1輛列車在5個區(qū)間和2輛列車在2個區(qū)間的行駛，快速恢復(fù)了圖定計(jì)劃。綜上，在行車密度較大的復(fù)雜場景中，Q(λ)學(xué)習(xí)能夠得到比FCFS更好地運(yùn)行調(diào)整方案，能夠更好的輔助調(diào)度員快速、安全地完成高鐵列車的運(yùn)行計(jì)劃調(diào)整。

圖7 Q(λ)學(xué)習(xí)算法的運(yùn)行計(jì)劃調(diào)整方案

圖8 FCFS算法的運(yùn)行計(jì)劃調(diào)整方案

5 結(jié)束語

為應(yīng)對高鐵行車密度日益增大使簡單的目標(biāo)函數(shù)不能較好反應(yīng)調(diào)度方案在密集列車群下車站股道的分配和使用的情況，本文通過在目標(biāo)函數(shù)中引入股道運(yùn)用計(jì)劃使調(diào)度過程更加可靠和嚴(yán)謹(jǐn)，同時，突出運(yùn)行計(jì)劃調(diào)整方案的差異性。并針對高鐵運(yùn)行調(diào)整時由于決策鏈過長造成的學(xué)習(xí)過程獎勵更新緩慢問題，基于累積式資格跡設(shè)計(jì)多步獎勵更新機(jī)制，使單步?jīng)Q策更具全局性?；诰F路濟(jì)南西站—蚌埠南站的線路數(shù)據(jù)和運(yùn)營數(shù)據(jù)進(jìn)行突發(fā)晚點(diǎn)下運(yùn)行計(jì)劃調(diào)整對比實(shí)驗(yàn)，結(jié)果表明，在相同的學(xué)習(xí)回合數(shù)下，本文設(shè)計(jì)的面向高鐵運(yùn)行計(jì)劃調(diào)整的Q(λ)學(xué)習(xí)算法，在學(xué)習(xí)效率、收斂速度和收斂結(jié)果上均優(yōu)于傳統(tǒng)的強(qiáng)化學(xué)習(xí)方法Q學(xué)習(xí)算法。但目前，本文只對單一區(qū)段進(jìn)行實(shí)驗(yàn)，尚未考慮多區(qū)段鐵路網(wǎng)的復(fù)雜場景，將在今后的工作中繼續(xù)改進(jìn)。