莊　河，何世偉，戴楊鋮

(1.西南交通大學(xué) 交通運(yùn)輸與物流學(xué)院，四川 成都　610031； 2.中國(guó)鐵路總公司　運(yùn)輸局，北京　100844；3.北京交通大學(xué) 交通運(yùn)輸學(xué)院，北京　100044)

高速鐵路列車具有很高的正點(diǎn)率，但當(dāng)受到設(shè)備故障、惡劣天氣、突發(fā)事件等因素影響時(shí)，也會(huì)出現(xiàn)列車到達(dá)車站時(shí)刻偏離計(jì)劃運(yùn)行圖的情況，因此需要對(duì)列車運(yùn)行計(jì)劃進(jìn)行調(diào)整。

高速鐵路列車運(yùn)行調(diào)整具有約束條件復(fù)雜、優(yōu)化指標(biāo)多、實(shí)時(shí)性高、動(dòng)態(tài)性強(qiáng)等特點(diǎn)。文獻(xiàn)[1—3]采用基于列車到發(fā)車站時(shí)刻等決策值的方法進(jìn)行列車運(yùn)行調(diào)整優(yōu)化；文獻(xiàn)[4]構(gòu)建了以最小化等待時(shí)間及最小化中高速列車總旅行時(shí)間的雙目標(biāo)優(yōu)化模型，采用分支定界法與束搜索算法相結(jié)合的方法求解；文獻(xiàn)[5]設(shè)計(jì)了基于替代圖的列車運(yùn)行調(diào)整計(jì)劃編制模型及優(yōu)化方法；文獻(xiàn)[6]針對(duì)高速鐵路列車運(yùn)行調(diào)整復(fù)雜性高的特點(diǎn)，采用貪婪算法進(jìn)行實(shí)時(shí)列車調(diào)整；文獻(xiàn)[7]建立列車到發(fā)時(shí)刻與進(jìn)路同步優(yōu)化的高速鐵路列車運(yùn)行調(diào)整整數(shù)規(guī)劃模型，設(shè)計(jì)了基于優(yōu)先級(jí)規(guī)則的調(diào)度調(diào)整啟發(fā)式算法；文獻(xiàn)[8—9]采用以列車運(yùn)行順序?yàn)殛P(guān)注對(duì)象的序優(yōu)化方法；文獻(xiàn)[10—11]分別采用禁忌搜索算法和遺傳算法進(jìn)行列車運(yùn)行調(diào)整。這些研究推進(jìn)并豐富了列車運(yùn)行計(jì)劃調(diào)整的優(yōu)化方法體系，數(shù)學(xué)模型也具有直觀的優(yōu)點(diǎn)，但由于這類數(shù)學(xué)模型變量多、構(gòu)模與算法復(fù)雜，加上問(wèn)題的動(dòng)態(tài)性，很難得到令人滿意的解，因此，亟須研究提出高速鐵路列車運(yùn)行計(jì)劃調(diào)整的新方法。

策略是指對(duì)將來(lái)任意可能的狀態(tài)可采取的行動(dòng)的集合[12-13]，如在生產(chǎn)調(diào)度工作中，可推遲加工設(shè)備的開、完工時(shí)間，可調(diào)整加工設(shè)備的加工順序等。高速鐵路列車運(yùn)行調(diào)整優(yōu)化問(wèn)題與一般生產(chǎn)調(diào)度優(yōu)化相通，如調(diào)度員確定相鄰的相互沖突列車是順晚、還是在前方站或后方站越行，就類似于生產(chǎn)調(diào)度的策略?；诓呗缘膬?yōu)化方法是指以策略而非傳統(tǒng)決策值為對(duì)象的優(yōu)化方法。有學(xué)者基于策略研究了高速鐵路列車運(yùn)行調(diào)整問(wèn)題：文獻(xiàn)[14]提出將客運(yùn)專線列車運(yùn)行調(diào)整問(wèn)題轉(zhuǎn)化為車間調(diào)度問(wèn)題，并針對(duì)局部調(diào)整和大面積調(diào)整分別提出了實(shí)用可行的調(diào)整策略模型及算法。這些基于策略的研究成果，進(jìn)一步拓展了高速鐵路列車運(yùn)行調(diào)整問(wèn)題研究的思路，但多采用固定策略的仿真分析方法，使得各種調(diào)度策略之間缺乏銜接性和關(guān)聯(lián)性，也無(wú)法保證解的優(yōu)化質(zhì)量。馬氏決策過(guò)程模型通過(guò)揭示不同狀態(tài)下優(yōu)化策略與轉(zhuǎn)移概率和獲得報(bào)酬的關(guān)系，解決各種調(diào)度策略之間的銜接性和關(guān)聯(lián)性問(wèn)題，并在保證解的優(yōu)化質(zhì)量前提下簡(jiǎn)化計(jì)算過(guò)程，在很多領(lǐng)域得到了較好的應(yīng)用[12-13]。因此，可基于馬氏決策過(guò)程模型和策略優(yōu)化方法研究高速鐵路列車運(yùn)行調(diào)整問(wèn)題。

