王榮笙，張 琦，張 濤，王 濤，丁舒忻

（1.中國鐵道科學研究院 研究生部，北京 100081；2.中國鐵道科學研究院集團有限公司 通信信號研究所，北京 100081；3.中國鐵道科學研究院集團有限公司 國家鐵路智能運輸系統(tǒng)工程技術(shù)研究中心，北京 100081）

我國高速鐵路已進入大規(guī)模網(wǎng)絡(luò)化運營時期，其路網(wǎng)規(guī)模、行車密度、場景工況、旅客發(fā)送量以及運輸組織復(fù)雜性均為世界高鐵之最。巨大的客流壓力和多變的運營場景下，高鐵路網(wǎng)呈現(xiàn)出前所未有的時空復(fù)雜度。同時，我國高鐵跨越高原、高熱、高濕、大風、地震等復(fù)雜工況地區(qū)，可能導致列車產(chǎn)生大范圍延誤，此時需要進行列車運行調(diào)整工作，恢復(fù)正常運行秩序。目前，我國高速鐵路列車運行調(diào)整仍以列車調(diào)度員憑經(jīng)驗處置為主，現(xiàn)場工作強度較大，也難以同時保證調(diào)整策略的實時性和近似最優(yōu)性。

高速鐵路列車運行調(diào)整問題具有NP 難（NPhard）特性［1-2］，該問題是指受突發(fā)事件影響，調(diào)整列車運行計劃使列車恢復(fù)有序運行狀態(tài)［3］。問題求解過程中列車和車站數(shù)量的增加會導致求解時間呈現(xiàn)指數(shù)級甚至階乘式增長。國內(nèi)外學者通常以晚點較小的擾動場景或晚點嚴重的干擾場景為出發(fā)點［4-5］，或基于運籌學方法［6-8］，或基于進化算法［9-10］，對突發(fā)事件下各列車在各車站的進路、接發(fā)車時刻、發(fā)車次序進行調(diào)整或協(xié)同優(yōu)化［11-13］，力求獲取近似最優(yōu)的調(diào)整策略。但上述方法均需自行設(shè)計模型分支定界或啟發(fā)式規(guī)則，模型構(gòu)造嚴重依賴于個體經(jīng)驗，同時得到的模型在加快算法收斂速度和搜索近似最優(yōu)解等方面的表現(xiàn)仍不理想。

以強化學習為代表的人工智能方法在實時求解列車運行最優(yōu)調(diào)整方案上具有獨特優(yōu)勢。強化學習方法通過智能體與環(huán)境之間的不斷試錯學習，以獲取獎勵函數(shù)最大（目標函數(shù)最優(yōu)）的學習策略，生成的離線訓練模型可直接用于問題的在線實時求解，無須對研究問題重新建模［14］，即采用離線訓練、在線調(diào)整的形式就能很好地同時滿足調(diào)整策略在實時性和近似最優(yōu)性方面的需求。目前，強化學習在軟件項目分配方案、庫存管理、車間作業(yè)調(diào)度等調(diào)度優(yōu)化問題中得到廣泛應(yīng)用［15-17］，部分學者也將其應(yīng)用到列車運行調(diào)整問題中。如文獻［18］通過分析鐵路設(shè)施基礎(chǔ)布局構(gòu)建強化學習環(huán)境，離線訓練生成的模型能實時優(yōu)化初始晚點下的時刻表；文獻［19-20］基于強化學習方法確定了不同優(yōu)先級列車占用車站股道的次序；文獻［21］利用深度強化學習方法優(yōu)化列車在車站的發(fā)車次序，生成了列車總晚點時間最短的運行圖調(diào)整方案。目前的研究雖然從宏觀、微觀不同角度構(gòu)建出列車運行調(diào)整的強化學習環(huán)境，但在強化學習策略最優(yōu)性驗證方面的研究較少，仍存在極大的改善空間。

