王銘銘，王 莉，許心越，秦 勇

(1.北京交通大學(xué) 交通運(yùn)輸學(xué)院, 北京 100044；2.北京交通大學(xué) 軌道交通控制與安全國(guó)家重點(diǎn)實(shí)驗(yàn)室, 北京 100044)

面向突發(fā)事件下列車實(shí)時(shí)調(diào)度優(yōu)化問(wèn)題是考慮突發(fā)事件影響，對(duì)已發(fā)布執(zhí)行列車運(yùn)行計(jì)劃的實(shí)時(shí)調(diào)整。隨著列車運(yùn)行速度提高、開(kāi)行密度增大，突發(fā)事件下列車運(yùn)行計(jì)劃調(diào)整問(wèn)題已逐漸成為鐵路運(yùn)輸組織的研究熱點(diǎn)[1]，但現(xiàn)有研究主要集中于擾動(dòng)情景下的列車日計(jì)劃調(diào)整，面向大面積列車晚點(diǎn)和區(qū)間限速等嚴(yán)重復(fù)合場(chǎng)景下高速列車實(shí)時(shí)調(diào)度問(wèn)題還未得到較好地解決，是現(xiàn)場(chǎng)調(diào)度亟需解決的問(wèn)題之一。本文針對(duì)嚴(yán)重初始延誤和區(qū)間限速情況下列車實(shí)時(shí)調(diào)度優(yōu)化方法進(jìn)行研究。

突發(fā)事件可分為輕微擾動(dòng)和嚴(yán)重?cái)_動(dòng)[2]。輕微擾動(dòng)下列車實(shí)時(shí)調(diào)度優(yōu)化主要針對(duì)列車發(fā)生輕微初始延誤場(chǎng)景，文獻(xiàn)[3-5]從微觀層面采用替代圖刻畫列車運(yùn)行邏輯關(guān)系，建立面向輕微延誤的列車運(yùn)行調(diào)整模型，但模型復(fù)雜度隨研究場(chǎng)景復(fù)雜程度呈指數(shù)增長(zhǎng)，無(wú)法解決大規(guī)模嚴(yán)重?cái)_動(dòng)問(wèn)題[6-7]。嚴(yán)重?cái)_動(dòng)下的列車實(shí)時(shí)調(diào)度稱為擾動(dòng)管理，現(xiàn)階段研究主要針對(duì)單一擾動(dòng)場(chǎng)景進(jìn)行調(diào)度優(yōu)化。文獻(xiàn)[8-10]針對(duì)周期運(yùn)行圖采用事件活動(dòng)網(wǎng)絡(luò)構(gòu)建列車運(yùn)行調(diào)整模型，處理線路中斷情況下的列車運(yùn)行調(diào)整問(wèn)題。文獻(xiàn)[11]提出單線鐵路區(qū)間能力失效條件下的列車運(yùn)行調(diào)整模型，并設(shè)計(jì)不確定性分枝定界求解算法。文獻(xiàn)[12-14]針對(duì)區(qū)間完全或部分中斷情況，基于事件活動(dòng)網(wǎng)絡(luò)提出列車運(yùn)行調(diào)整模型。文獻(xiàn)[15]研究區(qū)間突發(fā)故障中斷下的列車運(yùn)行調(diào)整問(wèn)題，建立混合整數(shù)線性規(guī)劃模型。上述文獻(xiàn)僅針對(duì)區(qū)間完全或部分中斷單一場(chǎng)景進(jìn)行研究，嚴(yán)重初始晚點(diǎn)和區(qū)間限速等并發(fā)場(chǎng)景造成大面積列車連帶晚點(diǎn)，影響時(shí)空范圍更廣、需要調(diào)度列車多，這使得調(diào)度場(chǎng)景更加復(fù)雜、約束耦合更強(qiáng)、全局調(diào)度優(yōu)化問(wèn)題更加困難。

