基于Q學(xué)習(xí)算法的摘掛列車調(diào)車作業(yè)計劃優(yōu)化

施俊慶，陳林武，林柏梁，孟國連，夏順?gòu)I

（1.浙江師范大學(xué) 工學(xué)院,浙江 金華 321004；2.浙江師范大學(xué) 浙江省城市軌道交通智能運維技術(shù)與裝備重點實驗室,浙江 金華 321004；3.北京交通大學(xué) 交通運輸學(xué)院,北京 100044）

調(diào)車作業(yè)計劃是規(guī)定車輛如何調(diào)移及其作業(yè)程序的具體行動計劃。按站順編組摘掛列車是指將調(diào)車場某調(diào)車線上集結(jié)的去往前方中間站的車輛，從雜亂無章到按到達中間站的順序進行編組的過程，是一項十分復(fù)雜而重要的工作。

調(diào)車作業(yè)計劃的質(zhì)量決定了車站調(diào)車工作的效率［1］，許多學(xué)者對此展開深入研究，力求不斷提高編制質(zhì)量。文獻［2］提出了“表格調(diào)車法”，將摘掛列車車輛編組順序問題轉(zhuǎn)變?yōu)? 種編號問題，減少了調(diào)車鉤數(shù)和占用的調(diào)車線數(shù)。文獻［3］提出了“統(tǒng)籌對口調(diào)車法”，將編組調(diào)車過程描述為一系列連續(xù)的對口過程，優(yōu)化了選編調(diào)車的連掛鉤數(shù)。文獻［4—5］根據(jù)編制鉤計劃條件下的調(diào)車方案及摘掛列車下落等特點，提出變異方案的概念和“消逆法”調(diào)車作業(yè)理論，改進了調(diào)車作業(yè)編制方法。文獻［6］分析了車組隔離、股道數(shù)量限制等情況下的編組摘掛列車鉤計劃優(yōu)化問題。文獻［7］將摘掛列車下落問題抽象為排序問題，提出了1種基于排序二叉樹的編組鉤計劃自動編制方法。文獻［8］在改進“分析計算法”的基礎(chǔ)上，提出溜放鉤數(shù)計算式，優(yōu)化了調(diào)車方案的選擇。文獻［9］提出了基于分支定界法的摘掛列車編組優(yōu)化算法。

隨著信息技術(shù)的進步，傳統(tǒng)的優(yōu)化算法已無法滿足鐵路調(diào)車工作決策智能化發(fā)展的需求，強化學(xué)習(xí)的出現(xiàn)為此提供了新思路。強化學(xué)習(xí)技術(shù)是機器學(xué)習(xí)的1 個分支，從算法上看主要包括基于值的算法和基于策略的算法，可以作為支持調(diào)車工作智能化決策的有效工具。Watkins 于1989年首次提出的Q學(xué)習(xí)算法是1 種典型的基于值的算法，也是目前強化學(xué)習(xí)算法中應(yīng)用最廣泛且最有效的1 種算法［10—11］。在鐵路智能調(diào)度方面，文獻［12］根據(jù)車輛的位置、到達時間、停留時間等運行狀況，基于強化學(xué)習(xí)方法對列車調(diào)度算法進行了改進；文獻［13］以減少調(diào)車機車移動為目的，研究了基于Q學(xué)習(xí)算法的貨車調(diào)度優(yōu)化問題。在列車運行控制方面，文獻［14—15］通過預(yù)測列車的運行狀態(tài)和調(diào)車計劃等，運用強化學(xué)習(xí)技術(shù)和深度Q學(xué)習(xí)算法研究了列車的控制方法；文獻［16］引入帶軌跡的延遲獎勵，結(jié)合Q學(xué)習(xí)算法研究了列車運行調(diào)整問題，減少了相應(yīng)的計算時間。

本文將強化學(xué)習(xí)技術(shù)和Q學(xué)習(xí)算法應(yīng)用于摘掛列車編組調(diào)車作業(yè)計劃優(yōu)化問題。在表格調(diào)車法的基礎(chǔ)上，通過動作、狀態(tài)和獎勵3 要素的設(shè)置構(gòu)建強化學(xué)習(xí)模型，改進Q學(xué)習(xí)算法，以最小化調(diào)車程為目標(biāo)建立待編車列和最佳調(diào)車作業(yè)方案之間的映射關(guān)系，智能體學(xué)習(xí)充分即累加Q值達到收斂狀態(tài)時，計算得到優(yōu)化后的調(diào)車表及調(diào)車作業(yè)計劃。