本文面向人工智能方法應(yīng)用于列車運行調(diào)整的迫切需求，基于列車調(diào)度員的調(diào)圖視角提出蒙特卡羅樹搜索-強化學習（Monte Carlo Tree Search-Re?inforcement Learning，MCTS-RL）的列車運行智能調(diào)整方法，包括MCTS-RL 的列車運行智能調(diào)整離線訓練模型、強化學習方法、MCTS 的發(fā)車次序決策方法和沖突消解啟發(fā)式規(guī)則。通過MCTS-RL 方法一次性離線訓練生成在線調(diào)整模型，用于實時調(diào)整晚點場景下的實績運行圖，并通過與CPLEX 求解器下的運行圖調(diào)整方案進行對比，驗證MCTS-RL方法下學習策略的最優(yōu)性。

1 高速鐵路列車運行調(diào)整數(shù)學模型

1.1 問題描述

高速鐵路列車運營中，突發(fā)事件會造成列車在車站的到達晚點或出發(fā)晚點，在列車運行圖中表現(xiàn)為列車運行線的偏移，此時需要綜合考慮列車的運行情況，通過調(diào)整各列車在各車站的接、發(fā)車時刻和發(fā)車次序，給出總晚點時間最短的列車運行調(diào)整策略，以保證列車運行效率。

列車在車站和區(qū)間的作業(yè)時間示意圖如圖1 所示。圖中：L 為線路上列車總數(shù)，列車l∈{1,2,…,L}；S為線路上車站數(shù)量，車站s∈{1,2,…,S}；和分別為列車l在車站s的實際到站時刻和實際發(fā)車時刻；為列車l 在車站s+1 的實際到站時刻；tl，s，s+1為列車l 在區(qū)間（s，s+1）的實際區(qū)間運行時間；和分別為相鄰2列列車l和l+1在區(qū)間（s，s+1）內(nèi)通過任意位置x的通過時刻。由圖1可知：以列車調(diào)度員調(diào)整列車運行圖為視角，可將列車運行調(diào)整過程拆解為2 個階段：首先選擇列車在車站的發(fā)車次序，之后消解列車在車站和區(qū)間的運行沖突，這樣一來，合理調(diào)整接、發(fā)車時刻和，可使所有列車在各站的總晚點時間最短。由此，列車運行調(diào)整可描述為以列車總晚點時間最短為優(yōu)化目標，按時間順序給出列車在沿線各車站最優(yōu)發(fā)車次序的動態(tài)規(guī)劃過程。

圖1 列車在車站和區(qū)間的作業(yè)時間示意圖

同時，為研究方便且不失高速鐵路列車運行調(diào)整的一般實際性，做出如下基本假設(shè)：

（1）初始晚點發(fā)生后，線路將不再產(chǎn)生向其他線路傳播的晚點；

（2）列車在車站的實際到達和出發(fā)時刻不早于圖定時刻；

（3）相鄰2 列列車的到達—發(fā)車和發(fā)車—到達作業(yè)若發(fā)生在同一股道，會產(chǎn)生作業(yè)時間沖突。因這種情況在實際中極少，可視為以上2 種作業(yè)全部在不同股道進行，互不影響。

1.2 數(shù)學模型

1.2.1 目標函數(shù)

突發(fā)事件引起列車晚點時，鐵路運營方關(guān)注更多的是在調(diào)整各列車在各車站的接、發(fā)車時刻后，使線路上列車總晚點時間最短。故定義高速鐵路列車運行調(diào)整數(shù)學模型的目標函數(shù)Z 為列車實際到站、發(fā)車時刻與圖定到站、發(fā)車時刻的偏差之和的最小值，即

1.2.2 約束條件

高鐵列車在線路上運行時，需要考慮車站作業(yè)時間約束和區(qū)間作業(yè)時間約束。

1）車站作業(yè)時間約束

為保證列車在車站到站、發(fā)車和接發(fā)旅客等基礎(chǔ)作業(yè)的可行性，根據(jù)假設(shè)（2），列車l 實際的到站時刻和發(fā)車時刻不應(yīng)早于對應(yīng)的圖定時刻，即

對于經(jīng)停車站s 的列車l，其實際停站時間應(yīng)符合最小值約束，即列車l 在車站s 的實際停站時間不小于該車在該站的最小停站時間。值得注意的是，停站列車應(yīng)保證旅客的正常上下車，故停站列車的作業(yè)不能由“停站”改為“通過”，但通過作業(yè)的列車若為低等級列車，可將其作業(yè)由“通過”改為“停站”，供后行高等級列車越行