面向突發(fā)事件的列車實(shí)時(shí)調(diào)度問(wèn)題屬于NP-hard問(wèn)題，模型求解時(shí)間隨問(wèn)題規(guī)模擴(kuò)大而增加，因此相關(guān)學(xué)者也致力于求解算法的研究。面向新增列車運(yùn)行線情況，文獻(xiàn)[16]提出基于ADMM(Alternating Direction Method of Multipliers)的運(yùn)行圖優(yōu)化算法。文獻(xiàn)[17]針對(duì)雙線鐵路運(yùn)行調(diào)整問(wèn)題，提出禁忌搜索算法，以列車晚點(diǎn)最小為目標(biāo)，搜索受影響列車的最優(yōu)運(yùn)行順序。文獻(xiàn)[18]提出遺傳和粒子群混合啟發(fā)式算法，求解輕微初始延誤下的列車運(yùn)行調(diào)整模型，但在可接受時(shí)間內(nèi)獲得可行解與最優(yōu)解差距19.6%。文獻(xiàn)[19]針對(duì)列車變更運(yùn)行徑路情況，提出列車運(yùn)行調(diào)整的分支定價(jià)算法，但僅探討了小規(guī)模算例的適用性。文獻(xiàn)[20]針對(duì)輕微延誤情況，提出基于分階段多叉樹(shù)的延誤列車運(yùn)行優(yōu)化調(diào)整算法，實(shí)現(xiàn)列車總延誤最小。

上述文獻(xiàn)大多數(shù)采用啟發(fā)式算法求解，大規(guī)模算例情況下并未獲得最優(yōu)解，綜上，嚴(yán)重影響下列車實(shí)時(shí)調(diào)度優(yōu)化問(wèn)題研究尚比較缺乏，且目前我國(guó)采用非周期性運(yùn)行圖，運(yùn)輸組織模式更加復(fù)雜，國(guó)外相關(guān)研究成果不適用于我國(guó)嚴(yán)重突發(fā)事件下列車實(shí)時(shí)調(diào)度問(wèn)題。此外，符合我國(guó)高速鐵路特性的面向嚴(yán)重初始延誤與區(qū)間限速的列車實(shí)時(shí)調(diào)度優(yōu)化模型，且能夠運(yùn)用于調(diào)度現(xiàn)場(chǎng)輔助決策的研究成果不足。

本文將模型復(fù)雜非線性約束以中間決策變量線性化為析取不等式約束組，采用分枝定界算法，在滿足實(shí)時(shí)性情況下，獲得最優(yōu)列車調(diào)度方案，基于文獻(xiàn)[12-13, 21]，針對(duì)嚴(yán)重初始晚點(diǎn)和區(qū)間限速場(chǎng)景，從宏觀層面構(gòu)建事件活動(dòng)網(wǎng)絡(luò)，考慮調(diào)整后列車調(diào)度方案與原列車調(diào)度方案的偏離程度最小化，提出列車實(shí)時(shí)調(diào)度優(yōu)化模型相關(guān)約束和目標(biāo)函數(shù)的線性化方法；實(shí)例驗(yàn)證所提出模型算法的有效性，并將所提出模型算法嵌入現(xiàn)場(chǎng)調(diào)度輔助決策系統(tǒng)中進(jìn)行應(yīng)用，實(shí)現(xiàn)嚴(yán)重初始晚點(diǎn)和區(qū)間限速情況下的列車實(shí)時(shí)調(diào)度。

1 問(wèn)題描述與界定

1.1 問(wèn)題描述

大面積列車晚點(diǎn)、單列車發(fā)生較大晚點(diǎn)和長(zhǎng)時(shí)間區(qū)間限速波及列車多、影響時(shí)間久，降低列車運(yùn)輸服務(wù)質(zhì)量、影響行車安全，需要對(duì)在途和當(dāng)日計(jì)劃運(yùn)行列車進(jìn)行實(shí)時(shí)調(diào)度。事件活動(dòng)網(wǎng)絡(luò)示意見(jiàn)圖1。

圖1 事件活動(dòng)網(wǎng)絡(luò)示意