1 問題描述

沿用文獻［1］中的表述描述調(diào)車作業(yè)計劃編制問題，用阿拉伯?dāng)?shù)字代替車組到站，并規(guī)定距離本站最遠的車組到站為“1”，從遠到近依次編為2，3，…，調(diào)車機車在調(diào)車場的右端作業(yè)，根據(jù)“按站順編組”的要求，將待編車列中的車組連掛成列，并使列車編成后各車組的排列順序為依次遞增或相等。調(diào)車作業(yè)計劃優(yōu)化的本質(zhì)是通過調(diào)車鉤的安排，實現(xiàn)調(diào)車程的最小化。其中，調(diào)車鉤指機車連掛或摘解1 組車輛的作業(yè)，分為“掛車鉤”和“摘車鉤”；調(diào)車程指機車或機車連掛車輛加減速1次的移動，通常情況1 個掛車鉤對應(yīng)于2 個調(diào)車程，1 個摘車鉤對應(yīng)于1 個調(diào)車程。調(diào)車作業(yè)計劃的編制可用調(diào)車表來進行。調(diào)車表是調(diào)車場的示意圖，橫格為“列”，表示股道，豎格為“行”，表示車組在待編車列中的相互位置。假設(shè)：每個車組僅含1 輛車，牽出線及調(diào)車線的存車、調(diào)車機車的牽引能力等不受限制。

同時引入如下定義。

（1）接連：從左側(cè)某車組起，相鄰車組編號差值不大于1且為遞增或相等的形式。

（2）非接連：與接連相對應(yīng)，相鄰車組不滿足接連定義的其他所有形式。

（3）目標(biāo)暫合列：調(diào)車表中非接連形式車組的所在列。

（4）非接連數(shù)：非接連形式的車組數(shù)量。相鄰2 個車組組成非接連形式后，便會產(chǎn)生1 個非接連數(shù)。

例如，調(diào)車表中某列的車組編號依次為“1323456”。其中，相鄰車組1 與3 之間的編號差值為2，該相鄰車組構(gòu)成非接連形式；相鄰車組3與2 的編號為遞減，該相鄰車組也構(gòu)成非接連形式；從第3個車組起，相鄰車組2，3，4，5 與6 構(gòu)成接連形式。該列為目標(biāo)暫合列，非接連數(shù)為2。

2 調(diào)車作業(yè)問題的強化學(xué)習(xí)模型

在表格調(diào)車法的基礎(chǔ)上，將調(diào)車作業(yè)計劃分為下落和重組2 個部分，通過動作、狀態(tài)和獎勵3 要素的設(shè)置構(gòu)建強化學(xué)習(xí)模型。

2.1 相關(guān)參數(shù)及定義

參數(shù)：K為某站實際可用的股道數(shù)量；L為待編車列中的車組數(shù)量；G為掛車鉤數(shù)；D為摘車鉤數(shù)；Z為調(diào)車機車最左端連掛的車組編號；Cij為調(diào)車表中第i列中第j輛車；Li為第i條股道上的車組數(shù)；Pi為第i條股道上的最右端車組編號，若第i條股道上沒有車組，則不存在Pi。

編組列車時，為了調(diào)轉(zhuǎn)待編車列中車組間的排序，需要將待編車列中的反順序車組分解到不同的股道上，這種調(diào)車過程反映在調(diào)車表上，被稱為下落［1］。任取待編車列“34172612537”的某一下落方案為例，所有車組下落后，各車組在調(diào)車場（調(diào)車表）中的位置見表1。表中：每1 格中的數(shù)字表示相應(yīng)編號的車組下落到對應(yīng)編號的股道上。由表1可知：此時K=5，L=11；對于第1 條股道，C11=3，C12=4，C13=5，L1=3，P1=5；存在唯一的目標(biāo)暫合列，即i=4，此目標(biāo)暫合列中僅車組7與6構(gòu)成非接連形式，非接連數(shù)為1。