本文構(gòu)建高速鐵路列車運(yùn)行調(diào)整問(wèn)題的馬氏決策過(guò)程模型；給出列車運(yùn)行調(diào)整行動(dòng)的最優(yōu)策略條件，設(shè)計(jì)模型求解的策略優(yōu)化方法；結(jié)合實(shí)際案例，將策略優(yōu)化方法的求解結(jié)果與傳統(tǒng)模型優(yōu)化算法、人工調(diào)整方法的結(jié)果進(jìn)行對(duì)比，以驗(yàn)證馬氏決策過(guò)程模型和策略優(yōu)化方法的正確性和有效性。

1　高速鐵路列車運(yùn)行調(diào)整馬氏決策過(guò)程模型的構(gòu)建

定義如下概念和參數(shù)：將高速鐵路行車調(diào)度員對(duì)列車進(jìn)行調(diào)整的時(shí)間點(diǎn)稱為決策時(shí)刻，令T為所有決策時(shí)刻的集合，且T={0,1,2,…,e,…,E}，E為階段數(shù)或總時(shí)刻點(diǎn)數(shù)。在每個(gè)決策時(shí)刻e，設(shè)相鄰且存在沖突的列車所在位置為狀態(tài)ζe，S為高速鐵路行車組織中列車的常見(jiàn)沖突狀態(tài)集合，也稱為狀態(tài)空間，ζe∈S，S={1,2,3}，其中“1”表示前、后列車同速，因前行列車晚點(diǎn)而導(dǎo)致的沖突(簡(jiǎn)稱同速列車沖突)，“2”表示前面為高速列車，后面為中速列車，前行列車晚點(diǎn)導(dǎo)致的沖突(簡(jiǎn)稱高中速列車沖突)，“3”表示前面為中速列車，后面為高速列車，前行列車晚點(diǎn)導(dǎo)致的沖突(簡(jiǎn)稱中高速列車沖突)。

在狀態(tài)ζe下，行車調(diào)度員可采取的調(diào)整措施稱為行動(dòng)a，A(ζe)為所有行動(dòng)的集合，a∈A(ζe)，A(ζe)={1,2,3}，其中“1”表示后行列車順晚(簡(jiǎn)稱順晚)，“2”表示后行列車在沖突區(qū)間的前方站越行前行列車(簡(jiǎn)稱前方站越行)，“3”表示后行列車在沖突區(qū)間的后方站越行前行列車(簡(jiǎn)稱后方站越行)。

在任意決策時(shí)刻e，狀態(tài)為ζe，采取行動(dòng)a后，下一個(gè)決策時(shí)刻系統(tǒng)所處的狀態(tài)由概率分布p(·|ζe,a) 決定，以此時(shí)列車加權(quán)總晚點(diǎn)時(shí)間作為調(diào)度員采取行動(dòng)將獲得的報(bào)酬r(ζe,a)，當(dāng)報(bào)酬為正值時(shí)，表示列車調(diào)整的目標(biāo)有改善(即加權(quán)總晚點(diǎn)時(shí)間減少)，為負(fù)值時(shí)表示列車調(diào)整的目標(biāo)進(jìn)一步惡化。由于高速鐵路列車運(yùn)行調(diào)整決策過(guò)程符合馬氏決策過(guò)程的重要特征，即列車狀態(tài)的轉(zhuǎn)移概率和報(bào)酬僅僅依賴于當(dāng)前的狀態(tài)和調(diào)度員采取的行動(dòng)，而不直接依賴于以前的情況，則高速鐵路列車運(yùn)行調(diào)整問(wèn)題的馬氏決策過(guò)程模型為

{T,S,A(ζe),p(·|ζe,a),r(ζe,a)}

(1)

2　高速鐵路列車運(yùn)行調(diào)整馬氏決策過(guò)程模型的最優(yōu)策略條件

2.1　馬氏決策過(guò)程模型策略的定義

對(duì)于馬氏決策過(guò)程模型，有如下定義[12]。

定義1：如果狀態(tài)空間下的函數(shù)f滿足對(duì)每個(gè)ζe∈S有f(ζe)∈A(ζe)，即f:S→A(ζe)，則稱f為確定性決策規(guī)則，也稱為決策函數(shù)；全體決策函數(shù)所組成的集合記為F。