圖1中，當(dāng)區(qū)間(車站1，車站2)發(fā)生長(zhǎng)時(shí)間限速，列車G3、G5、G7、G9、G11直接受到影響，不能按照計(jì)劃運(yùn)行圖運(yùn)行。因此，需要實(shí)時(shí)調(diào)度運(yùn)行圖中列車，所需調(diào)度列車不僅受到列車在區(qū)間最小運(yùn)行時(shí)分、列車最小停站時(shí)分和列車最小運(yùn)行間隔時(shí)分等基本相關(guān)約束的制約，還受已發(fā)布執(zhí)行列車運(yùn)行圖和突發(fā)事件影響的限制。在滿足上述眾多約束情況下，調(diào)整受影響區(qū)段上列車途經(jīng)各站的到發(fā)時(shí)刻、決策列車在沖突時(shí)空范圍的最佳運(yùn)行順序和停運(yùn)列車，最大程度降低列車調(diào)度方案與原列車運(yùn)行計(jì)劃的偏離程度。

1.2 問(wèn)題界定

在突發(fā)事件條件下，列車實(shí)時(shí)調(diào)度是一項(xiàng)復(fù)雜工作，為簡(jiǎn)化研究問(wèn)題，根據(jù)高速鐵路調(diào)度現(xiàn)場(chǎng)作業(yè)，提出假設(shè)如下：

(1)為保證全線列車實(shí)時(shí)調(diào)度，將車站刻畫為具有能力的節(jié)點(diǎn)，車站能力用車站到發(fā)線數(shù)量表征，不詳細(xì)研究車站到發(fā)線運(yùn)用方案。

(2)僅考慮嚴(yán)重初始延誤和區(qū)間限速時(shí)空范圍已知，未受突發(fā)事件影響時(shí)段和區(qū)段，高速列車基本按圖正常行車，不研究嚴(yán)重初始延誤和區(qū)間限速對(duì)動(dòng)車組運(yùn)用計(jì)劃的影響。

2 模型構(gòu)建

2.1 問(wèn)題抽象

采用事件活動(dòng)網(wǎng)絡(luò)表征列車運(yùn)行邏輯關(guān)系。在事件活動(dòng)網(wǎng)絡(luò)中，事件表示列車在其途經(jīng)各車站的到達(dá)或出發(fā)事件節(jié)點(diǎn)，活動(dòng)是連接兩個(gè)相關(guān)聯(lián)事件的有向弧段，詳細(xì)描述參考文獻(xiàn)[13]。圖1為3趟列車在路網(wǎng)的事件活動(dòng)網(wǎng)絡(luò)，列車1和2的運(yùn)行徑路是{車站A，車站B，車站C}，列車3的運(yùn)行徑路是{車站D，車站B，車站C}。在突發(fā)事件情況下，需要決策事件活動(dòng)網(wǎng)絡(luò)中各列車事件的發(fā)生時(shí)刻、相鄰列車在其運(yùn)行沖突徑路上事件的發(fā)生順序和列車事件是否取消，從而降低突發(fā)事件對(duì)列車運(yùn)行計(jì)劃的影響，保障列車運(yùn)行安全和服務(wù)質(zhì)量。

2.2 模型參數(shù)與決策變量

參數(shù)及含義見(jiàn)表1。

表1 模型參數(shù)

ωe為整數(shù)決策變量，表示調(diào)整后事件e發(fā)生時(shí)刻；ce為0-1決策變量，事件e被取消為1，否則為0；o(ei,ej)為0-1決策變量，事件ei早于事件ej為1，否則為0 。

2.3 模型建立

面向突發(fā)事件影響高速鐵路列車實(shí)時(shí)調(diào)度的主要目的是能夠快速恢復(fù)列車按圖行車，盡可能減少調(diào)整后列車調(diào)度方案與列車運(yùn)行計(jì)劃的偏離程度。偏離程度可用調(diào)整后列車在計(jì)劃停車站的到發(fā)時(shí)刻與計(jì)劃時(shí)刻的偏差和取消列車數(shù)量衡量。

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

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

(1)

(2)

式(1)表示與列車運(yùn)行計(jì)劃時(shí)刻偏差最小化；式(2)表示取消列車數(shù)量最小化。

(3)

(2)列車運(yùn)行計(jì)劃時(shí)刻偏差約束

de≥ωe-pte

e∈e{r,s,l|r∈T,s∈Rr,l∈{dep,arr}}

(4)

de≥-(ωe-pte)

e∈e{r,s,l|r∈T,s∈Rr,l∈{dep,arr}}

(5)