對于列車l經(jīng)停的車站s，其接發(fā)列車數(shù)量ns應(yīng)符合最大值約束，即ns不大于車站s 可接發(fā)列車的最大數(shù)量

當有相鄰2 列列車l 和l+1 在車站s 相繼執(zhí)行到達、通過和發(fā)車作業(yè)時，涉及到的車站作業(yè)間隔時間共有7 種，分別為：通過—通過間隔時間通過—發(fā)車間隔時間通過—到達間隔時間到達—到達間隔時間到達—通過間隔時間發(fā)車—發(fā)車間隔時間發(fā)車—通過間隔時間。7 種車站作業(yè)間隔時間均存在最小值約束，不同類型車站間隔時間的最小值與車站類型、道岔操作方式等因素有關(guān)。為研究方便且不失實際性，令上述7種車站作業(yè)間隔時間的最小值均為（實際可根據(jù)車站具體要求進行修改），即

根據(jù)假設(shè)（3），故式（6）中不再考慮到達—發(fā)車間隔作業(yè)和發(fā)車—到達間隔作業(yè)。

2）區(qū)間作業(yè)時間約束

2 列車運行智能調(diào)整方法

要采用強化學習求解建立的高速鐵路列車運行調(diào)整數(shù)學模型，需要分析強化學習機制與列車運行調(diào)整過程之間的對應(yīng)關(guān)系，構(gòu)建列車運行智能調(diào)整離線訓練模型中的強化學習環(huán)境和智能體。對列車運行調(diào)整方案求解時，為了計算模型中列車總晚點時間最短下的列車發(fā)車次序，提出蒙特卡羅樹搜索的發(fā)車次序決策方法；為了消解模型中列車在車站和區(qū)間的運行沖突，提出啟發(fā)式規(guī)則。

2.1 蒙特卡羅樹搜索--強化學習的列車運行智能調(diào)整離線訓練模型

列車運行調(diào)整過程具有馬爾可夫性質(zhì)，即未來車站狀態(tài)下的發(fā)車次序信息僅與當前車站狀態(tài)有關(guān)，與過去車站狀態(tài)的歷史信息無關(guān)。強化學習方法本質(zhì)上是1種基于動態(tài)規(guī)劃思想且具有馬爾可夫性質(zhì)的半監(jiān)督機器學習方法［14］，包括智能體和環(huán)境。智能體相當于決策者；環(huán)境包括狀態(tài)集、動作集和獎勵函數(shù)。采用強化學習離線訓練—在線調(diào)整的機制，學習該過程的列車運行最優(yōu)調(diào)整策略。

對于圖1 所示的列車運行調(diào)整過程來說，前一階段選擇列車在車站的最優(yōu)發(fā)車次序時，采用蒙特卡羅樹搜索（Monte Carlo Tree Search，MCTS）方法，該方法基于博弈樹結(jié)構(gòu)，整合了廣度優(yōu)先搜索和深度優(yōu)先搜索的各自優(yōu)點，被視為求解決策過程最優(yōu)化的高效快速搜索方法之一［22］，并已在圍棋人工智能AlphaGo的策略選擇問題中得到充分應(yīng)用［23-24］；后一階段消解列車在車站和區(qū)間的運行沖突時，設(shè)計并運用啟發(fā)式規(guī)則。

基于高速鐵路列車運行調(diào)整數(shù)學模型和列車運行調(diào)整過程，構(gòu)建強化學習方法的智能體和環(huán)境。其中：環(huán)境中的MCTS 方法和啟發(fā)式規(guī)則先后用于生成列車發(fā)車次序和消解列車運行沖突；智能體與環(huán)境不斷交互學習生成最終離線訓練模型。在列車運行調(diào)整過程中，當輸入列車接車或者發(fā)車晚點時，該模型可直接用于列車運行調(diào)整問題的實時求解，無須重新離線訓練。由此得到基于蒙特卡羅樹搜索-強化學習（Monte Carlo Tree Search-Rein?forcement Learning， MCTS-RL）方法下的列車運行智能調(diào)整離線訓練模型，其流程圖如圖2 所示。圖中：Ss，As，Rs分別為強化學習訓練至車站s時的狀態(tài)集、動作集和獎勵函數(shù)。