定義2：1個(gè)決策函數(shù)序列π=(f0,f1,f2,…，fe,…)，fe∈F，e∈T，稱為(確定性)1個(gè)馬氏決策策略，其中fe是決策時(shí)刻e的決策函數(shù)，不依賴于決策時(shí)刻e以前系統(tǒng)的歷史；全體馬氏策略所組成的集合記做Πm，稱為馬氏策略類。

由于給定調(diào)整范圍(時(shí)段、區(qū)間和列車數(shù))的高速鐵路列車運(yùn)行調(diào)整優(yōu)化問(wèn)題屬于有限狀態(tài)、可數(shù)行動(dòng)的情形，對(duì)其最優(yōu)策略的結(jié)構(gòu)有如下定理。

定理1的證明參見(jiàn)文獻(xiàn)[15]。

定理2：1個(gè)馬氏決策策略π=(f0,f1,f2,…,fe,…)∈Πm是1個(gè)最優(yōu)策略的充要條件是：每個(gè)決策規(guī)則在每個(gè)可實(shí)現(xiàn)的歷史上都要采取最優(yōu)的行動(dòng)。

定理2的證明參見(jiàn)文獻(xiàn)[13]。

2.2　列車順晚行動(dòng)及其最優(yōu)策略條件

定理3：在出現(xiàn)大面積列車晚點(diǎn)時(shí)，若所有列車本身均無(wú)故障，且所有列車晚點(diǎn)均未超過(guò)最大可接受晚點(diǎn)時(shí)間，則應(yīng)采用列車順晚依次開行的行動(dòng)。

定理3的證明如下。

在決策時(shí)刻0，列車有3種沖突狀態(tài)，即ζ0={1，2，3}。

狀態(tài)1(ζ0=1，即同速列車沖突)如圖1所示，2列列車的運(yùn)行線為平行線。假設(shè)列車i晚點(diǎn)而列車j不晚點(diǎn)，并假設(shè)列車i在k+1站的晚點(diǎn)時(shí)間為tw，則對(duì)于后面的列車j，可根據(jù)車站間隔時(shí)間將其調(diào)整至當(dāng)前可行的最早到達(dá)時(shí)間，調(diào)整時(shí)間為tx；因?yàn)橹髮?duì)這2列車均可以通過(guò)壓縮區(qū)間運(yùn)行時(shí)間和車站停留時(shí)間來(lái)恢復(fù)其正點(diǎn)運(yùn)行，故應(yīng)采用列車順晚依次開行的行動(dòng)，不考慮列車越行。另一方面，假設(shè)列車i和列車j均晚點(diǎn)，此時(shí)，tx不僅可調(diào)整余地小，而且也不符合考慮列車越行問(wèn)題的基本條件(晚點(diǎn)均未超過(guò)最大可接受時(shí)間)，故應(yīng)采用列車順晚依次開行的行動(dòng)，不考慮列車越行。

狀態(tài)2(ζ0=2，即高中速列車沖突)如圖2所示，前行的高速列車i在k+1站晚點(diǎn)tw，tx為中速列車j在k+1站的預(yù)計(jì)到達(dá)時(shí)間與高速列車i的實(shí)際到達(dá)時(shí)間之差，Idd為車站不同時(shí)到達(dá)最小間隔時(shí)間。若tx>Idd，則列車j不需要進(jìn)行調(diào)整，否則，根據(jù)車站間隔時(shí)間把列車j調(diào)整至當(dāng)前可行的最早到達(dá)時(shí)間即可，故應(yīng)采用列車順晚依次開行的行動(dòng)，不考慮列車越行；之后列車i和列車j同樣可以通過(guò)壓縮區(qū)間運(yùn)行時(shí)間和車站停留時(shí)間來(lái)恢復(fù)正點(diǎn)運(yùn)行。這種沖突對(duì)后車帶來(lái)的連帶晚點(diǎn)影響最為輕微，若后行列車也晚點(diǎn)，則應(yīng)采用列車順晚依次開行的行動(dòng)，更無(wú)需考慮列車越行。

圖1　同速列車順晚依次開行

圖2　高中速列車順晚依次開行

狀態(tài)3(ζ0=3，即中高速列車沖突)如圖3所示，若前行的中速列車i在k+1站發(fā)生晚點(diǎn)，與后行的高速列車j在區(qū)間發(fā)生沖突，在不改變列車到發(fā)順序的前提下，后行高速列車j只能根據(jù)車站間隔時(shí)間進(jìn)行調(diào)整(減速慢行)，調(diào)整時(shí)間tx。由圖3可以發(fā)現(xiàn)，這種調(diào)整會(huì)大大限制列車j在區(qū)間的運(yùn)行速度，并且下一區(qū)間依然會(huì)受到列車i的牽制，帶來(lái)連帶晚點(diǎn)影響。但根據(jù)定理3：對(duì)于大面積列車晚點(diǎn)，所有列車自身均無(wú)故障，且所有列車晚點(diǎn)均未超過(guò)最大可接受時(shí)間，此時(shí)由于后續(xù)高速列車也同樣晚點(diǎn)，導(dǎo)致tx大大減少，甚至為0，因此，該情況下仍應(yīng)采用列車順晚依次開行的行動(dòng)，無(wú)需考慮列車越行。只有當(dāng)后行的高速列車晚點(diǎn)時(shí)間超出最大可接受時(shí)間時(shí)，才有必要考慮列車越行。

