基于蒙特卡羅樹搜索
--強(qiáng)化學(xué)習(xí)的列車運(yùn)行智能調(diào)整方法

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

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

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

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

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

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

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

1.1 問題描述

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

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

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

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

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

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

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

1.2 數(shù)學(xué)模型

1.2.1 目標(biāo)函數(shù)

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

1.2.2 約束條件

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

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

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

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

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

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

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

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

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

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

2.1 蒙特卡羅樹搜索--強(qiáng)化學(xué)習(xí)的列車運(yùn)行智能調(diào)整離線訓(xùn)練模型

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

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

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

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

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

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

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

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

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

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

2.2 強(qiáng)化學(xué)習(xí)方法

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

1）狀態(tài)集Ss

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

2）動(dòng)作集As

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

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

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

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

4）獎(jiǎng)勵(lì)函數(shù)R

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

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

5）智能體

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 算例仿真

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

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

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

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

表1 典型晚點(diǎn)場景

3.2 計(jì)算結(jié)果

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

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

表2 強(qiáng)化學(xué)習(xí)的訓(xùn)練參數(shù)

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

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

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

1）3種方法下求解指標(biāo)對(duì)比

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

表3 FCFS，CPLEX和MCTS--RL的求解指標(biāo)對(duì)比

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

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

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

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

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

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

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

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

4 結(jié) 語

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

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