基于約束規(guī)劃方法的高速鐵路調(diào)整優(yōu)化模型

曾 壹，張 琦，陳 峰

(1.中國鐵道科學(xué)研究院集團(tuán)有限公司 研究生部，北京 100081；2.中國鐵道科學(xué)研究院集團(tuán)有限公司 通信信號研究所，北京 100081；3.國家鐵路智能運(yùn)輸系統(tǒng)工程技術(shù)研究中心，北京 100081)

運(yùn)行圖是列車調(diào)度員使用的鐵路運(yùn)輸綜合計(jì)劃，是行車組織工作的基礎(chǔ)。高速鐵路列車運(yùn)行調(diào)整屬于大規(guī)模組合優(yōu)化問題，在有限時(shí)間內(nèi)求出最優(yōu)解是問題的難點(diǎn)。國內(nèi)外學(xué)者在調(diào)整理論建模方面開展了大量研究實(shí)驗(yàn)，然而數(shù)學(xué)規(guī)劃[1-2]和圖論[3-4]方法都難以達(dá)到調(diào)度支持系統(tǒng)實(shí)時(shí)計(jì)算要求。為提高計(jì)算效率，本文將列車調(diào)整計(jì)劃的組合優(yōu)化問題轉(zhuǎn)化為多個(gè)宏觀事件節(jié)點(diǎn)在運(yùn)行圖間隔時(shí)間規(guī)定下求出可行解的約束滿足問題[5]CSP(Constraint Satisfaction Problem)求解。

約束規(guī)劃方法是求解約束滿足問題的高速計(jì)算方法，特點(diǎn)是使用約束傳遞機(jī)制在約束條件劃定的解空間內(nèi)迭代搜索并調(diào)整變量取值。在變量無法求出可行解時(shí)，算法將不進(jìn)行約束傳遞，而是使用試錯(cuò)回退機(jī)制重新計(jì)算。列車計(jì)劃調(diào)整問題中的約束規(guī)劃方法根據(jù)運(yùn)行圖間隔時(shí)間條件[6-8]或線路設(shè)備占用條件[9-10]定義檢查方法與解空間。當(dāng)擾動發(fā)生后，約束傳遞算法迭代檢查被擾動事件并且只改變變量取值，而列車到開事件關(guān)系的調(diào)整由試錯(cuò)回退機(jī)制根據(jù)列車越行[6]、分解[7]等調(diào)度措施的運(yùn)行圖樣式確定，從而有效限制了單次調(diào)整需要考慮的變量個(gè)數(shù)和取值范圍。約束規(guī)劃方法在列車計(jì)劃調(diào)整問題中作為輔助方法提供混合整數(shù)規(guī)劃模型的初始解[8]，或應(yīng)用于宏觀[6-7]與微觀[9-10]規(guī)模的擾動管理，達(dá)到降低計(jì)算耗時(shí)的效果。

本文在學(xué)習(xí)上述方法特性的基礎(chǔ)上，設(shè)計(jì)一種列車調(diào)整計(jì)劃的約束規(guī)劃優(yōu)化模型。模型將調(diào)整問題轉(zhuǎn)化為CSP問題，通過制約傳播方法檢查運(yùn)行圖間隔時(shí)間、股道占用條件并觸發(fā)使用線路緩沖時(shí)間或越行策略改變運(yùn)行計(jì)劃，調(diào)整過程可使用人機(jī)交互參數(shù)配置。模型與同等約束條件下的整數(shù)規(guī)劃模型進(jìn)行對比，驗(yàn)證了在多種干擾條件下的晚點(diǎn)總時(shí)長減少與計(jì)算效率提高。

1 約束滿足問題建模與約束規(guī)劃算法設(shè)計(jì)

1.1 CSP問題構(gòu)建與間隔時(shí)間條件

約束滿足問題是探索滿足有限個(gè)制約條件限制的多變量組合可行解的數(shù)學(xué)問題[5]，具備以下特征：