圖3　中高速列車順晚依次開行

綜上，在決策時(shí)刻0時(shí)，對(duì)于列車沖突的3種沖突狀態(tài)ζ0，所采取的最優(yōu)行動(dòng)均為列車順晚依次開行。

采用同樣的分析方法可得，在任意決策時(shí)刻e，對(duì)于列車沖突的3種狀態(tài)ζe，所采取的最優(yōu)行動(dòng)仍為列車順晚依次開行。

由此可得，在0，1，2，…，e，…，E序列決策時(shí)刻中，對(duì)于列車沖突的3種沖突狀態(tài)，所采取的最優(yōu)行動(dòng)均為列車順晚依次開行。

根據(jù)定理1和定理2，1個(gè)決策策略是最優(yōu)策略的充要條件就是每個(gè)決策規(guī)則在每個(gè)可實(shí)現(xiàn)的歷史上都要采取最優(yōu)的行動(dòng)，由于上述討論的每個(gè)行動(dòng)均為最優(yōu)且符合最優(yōu)平穩(wěn)策略的條件，故定理3得證。

2.3　列車越行行動(dòng)及其最優(yōu)策略條件

當(dāng)前行列車出現(xiàn)嚴(yán)重晚點(diǎn)或列車晚點(diǎn)超過(guò)最大可接受時(shí)間，而后行列車運(yùn)行沒(méi)有晚點(diǎn)或者晚點(diǎn)較少，不符合列車順晚依次開行行動(dòng)的最優(yōu)策略條件時(shí)，就需要考慮相鄰沖突列車間的越行問(wèn)題。在討論列車越行行動(dòng)前，先給出如下定義。

定義4：在狀態(tài)ζe下，若2列列車在區(qū)間發(fā)生沖突，對(duì)于后行列車是在前方站越行(行動(dòng)2，a=2)還是在后方站越行(行動(dòng)3，a=3)，是由采取該行動(dòng)所獲得的行動(dòng)報(bào)酬決定的，行動(dòng)報(bào)酬較大的行動(dòng)則為狀態(tài)ζe下的最優(yōu)行動(dòng)。

在決策時(shí)刻e，列車沖突狀態(tài)ζe=3時(shí)，即中高速列車沖突，如圖4所示。設(shè)t0為后行列車與前行列車在i站的預(yù)計(jì)到達(dá)時(shí)間之差；Iff為車站不同時(shí)發(fā)車最小間隔時(shí)間；ti和tj分別為列車i和列車j的區(qū)間運(yùn)行時(shí)分，則有ti>tj(注：也可能前行列車為故障限速運(yùn)行列車或嚴(yán)重晚點(diǎn)列車)；li和lj分別為列車i和列車j的等級(jí)(或權(quán)重)。下面分t0

圖4　狀態(tài)ζ時(shí)列車沖突基本情況圖

當(dāng)t0

由圖5可知，2種越行行動(dòng)都可以疏解區(qū)間的沖突。分別計(jì)算2種越行行動(dòng)下的報(bào)酬Tk和Tk+1，即列車i和列車j在區(qū)間內(nèi)的加權(quán)總旅行時(shí)間(自在k站到達(dá)起直至從k+1站發(fā)車時(shí)止的時(shí)間)，分別為

Tk=lj(tj+Idd-t0)+li(Idd+Iff+ti)

(2)

Tk+1=lj(ti+Idd-t0)+li(ti+Idd+Iff)

(3)

圖5　當(dāng)t0

已知ti>tj，故Tk

同時(shí)，列車j無(wú)論是在k站越行還是在k+1站越行，列車i離開k+1站的時(shí)間相同，即對(duì)下一個(gè)狀態(tài)的后行列車影響是相同的，則列車j在k站進(jìn)行越行為最優(yōu)行動(dòng)。

當(dāng)t0≥Idd時(shí)，列車在k站或k+1站的越行行動(dòng)如圖6所示。

圖6　當(dāng)t0≥Idd時(shí)列車在k站或k+1站的越行行動(dòng)

由圖6可知，與圖5情況不同之處在于，若列車在k站越行，則只需調(diào)整列車i即可，列車j完全不受干擾。分別計(jì)算此時(shí)的Tk和Tk+1，即

