郭一唯，黃艨靼，李 博，何 清

（1.中國鐵道科學研究院集團有限公司 運輸及經(jīng)濟研究所，北京 100081；2.中國科學院 智能信息處理重點實驗室，北京 100190；3.中國科學院 計算技術研究所，北京 100190；4.中國科學院大學 計算機科學與技術學院，北京 100049)

列車運行圖是鐵路行車組織的基礎，是對鐵路運輸各部門工作的統(tǒng)籌計劃。列車運行圖的編制與調(diào)整是一項復雜而艱巨的工作，常常需要消耗大量的時間和人力成本。隨著信息技術的高速發(fā)展，國內(nèi)外相關領域的專家學者以實現(xiàn)列車運行圖編制與調(diào)整的自動化、智能化為目標，開展了許多理論方法層面的有益探索和嘗試。人工智能方法在圍棋領域的成功應用[1]引起關注，既有研究對高速鐵路調(diào)度指揮場景下利用人工智能方法解決列車運行實時調(diào)整問題展開初步探索[2-4]，但對于列車運行計劃編制階段的運行圖調(diào)整問題還鮮有涉及；針對列車運行圖的調(diào)整與優(yōu)化問題，往往以運籌學模型方法為基礎框架，當遇到難以高效求解的場景時，需要借助專家知識和既有經(jīng)驗，提出各種調(diào)整策略或啟發(fā)式算法以實現(xiàn)運行圖的優(yōu)化[5-6]。但是，這些方法在求解大規(guī)模列車運行圖問題時仍然存在一定的困難。因此，亟需借鑒人工智能方法在其他領域應用的成功經(jīng)驗，利用人工智能方法初步探索和解決計劃編制階段的列車運行圖調(diào)整問題，為解決該問題提供一種可行的方法。

1 考慮均衡性的城際鐵路列車運行圖調(diào)整模型構建

1.1 影響因素

城際鐵路列車運行圖的調(diào)整涉及鐵路運輸組織和管理中的眾多環(huán)節(jié)，其影響因素如下。①客流需求因素。列車起訖點，列車始發(fā)、終到時間，列車中途停站地點和時間，相同起訖點、相同停站結(jié)構的列車在運行圖上的分布，相同起訖點、不同停站結(jié)構的列車在運行圖上的分布等。②動車組運用因素。動車組周轉(zhuǎn)計劃、動車組分配計劃、動車組檢修計劃。③車站作業(yè)因素。到發(fā)線運用計劃，吸污、上水作業(yè)計劃等。④行車安全因素。列車區(qū)間運行時分、列車起停車附加時分、列車區(qū)間追蹤間隔時間、車站追蹤間隔時間等。⑤能力利用因素。繁忙線路區(qū)段內(nèi)的點線能力協(xié)調(diào)、繁忙線路區(qū)段之間的能力協(xié)調(diào)運用等。⑥其他影響因素。獨門車、標桿車等特殊列車的編圖要求。

1.2 模型構建

1.2.1 模型假設

（1）線路的封閉性假設。假設所考慮的線路區(qū)段是相對封閉的，沒有跨線列車的干擾，可以對該區(qū)段運行圖進行一體化編制和調(diào)整。

（2）運行圖參數(shù)已知假設。假設列車區(qū)間運行時分、列車起停車附加時分、列車區(qū)間追蹤間隔時間、車站追蹤間隔時間、各主要車站的停站頻次以及每次停站的時間范圍標準等約束條件是給定的。

（3）不考慮其他計劃假設。假設動車組交路計劃、車站到發(fā)線分配計劃都是相對靈活的，在列車運行圖的編制和調(diào)整過程中暫不考慮。

（4）列車無越行假設。假設同方向列車之間不發(fā)生越行。

1.2.2 模型描述

城際鐵路列車運行圖的調(diào)整問題可以表示為離散時間馬爾可夫決策過程，其具體的特征如下。

（1）環(huán)境狀態(tài)集合S。給定待研究的線路區(qū)段(包含車站、區(qū)間等設施信息)，可以將在一定時間范圍內(nèi)所有列車的每種可能的時空分布(運行圖不一定可行)定義為一個環(huán)境狀態(tài)st，其中t為一個離散時間步序列(t= 0，1，…)，并將所有可能的列車時空分布狀態(tài)的集合定義為模型的環(huán)境狀態(tài)集合S= {st}。在不考慮車站到發(fā)線分配方案的情況下，每個環(huán)境狀態(tài)st僅包含運行圖上各列車的起訖點、運行徑路、在徑路上各站的到達和出發(fā)時刻信息，而不包含列車在沿途各站的到發(fā)線分配信息。

（2）動作集合A。動作集合可以分為3個動作大類：平移(A1)、交換(A2)和改變停站時間(A3)。每個動作大類又由數(shù)量不等的基本動作（如向右平移1 min、向左平移300 min、交換編號為2和編號為245的2條運行線）組成。

