基于啟發(fā)式回溯算法的鐵路編組站調(diào)車場股道活用研究

馬 亮，張曉霞，郭 進

(1.電子科技大學(xué) 光電信息學(xué)院，四川 成都 610054；2.西南交通大學(xué) 信息科學(xué)與技術(shù)學(xué)院，四川 成都 610031)

調(diào)車場是編組站辦理改編作業(yè)的關(guān)鍵設(shè)施，對通過車站的車流起著“蓄洪”作用，如果調(diào)車場股道得不到靈活運用，可能會造成車站堵塞。為了提高解編調(diào)車作業(yè)效率和階段計劃配流方案的兌現(xiàn)率，需要在動態(tài)配流的基礎(chǔ)上，實現(xiàn)調(diào)車場股道活用。

一般情況下車站調(diào)度員(站調(diào))按照“定而不死、活而不亂”的指導(dǎo)思想對調(diào)車場股道分工靈活掌握，但是當(dāng)列車不均衡、密集到達(dá)、車流方向遠(yuǎn)多于調(diào)車場股道數(shù)時，很難做到靈活使用股道。文獻(xiàn)[1-3]研究調(diào)車場股道的固定使用，一般用來作為實際作業(yè)的基本準(zhǔn)則。在以往階段計劃智能編制研究[4-7]中很少考慮調(diào)車場股道的活用對動態(tài)配流的影響，如果調(diào)車場股道得不到充分活用，可能會影響到發(fā)車流的接續(xù)關(guān)系和配流方案的實施。文獻(xiàn)[8]研究了配流和調(diào)車場股道調(diào)整使用的協(xié)同優(yōu)化，但是模型中將不同方向的車流盡量流入不同的股道，這樣可能會增加解體鉤數(shù)和編組鉤數(shù)；同時，文獻(xiàn)中只是以出發(fā)車流來源作為調(diào)車場車流變化的依據(jù)，沒有考慮解編作業(yè)和車輛在車列中的順位等因素，模型和算法還需完善。

本文在動態(tài)配流決策出解編作業(yè)起止時間和出發(fā)車列車流來源及編組內(nèi)容[8]的基礎(chǔ)上，綜合考慮了調(diào)車場車流隨著解編作業(yè)動態(tài)變化、調(diào)車場股道的容量和解編作業(yè)時序限制等，并設(shè)計“開口”算法將到達(dá)車列按照順位、去向(車種)分為車組，以車組在調(diào)車場集結(jié)股道為變量，建立調(diào)車場股道活用整數(shù)優(yōu)化模型。為了加快求解，在同去向車流盡量集結(jié)于一條股道、其他車流集結(jié)不影響編入出發(fā)車列的車流集結(jié)、減少越區(qū)作業(yè)和交叉干擾等規(guī)則的基礎(chǔ)上，設(shè)計了變量取值動態(tài)排序(Value Ordering Heuristics， ValOH)[9，10]的啟發(fā)式回溯算法(Heuristic Backtracking，HBT)[10]每次選擇優(yōu)先級最高的股道，當(dāng)沒有股道能夠容納此車組時回溯，最終無解時就二次分解車組，直到所有的車組都有集結(jié)股道并達(dá)到最優(yōu)。

1 調(diào)車場股道活用問題描述及求解思路

調(diào)車場股道按照用途分為如下幾類[11]：

(1)供列車編組計劃規(guī)定的到站或去向的車輛解體、集結(jié)、編組用的線路，包括直達(dá)、直通、區(qū)段、摘掛以及小運轉(zhuǎn)列車集結(jié)、解編用的線路和編發(fā)線；

(2)供空車解體、集結(jié)、編組用的線路；

(3)供本站作業(yè)車或交換車用的線路；

(4)供其他專門作業(yè)用的車輛停車的線路，主要指守車、待整車、倒裝車、待修車、超限車或禁止過峰車以及危險品、易燃品車等的停留線。

定義1前三類股道中集結(jié)具有方向(車種)屬性的有調(diào)車，可以統(tǒng)一稱為活用股道集；站調(diào)在編制階段計劃時無法準(zhǔn)確掌握扣修、禁溜和禁過峰等專用車輛，所以將第四類股道稱為固定股道集。