(1)問題描述可等效為多個(gè)約束條件的集合。

(2)所有約束條件使用等式、不等式、邏輯表達(dá)式的形式表述。

(3)所有變量均具備特定的取值范圍。

階段計(jì)劃受到運(yùn)行圖間隔時(shí)間條件的約束并具有一定的時(shí)間范圍，能夠相應(yīng)轉(zhuǎn)化為符合以下特征的CSP問題：

(1)問題的約束條件為多個(gè)運(yùn)行圖間隔時(shí)間條件的集合。

(2)所有約束條件使用不等式表述。

(3)所有變量的時(shí)間取值來自一定時(shí)間范圍的階段計(jì)劃。

表1 運(yùn)行圖間隔時(shí)間條件的分類

1.2 約束傳遞方法與間隔條件整合

約束傳遞是約束規(guī)劃算法判定變量值是否實(shí)現(xiàn)約束滿足并修正不符合制約關(guān)系式要求變量值的子方法。方法最大的特點(diǎn)是通過修正變量值觸發(fā)下一個(gè)關(guān)聯(lián)變量檢查，從而將所有潛在不滿足條件設(shè)置變量的檢查流程轉(zhuǎn)化為方法自身的內(nèi)部觸發(fā)與迭代流程。約束傳遞的舉例說明如圖 1所示。

圖1 列車i出發(fā)晚點(diǎn)的制約傳播

流程從列車i在車站1出發(fā)的事件發(fā)生晚點(diǎn)開始，晚點(diǎn)將觸發(fā)約束傳遞方法檢查出發(fā)事件與i車到達(dá)車站2的時(shí)間之間是否滿足最小區(qū)間運(yùn)行時(shí)間Tt(i,1)，如果約束條件不滿足，約束傳遞方法將調(diào)整i車在車站2的到達(dá)時(shí)間。由于到達(dá)事件時(shí)刻的變動，該變動又將觸發(fā)約束傳遞方法檢查i車在車站2的到達(dá)事件。如果該事件與列車i*在車站2的到達(dá)事件不滿足最小同向到達(dá)間隔時(shí)間Ta(i,i*,2)，約束傳遞方法又將調(diào)整列車i*在車站2的到達(dá)時(shí)間，進(jìn)一步觸發(fā)其他相關(guān)事件的約束傳遞方法檢查。

( 1 )

表 1中最小停車時(shí)間Ts(i,j)和技術(shù)作業(yè)標(biāo)準(zhǔn)時(shí)間To(i,j)的事件對關(guān)系一致，兩個(gè)條件只要取最大的約束值代入式( 1 )并達(dá)成約束滿足，即可判定較小約束值的條件也達(dá)到約束滿足。另外，車站會車約束Tm(i,i*,j)可被分解為最小不同時(shí)到達(dá)間隔時(shí)間Da(i,i*,j)與最小停車時(shí)間Ts(i,j)的組合，Tm(i,i*,j)與Da(i,i*,j)同理也只需代入最大約束值即可達(dá)成兩者的約束滿足判定。上述條件可表述為約束傳遞范式的極大加代數(shù)條件整合結(jié)果如式( 2 )所示。

( 2 )

此分類方式不僅降低了大規(guī)模計(jì)劃調(diào)整問題的計(jì)算量，還表明同站間隔類約束條件除終到站最小折返時(shí)間約束Tr(i,i*,j)與股道最小發(fā)到間隔Le(i,i*,j)外，均為同類事件之間的間隔關(guān)系。

1.3 試錯(cuò)回退機(jī)制與股道沖突建模

試錯(cuò)回退機(jī)制是由特定解或解空間不存在作為條件觸發(fā)可行解樣式的約束規(guī)劃算法子方法。在運(yùn)行圖間隔時(shí)間條件的CSP問題構(gòu)建中，試錯(cuò)回退機(jī)制提供了列車到開事件關(guān)系變化的備選調(diào)度方案。以越行方案為例，試錯(cuò)回退機(jī)制的操作可描述為由線路條件觸發(fā)并確定圖 2所示列車事件時(shí)間序列的過程。