圖2 列車運行智能調(diào)整離線訓練模型流程圖

圖2 描述了智能體與列車運行調(diào)整強化學習環(huán)境不斷交互，搜索列車運行最優(yōu)調(diào)整策略的離線訓練過程，步驟如下。

步驟1：智能體觀測當前車站s 的狀態(tài)集Ss，并基于MCTS從動作集As中隨機選擇1個動作；

步驟2：應(yīng)用啟發(fā)式規(guī)則檢測并消解當前車站s 及下一區(qū)間（s，s+1）的列車運行沖突，然后判定當前車站s的狀態(tài)集Ss是否為終止狀態(tài)（是否調(diào)整至終點站）；

步驟3：若當前車站s 的狀態(tài)集Ss不是終止狀態(tài)，則更新至下一車站s+1 的狀態(tài)集Ss+1，并繼續(xù)確定所有列車在該車站的動作集；

步驟4：若當前車站s 的狀態(tài)集Ss處于終止狀態(tài)（即已調(diào)整至終點站S），則表明從始發(fā)站訓練至終點站S 的1 次訓練片段結(jié)束，此時記錄所有列車在之前所有車站（1，…，s，…，S）的動作集集合，組成強化學習策略，計算獎勵函數(shù)Rs（即目標函數(shù)值）并傳遞給智能體，供其評估和改進學習策略，然后進入下一次訓練片段，形成智能體和強化學習環(huán)境試錯學習的閉環(huán)反饋過程；

步驟5：若當前訓練次數(shù)未達到最大值時，則令當前的調(diào)整車站為始發(fā)站，轉(zhuǎn)至步驟1 繼續(xù)訓練；否則，輸出此時的列車運行智能調(diào)整離線訓練模型，模型中的學習策略可直接用于列車運行圖的實時調(diào)整。

2.2 強化學習方法

根據(jù)建立的數(shù)學模型和圖2所示的離線訓練模型流程圖，設(shè)計列車運行智能調(diào)整的強化學習環(huán)境。

1）狀態(tài)集Ss

式中：Ss中第1 列表示所有列車在當前車站s 下的到站時刻，由上一車站狀態(tài)集Ss-1下的發(fā)車時刻和上述所有列車在區(qū)間（s-1，s）的實際區(qū)間運行時間決定；Ss中第2列表示所有列車在當前車站s 下的發(fā)車時刻，由動作集As決定。

2）動作集As

將As設(shè)置為列車在車站s所有發(fā)車次序情形的集合，即所有列車在車站s的第1 種發(fā)車次序為e1，第2 種發(fā)車次序為e2，一直到第L！種發(fā)車次序為eL！，有

結(jié)合式（9），調(diào)整Ss中第2 列（實際發(fā)車時刻）的向量順序，形成不同發(fā)車次序下的動作集。

3）狀態(tài)轉(zhuǎn)移概率P（Ss+1|Ss，As）

表示當列車處于當前車站s的狀態(tài)集Ss和動作集As時，轉(zhuǎn)移到下一車站s+1 的狀態(tài)集Ss+1的概率。若當前車站不是終點站，則一定會發(fā)生狀態(tài)轉(zhuǎn)移，由Ss轉(zhuǎn)移至Ss+1，即P（Ss+1|Ss，As）=1；若當前車站是終點站，則一次訓練片段結(jié)束，不再進行狀態(tài)轉(zhuǎn)移，即P（Ss+1|Ss，As）=0，此時輸出獎勵函數(shù)。

4）獎勵函數(shù)R

將R 視為高速鐵路列車運行調(diào)整數(shù)學模型的目標函數(shù)，對應(yīng)于式（1） 列車總晚點時間獎勵函數(shù)R 設(shè)置為列車總晚點時間的負值，即

列車總晚點時間越短，獎勵函數(shù)R值越大，說明列車運行調(diào)整策略越優(yōu)。

5）智能體