表1 初始下落方案調(diào)車表

將待編車列的最右端車組定義為端組。考慮到分解待編車列時，若端組為最大編號車組，對其進行下落操作可能會產(chǎn)生1 個多余的摘車鉤。基于此，本文假設(shè)端組為最大編號車組時，根據(jù)下落方案所得的調(diào)車表，端組及其所在列左端直接相連的車組將連掛在調(diào)車機車上，不進行下落。例如在表1中，端組為最大編號車組（車組7），但調(diào)車表中其左端相鄰位置并無車組，所以僅端組不下落。

2.2 強化學(xué)習(xí)的動作與狀態(tài)

1）動作

以調(diào)車機車為智能體，將車組下落的股道編號定義為智能體的動作。用1個L維的行向量αn表示智能體對第n個車組的動作（1≤n≤L），αn中第n個分量記為an，表示智能體選擇的股道編號，其余分量均為0。如果智能體可選擇的動作有K種，則有動作集合A={1，2，…，K}，但各車組可選擇的動作均為K種時會存在大量重復(fù)解，為了減少重復(fù)性，規(guī)定第n個車組可選擇的動作集合An（An?A）為

2）狀態(tài)

為反映調(diào)車場對應(yīng)的股道下落情況，以調(diào)車表為環(huán)境，將調(diào)車表簡化為1 個L維的行向量Sn=(x1，x2，…，xL)，用于表示第n個車組下落后的調(diào)車表狀態(tài)，其中xn表示第n個車組下落后所處的股道編號。當(dāng)?shù)趎個車組未下落時，xn=0；當(dāng)?shù)趎個車組選擇某1 條股道下落時，向量Sn中第n個分量變?yōu)樗x股道編號an，并且狀態(tài)發(fā)生1 次變化。設(shè)調(diào)車表的初始狀態(tài)S0=(0，0，…，0)，此時所有車組均未開始下落；調(diào)車表的目標(biāo)狀態(tài)SL=(a1，a2，…，aL)，此時所有車組均完成下落。以表1為例，下落全部完成時該調(diào)車表對應(yīng)的狀態(tài)S11即為目標(biāo)狀態(tài)，S11=(1，1，2，4，3，4，2，2，1，3，4)。

3）狀態(tài)更新規(guī)則

當(dāng)調(diào)車表處于初始狀態(tài)S0時，全部車組均未下落，此時，智能體對第1 個車組選擇的動作為α1=(a1，0，0，…，0)，據(jù)此更新的下1 個狀態(tài)為S1。以此類推，在狀態(tài)Sn?1下，智能體采取動作αn（αn∈An）后，下1個狀態(tài)更新為Sn，即

式中：Sn為更新后的狀態(tài)；αn為對第n個車組的動作。

以表1為例，當(dāng)?shù)? 個車組下落后，狀態(tài)S4=(1，1，2，4，0，0，0，0，0，0，0)，此時智能體對第5個車組的動作α5=(0，0，0，0，2，0，0，0，0，0，0)，更新后的狀態(tài)S5=(1，1，2，4，2，0，0，0，0，0，0)。

2.3 車組掛車、摘車條件和車輛重組流程

當(dāng)所有車組均下落后，需要通過掛車和摘車對調(diào)車場上的車輛進行重組，以實現(xiàn)按站順編組。掛車、摘車的具體條件及車輛重組流程如下。

1）掛車條件

條件1：存在Cij及其右端所有車組，都能與調(diào)車機車上連掛的車組構(gòu)成接連形式，且股道中不存在比Cij大的車組。

條件2：按非接連數(shù)從大到小依次尋找目標(biāo)暫合列，其中存在Cij=Pm或Cij=Pm+1，且i≠m。

條件3：全部由接連構(gòu)成的列中存在Cij=Pm或Cij=Pm+1，且i≠m。

當(dāng)滿足以上任意1 條掛車條件時，將車組Cij及其右端的所有車組掛至調(diào)車機車上。

2）摘車條件

條件4：存在Pi，使Z=Pi。

條件5：存在Pi，使Z=Pi+1。