圖2 回退檢索與列車越行時(shí)序

圖 2中，列車i在車站2通過到達(dá)事件最小同向到達(dá)時(shí)間約束Ta(i,i*,j)的約束傳遞判定項(xiàng)，觸發(fā)回退檢索并在車站1停車等待列車i出發(fā)。依據(jù)式( 2 )條件得出列車i序列后移在車站1引起的事件關(guān)系變動如圖 3所示。

圖3 回退檢索引起的出發(fā)事件關(guān)系變動

( 3 )

式中：SL、SU分別為影響區(qū)域下界、上界的搜索函數(shù)。文獻(xiàn)[6，13]提出的搜索方法將回退檢索的影響范圍固定為同站30 min內(nèi)的列車事件，本文在該方法的基礎(chǔ)上改進(jìn)并采用同站間隔關(guān)系的運(yùn)行圖間隔時(shí)間條件定義受影響的事件范圍搜索函數(shù)為

( 4 )

越行操作未增刪列車運(yùn)行事件，但局部改變了列車到發(fā)關(guān)系。設(shè)iU、iL為圖 3上下界事件的車次號，則保持CSP問題在事件關(guān)系變更后間隔時(shí)間條件值正確調(diào)用的出發(fā)事件同站間隔關(guān)系參數(shù)更新方法可陳述為替換與賦值關(guān)系。

( 5 )

由于高鐵雙線區(qū)段不需考慮會車條件，折返條件只在列車終到站應(yīng)用，出發(fā)事件的同站間隔關(guān)系變更只需更新最小同向出發(fā)間隔時(shí)間Td(i,i*,j)。列車i在其他車站出發(fā)事件后移引起的事件關(guān)系變動與間隔關(guān)系參數(shù)變更情況可分別參考圖 3、式( 5 )。

同樣的，越行操作引起的列車i在其他車站到達(dá)事件之間的關(guān)系變動可整理為圖 4，事件關(guān)系變更后的到達(dá)時(shí)間同站間隔關(guān)系更新方法可參考式( 5 )。

圖4 回退檢索引起的到達(dá)事件關(guān)系變動

( 6 )

( 7 )

函數(shù)Lc(j,m)檢測到股道計(jì)劃沖突后，約束傳遞方法的調(diào)整規(guī)則如下：

(1)車站主股道只用于排列通過進(jìn)路，不用于待避。

(2)營業(yè)站的到開可以晚點(diǎn)，但不能更換計(jì)劃使用的股道。

(4)如果調(diào)整策略要求并且站細(xì)允許，就進(jìn)行股道更換。

( 8 )

2 調(diào)整策略設(shè)計(jì)與約束規(guī)劃總體流程

約束規(guī)劃算法通過約束傳遞子方法檢查運(yùn)行圖間隔時(shí)間、越行和股道沖突條件并觸發(fā)運(yùn)行計(jì)劃的改動。為加強(qiáng)算法可控性，本文在約束規(guī)劃算法中量化處理了緩沖時(shí)間和越行的自動觸發(fā)關(guān)鍵參數(shù)，建立兩類調(diào)整方法的人機(jī)交互參數(shù)控制方式以及無緩沖時(shí)間和越行調(diào)整策略的PERT仿真方法[14]。

2.1 緩沖時(shí)間建模設(shè)置與約束傳遞整合

表2 一種緩沖時(shí)間的分配方法

( 9 )

2.2 越行調(diào)整模式與參數(shù)設(shè)置

約束規(guī)劃算法通過約束傳遞檢查最小同向到達(dá)時(shí)間約束Ta(i,i*,j)的方式觸發(fā)回退檢索子方法和運(yùn)行線越行操作。圖3、圖4的單站出發(fā)、到達(dá)事件變動能夠表達(dá)為如圖5所示的越行樣式。圖5中還包含晚點(diǎn)順序傳遞樣式，對應(yīng)回退檢索未被觸發(fā)情況下的約束傳遞檢查情況。