（3）策略集合π。在時間步t，面對一個需要調(diào)優(yōu)的環(huán)境狀態(tài)st，對每個可選動作at的選擇概率πq=P(at|st)稱作一個策略，則策略集合為π= {πq}(q= 0，1，2，…，N)。策略集合是一個有限集合，需要通過對相關數(shù)據(jù)的采樣和訓練得到。

（4）環(huán)境的獎勵R。在時間步t，智能體選擇并實施了動作at后，環(huán)境對該動作的反饋信號值稱作獎勵，記為R。而R=R(st，at，st+1)是當前環(huán)境狀態(tài)、當前所選動作以及下一時間步環(huán)境狀態(tài)的標量函數(shù)。獎勵主要用于計算收獲，而R本身是由運行圖圖面打分函數(shù)計算得到。

（5）收獲G。收獲是獎勵R隨時間步的累積值， 對 于 時 間 步t， 收 獲Gt=Rt+1+γRt+2+γ2Rt+3+… =Rt+1+γGt+1，其中γ∈ [0，1]稱為折扣因子，其主要反映距離當前時間步越近的獎勵越重要。收獲G用于對策略集合進行訓練和估計。

1.3 模型求解

為了求解城際鐵路列車運行圖調(diào)整問題的離散時間馬爾可夫決策過程模型，提出以下2個關鍵算法。

1.3.1 運行圖圖面打分函數(shù)

運行圖的可行性和運行圖列車分布的均衡性是衡量運行圖一體化調(diào)整優(yōu)化質(zhì)量的重要評價標準。為此，設計運行圖圖面打分函數(shù)，計算模型中的環(huán)境獎勵R，進而對策略集合進行訓練和估計。運行圖圖面打分函數(shù)為

式中：Score(st)是對圖面(對應于在某個時間步的環(huán)境狀態(tài)st)進行總體打分的函數(shù)；μ和ω為常量參數(shù)，需要結(jié)合具體案例通過多次實驗估計得到；ev(st)是圖面均衡性打分函數(shù)，由公式 ⑵ 至 ⑸ 式給出；conf(st)是圖面沖突嚴重程度打分函數(shù)，由公式⑹給出。

式中：σi(st)是在時間步t的圖面上服務于第i對旅客OD之間的相鄰列車出發(fā)間隔時間的標準差，每對可能的旅客OD之間運行的所有列車都參與計算，包括在起站(O)始發(fā)在訖站(D)終到、在起站始發(fā)在訖站停留后通過、在起站停留后通過在訖站終到、在起訖站均停留后通過4種列車。Yi= (yi,1，yi,2，…，yi,ni-1)表示服務于第i對旅客OD之間的相鄰列車出發(fā)間隔時間向量，是由服務于第i對旅客OD之間的列車出發(fā)時刻順序排列向量Xi= (xi,1，xi,2，…，xi,ni)通過公式 ⑷ 求得。E(Yi)是Yi的數(shù)學期望。關于運行圖均衡性量化分析的理論推導，可參考孫焰等[7]的相關論述。

運行圖的可行性是均衡性的前提，因而需要對運行圖圖面的可行性進行打分評價。由于模型假設不考慮微觀層面的車站到發(fā)線分配以及動車組交路計劃，并且假設同方向列車之間不發(fā)生越行，因而可以將運行圖可行性的評價轉(zhuǎn)化為一個較為簡單的圖面沖突嚴重程度打分函數(shù)

式中：Ni,j,SX和Ni,j,XX分別為在環(huán)境狀態(tài)st對應的圖面上在車站i同時競爭時刻點j的上、下行列車數(shù)量；m為在所考慮的線路區(qū)段內(nèi)的車站數(shù)；n為需要進行沖突檢查的時刻的總數(shù)，如果時間粒度為1 min，則在環(huán)境狀態(tài)st對應的圖面上，n＜1 440。

將conf(st)設計為一個二次函數(shù)，主要體現(xiàn)沖突檢查與化解任務的重要性，讓經(jīng)過訓練的“智能體”在運行圖調(diào)整的過程中優(yōu)先處理沖突檢查與化解，而后考慮尋求均衡性的目標。

基于公式 ⑴ 至 ⑹ 定義的運行圖圖面打分函數(shù)，在時間步t實施某個動作at的環(huán)境獎勵值R的計算公式為

1.3.2 Sarsa算法

Sarsa算法是一種在策略(on-policy)強化學習算法[8]，其主要思路是通過定義Q函數(shù)(動作值函數(shù))，把在線產(chǎn)生的狀態(tài)、動作和獎勵的采樣數(shù)據(jù)代入Q函數(shù)的更新公式里，通過迭代學習更新動作價值直至收斂。由Sarsa算法求得的動作價值可以看作是對相應收獲G的一個有偏估計，因為它的采樣序列并不是完整的狀態(tài)序列。Sarsa的更新公式為

式中：α為學習因子；γ為折扣因子。

α和γ2個參數(shù)都需要結(jié)合具體案例通過多次實驗估計得到。

2 案例驗證

2.1 案例分析