強化學習智能體針對突發(fā)事件下列車晚點情況，在環(huán)境對約束條件（列車的車站作業(yè)時間和區(qū)間作業(yè)時間）的有效表征下，調(diào)整各列車在各車站的接發(fā)車時刻，故智能體相當于實際中給出列車運行調(diào)整計劃的列車調(diào)度員?；诟咚勹F路列車運行調(diào)整數(shù)學模型設(shè)計強化學習方法的智能體和環(huán)境，智能體與環(huán)境的不斷交互，最終生成總晚點時間最短的列車運行智能調(diào)整離線訓練模型，模型策略可直接用于問題實時求解，無須重新離線訓練。智能體中的學習策略π 是所有狀態(tài)下沿線各車站動作集的集合，表示從始發(fā)站調(diào)整至終點站1個完整的發(fā)車次序集合，故某個車站選擇的發(fā)車次序不同導致每次訓練的學習策略也不同。

2.3 發(fā)車次序決策方法

2.3.1 可行發(fā)車次序的啟發(fā)式規(guī)則

從運行圖來看，當晚點列車的運行線發(fā)生偏移后，智能體會綜合考慮不同的發(fā)車次序構(gòu)成的不同強化學習策略，并從中選擇使列車總晚點最短的列車運行調(diào)整策略。車站發(fā)車次序總數(shù)等于列車總數(shù)L 的階乘，但并非所有L！種發(fā)車次序結(jié)果都是可行的，原因有二：其一，通過作業(yè)的2 列列車在車站不可能改變列車運行順序；其二，某些發(fā)車次序并不滿足車站作業(yè)間隔時間的約束。以圖3為例說明這種不可行的發(fā)車次序。由圖3可知：對于接連經(jīng)過車站s+1 的停站列車和通過不停站列車，因存在車站作業(yè)間隔時間的約束關(guān)系，后行通過的列車l+1無法越行當前停站時間只有2 min的停站列車l，因此車站s+1 可行的發(fā)車次序有且只有{列車l，列車 }l+1 。故設(shè)計啟發(fā)式規(guī)則對各車站的發(fā)車次序集合進行“剪枝”，剔除其中不可行的發(fā)車次序，以便最終輸入到強化學習環(huán)境動作集中的沿線車站所有發(fā)車次序均是可行的。

圖3 不可行發(fā)車次序示意圖

2.3.2 可行發(fā)車次序樹結(jié)構(gòu)

通過啟發(fā)式規(guī)則，輸出各車站可行的發(fā)車次序。以相鄰3列列車l，l+1和l+2為例，設(shè)計得到蒙特卡羅樹搜索算法下博弈樹的數(shù)據(jù)結(jié)構(gòu)如圖4所示。由圖4 可知：始發(fā)站（車站1）的發(fā)車次序為樹結(jié)構(gòu)的根節(jié)點，車站2 的3 種發(fā)車次序為連接始發(fā)站根節(jié)點的3個子節(jié)點，以此類推，最終可遍歷至終點站S發(fā)車次序的子節(jié)點。

圖4 發(fā)車次序樹結(jié)構(gòu)示意圖

2.3.3 蒙特卡羅樹搜索的最優(yōu)發(fā)車次序算法

結(jié)合上述發(fā)車次序的博弈樹結(jié)構(gòu)，提出MCTS的列車最優(yōu)發(fā)車次序算法，步驟如下。

步驟1：輸入始發(fā)站（車站序號s=1）根節(jié)點狀態(tài)S1。

步驟2：判斷其后的車站子節(jié)點（發(fā)車次序）是否被訪問過，若已被訪問，轉(zhuǎn)步驟3；否則轉(zhuǎn)步驟4。

步驟3：利用上限置信區(qū)間（UCT）算法求出各子節(jié)點函數(shù)值（算法和求解方法可參考文獻［22］），選取函數(shù)值最大的子節(jié)點（發(fā)車次序）作為當前節(jié)點動作并轉(zhuǎn)步驟4；若函數(shù)值相等，則隨機選擇1個子節(jié)點，轉(zhuǎn)步驟5。

步驟4：隨機選擇1 個未被訪問的子節(jié)點，轉(zhuǎn)步驟5。