圖5 運(yùn)行線調(diào)整模式

(10)

當(dāng)δD≤δ

調(diào)度區(qū)段內(nèi)不同類型列車依據(jù)承擔(dān)運(yùn)輸組織任務(wù)的重要程度分為不同的優(yōu)先級別[15]。在高鐵調(diào)度區(qū)段內(nèi)，除城際動車組外還存在高速動車組、少量直通貨車(部分區(qū)段運(yùn)行圖中存在車次規(guī)劃)、檢測車與回送車底。由于高速動車組跨多個(gè)調(diào)度區(qū)段行車，其優(yōu)先級應(yīng)為最高，其次是城際動車組與直通貨車。檢測車通常編制在第一班末，而回送車底多在動車段與車場間行車，故這兩類車不做進(jìn)一步討論。

綜上所述，高鐵調(diào)度區(qū)段的越行模式可歸納如下：

(1)同級別列車發(fā)生晚點(diǎn)后，根據(jù)δ值確定的晚點(diǎn)情況，δ大于δD1通過緩沖時(shí)間處理，小于δD1需組織晚點(diǎn)車待避。δD1為同級別列車之間的調(diào)整閾值。

(2)高級別列車發(fā)生晚點(diǎn)影響低級別列車時(shí)，通過緩沖時(shí)間處理。

(3)低級別旅客列車發(fā)生晚點(diǎn)影響高級別列車時(shí)，δ小于δD2的晚點(diǎn)需組織晚點(diǎn)車待避，δ大于δD2則通過緩沖時(shí)間處理，部分晚點(diǎn)可以傳播到高級別列車。δD2為不同級別列車之間的調(diào)整閾值。

(4)低級別直通貨車發(fā)生晚點(diǎn)影響高級別列車時(shí)，需組織晚點(diǎn)車待避。

(5)待避晚點(diǎn)列車的級別低于同類型列車，但相對其他類型列車的優(yōu)先級別設(shè)置不變。同類型的待避晚點(diǎn)列車按照同級別列車的場景處理。

(6)為減少旅客不滿，旅客列車在調(diào)度區(qū)段內(nèi)最多只能待避一次，且時(shí)長不超過δD3。δD3為設(shè)置的最長待避時(shí)間。

在越行模式內(nèi)，相同與不同列車級別的調(diào)整閾值δD1、δD2以及最長待避時(shí)間δD3能夠根據(jù)實(shí)際應(yīng)用需要設(shè)置。

2.3 調(diào)整優(yōu)化總體流程與約束條件判定次序

約束規(guī)劃算法通過整合緩沖時(shí)間與越行樣式實(shí)現(xiàn)了可調(diào)參數(shù)的自動調(diào)整功能。在該功能關(guān)閉時(shí)，算法將不會進(jìn)行調(diào)整策略輸出，而是按照文獻(xiàn)[6]描述的PERT方法，進(jìn)行不斷將間隔約束時(shí)長加算到鄰接事件的仿真計(jì)算。由于不涉及運(yùn)行計(jì)劃節(jié)點(diǎn)增刪或到發(fā)次序變動，仿真計(jì)算能夠滿足CSP問題的前置條件。調(diào)整優(yōu)化模型的總體流程如圖 6所示。

圖6 調(diào)整優(yōu)化模型的總體流程

約束條件檢索方法內(nèi)部設(shè)計(jì)為優(yōu)先檢查觸發(fā)大計(jì)算量以及同站間隔關(guān)系的條件，能起到防止小規(guī)模變動頻繁觸發(fā)的效果。模塊的約束條件檢測按照表3的固定次序進(jìn)行。

表3 約束條件的判定次序

3 等效整數(shù)規(guī)劃模型設(shè)計(jì)