e∈e{r,s,l|r∈T,s=Rr,l∈{arr,dep}}

(6)

T,s=Rr,l∈{arr,dep}}

(7)

e∈e{r,s,l|r∈T,s=Rr,l∈{arr,dep}}

(8)

(3)列車取消約束

為避免取消列車對(duì)旅客造成較大的影響，該模型僅在列車始發(fā)站決策該列車是否取消。列車在始發(fā)站的出發(fā)晚點(diǎn)超過(guò)晚點(diǎn)容忍閾值DTtoler，該列車取消。

de-DTtoler≥(ce-1)·Me∈e{r,s,l|r∈

T,s=or,l=dep}

(9)

所屬同列車的事件取消決策與前一事件的取消決策一致，即同列車的后續(xù)事件取消決策取決于列車在始發(fā)站出發(fā)事件的取消決策。

ce=ce′

(10)

e∈e{r,s,l|r∈T,s=or,l=dep}

e′∈e{r′,s′,l′|r′=r,s′∈Rr,l′∈{dep,arr}}

(4)列車出發(fā)時(shí)刻約束

由于列車時(shí)刻表已向旅客發(fā)布，列車在計(jì)劃停車站調(diào)整后的出發(fā)時(shí)刻，不能早于計(jì)劃發(fā)車時(shí)刻。