Tk=ljtj+li(t0+Iff+ti)

(4)

Tk+1=lj(ti+Idd-t0)+li(ti+Idd+Iff)

(5)

令Tk≤Tk+1，由式(4)和(5)可得

(6)

令Tk>Tk+1，由式(4)和式(5)可得

(7)

基于定理2和列車越行行動(dòng)有如下推論。

推論：在高速鐵路列車運(yùn)行調(diào)整過(guò)程中，采取相應(yīng)調(diào)整行動(dòng)，使前后兩相鄰存在潛在沖突的列車其關(guān)系始終滿足條件1或條件3，且在任意狀態(tài)下采取的列車越行行動(dòng)均為最優(yōu)行動(dòng)，即每個(gè)決策規(guī)則要求在每個(gè)可實(shí)現(xiàn)的歷史都應(yīng)采取列車越行行動(dòng)，則這些行動(dòng)對(duì)應(yīng)的馬氏決策策略是1個(gè)最優(yōu)策略。

應(yīng)該看到，在高速鐵路行車調(diào)度決策過(guò)程中，如果采取相應(yīng)調(diào)整行動(dòng)，使前后兩相鄰存在潛在沖突的列車其關(guān)系滿足條件2時(shí)，盡管其出現(xiàn)概率很小，但理論上并不能保證后續(xù)優(yōu)化行動(dòng)序列對(duì)應(yīng)的策略為最優(yōu)策略，此時(shí)，可以分別計(jì)算不同越行行動(dòng)在前方站和后方站的報(bào)酬，采取多步的狀態(tài)遞歸方法，再比較其優(yōu)劣，從中選擇更優(yōu)化的行動(dòng)序列。

3　策略優(yōu)化方法

3.1　基于極大加代數(shù)和矩陣的列車到發(fā)時(shí)刻計(jì)算方法[16-17]

3.1.1矩陣的建立

假定在調(diào)整時(shí)段內(nèi)某個(gè)區(qū)段上有K個(gè)車站、N列列車，定義如下矩陣。

列車越行矩陣O=(oi,k)N×(K-1)，矩陣元素oi,k為第i行第k列位置上的數(shù)據(jù)，取第k個(gè)運(yùn)行區(qū)間內(nèi)按時(shí)間順序排在第i位的列車編號(hào)，i∈{1,…,N},k∈{1,…,K-1}。如圖7所示：列車越行矩陣的第1列數(shù)據(jù)1，2，3分別對(duì)應(yīng)第1個(gè)運(yùn)行區(qū)間內(nèi)按時(shí)間順序的列車編號(hào)1,2,3；第2列數(shù)據(jù)2，1，3分別對(duì)應(yīng)第2個(gè)運(yùn)行區(qū)間內(nèi)按時(shí)間順序的列車編號(hào)2, 1, 3；可見(jiàn)，列車1和列車2的位置順序交換了，這是因?yàn)樵趉=2站列車1被列車2越行；依次類推，可以得到整個(gè)區(qū)段中的列車越行矩陣。

列車i在k站的到、開時(shí)刻矩陣X=(xi,k)N×(2K-2)，其中，xi,2k-1為列車i在k站的到達(dá)時(shí)刻，xi,2k為列車i在k站的出發(fā)時(shí)刻，k=1,2,…,K-1。

圖7　區(qū)段內(nèi)列車越行矩陣圖示

3.1.2極大加代數(shù)法推算列車運(yùn)行時(shí)刻表

采用文獻(xiàn)[16]給出的基于極大加代數(shù)和矩陣的列車時(shí)刻表遞推算法，可以快速推算在確定越行順序和無(wú)沖突列車條件下，由狀態(tài)ζe到狀態(tài)ζe+1所有列車在不同車站的到發(fā)時(shí)刻。

(1)第1列車在其經(jīng)過(guò)k站時(shí)的到發(fā)時(shí)刻x1,2k和x1,2k+1，以及各次列車按照最小發(fā)車間隔在始發(fā)站的始發(fā)時(shí)刻xi,1的計(jì)算式分別為

(8)

k=2,…,K；

xi,1=Iff(i-1)；i=2,…,N

(9)

(2)后續(xù)列車在k站的到達(dá)時(shí)刻xoi,k,2k和發(fā)車時(shí)刻xoi,k+1,2k+1的計(jì)算式分別為

k=1,2,…，K-2;i=2,3,…,N

(10)

xoi-1,k+1,2k+1+Iff)

k=1,2,…，K-2;i=2,3,…,N

(11)

(3)后續(xù)列車在終到站K的到達(dá)時(shí)刻xoi,K-1,2K-2的計(jì)算式為

(12)

i=2,3,…,N