列車運(yùn)行調(diào)整問題的傳統(tǒng)方法是建立整數(shù)規(guī)劃模型求解，除了運(yùn)行圖間隔時(shí)間和車站能力的安全條件約束外，列車到站、出站時(shí)刻還受到?jīng)Q策變量規(guī)定的到發(fā)次序約束。離散型決策變量的排列組合包含列車越行、車次取消等調(diào)度措施的所有可能情況，使模型能夠算出最優(yōu)解，然而也導(dǎo)致算法時(shí)間復(fù)雜度隨著決策變量的增加而呈現(xiàn)出指數(shù)型增長。相比之下，約束規(guī)劃算法的到發(fā)次序變動樣式由試錯(cuò)回退機(jī)制固定，雖然無法遍歷所有可能的到發(fā)次序調(diào)整情況，但解空間冗余度小，能用于高速計(jì)算可行解。為對比驗(yàn)證約束規(guī)劃算法可行解趨近最優(yōu)解的程度以及計(jì)算效率的改善情況，本文設(shè)計(jì)同等運(yùn)行圖間隔時(shí)間、車站能力以及調(diào)度措施條件約束下的整數(shù)規(guī)劃算法。式(11)為整數(shù)規(guī)劃模型的目標(biāo)函數(shù)。

(11)

單列列車的區(qū)間運(yùn)行、車站停車和技術(shù)作業(yè)條件可表述為式(12)～式(14)。j*用于標(biāo)示運(yùn)行圖車次i通過車站j后到達(dá)的車站。車次i在車站j不存在技術(shù)作業(yè)時(shí)，To(i,j)→-∞。

(12)

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)

(23)

(24)

(25)

(26)

整數(shù)規(guī)劃模型相應(yīng)的變量值域定義如式(27)～式(30)所示。模型中的列車事件關(guān)聯(lián)關(guān)系來自運(yùn)行圖GPlan。

(27)

(28)

(29)

(30)

4 模型應(yīng)用案例與分析

模型采用京津城際某月的運(yùn)行圖進(jìn)行列車調(diào)整計(jì)算，運(yùn)行圖包含20個(gè)節(jié)點(diǎn)，約250列車。場景設(shè)置的具體情況見表4。在調(diào)度區(qū)段擾動時(shí)長較大時(shí)，調(diào)度員進(jìn)行的列車取消、加開等調(diào)度措施會破壞列車調(diào)整問題的CSP建模條件，故擾動時(shí)長限定在10、20、 30 min的情景下。

表4 擾動場景的參數(shù)設(shè)置

案例采用整數(shù)規(guī)劃模型與PERT仿真方法作為對照組，驗(yàn)證約束規(guī)劃模型的晚點(diǎn)總時(shí)長和計(jì)算時(shí)間。線路緩沖時(shí)間按照表 2設(shè)置并應(yīng)用于區(qū)間運(yùn)行時(shí)間、折返時(shí)間以及兩類追蹤間隔時(shí)間。調(diào)整模式的構(gòu)建參數(shù)δD1、δD2、δD3分別為5、5、20 min。三類算法均使用C++編碼，整數(shù)規(guī)劃模型通過調(diào)用ILOG CPLEX求解，CPU主頻為2.5 GHz，所有計(jì)算時(shí)間由Windows平臺下的查詢性能計(jì)數(shù)器統(tǒng)計(jì)。9種場景下的約束規(guī)劃模型、PERT仿真和整數(shù)規(guī)劃模型計(jì)算結(jié)果見表5。

表5 不同干擾情況下調(diào)整計(jì)算結(jié)果

表5計(jì)算結(jié)果表明，整數(shù)規(guī)劃模型的晚點(diǎn)總時(shí)長緩解效果最好，原因是問題構(gòu)建中每個(gè)列車事件都有對應(yīng)的不等式描述越行與股道變更情況。大規(guī)模的問題描述保證了求解精度，也帶來了算法復(fù)雜度問題。而在同等問題規(guī)模與約束條件下，約束規(guī)劃模型在所有場景內(nèi)的計(jì)算效率均高于整數(shù)規(guī)劃模型，原因?yàn)閮?nèi)部約束傳遞與試錯(cuò)回退機(jī)制能夠有效限定列車運(yùn)行調(diào)整問題的解空間，只要依據(jù)調(diào)度措施合理設(shè)計(jì)，就能實(shí)現(xiàn)可行解的高速計(jì)算。