步驟5：判定當前節(jié)點是否為終點站子節(jié)點，若是，轉(zhuǎn)步驟6；否則，轉(zhuǎn)移至下一車站，轉(zhuǎn)步驟2。

步驟6：擴展生成終點站子節(jié)點的動作（可行發(fā)車次序），隨機選擇1 個動作并在樹結(jié)構(gòu)中加入該動作的新狀態(tài)，轉(zhuǎn)步驟7。

步驟7：從根節(jié)點到當前節(jié)點，完成1 次完整回合的模擬訓練，轉(zhuǎn)步驟8。

步驟8：將模擬訓練的勝負結(jié)果回溯至樹中，更新UCT 算法參數(shù)，若當前回合數(shù)未達到所設(shè)定的最大值，轉(zhuǎn)步驟1；若已達到設(shè)定的最大值，終止模擬，輸出列車運行調(diào)整的最優(yōu)發(fā)車次序。

2.4 沖突消解啟發(fā)式規(guī)則

在MCTS 給出最優(yōu)發(fā)車次序后，晚點列車和運行線發(fā)生偏移可能與后行列車在區(qū)間或者車站產(chǎn)生沖突，在列車運行圖中表現(xiàn)為沖突列車的運行線在區(qū)間產(chǎn)生交點，或沖突列車在車站不滿足車站作業(yè)間隔時間的最小值約束，嚴重影響行車安全。因此在蒙特卡羅樹搜索生成列車在車站的發(fā)車次序后，基于消解列車運行沖突的傳統(tǒng)方法［25］設(shè)計啟發(fā)式規(guī)則，將其運用于列車在車站和區(qū)間運行沖突的消解，步驟如下。

步驟1：在強化學習環(huán)境中，輸入晚點場景下的實際接發(fā)車時刻矩陣Ss。

步驟2：檢測當前相鄰2 列列車l 和l+1 在車站s的實際發(fā)車間隔時間（即是 否滿足 最 小車站 作 業(yè)間隔 時 間的約束，若滿足，轉(zhuǎn)步驟3；否則，轉(zhuǎn)步驟4。

步驟3：轉(zhuǎn)移至下一組的相鄰2 列列車，繼續(xù)檢測發(fā)車間隔時間是否滿足的約束，若不滿足，轉(zhuǎn)步驟2；否則將繼續(xù)檢測該站所有其他列車，直到所有列車完成檢測后，轉(zhuǎn)步驟5。

步驟5：檢測列車l 與后行受晚點影響列車在區(qū)間（s，s+1）是否存在沖突，若存在沖突，則運用啟發(fā)式規(guī)則消解沖突；否則，轉(zhuǎn)步驟6。

步驟6：檢測當前相鄰2 列列車l 和l+1 在車站s的到站間隔時間（即是否滿足最小車站作業(yè)間隔時間的約束，若滿足，轉(zhuǎn)步驟7；否則，轉(zhuǎn)步驟8。

步驟7：轉(zhuǎn)移至下一組的相鄰2 列列車繼續(xù)檢測到站間隔時間是否滿足的約束，若不滿足，轉(zhuǎn)步驟6；否則將繼續(xù)檢測該站所有其他列車，直到所有列車完成檢測后，轉(zhuǎn)步驟9。

步驟9：基于MCTS-RL 方法調(diào)整所有列車在車站s 的發(fā)車次序，并選擇其中1 種，當s=S 時，轉(zhuǎn)步驟10；否則，轉(zhuǎn)步驟2。

步驟10：計算列車總晚點時間下的獎勵函數(shù)值，輸出列車運行調(diào)整策略。

3 算例仿真

以京滬高鐵北京南—泰安段的某日計劃運行圖作為初始數(shù)據(jù)輸入，設(shè)置大量晚點場景并選擇其中2 個作為典型場景，基于前述數(shù)學模型和列車運行調(diào)整過程，構(gòu)建得到強化學習環(huán)境與智能體，并令其不斷交互學習；基于MCTS-RL 一次性生成離線訓練模型得到列車運行智能調(diào)整方法（簡稱MCTS-RL 法）。在列車運行調(diào)整過程中，當輸入列車接車或者發(fā)車晚點時，該離線訓練模型可直接用于列車運行調(diào)整問題的實時求解，無須重新建模求解。將MCTS-RL 方法下的方案與同樣應(yīng)用本文數(shù)學模型、但求解時分別采用先到先服務(wù)（First-Come-First-Served，F(xiàn)CFS）法［6］和CPLEX 求解器得到的調(diào)整方案進行對比，驗證本文提出方法的有效性和最優(yōu)性。

