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

（1.中國(guó)鐵道科學(xué)研究院集團(tuán)有限公司 運(yùn)輸及經(jīng)濟(jì)研究所，北京 100081；2.中國(guó)科學(xué)院 智能信息處理重點(diǎn)實(shí)驗(yàn)室，北京 100190；3.中國(guó)科學(xué)院 計(jì)算技術(shù)研究所，北京 100190；4.中國(guó)科學(xué)院大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，北京 100049)

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

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

1.1 影響因素

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

1.2 模型構(gòu)建

1.2.1 模型假設(shè)

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

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

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

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

1.2.2 模型描述

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

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

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

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

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

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

1.3 模型求解

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

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

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

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

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

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

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

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

基于公式 ⑴ 至 ⑹ 定義的運(yùn)行圖圖面打分函數(shù)，在時(shí)間步t實(shí)施某個(gè)動(dòng)作at的環(huán)境獎(jiǎng)勵(lì)值R的計(jì)算公式為

1.3.2 Sarsa算法

Sarsa算法是一種在策略(on-policy)強(qiáng)化學(xué)習(xí)算法[8]，其主要思路是通過(guò)定義Q函數(shù)(動(dòng)作值函數(shù))，把在線產(chǎn)生的狀態(tài)、動(dòng)作和獎(jiǎng)勵(lì)的采樣數(shù)據(jù)代入Q函數(shù)的更新公式里，通過(guò)迭代學(xué)習(xí)更新動(dòng)作價(jià)值直至收斂。由Sarsa算法求得的動(dòng)作價(jià)值可以看作是對(duì)相應(yīng)收獲G的一個(gè)有偏估計(jì)，因?yàn)樗牟蓸有蛄胁⒉皇峭暾臓顟B(tài)序列。Sarsa的更新公式為

式中：α為學(xué)習(xí)因子；γ為折扣因子。

α和γ2個(gè)參數(shù)都需要結(jié)合具體案例通過(guò)多次實(shí)驗(yàn)估計(jì)得到。

2 案例驗(yàn)證

2.1 案例分析

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

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

2.2 參數(shù)設(shè)置

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

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

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

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

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

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

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

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