選取京津城際鐵路2018年年底的實績運行圖作為案例。京津城際鐵路包含4種列車運行徑路，分別為北京南城際場至天津城際場、北京南城際場至天津西城際場、北京南城際場至濱海(于家堡)和天津城際場至濱海。京津城際鐵路線路示意圖如圖1所示。

通過分析實績運行圖可知，京津城際鐵路列車具有以下3個特點：①除了在北京南城際場至天津城際場區(qū)段有4對/d去往東北方向的跨線列車外，剩余的129.5對/d列車均為本線列車，跨線列車比例很小，基本可以做到對所有本線列車在全天有效時間范圍之內(nèi)的統(tǒng)籌調(diào)整與優(yōu)化；②本線列車的類型單一(均由設計時速350 km/h的8輛編組復興號高速動車組擔當)，列車之間無越行情形發(fā)生，符合模型方法的前提假設；③除了亦莊、永樂2個車站暫無停站要求外，沿線其余各站均有服務頻率和均衡性方面的需求，同時由于線路在南倉線路所分叉為2個方向，需要平衡兼顧不同運行區(qū)段之間的服務需求，與運行圖圖面統(tǒng)籌調(diào)整優(yōu)化的思路吻合。

2.2 參數(shù)設置

在算例中，暫不考慮動車組交路和車站到發(fā)線分配方案的求解與生成，同時不考慮實績運行圖中北京南城際場至天津城際場區(qū)段內(nèi)的4對/d跨線列車，僅考慮129.5對/d本線列車。算例相關參數(shù)配置如表1所示。

2.3 計算結(jié)果

本次算例實驗運行在Windows 10系統(tǒng)環(huán)境下，運用Python結(jié)合C++語言編寫程序代碼，在Visual Studio 2017環(huán)境下編譯，CPU為Intel酷睿i7-8750H (6核 )。

圖1 京津城際鐵路線路示意圖Fig.1 Map of Beijing-Tianjin intercity railway

表1 算例相關參數(shù)配置Tab.1 Parameter configuration of the case study

為了對模型的策略集合π進行訓練和估計，基于表1中的參數(shù)配置，通過對大量隨機生成的有沖突且列車運行線排布不均勻的運行圖圖面的自動調(diào)整、推演、試錯和學習，經(jīng)過28 h的運算，得到了一個3 GB大小的策略查詢字典文件，對應于在各種不同圖面狀態(tài)下為了朝最有利于沖突疏解和提高圖面均衡性的方向發(fā)展，應當在下一個時間步選擇實施的最佳或近似最佳動作。同時，經(jīng)過訓練后，得到公式 ⑴ 中的2個參數(shù)在μ= -1，ω= -15時有比較好的收斂效果。其中，參數(shù)取值為負，表示打分函數(shù)Score(st)的絕對值越低時，其對應的圖面狀態(tài)距離打分函數(shù)所尋求的最佳狀態(tài)越接近。

得到策略集合之后，為了測試其在最不利情形下的效率和效果，基于表1中的參數(shù)配置，初始圖面狀態(tài)如圖2所示。圖2呈現(xiàn)出一個極端場景，即在各運行區(qū)段開行的不同起訖站、不同行別、不同停站結(jié)構的列車259列/d，在其各自的始發(fā)站的出發(fā)時刻都被“擠壓”在早上6 : 00，從而形成一張沖突嚴重程度極高的不可行圖面。由打分函數(shù)計算得到初始圖面的評分約為-7 850 000分，遠遠低于理論上的最大值(0分)。以這個初始圖面為初始狀態(tài)開始迭代，隨著時間步的推移，每次從策略集合中選擇一個當前狀態(tài)下的最佳動作，約300次迭代之后，可以得到一張無沖突的圖面，在CPU未滿載的情況下這個過程大約需要花費40 min左右。然后，在不引入新沖突的條件下，對圖面進行均衡性的優(yōu)化，大約在1 000次迭代(含之前的300次）之后可得到一張經(jīng)過充分優(yōu)化的圖面。迭代1 000次得到的圖面狀態(tài)如圖3所示，對應的圖面打分為-70分，接近于理論上限(0分)，在CPU未滿載的情況下整個過程可在2 h之內(nèi)完成。

圖2 初始圖面狀態(tài)Fig.2 Initial state of the timetable

圖3 迭代1 000次得到的圖面狀態(tài)Fig.3 State of the timetable after 1 000 iterations

3 結(jié)束語

列車運行圖的調(diào)整優(yōu)化需要同時考慮鐵路運輸生產(chǎn)實踐中多個部門、多個環(huán)節(jié)的復雜因素?？紤]均衡性的城際鐵路列車運行圖的調(diào)整優(yōu)化算例，運用人工智能方法，初步探索計劃編制階段的列車運行圖調(diào)整問題，驗證模型方法在解決相對簡單的小規(guī)模問題場景中的可行性。然而，該模型方法與實際應用還有較大的距離，還應一體化地考慮動車組和車站到發(fā)線運用問題，更加全面地考慮旅客出行需求，通過運用該方法解決成網(wǎng)條件下大量跨線列車在長大干線上運行所帶來的復雜問題。