3.1 參數(shù)設(shè)置和晚點場景

以京滬高鐵北京南—泰安段沿線的北京南、廊坊、天津南、滄州西、德州東、濟南西和泰安7個車站為背景，某日線上共開行列車79列。列車在6個站間的最小區(qū)間運行時間分別為15，14，14，21，17 和15 min；最小停站時間和最小車站作業(yè)間隔時間均設(shè)置為2 min。

針對該日計劃運行圖中的全部79 列列車，隨機設(shè)置10~30 min 的大量發(fā)車晚點和到站晚點場景，并從中選擇2個較具代表性的場景見表1。

表1 典型晚點場景

3.2 計算結(jié)果

針對設(shè)置的大量晚點場景，基于Python 3.6.5編寫強化學習環(huán)境，在Intel Core i7-4710MQ@2.5 GHz，12 GB 的電腦上一次性離線訓練，生成最終的MCTS-RL 在線調(diào)整模型。強化學習訓練時，列車運行圖采用深度卷積神經(jīng)網(wǎng)絡(luò)進行狀態(tài)集輸入特征的學習，深度學習框架TensorFlow 版本為tensorflow-gpu 1.8.0。

經(jīng)過多次強化學習訓練交叉驗證后，確定其訓練參數(shù)見表2。表中：探索開發(fā)比表示訓練階段隨機搜索策略占所有策略的比值；折算因子表示某個訓練片段中隨著車站狀態(tài)集不斷向前推移，獎勵函數(shù)值所呈現(xiàn)的指數(shù)衰減趨勢（即距離當前狀態(tài)越遠的車站狀態(tài)集，對智能體影響越?。?。

表2 強化學習的訓練參數(shù)

以表1中的2個典型場景為例，分別采用FCFS法、CPLEX 求解器方法（簡稱CPLEX 法）以及MCTS-RL 法求解列車運行調(diào)整方案。FCFS 法用于驗證MCTS-RL 法在減小列車總晚點時間上的有效性。考慮到CPLEX 法的求解結(jié)果一定最優(yōu)，故以CPLEX 下的調(diào)整方案（即最優(yōu)方案）驗證MCTS-RL法下調(diào)整方案的最優(yōu)性。

為表達FCFS法（或MCTS-RL法）下調(diào)整方案與CPLEX下最優(yōu)方案之間的總晚點差值（Gap），引入η

式中：τ為FCFS 法/MCTS-RL 法下調(diào)整方案的總晚點時間，min；τopt為CPLEX 最優(yōu)方案的總晚點時間，min。

1）3種方法下求解指標對比

FCFS、CPLEX 和MCTS-RL 這3 種方法下，求解得到調(diào)整方案的總晚點時間及求解時間對比見表3。由表3可得到如下結(jié)論。

表3 FCFS，CPLEX和MCTS--RL的求解指標對比

（1） 在列車總晚點時間方面，CPLEX 和MCTS-RL 方法下的更短，分別比FCFS 法縮短14 min 和48 min；這意味著在2 個典型晚點場景下，CPLEX 和MCTS-RL 方法下最優(yōu)方案能夠分別縮短5.51%和22.43%的晚點時間。

（2）在列車運行調(diào)整求解實時性方面，F(xiàn)CFS法能分別在0.005 s和0.013 s內(nèi)給出與圖定發(fā)車次序相同的調(diào)整策略，具有較好的實時性；CPLEX求解器雖然得到總晚點時間最短的最優(yōu)調(diào)整策略，但求解時間分別達24.044 s 和24.605 s，考慮到案例涉及參數(shù)、變量較少，若將其運用于真實場景下，求解時間可能會隨著車站、列車數(shù)量的增加而呈現(xiàn)指數(shù)級增長；MCTS-RL雖消耗大量時間用于試錯學習的離線訓練，但訓練結(jié)束后可產(chǎn)生總晚點時間最短的列車運行調(diào)整學習策略，智能體憑借該策略能夠在短于0.001 s 時間內(nèi)給出同樣最優(yōu)的列車運行調(diào)整策略。相較于CPLEX 法，MCTS-RL法的求解效率高很多。