當(dāng)滿足以上任意1 條摘車條件時，將調(diào)車機車最左端的車組溜放至相應(yīng)股道。

3）車輛重組流程

車輛重組的具體流程如圖1所示。待編車列下落完畢后，其余車組需先根據(jù)調(diào)車表依次判斷條件1—3，確定是否掛車；然后判斷調(diào)車機車上所有車組是否構(gòu)成接連且調(diào)車表中是否沒有比Z大的車組，若成立，且調(diào)車表中存在剩余車組則繼續(xù)判斷掛車條件，直到不成立；再根據(jù)條件4—5 確定是否摘車，溜放車組直至調(diào)車機車上的所有車組構(gòu)成接連形式，且股道中不存在比Z大的車組；此時，若本輪還未進行過掛車或摘車作業(yè)，需將Z車組隨機溜放至任意股道，并再次判斷摘掛條件；循環(huán)上述過程，直至調(diào)車表中無車組，最后獲得調(diào)車作業(yè)計劃表，并根據(jù)計劃表得到掛車鉤數(shù)G和摘車鉤數(shù)D。

圖1 下落后車組的重組流程

2.4 獎勵函數(shù)設(shè)計

編組列車過程中，調(diào)車程的數(shù)量是評判下落方案優(yōu)劣的主要依據(jù)。同時，下落后調(diào)車表中非接連數(shù)越多，需要的掛車鉤就越多，調(diào)車程數(shù)量也會隨之增加，因此根據(jù)車組下落后的接連狀態(tài)及總調(diào)車程，分即時獎勵和附加獎勵2部分設(shè)計獎勵函數(shù)。

根據(jù)車組下落后的接連狀態(tài)確定即時獎勵，規(guī)定下落過程中，對第n個車組執(zhí)行動作αn后獲得的即時獎勵rSn?1，αn為

式中：λ為0-1 變量，當(dāng)執(zhí)行動作后能與所在股道上的相鄰車組構(gòu)成接連時取1；否則取0。

車輛重組后，根據(jù)調(diào)車程數(shù)量確定下落方案的附加獎勵Rrestructure為

式中：φ為任意正數(shù)。

合并上述2 部分獎勵，智能體每選擇1 個動作后的累積獎勵RSn?1，αn為

式中：RSn?1，αn為智能體在狀態(tài)Sn?1時選擇動作αn的累積獎勵；m為1到n的自然數(shù)。

智能體依據(jù)環(huán)境狀態(tài)選擇動作，每次執(zhí)行動作后，根據(jù)上述計算式確定累積獎勵。當(dāng)所有車組完成下落，即達到目標(biāo)狀態(tài)時，需根據(jù)車組下落和車輛重組過程得到調(diào)車作業(yè)計劃表，并統(tǒng)計相應(yīng)的掛車鉤數(shù)和摘車鉤數(shù)，計算附加獎勵。調(diào)車作業(yè)計劃表的優(yōu)劣通過獎勵函數(shù)體現(xiàn)，獎勵函數(shù)計算得到的數(shù)值越大，意味著調(diào)車作業(yè)計劃表越優(yōu)。

3 Q學(xué)習(xí)算法改進

改進Q學(xué)習(xí)算法，對調(diào)車作業(yè)的強化學(xué)習(xí)模型進行求解。Q學(xué)習(xí)算法根據(jù)智能體執(zhí)行每個動作后的累積獎勵來決定狀態(tài)與相應(yīng)的動作之間的映射關(guān)系。映射關(guān)系通過Q值來表示，即智能體在狀態(tài)Sn?1時選擇動作αn能夠獲得獎勵的期望。Q值越大，說明該狀態(tài)下執(zhí)行該動作越有利。求解前文模型時，在調(diào)車程最小化的目標(biāo)下，構(gòu)建待編車列與最優(yōu)調(diào)車作業(yè)計劃間的映射關(guān)系。以全部車組下落完畢為1 次迭代，每次迭代中，當(dāng)?shù)趎個車組下落時，根據(jù)當(dāng)前狀態(tài)Sn?1，從動作集合An中選擇可用的動作αn并執(zhí)行，Q值根據(jù)迭代中的累積獎勵進行更新。