ωe-pTe≥ce·Me∈e{r,s,l|r∈T,s∈or∪

(11)

(5)列車初始延誤約束

由于突發(fā)事件造成大面積列車延誤dte，發(fā)生初始延誤的事件調(diào)整后的發(fā)生時(shí)刻不早于事件計(jì)劃發(fā)生時(shí)刻與初始延誤時(shí)間的總和。

ωe-pte≥ce·(M-dte)+dte

(12)

(6)區(qū)間限速約束

(13)

(14)

zr為列車是否受突發(fā)事件影響，具體取值為

(15)

(16)

(17)

(18)

(19)

(20)

受突發(fā)事件影響的列車在事件影響時(shí)空范圍內(nèi)的區(qū)間運(yùn)行時(shí)分增加，其增加程度取決于區(qū)間限速等級(jí)，根據(jù)高速鐵路行車規(guī)則和突發(fā)事件下應(yīng)急響應(yīng)預(yù)案，確定列車在突發(fā)事件下的限速等級(jí)和區(qū)間運(yùn)行時(shí)分增加程度θ。其具體約束為

(21)

(e,e′)=a∈Arun

(7)車站到發(fā)線數(shù)量約束

列車進(jìn)站時(shí)，應(yīng)至少存在一條空閑股道供列車停站或通過(guò)。根據(jù)列車到達(dá)車站順序和從車站出發(fā)順序，分別統(tǒng)計(jì)列車r′到達(dá)車站之前從同一方向到達(dá)該車站的列車數(shù)量和列車r′從該車站出發(fā)之前向同一方向出發(fā)的列車數(shù)量。為避免始發(fā)站列車無(wú)到達(dá)時(shí)刻和終到站列車無(wú)出發(fā)時(shí)刻，定義列車從動(dòng)車段進(jìn)入車站的時(shí)刻為始發(fā)站列車進(jìn)入車站時(shí)刻，列車進(jìn)入動(dòng)車段的時(shí)刻為終到站列車從車站出發(fā)時(shí)刻。本文僅限定到發(fā)線數(shù)量約束，并不考慮到發(fā)線使用方案。

(22)

e∈e{r,s,l|r∈T,s=s′,l=arr}

e′∈e{r′,s′,l′|r′∈T,s′=Rr′,l′=arr}

e″∈e{r″,s″,l″|r″∈T,s″=s′,l″=dep}

e?∈e{r?,s?,l?|r?=r′,s?=s′,l?=dep}

此外，為決策同一方向相鄰列車相繼到達(dá)同一車站時(shí)是否占用該車站同一到發(fā)線，引入決策變量：χ(e″,e′)為事件e″和事件e′是否占用相同到發(fā)線，具體取值為

(23)

e″∈e{r″,s″,l″|r″∈T,r″≠r′,s″=s′,l″=dep}

e′∈e{r′,s′,l′|r′∈T,s′=Rr′,l′=arr}

(24)

e″∈e{r″,s″,l″|r″∈T,r″≠r′,s″=s′,l″=dep}

e′∈e{r′,s′,l′|r′∈T,s′=Rr′,l′=arr}，

(8)其他約束

在滿足上述約束條件下，同時(shí)也需要滿足列車區(qū)間運(yùn)行活動(dòng)和停站作業(yè)時(shí)間約束、列車在站到發(fā)時(shí)刻邏輯約束和線路能力約束，并保證相鄰列車無(wú)法在區(qū)間越行。

(25)

(e,e′)=aa∈Arun∪Adwell，

e∈e{r,s,l|r∈T,s∈Rr,l=dep}，

e′∈e{r′,s′,l′|r′=r,s′=sr,l′=arr}

或e∈e{r,s,l|r∈T,s∈Rr,l=arr}，

e′∈e{r′,s′,l′|r′=r,s′=s,l′=dep}

ωe′-ωe≥0

(26)

e∈e{r,s,l|r∈T,s∈Rr,l=arr}

e′∈e{r′,s′,l′|r′=r,s′=s,l′=dep}，

(e,e′)=a，a∈Astation

(27)

(28)

o(e,e′)+o(e′,e)=1

(29)

o(e,e′)-o(e″,e?)=0

(30)

e?∈e{r?,s?,l?|r?=r′,s?=s″,l?=l″} (e″,e?)∈Arun

2.4 模型求解

由于模型包含大量0-1決策變量，因此采用分枝定界算法求解。該算法通過(guò)模型決策變量集合構(gòu)建分枝定界搜索樹(shù)，分枝定界搜索樹(shù)用于表示分枝定界求解過(guò)程中樹(shù)形結(jié)構(gòu)，由節(jié)點(diǎn)和邊兩種元素組成，通過(guò)不斷地分枝和剪枝過(guò)程，逐步尋求模型最優(yōu)解。算法涉及的變量見(jiàn)表2。

表2 算法涉及參數(shù)

求解該模型的分枝定界算法步驟如下。

Step1初始化

根據(jù)模型決策變量，構(gòu)建模型分枝定界搜索樹(shù)的節(jié)點(diǎn)集合N，選取當(dāng)前具有最小整數(shù)估計(jì)的節(jié)點(diǎn)為根節(jié)點(diǎn)，節(jié)點(diǎn)定義初始解上界LUB←+∞，g=0，Lg=?。

Step2分枝過(guò)程

Step3剪枝過(guò)程

Step4終止條件

判斷算法運(yùn)行時(shí)間或模型上下界的差值是否滿足預(yù)設(shè)定值，若滿足，算法終止，模型所求解出的最小下界即為最優(yōu)可行解；否則，進(jìn)入Step2。

3 實(shí)例分析

3.1 實(shí)例描述

以2018年7月25日岳陽(yáng)東站至廣州南站的武廣高速鐵路區(qū)段的64對(duì)上下行高速列車運(yùn)行計(jì)劃與相關(guān)數(shù)據(jù)進(jìn)行實(shí)際算例分析。研究區(qū)段沿線共經(jīng)過(guò)14個(gè)車站，13個(gè)運(yùn)行區(qū)間。為增加算例復(fù)雜程度，所選取列車具有不同的停站模式，并存在越行現(xiàn)象。

相關(guān)參數(shù)設(shè)置如下：為降低臨時(shí)取消列車策略對(duì)乘客帶來(lái)的負(fù)面影響，考慮取消列車數(shù)量在目標(biāo)函數(shù)中的費(fèi)用遠(yuǎn)大于列車在計(jì)劃停車站的到發(fā)時(shí)刻總偏差費(fèi)用，根據(jù)文獻(xiàn)[22]設(shè)置目標(biāo)函數(shù)費(fèi)用wdiff=1 元和wcancel=1 000 元，列車在計(jì)劃停車站的到發(fā)時(shí)刻總偏差費(fèi)用和取消列車費(fèi)用的詳細(xì)分析見(jiàn)3.2.2節(jié)；假設(shè)列車取消閾值DTtoler為晚點(diǎn)時(shí)分1 800 s。相鄰列車最小到達(dá)和出發(fā)間隔同為180 s；相鄰?fù)较蛄熊囅嗬^占用同一到發(fā)線的最小發(fā)到間隔時(shí)間為240 s。根據(jù)實(shí)績(jī)列車運(yùn)行數(shù)據(jù)，統(tǒng)計(jì)分析列車在區(qū)間最小運(yùn)行時(shí)分，相應(yīng)數(shù)值見(jiàn)表3；列車在計(jì)劃停車站計(jì)劃停站時(shí)分為列車最小停站時(shí)分，列車在非計(jì)劃停車站的最小停站時(shí)分為0。車站能力參照“車站到發(fā)線數(shù)量”，其相應(yīng)取值見(jiàn)表4，注意其值不包括車站正線數(shù)量。區(qū)間限速等級(jí)與區(qū)間最小運(yùn)行時(shí)分增加程度θ的對(duì)應(yīng)關(guān)系可參照參考文獻(xiàn)[23]。原列車運(yùn)行計(jì)劃方案見(jiàn)圖2。