(4)定義yi,K為列車i到達(dá)終點(diǎn)站K的圖定終到時(shí)刻，所有列車的總加權(quán)晚點(diǎn)時(shí)間tall的計(jì)算式為

(13)

3.2　策略優(yōu)化方法的實(shí)現(xiàn)

根據(jù)上文的理論和計(jì)算公式，設(shè)計(jì)的高速鐵路列車運(yùn)行調(diào)整策略優(yōu)化方法步驟如下。

Step1：從調(diào)整初始時(shí)刻開始，按照基本圖的越行矩陣，運(yùn)用式(8)—式(11)計(jì)算各次列車(含初始晚點(diǎn)列車)在各站的到發(fā)時(shí)刻，并按照時(shí)間先后順序，同步比較相鄰列車在各站的到發(fā)時(shí)刻是否存在沖突，若存在沖突，則令e=0, 轉(zhuǎn)Step2；否則轉(zhuǎn)Step6。

Step2：對(duì)于系統(tǒng)狀態(tài)ζe，根據(jù)沖突列車是否出現(xiàn)嚴(yán)重晚點(diǎn)或列車晚點(diǎn)是否超過(guò)最大可接受時(shí)間的情況，判斷其是否符合2.2節(jié)給出的列車順晚依次行動(dòng)的最優(yōu)策略條件，若符合則轉(zhuǎn)Step3，否則轉(zhuǎn)Step4。

Step3：采取順晚行動(dòng)疏解沖突狀態(tài)ζe，列車越行矩陣保持不變，轉(zhuǎn)Step5。

Step4：根據(jù)2.3節(jié)給出的列車越行行動(dòng)的最優(yōu)策略條件，采取相應(yīng)越行行動(dòng)疏解沖突狀態(tài)ζe，同時(shí)修改列車越行矩陣。

Step5：按照新的列車越行矩陣，運(yùn)用式(8)—式(11)計(jì)算各次列車在后續(xù)各站的到發(fā)時(shí)刻，并按照時(shí)間先后順序，同步比較相鄰列車在各站的到發(fā)時(shí)刻是否存在沖突。若存在新的相鄰沖突列車，則令e=e+1，轉(zhuǎn)Step2；否則轉(zhuǎn)Step6。

Step6：計(jì)算所有列車的總加權(quán)晚點(diǎn)時(shí)間tall，輸出結(jié)果，計(jì)算結(jié)束。

4　算例分析

4.1　實(shí)例概況

選取京滬高速鐵路德州東至徐州東區(qū)段下行方向?yàn)槔摃r(shí)段列車密度相對(duì)密集，前行列車出現(xiàn)晚點(diǎn)后對(duì)后續(xù)列車運(yùn)行將產(chǎn)生較大影響。該區(qū)段共有8個(gè)車站，依次為德州東、濟(jì)南西、崔馬莊(線路所)、泰安、曲阜東、滕州東、棗莊、徐州東站，對(duì)應(yīng)車站編號(hào)為k=1，2，…，8；調(diào)整時(shí)段選取某天的13:00—17:00；調(diào)整時(shí)段內(nèi)基本列車運(yùn)行圖采用實(shí)際的運(yùn)行圖，如圖8所示，列車按照進(jìn)入該調(diào)整區(qū)段的時(shí)間先后編號(hào)為1～37(具體車次見(jiàn)圖8)；其中，區(qū)間運(yùn)行時(shí)間、車站間隔時(shí)間、列車運(yùn)行時(shí)刻表、列車停站情況可參見(jiàn)京滬高速鐵路列車運(yùn)行圖資料[18]。

由于此次調(diào)整不存在中速列車，假定5號(hào)列車(G325)、12號(hào)列車(G133)、19號(hào)列車(G29)、21號(hào)列車(G3)、27號(hào)列車(G141)、35號(hào)列車(G35)這6列列車為重點(diǎn)列車，列車等級(jí)為2.5，其余列車等級(jí)為1.25。隨機(jī)產(chǎn)生8個(gè)列車晚點(diǎn)算例，其中，第1—第7個(gè)算例對(duì)應(yīng)于不同的單列列車晚點(diǎn)情形，第8個(gè)算例對(duì)應(yīng)于由于天氣異常需要臨時(shí)限速，從而導(dǎo)致多列車晚點(diǎn)情形，且臨時(shí)限速200 km·h-1；晚點(diǎn)列車編號(hào)n，限速區(qū)間編號(hào)h(對(duì)應(yīng)車站h到車站h+1的區(qū)間，經(jīng)過(guò)該區(qū)間的列車由于限速等原因假定均晚點(diǎn)一定時(shí)間)和晚點(diǎn)列車所在車站的編號(hào)均見(jiàn)表1。

圖8　調(diào)整區(qū)段的基本列車運(yùn)行圖

4.2　調(diào)整計(jì)算結(jié)果