使用動態(tài)的Q表來存儲智能體學(xué)習(xí)所得到的經(jīng)驗知識，見表2。表中：每行數(shù)字中的第1 到L列構(gòu)成狀態(tài)，第L+1 列為該狀態(tài)對應(yīng)的Q值。在初始時刻，Q表僅記錄了初始狀態(tài)S0及其對應(yīng)的Q值；每當(dāng)狀態(tài)發(fā)生變化時，Q表中該狀態(tài)對應(yīng)的Q值將被更新；若Q表中無該狀態(tài)，則插入該狀態(tài)及其Q值。智能體學(xué)習(xí)得到的最終Q表體現(xiàn)了待編車列和最優(yōu)調(diào)車作業(yè)方案之間的映射關(guān)系。

表2 智能體學(xué)習(xí)得到的動態(tài)Q表

第n個車組下落時，Q值的更新計算式為

式中：Q′n?1(Sn?1，αn)為狀態(tài)Sn?1時智能體執(zhí)行動作αn后更新的Q值，αn由策略π(α|S)決定，該策略表示狀態(tài)S下選擇動作α的概率；β為學(xué)習(xí)率，β∈(0，1]，學(xué)習(xí)率越大，表示采用新的嘗試得到的結(jié)果比例越大，保持舊的結(jié)果的比例越小；γ為折扣系數(shù)，γ∈(0，1]，如果γ接近于0，則智能體會傾向于即時獎勵，如果γ接近于1，則智能體會更多地考慮未來的獎勵，愿意延遲獎勵［11］。

其中，

式中：ε為智能體的探索率；y為迭代次數(shù)；argmaxQ(S，α)為狀態(tài)S下使得Q值最大的動作。

將Q表中的Q值之和定義為累加Q值。設(shè)定連續(xù)1 000 步內(nèi)累加Q值不發(fā)生變化即收斂。算法的具體過程如下。

步驟1：智能體開始學(xué)習(xí)，初始化Q表，確定待編車列，默認參數(shù)β=0.5，γ=0.9，φ=5 000。

步驟2：生成初始狀態(tài)S0。

步驟3：根據(jù)當(dāng)前狀態(tài)Sn?1，從可選擇的動作集合An中，按式（7）選擇動作αn。

步驟4：根據(jù)動作αn將狀態(tài)更新為Sn，并計算累積獎勵RSn?1，αn，按式（6）更新Q值。

步驟5：判斷Sn是否為目標(biāo)狀態(tài)，是則執(zhí)行步驟6，否則執(zhí)行3。

步驟6：判斷累加Q值是否已經(jīng)收斂，是則執(zhí)行步驟7，表示此時智能體已學(xué)習(xí)充分，否則執(zhí)行步驟2。

步驟7：退出循環(huán)并記錄數(shù)據(jù)，結(jié)束算法學(xué)習(xí)，求解得到最優(yōu)調(diào)車作業(yè)計劃。

4 算例分析

4.1 計算過程

采用上文模型和算法進行算例分析，使用的實驗運行環(huán)境為：設(shè)備CPU-Intel Core i7，工具Vi?sual Studio（C#）。

以上文待編車列“34172612537”為例，在可用股道數(shù)量為3條時（K=3），強化學(xué)習(xí)模型進行充分學(xué)習(xí)后，累加Q值的變化如圖2所示。起始階段累加Q值為零，并且智能體會有較大概率進行探索，學(xué)習(xí)各種方案；隨著迭代次數(shù)的增加，累加Q值會不斷增加，而當(dāng)智能體學(xué)習(xí)充分后，會執(zhí)行回報最大的動作序列，使得累加Q值趨于穩(wěn)定，達到收斂狀態(tài)。

圖2 累加Q值的變化