表3 區(qū)間最小運(yùn)行時(shí)分(包括啟停附加時(shí)分)

表4 車站到發(fā)線數(shù)量

圖2 原列車運(yùn)行計(jì)劃方案

為驗(yàn)證模型與算法對(duì)嚴(yán)重初始延誤和區(qū)間限速場(chǎng)景處置的適用性和實(shí)時(shí)性，通過(guò)調(diào)整初始晚點(diǎn)和區(qū)間臨時(shí)限速的時(shí)間和地點(diǎn)，設(shè)計(jì)了4種不同嚴(yán)重程度的突發(fā)事件場(chǎng)景。突發(fā)事件場(chǎng)景及其具體參數(shù)設(shè)置見(jiàn)表5。

表5 突發(fā)事件場(chǎng)景參數(shù)設(shè)置

3.2 算例結(jié)果

本文算例實(shí)現(xiàn)環(huán)境：CPU為Inter (R) Core (TM) i7 10510U 2.30 GHz、內(nèi)存16.0 GB、Windows 10的64位筆記本電腦，采用Python 3.6調(diào)用Gurobi 9.0.1編程，實(shí)現(xiàn)對(duì)所提出模型與算法進(jìn)行實(shí)例驗(yàn)證。

3.2.1 可行性分析

針對(duì)表5中4種突發(fā)事件場(chǎng)景進(jìn)行求解，求解結(jié)果見(jiàn)表6。由表6可知，不同的突發(fā)事件場(chǎng)景對(duì)列車運(yùn)行影響不同；并隨著突發(fā)事件影響程度增加，模型最優(yōu)解的列車到發(fā)時(shí)刻總偏差和停運(yùn)列車數(shù)量在增加；對(duì)比突發(fā)事件場(chǎng)景1、2的調(diào)整后列車運(yùn)行計(jì)劃可知：由于區(qū)間限速影響時(shí)空范圍較大，會(huì)造成嚴(yán)重的大面積列車到發(fā)晚點(diǎn)。在本文提出的優(yōu)化模型和算法下，上述4種突發(fā)事件場(chǎng)景均在120 s內(nèi)求解出最優(yōu)解，滿足列車運(yùn)行計(jì)劃調(diào)整的實(shí)時(shí)性要求。

表6 突發(fā)事件場(chǎng)景下的計(jì)算結(jié)果

針對(duì)復(fù)雜場(chǎng)景4，采用本文所提出的列車實(shí)時(shí)調(diào)度模型進(jìn)行優(yōu)化列車實(shí)時(shí)調(diào)度方案。圖3和圖4分別是列車在途經(jīng)各站的出發(fā)晚點(diǎn)和到達(dá)晚點(diǎn)分布情況。從圖3和圖4可看出，受突發(fā)事件影響晚點(diǎn)列車共32趟，其中一部分列車是由于G6132次列車在廣州南站始發(fā)晚點(diǎn)，造成后續(xù)列車發(fā)生連帶晚點(diǎn)，另一部分是由于樂(lè)昌東站至郴州西站區(qū)間在08：00—09：00間發(fā)生區(qū)間臨時(shí)限速導(dǎo)致。此外，結(jié)果表明在列車實(shí)時(shí)調(diào)度下，受影響上行列車晚點(diǎn)在后續(xù)車站逐步減少，區(qū)間限速對(duì)列車運(yùn)行計(jì)劃影響較大。