分別采用人工調(diào)整、傳統(tǒng)的優(yōu)化模型方法和本文的策略優(yōu)化方法進(jìn)行列車運(yùn)行調(diào)整，采用主頻為2.5 GHz的聯(lián)想Y480電腦計(jì)算，策略優(yōu)化調(diào)整的平均時(shí)間約為5 s，而優(yōu)化模型計(jì)算時(shí)間約為6 min，計(jì)算運(yùn)行圖調(diào)整方案的列車總加權(quán)晚點(diǎn)時(shí)間，結(jié)果也列于表1中。以算例4為例，對(duì)應(yīng)列車3在車站4的晚點(diǎn)，列車晚點(diǎn)運(yùn)行圖人工調(diào)整方案如圖9所示，采用本文的模型和策略優(yōu)化方法調(diào)整得到的列車運(yùn)行圖如圖10所示。由于采用了越行的調(diào)整方式(注：圓圈處為沖突列車位置)，較人工方案加權(quán)晚點(diǎn)時(shí)間減少5 min。

由表1、圖9和圖10結(jié)果可以看出，表1最后2列數(shù)據(jù)完全相同，表明采用策略優(yōu)化方法與傳統(tǒng)數(shù)學(xué)模型的優(yōu)化結(jié)果相同，且能取得較人工調(diào)整方法更好的優(yōu)化效果，而較傳統(tǒng)數(shù)學(xué)優(yōu)化模型方法，又可大大提高問(wèn)題的求解效率，這說(shuō)明策略優(yōu)化方法具有優(yōu)良的計(jì)算性能，能滿足高速鐵路行車調(diào)度決策系統(tǒng)開發(fā)的需要。

表1　采用不同列車運(yùn)行調(diào)整方法時(shí)不同算例的列車總加權(quán)晚點(diǎn)時(shí)間

圖9　列車晚點(diǎn)運(yùn)行圖人工調(diào)整方案

圖10　策略優(yōu)化后的列車運(yùn)行圖

5　結(jié)　論

本文運(yùn)用馬氏決策過(guò)程模型和策略優(yōu)化方法研究了高鐵列車運(yùn)行調(diào)整問(wèn)題，通過(guò)設(shè)立相鄰且存在沖突的列車所在的位置為狀態(tài)，選擇列車順晚、前方站越行、后方站越行等調(diào)度員可采取的調(diào)整措施作為行動(dòng)，采用列車加權(quán)總晚點(diǎn)時(shí)間作為行車調(diào)度員獲得的報(bào)酬，構(gòu)建了高速鐵路列車運(yùn)行調(diào)整問(wèn)題的馬氏決策過(guò)程模型；給出了列車順晚開行和越行調(diào)整行動(dòng)的最優(yōu)策略條件。在此基礎(chǔ)上，設(shè)計(jì)了策略優(yōu)化方法。以某高速鐵路區(qū)段為例，假設(shè)多種典型晚點(diǎn)情況進(jìn)行調(diào)整，通過(guò)人工調(diào)整、傳統(tǒng)數(shù)學(xué)模型優(yōu)化方法與本文的策略優(yōu)化方法的比較，表明策略優(yōu)化方法能取得較人工調(diào)整方法更好的優(yōu)化效果，較傳統(tǒng)的數(shù)學(xué)模型優(yōu)化方法可大大提高求解效率，從而驗(yàn)證了高速鐵路列車運(yùn)行調(diào)整馬氏決策過(guò)程模型和策略優(yōu)化方法的有效性，也為進(jìn)一步深化研究列車運(yùn)行調(diào)整的快速有效方法提供了解決問(wèn)題的新途徑。

[1]CORDEAU J， TOTH P, VIGO D. A Survey of Optimization Models for Train Routing and Scheduling[J]. Transportation Science，1998， 32 (4)：380-404.

[2]ANDREA D’Ariano，DARIO Pacciarelli，MARCO Pranzo. A Branch and Bound Algorithm for Scheduling Trains in a Railway Network[J]. European Journal of Operational Research，2007， 183 (2):643-657.

[3]CAPRARA A，F(xiàn)ISCHETTI M，TOTH P. Modeling and Solving the Train Timetabling Problem[J]. Operations Research，2002，50(5):851-861.

[4]ZHOU Xuesong,ZHONG Ming. Bicriteria Train Scheduling for High-Speed Passenger Railroad Planning Applications[J]. European Journal of Operational Research， 2005，167(3):752-771.

[5]王濤, 張琦; 趙宏濤, 等. 基于替代圖的列車運(yùn)行調(diào)整計(jì)劃編制及優(yōu)化方法[J]. 中國(guó)鐵道科學(xué)，2013，34(5):126-133.