2）列車運行圖調(diào)整結(jié)果

針對2 個典型晚點場景，F(xiàn)CFS、CPLEX 和MCTS-RL 這3 種方法下的運行圖調(diào)整結(jié)果對比，分別如圖5 和圖6 所示。圖中：實線和虛線分別表示該方法下不需要調(diào)整、應(yīng)進行調(diào)整的列車運行線；線型粗細用于區(qū)分運行線歸屬于不同列車。由圖5和圖6可得到如下結(jié)論。

圖5 典型晚點場景1下計劃運行圖和FCFS法、CPLEX法/MCTS--RL法得到的運行圖調(diào)整結(jié)果

圖6 典型晚點場景2下計劃運行圖和FCFS、CPLEX法/MCTS--RL法得到的運行圖調(diào)整結(jié)果

（1）CPLEX 求解器和MCTS-RL 方法下各列車在各車站的發(fā)車次序相同，這說明2 種方法下運行圖調(diào)整結(jié)果是相同的，進一步說明本文所提出MCTS-RL方法能給出同樣最優(yōu)的調(diào)整策略；相比于CPLEX，MCTS-RL 的優(yōu)勢在于無須每次重新求解新問題，而是可直接根據(jù)離線訓練模型下的學習策略，在線實時生成列車運行調(diào)整方案。

（2）與FCFS 法相比，CPLEX 法和MCTSRL 法均能夠通過調(diào)整列車在車站的接發(fā)車時刻，生成總晚點最短的列車運行調(diào)整策略。例如圖5中，最優(yōu)方案調(diào)整了第20 列和21 列列車（圖定9：30 始發(fā)）在北京南的發(fā)車次序和時刻，這樣第20 列列車能夠在滄州西站更早地恢復(fù)正點，但各列車在其余車站的發(fā)車次序與圖定相同；圖6中，最優(yōu)方案調(diào)整了第47 列列車（晚點后13：45 始發(fā)）與第48列列車（13：50 始發(fā)）在天津南站的發(fā)車次序和發(fā)車時刻，增加了第50列列車（14：12始發(fā)）在天津南站的停站時間，令第49列列車（晚點后14：15始發(fā)）在該站越行，使列車總晚點時間最短。

4 結(jié) 語

針對路網(wǎng)中列車的到站和發(fā)車晚點，根據(jù)高速鐵路列車運行調(diào)整數(shù)學模型，提出MCTS-RL的列車運行智能調(diào)整方法，設(shè)計由狀態(tài)集、動作集、狀態(tài)轉(zhuǎn)移概率和獎勵函數(shù)組成的強化學習環(huán)境。MCTS可給出總晚點時間最短下各列車在各車站的發(fā)車次序，然后設(shè)計啟發(fā)式規(guī)則消解列車運行沖突。MCTS-RL 通過離線訓練—在線調(diào)整的學習機制，實時輔助列車調(diào)度員調(diào)整列車運行圖，提升晚點場景下應(yīng)急處置效率。仿真結(jié)果表明，典型晚點場景下，MCTS-RL 方法下的在線調(diào)整模型能夠在0.001 s 內(nèi)給出與CPLEX 求解器同樣最優(yōu)的列車運行調(diào)整策略；與FCFS 方案相比，MCTS-RL 下最優(yōu)調(diào)整策略的總晚點時間又分別縮短14 min 和48 min。

與既有研究不同的是，本文研究基于列車調(diào)度員的宏觀調(diào)圖視角，后續(xù)工作可考慮車站進路、線路信號設(shè)備布置和列車運行狀態(tài)等實際微觀約束，同時還可進一步研究嚴重晚點場景下動車組運用計劃和列車運行圖的協(xié)同調(diào)整。