強化學習算法在高速鐵路運營調度中的應用

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

（1. 東北大學 流程工業綜合自動化國家重點實驗室，沈陽 110819；2. 中國鐵道科學研究院集團有限公司 通信信號研究所，北京 100081）

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

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

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

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

1 考慮股道運用約束的高鐵運行計劃調整問題

1.1 高鐵運行計劃調整問題描述

高鐵運行計劃調整問題是在一個時間區間內，固定已經發生的列車時刻點，對尚未發生的部分結合基本運輸組織計劃進行調整，包括調整列車的到發時間和車站使用的股道資源[7]。該問題涉及的到發時間和資源的定義如圖1所示。

圖1 到發時間和資源示意

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

1.2 高鐵運行計劃調整問題的目標函數設計

高鐵運行計劃調整問題通常采用的目標函數是最小化總晚點時間，則在給定時間區間下的n輛列車、m個車站的目標函數為

其中，和分別為列車i在車站j的圖定到達時間和發車時間。

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

設ta和td為列車i在車站j的到達和發車時間的晚點量，G?i,j為列車i在車站j使用的計劃股道，Gi,j為列車i在車站j使用的實際股道，是待求解的決策變量。考慮股道運用約束的高鐵運行調整包括兩方面：（1）列車使用的股道應與計劃股道盡可能一致；（2）調度的到發時間與計劃到發時間應盡可能一致。因此，引入股道運用計劃的目標函數為

其中：

該目標函數盡可能保證列車群在到發時間和股道運用上與原計劃一致，以實現在總晚點時間相差不大的情況下，優先選擇臨時變更到發線次數少的調度方案。通過引入該目標函數，可增大總晚點時間相差不大而股道運用不同的調度方案的差異性。

綜上，將兩部分目標函數合并，得到本文設計的綜合目標函數為

公式(3)的目標函數綜合考慮了總晚點時間和股道運用計劃，能夠更好地反應調度方案能夠恢復列車既定計劃的程度，總晚點時間越小，股道運用計劃重合度越高，則目標函數值越小，調度方案越好。

2 高鐵運行計劃調整中Q(λ)學習算法的應用

將傳統的強化學習方法Q學習算法應用于決策鏈較長的高鐵運行計劃調整問題時，該算法的單步獎勵更新機制會因過長的決策鏈導致學習過程獎勵更新緩慢，需要更多的學習回合數，才能得到有效獎勵值，影響算法的學習效率、收斂速度和收斂結果。本文提出的Q(λ)學習算法是在已有的Q學習算法基礎上，通過優化獎勵函數，設計啟發式動作空間，增加累積式資格跡，以優化Q學習算法在高鐵運行計劃調整問題中的收斂速度和求解效果。

2.1 獎勵函數的設計

在高鐵運行計劃調整問題中，一般要在所有列車終到或駛離本調度區段后，才能得到全面、準確的性能指標來評價一個調度方案的好壞。基于此種特點，本文將強化學習算法每個回合中間過程的獎勵設為零[8]，將回合終止狀態的獎勵設為目標函數的倒數。結合公式（3）定義獎勵函數為

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

2.2 狀態和動作設計

2.2.1 高鐵環境狀態定義

在高鐵運營中，鐵路網的上下行是分開的，互不干擾，所以本文均以下行的環境為例進行說明。以圖1為例，其下行資源集合的定義為

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

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

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

2.2.2 智能體的動作定義

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

動作空間的每個動作向量是一個n元組，其通項為

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

公式（8）為n輛列車的原始動作空間 ，其維數是 2n，但其中大部分動作向量產生的調度方案較差，甚至無解。直接用其進行學習，會導致強化學習算法的學習效率低下、收斂緩慢。因此，需對動作空間進行預處理，通過啟發式規則，預選出較好的動作向量。

（1） 規則1：股道資源沖突

在列車進站時，如果當前列車的計劃股道資源被占用，且當前車站不存在可臨時調整的股道資源，則該列車不可切換資源。設 Ω1為目標列車在決策時刻t存在股道資源沖突的動作向量的集合。

（2） 規則2：咽喉區段沖突

在切換資源時，如果多輛車同時駛入或駛離同一車站，則會在咽喉區段產生沖突。設 Ω2為目標列車在決策時刻t存在咽喉區段沖突的動作向量集合。

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

2.3 基于累積式資格跡的經驗更新機制

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

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

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

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

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

其中，Qt(S,A)為t時刻 (S,A)對應的Q值；α為學習率。

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

3 算法實現

綜上所述，本文設計的面向高鐵運行計劃智能調整的Q(λ)學習算法的基本流程如圖2所示。

圖2 Q(λ)學習算法的基本流程

（1）初始化Q(λ)學習的基本參數：最大迭代次數N、α、γ、λ、值函數表Q、資格跡表Tr、計劃時刻表T和資源列表 ?。加載高鐵交互環境的數據：事件隊列、狀態列表等。

（2）由晚點事件獲取其對應的狀態向量S0，初始化Q表、資格跡表Tr和當前回合數n=0。

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

（4）獲取決策時刻t的狀態St，再根據經典的動作選擇策略（ε貪婪策略）在由公式（9）生成的啟發式動作空間中選擇動作At，該動作控制高鐵交互環境的列車運行，進而產生后繼狀態St+1。

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

（6）判斷St是否為終止狀態，即所有列車是否完成行駛。如果沒有完成行駛，則返回（4），否則執行下一步。

（7）更新當前回合數n=n+1，判斷其是否大于最大迭代次數。如果不大于，則返回（3），否則完成學習，輸出得到的高鐵運行計劃調整方案。

4 試驗分析

4.1 仿真案例

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

表1 京滬線濟南西到蚌埠南站場規模表

試驗案例使用的時刻表基于京滬鐵路的真實運營案例，8站、7區間、20輛列車，共320個到發時間點，計劃運行圖如圖3所示。

圖3 試驗案例計劃運行圖

4.2 算法性能對比實驗

基于4.1節濟南西站—蚌埠南站的高鐵調度環境，分別使用Q學習和Q(λ)學習算法對列車突發晚點情況進行調度。Q學習算法的基本參數為α=0.3，γ=0.8，μ=100，N=700；Q(λ) 學習算法的基本參數為α=0.3，γ=0.7，λ=0.8，μ=100，N=700。列車群的突發晚點設置為G321在濟南西站晚到5 min，G117在泰安站晚到12 min。

使用上述設置采用不同的隨機數種子進行100次獨立實驗，2個算法的學習過程如圖4和圖5所示，對比結果如圖6所示。

圖4 Q學習算法的學習過程示意

圖5 Q(λ)學習算法的學習過程示意

圖6 學習過程的總晚點時間的收斂曲線及其波動范圍（100次獨立實驗）

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

先來先服務（FCFS，First Come First Service）的調度策略與調度員進行運行計劃調整的過程十分相似，因此，本文用FCFS的調整結果近似人工調度的結果，設置列車G117在濟南西站晚點20 min，分別用Q(λ)學習算法和FCFS進行運行計劃調整，運行計劃調整方案如圖7、圖8所示。

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

圖7 Q(λ)學習算法的運行計劃調整方案

圖8 FCFS算法的運行計劃調整方案

5 結束語

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