定義2將到解車列編組順序表中的車輛按照方向(車種)歸類成形如“方向(車種)/輛數(shù)”稱為編組內(nèi)容；如果再考慮車輛在車列中的順位，即相鄰的且方向(車種)相同的車輛歸為一類，稱為順位編組內(nèi)容。

調(diào)車場存車狀態(tài)的變化不僅和車輛的方向(車種)有關(guān)，還與車輛在車列中的順位有直接關(guān)系，所以在為到解車列“開口”劃分車組時應(yīng)以車列的順位編組內(nèi)容為依據(jù)。

定義3為了解體照顧編組，將到解車列中順位相鄰且編入相同出發(fā)車列、包含在同一條列車編組計劃或者相同方向(車種)的車輛歸為一組，稱為到達(dá)車組。如果車組被編入某出發(fā)車列，則車組特征為出發(fā)列車車次，否則為列車編組計劃的到站或者為車流方向(車種)，且特征優(yōu)先級依次降低。

在制定調(diào)車場股道活用方案時，應(yīng)該盡量使得同特征的到達(dá)車組在一條股道上集結(jié)。而且低等級特征車組盡量不要影響高等級特征車組的集結(jié)。

定義4到解車列中順位小的車輛靠近駝峰，優(yōu)先解體；調(diào)車場股道中順位大的靠近駝峰。如果某股道中只有一個車組，那么稱為露頭股道。將調(diào)車場股道中順位最大車組的特征稱為此股道的露頭特征。如果選擇露頭特征與某車組特征相同的露頭股道作為某車組的集結(jié)股道，稱為露頭原則。

在為車組選擇集結(jié)股道時應(yīng)優(yōu)先考慮露頭原則，其次再選擇低級別的股道，這樣既能降低股道的混用率，也能減少出發(fā)車列的編組調(diào)車鉤數(shù)。

定義5由能夠容納某到達(dá)車組的活用股道構(gòu)成的集合稱為此車組的可行活用股道集。根據(jù)可行活用股道集中各股道的存車狀態(tài)及到達(dá)車組特征按照股道活用規(guī)則劃分為若干等級股道群。

調(diào)車場股道活用應(yīng)充分體現(xiàn)解體照顧編組、當(dāng)前解體照顧后續(xù)解體、減少交叉干擾、均衡資源(牽出線、解編調(diào)機)運用等原則。將可行活用股道集按照滿足活用規(guī)則程度劃分等級股道群，并為到達(dá)車組優(yōu)先選擇高等級股道群中股道。

定義6任何時刻每條股道包含不同順位、不同特征的車組數(shù)稱為此時股道的混亂度。

每條調(diào)車場股道應(yīng)盡量集結(jié)同特征的車組，這樣才能實現(xiàn)“一掛編組”，達(dá)到解體照顧編組的目的，所以任何時候都要使得股道混亂度最小。

編組站調(diào)車場股道活用是根據(jù)動態(tài)配流方案、車列順位編組內(nèi)容、階段開始調(diào)車場現(xiàn)車及車流動態(tài)變化，為每個到達(dá)車組選擇可行的集結(jié)股道，以提高階段計劃兌現(xiàn)率和降低調(diào)車作業(yè)成本(調(diào)車鉤數(shù)、調(diào)車行程、調(diào)車時間等)[12]。由于確報和線路信息的不完整，目標(biāo)函數(shù)可以由股道混亂度最小和集結(jié)股道優(yōu)先級最大等價描述。調(diào)車場股道活用決策變量解空間隨著之前車組的集結(jié)而動態(tài)產(chǎn)生，符合回溯算法特征。為了加快搜索速度使用啟發(fā)式信息生成等級股道群，優(yōu)先選擇高等級股道達(dá)到剪枝目的。

2 調(diào)車場股道活用整數(shù)規(guī)劃模型

2.1 常量

在編制調(diào)車場股道活用表之前可以通過列車編組計劃、動態(tài)配流方案、確報和現(xiàn)車等車站管理信息子系統(tǒng)(SMIS)獲得：階段時間內(nèi)到解車列溜放作業(yè)的起止時間和編組順序表，出發(fā)車列編組作業(yè)的起止時間、車流來源和編組順序表，貨物列車編組計劃，調(diào)車場股道的屬性和階段初始時刻各股道的存車狀態(tài)等已知信息，定義常量如下：