圖3 受影響列車在各站出發(fā)晚點(diǎn)分布

圖4 受影響列車在各站到達(dá)晚點(diǎn)分布

3.2.2 目標(biāo)函數(shù)權(quán)重影響分析

本文所提出模型考慮調(diào)整后列車在計(jì)劃停車站的到發(fā)時(shí)刻與計(jì)劃時(shí)刻的偏差和取消列車數(shù)量的加權(quán)費(fèi)用和最小為目標(biāo)，為研究?jī)赡繕?biāo)費(fèi)用對(duì)列車調(diào)度優(yōu)化模型的影響，以突發(fā)事件場(chǎng)景2為例，對(duì)模型中目標(biāo)函數(shù)的費(fèi)用進(jìn)行影響分析，為模型在實(shí)際應(yīng)用中的費(fèi)用取值提供參考依據(jù)。

設(shè)置調(diào)整后列車在計(jì)劃停車站的到發(fā)時(shí)刻與計(jì)劃時(shí)刻的偏差費(fèi)用為1，依次增加取消列車策略費(fèi)用，計(jì)算列車優(yōu)化調(diào)度方案的列車總晚點(diǎn)時(shí)間和取消列車數(shù)量，分析取消列車策略費(fèi)用的影響，見(jiàn)圖5。由圖5可見(jiàn)，當(dāng)調(diào)整后列車在計(jì)劃停車站的到發(fā)時(shí)刻與計(jì)劃時(shí)刻的偏差費(fèi)用和取消列車費(fèi)用相等時(shí)，為使得模型目標(biāo)函數(shù)最小，受影響列車全部被取消，列車總晚點(diǎn)為0；隨著取消列車策略費(fèi)用增加，優(yōu)化后列車調(diào)度方案的列車總晚點(diǎn)時(shí)間和晚點(diǎn)列車數(shù)量逐漸增加，而取消列車數(shù)量逐漸減少；當(dāng)取消列車懲罰增加到550元時(shí)，取消列車數(shù)量為0，晚點(diǎn)列車數(shù)量為33列，列車總晚點(diǎn)達(dá)到最大為115 140 s。

圖5 取消列車費(fèi)用影響分析

考慮臨時(shí)取消列車對(duì)乘客造成負(fù)面影響較大，為降低取消列車對(duì)乘客的影響，一方面本文模型僅允許在始發(fā)站決策是否取消列車，避免取消在途列車；另一方面，調(diào)度員可提高臨時(shí)取消列車費(fèi)用，減少取消列車數(shù)量；此外，為提高列車正點(diǎn)率，可以適當(dāng)降低取消列車費(fèi)用，增加取消列車數(shù)量，從而降低晚點(diǎn)列車數(shù)量。

3.2.3 對(duì)比分析

以復(fù)雜場(chǎng)景4為例，分別采用所提出模型求解的列車最優(yōu)運(yùn)行順序和以先到先服務(wù)的現(xiàn)場(chǎng)調(diào)度策略，對(duì)調(diào)整后的列車調(diào)度方案進(jìn)行具體分析，進(jìn)一步說(shuō)明本文提出的模型和算法的有效性。

基于模型最優(yōu)運(yùn)行順序策略和基于先到先服務(wù)策略下的模型目標(biāo)函數(shù)上下界收斂曲線見(jiàn)圖6。由圖6可知，在不同運(yùn)行順序策略下，面向鐵路實(shí)際案例，算法均能在120 s內(nèi)實(shí)現(xiàn)收斂，獲取到最優(yōu)解，滿足調(diào)度現(xiàn)場(chǎng)列車運(yùn)行調(diào)整方案生成的實(shí)時(shí)性要求。在本文所提出模型的最優(yōu)列車運(yùn)行順序策略下，所獲得的列車實(shí)時(shí)調(diào)度方案明顯優(yōu)于現(xiàn)場(chǎng)按照先到先服務(wù)調(diào)度策略下的列車調(diào)度方案。與先到先服務(wù)調(diào)度策略相比，基于模型優(yōu)化下的調(diào)整后列車調(diào)度方案加權(quán)總偏離程度減少25%。由此可見(jiàn)，所提出的模型能夠在保證列車安全運(yùn)行前提下，能夠較大的減少突發(fā)事件對(duì)計(jì)劃列車運(yùn)行的影響。