(WANG Tao，ZHANG Qi，ZHAO Hongtao，et al. A Method for Generation and Optimization of Train Operation Adjustment Plan Based on Alternative Graph[J]. China Railway Science，2013，34(5):126-133. in Chinese)

[6]KRASEMANN J T. Design of an Effective Algorithm for Fast Response to the Re-Scheduling of Railway Traffic during Disturbances[J].Transportation Research Part C，2012，20(1):62-78.

[7]季學(xué)勝,孟令云.列車到發(fā)時(shí)刻與進(jìn)路同步優(yōu)化的高速鐵路列車運(yùn)行調(diào)整模型[J].中國(guó)鐵道科學(xué)，2014，35(4) ): 117-123.

(JI Xuesheng，MENG Lingyun. Train Operation Adjustment Model for Synchronously Optimizing Train Arrival/Departure Time and Route on High Speed Railway Network[J]. China Railway Science，2014，35(4): 117-123. in Chinese)

[8]陳雍君,周磊山.基于序優(yōu)化方法的列車運(yùn)行調(diào)整算法研究[J].鐵道學(xué)報(bào)，2010，32(3):1-8.

(CHEN Yongjun，ZHOU Leishan. Study on Train Operation Adjustment Algorithm Based on Ordinal Optimization [J]. Journal of the China Railway Society，2010，32(3):1-8. in Chinese)

[9]李曉娟,韓寶明,李得偉，等.基于轉(zhuǎn)換極大代數(shù)和序優(yōu)化的高速列車運(yùn)行調(diào)整方法[J].中國(guó)鐵道科學(xué)，2013，34(6):124-130.

(LI Xiaojuan, HAN Baoming, LI Dewei,et al. Method for High-Speed Train Operation Adjustment Based on Switching Max-Plux-Linear System and Ordinal Optimization[J].China Railway Science， 2013，34(6):124-130. in Chinese)

[10]董守清，王進(jìn)勇，閆海峰. 雙線鐵路列車運(yùn)行調(diào)整的禁忌搜索算法[J]. 中國(guó)鐵道科學(xué)，2005，26(4):114-119.

(DONG Shouqing，WANG Jinyong，YAN Haifeng. Tabu Search for Train Operation Adjustment on Double-Track Line[J]. China Railway Science，2005，26(4):114-119. in Chinese)

[11]王宏剛，張琦，王建英，等. 基于遺傳算法的高速鐵路行車調(diào)整模型[J]. 中國(guó)鐵道科學(xué)，2006，27(3):96-100.

(WANG Honggang, ZHANG Qi, WANG Jianying, et al. GA-Based Model of Train Operation Adjustment forHigh-Speed Railway[J]. China Railway Science，2006，27(3):96-100. in Chinese)

[12]WHITE D J. Markov Decision Processes[M]. Chichester：Wiley Press, 1993.

[13]董澤清, 劉克. 無(wú)界報(bào)酬折扣半馬氏模型最優(yōu)策略的結(jié)構(gòu)[J]. 中國(guó)科學(xué)：A輯，1985，15(11):975-985.

(DONG Zeqing，LIU Ke. Structure of Optimal Policy for Semi Markov Model with Unbounded Reward and Discount [J]. Scientia Sinica：A Edition，1985，15(11):975-985. in Chinese)

[14]石雨.客運(yùn)專線列車運(yùn)行調(diào)整的策略、模型與算法[D]. 北京: 北京交通大學(xué)，2010.

(SHI Yu. Strategies Models and Algorithms of Train Operation Adjustment for the Passenger Dedicated Railway [D]. Beijing: Beijing Jiaotong University，2010. in Chinese)

[15]BLACKWELL D. Discrete Dynamic Programming[J]. Annals of Mathematical Statistics，1962，33:719-726.

[16]李傳賓. 基于矩陣表示和極大代數(shù)法的高鐵周期列車運(yùn)行圖編制方法研究[D]. 北京:北京交通大學(xué)，2012.

(LI Chuanbin. Research on Periodic Timetabling for the Trains on High-Speed Railway Using Matrix Representation and Max-Plus Algebra Theory[D]. Beijing: Beijing Jiaotong University，2012. in Chinese)

[17]端嘉盈.高速鐵路開通后既有繁忙干線運(yùn)能計(jì)算及分析方法研究[D].北京:北京交通大學(xué)，2013.

(DUAN Jiaying. Research on the Carrying Capacity Calculation and Analysis Method of Existing Busy Main-Line after the High-Speed Railway Opened[D]. Beijing: Beijing Jiaotong University，2013. in Chinese)

[18]中國(guó)鐵路總公司.鐵運(yùn)函[2011]328號(hào) 關(guān)于公布京滬高速鐵路列車運(yùn)行圖的通知[S].北京:中國(guó)鐵路總公司，2016.