2.2 到達(dá)車列“開口”劃分車組及模型變量

到達(dá)車列并不是整列溜放，而是根據(jù)車輛的順位、去向(車種)劃分為車組。不同的劃分方法會產(chǎn)生不同的調(diào)車場股道存車狀態(tài)，最終會影響股道活用方案的優(yōu)劣。為了達(dá)到解體照顧編組目的，應(yīng)該盡量將編入同一出發(fā)車列的車輛劃分為一組，剩余車輛再按照列車編組計劃歸為一組，最后再按照去向(車種)劃分為一組。

(1)確定每個車輛的特征

(2)劃分車組

(3)模型變量

2.3 調(diào)車場車流動態(tài)變化

調(diào)車場車流動態(tài)變化是指調(diào)車場股道存車隨著到達(dá)車組的解體和出發(fā)車列的編組而增減。為了保障安全，目前大多數(shù)編組站還是采用雙推單溜或者單推單溜的解體方式，即使采用雙推雙溜模式也是分為兩個互不干擾的調(diào)車系統(tǒng)，因此，各車組溜放作業(yè)不會重疊，故車組對調(diào)車場股道車流變化的影響是確定的。編尾可以同時編組幾列出發(fā)車列，但是由于車輛在調(diào)車場股道中的位置已經(jīng)確定，因此編組作業(yè)對股道狀態(tài)變化的影響也是確定的。

(1)調(diào)車場車流初始狀態(tài)

調(diào)車場初始狀態(tài)并不是階段開始時刻調(diào)車場的現(xiàn)車狀態(tài)，而是編組完畢時刻不晚于第一個到達(dá)車組溜放開始、車流來源都是編組場現(xiàn)車的出發(fā)車列編組完畢并轉(zhuǎn)線而導(dǎo)致調(diào)車場車流減少的狀態(tài)。

?k=1，…，lh，?j=1，…，n

( 1 )

式( 1 )中集合減“-”表示在相應(yīng)股道的車輛集中剔除滿足條件的車輛；“←”表示用剔除之后的車輛集替換之前的車輛集。

(2)調(diào)車場車流增加狀態(tài)

?i=1，…，m

( 2 )

(3)調(diào)車場車流減少狀態(tài)

?j=1，…，n

( 3 )

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

調(diào)車場股道活用的目的是使得階段計劃密切聯(lián)系實際調(diào)車作業(yè)，提高階段計劃的兌現(xiàn)率，加快調(diào)車作業(yè)效率。要想使得調(diào)車作業(yè)效率最高，應(yīng)該盡量使得同種特征的車組在一條股道上集結(jié)。

( 4 )

式( 4 )表示任何時刻調(diào)車場股道的混亂度最小。

要想使得調(diào)車作業(yè)效率最高，除了要盡量滿足露頭原則，還要考慮實際作業(yè)中調(diào)機的分工、均衡牽出線負(fù)擔(dān)、減少越區(qū)作業(yè)和交叉干擾等。所以每個車組應(yīng)該優(yōu)先選擇最大化滿足上述原則的股道，即優(yōu)先選擇高等級股道群中的股道。

( 5 )

2.5 約束條件

任何時刻車組集結(jié)都應(yīng)該滿足股道容量限制。

(1)調(diào)車場股道換長限制

( 6 )

(2)調(diào)車場股道重量限制

( 7 )

3 啟發(fā)式回溯算法

為了提高基本回溯算法(Backtracking Algorithms，BT)[13]的求解效率，本文使用變量動態(tài)排序啟發(fā)式(Variable Ordering Heuristics，VarOH)[14，15]算法對未實例化變量進行排序，為分支選擇提供決策支持，使得較早檢測出沖突。還可以引入變量取值動態(tài)排序啟發(fā)式(Value Ordering Heuristics，ValOH)[9，10]對論域中的變量進行優(yōu)先級排序，加快收斂速度。由于模型中變量順序按照車組溜放時間和順位唯一確定，所以采用ValOH技術(shù)，對每個車組可行股道集進行優(yōu)先級排序，用優(yōu)先級最高的股道實例化變量。