圖6 不同策略下目標(biāo)函數(shù)上下界收斂曲線

針對(duì)嚴(yán)重突發(fā)事件場(chǎng)景4，基于本文所構(gòu)建模型獲得的調(diào)度策略，獲得調(diào)整后列車調(diào)度方案見(jiàn)圖7。從圖7可見(jiàn)，在突發(fā)事件場(chǎng)景3的影響下，基于本文所提出模型獲得的調(diào)度策略，在G2056次列車11：17到達(dá)岳陽(yáng)東終到站時(shí)，所有列車恢復(fù)按原計(jì)劃運(yùn)行圖行車，其事件恢復(fù)時(shí)間為137 min；在相同突發(fā)事件場(chǎng)景下，相較于基于先到先服務(wù)順序策略(事件恢復(fù)時(shí)刻為11：46)，本文所獲得最優(yōu)調(diào)整列車調(diào)度方案使得突發(fā)事件影響恢復(fù)時(shí)間減少29 min。

圖7 調(diào)整后列車調(diào)度方案

4 結(jié)論

本文通過(guò)事件活動(dòng)網(wǎng)絡(luò)從宏觀層面刻畫列車群運(yùn)行邏輯關(guān)系，對(duì)嚴(yán)重初始延誤和區(qū)間限速情況下的列車實(shí)時(shí)調(diào)度問(wèn)題進(jìn)行了建模與求解?？坍嬃肆熊嚾∠?、初始延誤與區(qū)間限速等相關(guān)約束，并對(duì)列車晚點(diǎn)、取消等非線性約束進(jìn)行線性化，以調(diào)整后列車調(diào)度方案與原列車運(yùn)行計(jì)劃的偏離程度最小為優(yōu)化目標(biāo)，構(gòu)建了面向嚴(yán)重初始延誤與區(qū)間限速的列車實(shí)時(shí)調(diào)度模型；同時(shí)，采用了基于分枝定界的列車調(diào)度優(yōu)化算法，能夠在線生成列車調(diào)度方案。

以武廣高速鐵路為實(shí)際驗(yàn)證算例，設(shè)計(jì)了4種嚴(yán)重突發(fā)事件場(chǎng)景，對(duì)所提出的模型和算法進(jìn)行了實(shí)例驗(yàn)證。對(duì)模型目標(biāo)函數(shù)費(fèi)用權(quán)重取值進(jìn)行了分析，給出在實(shí)際應(yīng)用中的一些指導(dǎo)性分析和說(shuō)明；通過(guò)與先到先服務(wù)調(diào)度策略下的列車調(diào)度方案對(duì)比，所提出模型和算法能夠有效的降低調(diào)整后列車調(diào)度方案和列車原運(yùn)行計(jì)劃的偏離程度(下降25%)和突發(fā)事件的恢復(fù)時(shí)間(減少29 min)。

目前本文主要針對(duì)嚴(yán)重突發(fā)事件影響初始延誤和區(qū)間限速情況，在宏觀層面對(duì)列車運(yùn)行計(jì)劃進(jìn)行調(diào)整，但未考慮動(dòng)車組運(yùn)用計(jì)劃和乘務(wù)組計(jì)劃的約束；另一方面，也并未在微觀層面對(duì)突發(fā)事件影響進(jìn)行分析，如在區(qū)間限速情況時(shí)，未考慮列車在途降速情況，而這需從微觀層面考慮列車的速度牽引曲線，本文為實(shí)現(xiàn)解決大規(guī)模列車運(yùn)行計(jì)劃調(diào)整實(shí)際案例，對(duì)上述細(xì)節(jié)暫未做詳細(xì)研究；此外，隨著微觀層面建模和問(wèn)題規(guī)模的擴(kuò)大，在權(quán)衡求解質(zhì)量和效率前提下，如何設(shè)計(jì)更為有效的啟發(fā)式算法，也是下一步研究方向。