智能體學(xué)習(xí)充分后的最優(yōu)調(diào)車表見表3，此時目標(biāo)狀態(tài)為s11=(1，1，2，3，3，3，2，2，1，2，2)。當(dāng)?shù)竭_目標(biāo)狀態(tài)后，智能體依照車輛重組流程，根據(jù)下落方案將車組依次溜放至相應(yīng)股道上。由表3可知：待編車列的端組為車組7，其相鄰位置為車組3，因此車組3 與7 均不溜放，連掛于調(diào)車機車上；車組下落結(jié)束后，根據(jù)車輛重組流程在調(diào)車表中依次尋找滿足掛車條件1—3的車組；股道3為目標(biāo)暫合列，該列第2 個車組及其右端相連的車組滿足條件2，因此將車組2 與6 連掛至調(diào)車機車，此時，調(diào)車機車上所有車組（2637）并不構(gòu)成接連，應(yīng)根據(jù)摘車條件4—5 尋找能夠溜放的股道；股道2中第3 個車組滿足條件4，因此將Z=2 溜放至股道2，此時調(diào)車機車上所有車組仍不構(gòu)成接連，須繼續(xù)根據(jù)條件4—5 尋找能夠溜放的股道，直至調(diào)車機車上所有車組構(gòu)成接連且股道中沒有比Z更大的車組，因此將Z=6溜放至股道1，Z=3溜放至股道2；此時僅剩端組7 連掛在調(diào)車機車上，且股道中沒有比7更大的車組，因此須再次尋找滿足掛車條件1—3的車組，直至股道中沒有任何車組。

表3 最優(yōu)調(diào)車表

表3執(zhí)行的具體調(diào)車作業(yè)計劃見表4。由表4可知：該方案共用到調(diào)車鉤12 個，其中掛車鉤5個，摘車鉤7個；用到調(diào)車程17個。

表4 調(diào)車作業(yè)計劃表

4.2 效果對比

選取待編車列“34172612537”為案例1，待編車列“42531244627756186”為案例2，待編車列“1543253213”為案例3，分別利用統(tǒng)籌對口法、排序二叉樹法和分支定界法，依次與本文方法進行調(diào)車作業(yè)計劃的對比驗證，結(jié)果見表5。對于案例1 中的統(tǒng)籌對口調(diào)車法在K=4 時存在多種優(yōu)化方案，本文任選1 種進行對比；案例2 和案例3中的待編車列及所用方法得到的結(jié)果，分別取自文獻［7］和文獻［9］。

由表5可得出以下結(jié)論。

表5 本文方法與其他方法得到的調(diào)車作業(yè)計劃表對比

（1）對比分析案例1 和案例2 結(jié)果，可以看出本文方法能在使用更少股道數(shù)量情況下得到優(yōu)于統(tǒng)籌對口法及排序二叉樹算法的調(diào)車作業(yè)計劃。

（2）案例3 結(jié)果體現(xiàn)出，在相似設(shè)備及工具條件下進行仿真計算，本文方法求解得到的調(diào)車作業(yè)計劃質(zhì)量近似于消逆規(guī)則的分支定界法，且用時僅為53 s，遠遠短于后者的求解時間1 076 s［9］。

5 結(jié) 語

本文在結(jié)合表格調(diào)車法、強化學(xué)習(xí)技術(shù)和Q學(xué)習(xí)算法的基礎(chǔ)上提出1種摘掛列車編組調(diào)車作業(yè)計劃優(yōu)化方法。將調(diào)車作業(yè)劃分為下落和重組2 部分，通過動作、狀態(tài)和獎勵3要素建立了調(diào)車作業(yè)問題的強化學(xué)習(xí)模型，從而使摘掛列車編組調(diào)車作業(yè)優(yōu)化問題轉(zhuǎn)化為對下落方案的尋優(yōu)問題。為求解該模型，改進Q學(xué)習(xí)算法，以最小化調(diào)車程為目標(biāo)建立起待編車列與最優(yōu)調(diào)車作業(yè)計劃之間的映射關(guān)系，智能體學(xué)習(xí)充分、即累加Q值達到收斂狀態(tài)時，即可得到最優(yōu)的調(diào)車表及相應(yīng)的調(diào)車作業(yè)計劃。3 組算例分析驗證了本文方法的合理性和有效性，相較于統(tǒng)籌對口法和排序二叉樹法，本文方法使用的股道數(shù)量更少、調(diào)車作業(yè)計劃更優(yōu)；相較于分支定界法，本文方法可在更短時間內(nèi)求解出質(zhì)量近似的調(diào)車作業(yè)計劃。這證實了本文方法有助于提高車站調(diào)車作業(yè)計劃編制的智能化決策水平。