3.1 變量取值動態(tài)排序啟發(fā)式

3.2 二次分解車組

3.3 啟發(fā)式回溯算法

3.4 算法時間復(fù)雜度分析

4 算例分析

4.1 算例求解

假設(shè)2013年8月15日某編組站調(diào)車場12:00～15:00階段內(nèi)其他股道被固定使用，各活用股道的屬性及階段開始時刻的存車情況見表1，12:00～15:00之間的計劃到達(dá)和出發(fā)車列數(shù)據(jù)見表2和表3，貨物列車編組計劃見表4。由于到發(fā)車列的編組順序表和調(diào)車場車輛信息量比較大，文中不作詳列，只給出車列或者車組的順位編組內(nèi)容，到達(dá)車列順位編組中最左邊車輛最靠近駝峰，調(diào)車場股道順位編組中最右邊車輛最靠近駝峰。

表1 調(diào)車場股道數(shù)據(jù)

表2 階段內(nèi)計劃到達(dá)列車數(shù)據(jù)

表3 階段內(nèi)計劃出發(fā)列車數(shù)據(jù)

表4 階段內(nèi)貨物列車編組計劃數(shù)據(jù)

本模型及算法在Inter Core i3-2310M 2.1 GHz & DRAM 2G & Windows XP& JDK1.6環(huán)境下的PC機上運行。由于本算例中所有車組都有可行股道，所以算法等同于貪心算法，但是由于在可行股道啟發(fā)式排序算法中充分考慮了當(dāng)前車組的集結(jié)對后續(xù)車組集結(jié)的影響等，所以結(jié)果接近于全局最優(yōu)解。如圖1所示為啟發(fā)式回溯算法求解過程，總的求解時間為5.4 s，調(diào)車場股道混亂度之和最小為675，車組集結(jié)股道優(yōu)先級之和最大為204，最后得到車組劃分和調(diào)車場股道活用方案見表5。

圖1 啟發(fā)式回溯算法求解過程

4.2 結(jié)果分析

從表5可知，編入出發(fā)車列的車組基本上選擇滿足露頭原則的股道，最大限度地實現(xiàn)了“一掛編組”，達(dá)到了解體照顧編組要求。其他特征的車組當(dāng)不存在露頭股道時，避免選擇空閑或者露頭特征為某出發(fā)列車的股道，確保高等級車組按照露頭原則選擇集結(jié)股道。譬如第8個車組溜放前各股道中沒有去往保定方向的車組，最后決策此車組借用露頭特征為豐臺的BZ08，只有這樣第9個車組才能按照露頭原則集結(jié)。

表5 到達(dá)車組股道集結(jié)方案即股道活用方案

如果沒有空閑且露頭的股道時，車組借用一條混亂度最大且剩余容量最小的股道集結(jié)。譬如第5個車組借用BZ08后，后續(xù)的第8、13等車組都集結(jié)于此股道。降低了其他重要股道的混亂度，達(dá)到了當(dāng)前解體照顧后續(xù)解體的目的。

4.3 與基本回溯算法比較

以式( 4 )為目標(biāo)函數(shù)設(shè)計基本回溯算法，從圖2可得當(dāng)求解時間達(dá)到20 min時股道混亂度之和最少為740，所以基本回溯算法效率和質(zhì)量遠(yuǎn)低于啟發(fā)式回溯算法。

圖2 基本回溯算法求解過程

5 結(jié)論

為了提高解編調(diào)車作業(yè)效率和階段計劃的兌現(xiàn)率，本文在動態(tài)配流的基礎(chǔ)上，綜合考慮了調(diào)車場存車隨著解編作業(yè)動態(tài)變化、調(diào)車場股道的容量和解編作業(yè)時序限制等，建立編組站調(diào)車場股道活用整數(shù)規(guī)劃模型。并結(jié)合現(xiàn)場實際，以同去向車流盡量集結(jié)于一條股道、其他車流集結(jié)盡量不影響出發(fā)列車源車流的集結(jié)、減少越區(qū)作業(yè)和交叉干擾等為原則，建立變量取值動態(tài)排序的啟發(fā)式回溯算法，提高了算法求解效率。通過算例表明啟發(fā)式回溯算法比基本回溯算法效率要高；調(diào)車場股道活用方案比固定使用方案更能適應(yīng)車流不均衡、密集到達(dá)情況。在此基礎(chǔ)上對動態(tài)配流方案進行調(diào)整，譬如延長部分到發(fā)車列解編作業(yè)時間和調(diào)整車流使用方案等，實現(xiàn)階段計劃的綜合最優(yōu)化。