約束規(guī)劃與整數(shù)規(guī)劃模型的計(jì)算結(jié)果如圖 7、圖8所示，計(jì)劃線為實(shí)線，調(diào)整線為虛線。由于場景3比場景1、2的擾動規(guī)模大，調(diào)整效果也更顯著，案例只給出場景3的圖示。圖中未列出部分僅用于車底與直通列車接入的車站，故節(jié)點(diǎn)總數(shù)量小于20個(gè)。約束規(guī)劃模型在同等約束條件下的計(jì)算效率遠(yuǎn)高于整數(shù)規(guī)劃模型，然而整數(shù)規(guī)劃模型的調(diào)整結(jié)果與計(jì)劃線差別與晚點(diǎn)整體的影響范圍都表現(xiàn)最優(yōu)，說明約束規(guī)劃模型的檢索機(jī)制只能有限地趨近最優(yōu)解，內(nèi)部機(jī)制還需要完善。

圖7 場景3的約束規(guī)劃列車調(diào)整模型計(jì)劃生成結(jié)果

圖8 場景3的整數(shù)規(guī)劃列車調(diào)整模型計(jì)劃生成結(jié)果

約束規(guī)劃模型調(diào)整策略的有效性還能通過晚點(diǎn)比率考察，晚點(diǎn)比率是約束規(guī)劃模型與PERT仿真晚點(diǎn)總時(shí)長的百分比，該比率越低，調(diào)整策略的效果越好。約束規(guī)劃模型場景1～3的調(diào)整結(jié)果與文獻(xiàn)[6]的晚點(diǎn)比率分析如圖 9所示，兩者分別為實(shí)線、虛線。圖9中5、15、25 min的晚點(diǎn)比率由亦莊—永樂下行方向區(qū)間封鎖8：25—8：30、8：25—8：40、8：25—8：50的擾動場景算出。

圖9 不同約束規(guī)劃調(diào)整優(yōu)化模型的比較分析

由于約束規(guī)劃優(yōu)化模型處理的調(diào)度區(qū)段內(nèi)多為城際列車，高等級直通列車只占很小比例，使得不同級別間越行現(xiàn)象發(fā)生的頻次少于文獻(xiàn)[6]。而文獻(xiàn)[6]處理的調(diào)度區(qū)段內(nèi)高、低等級列車數(shù)量各占一半，不同級別間越行的頻次多，從而達(dá)到更好的調(diào)整效果。得益于緩沖時(shí)間的有效利用，約束規(guī)劃模型在5 min干擾程度下的調(diào)整效果優(yōu)于文獻(xiàn)[6]。

5 結(jié)束語

本文在列車運(yùn)行調(diào)整問題構(gòu)建為CSP問題的基礎(chǔ)上，建立了基于約束規(guī)劃方法的高速鐵路調(diào)整優(yōu)化模型。優(yōu)化模型的最大特點(diǎn)是高效率計(jì)算，相比與同等運(yùn)行圖間隔時(shí)間、車站能力以及調(diào)度策略條件約束下的整數(shù)規(guī)劃算法，該模型具備更強(qiáng)的計(jì)算效率，但晚點(diǎn)總時(shí)長的優(yōu)化效果不及整數(shù)規(guī)劃算法，其內(nèi)部機(jī)制仍需進(jìn)一步改善。優(yōu)化模型算法計(jì)算效率高，具備較強(qiáng)的拓展?jié)摿?，后期研究可考慮將換乘、分解等調(diào)度手段引入約束傳遞方法，進(jìn)一步增強(qiáng)自動調(diào)整功能，為智能調(diào)度業(yè)務(wù)的系統(tǒng)集成提供有力的支持。