參考文獻(xiàn)：

[1]孫玉明,李紅漩.編制編組站調(diào)車場線路固定使用方案的探討[J].鐵道運輸與經(jīng)濟,2003,25(12):20-21.

SUN Yuming,LI Hongxuan.Discussion on Making Regular Utilization Plan of Shunting Yard Tracks in Marshalling Station[J].Railway Transpotr and Economy,2003,25(12):20-21.

[2]任勇.駝峰調(diào)車場線路固定使用方案的研究[J].太原科技,2003(5):24-26.

REN Yong.Research on the Scheme of Fixed Line Application at Hum PShunting Yard[J].Taiyuan Sci-Tech,2003(5):24-26.

[3]陳伯羽.鐵路調(diào)車場線路固定使用方案優(yōu)選方法研究[J].鐵道科學(xué)與工程學(xué)報,2006,3(6):80-82.

CHEN Boyu.Studying of Optimization of Fixed Usage Plan for Railway Marshalling Yard Tracks[J].Journal of Railway Science and Engineering,2006,3(6):80-82.

[4]黎浩東.鐵路編組站魯棒階段計劃編制及調(diào)整研究[D].北京:北京交通大學(xué),2012.

[5]王琦.不確定環(huán)境下編組站階段計劃優(yōu)化研究[D].北京:北京交通大學(xué),2010.

[6]王明慧,趙強.編組站智能調(diào)度系統(tǒng)階段計劃優(yōu)化模型及算法研究[J].鐵道學(xué)報,2005,27(6):1-9.

WANG Minghui,ZHAO Qiang.Optimal Model and Algorithm of Stage Plan of Intelligent Dispatching System for Marshalling Stations[J].Journal of the China Railway Society,2005,27(6):1-9.

[7]王世東,鄭力,張智海,等.編組站階段計劃自動編制的數(shù)學(xué)模型及算法[J].中國鐵道科學(xué),2008,29(2):120-125.

WANG Shidong,ZHENG Li,ZHANG Zhihai,et al.Mathematical Model and Algorithm for Automatically Programming the Stage Plan of Marshalling Station[J].Chinese Railway Science,2008,29(2):120-125.

[8]薛峰.編組站調(diào)度系統(tǒng)配流協(xié)同優(yōu)化理論與方法研究[D].成都:西南交通大學(xué),2009:91-105.

[9]HOOKER J N.Optimization and Constraint Programming[J].Informs Journal on Computing,2002,14(4):295-321.

[10]ROSSI F,et al.Handbook of Constraint Programming[M].Pisa:Elsevier,2006:103-109.

[11]劉其斌,馬桂貞.鐵路車站及樞紐[M].北京:中國鐵道出版社,1999.

[12]胡思繼.鐵路行車組織[M].2版.北京:中國鐵道出版社,2009:21-22.

[13]GOLOMB S W,BAUMERT L D.Backtrack Programming[J]. Journal of the ACM(JACM),1965,12(4):516-524.

[14]BACCHUS F,RUN P V.Dynamic Variable Ordering in CSPs[C]//Principles and Practice of Constraint Programming-CP′95.Springer Berlin Heidelberg,1995:258-275.

[15]HUANG J,DARWICHE A.A Structure-based Variable Ordering Heuristic for SAT[C]//IJCAI-03.Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence.United States:International Joint Conferences on Artificial Intelligence,2003:1 167-1 172.

[16]呂國英,任瑞整,錢宇華.算法設(shè)計與分析[M].北京:清華大學(xué)出版社,2006:211-226.

[17]趙端陽,左伍衡.算法分析與設(shè)計[M].北京:清華大學(xué)出版社,2012:207-247.