基于啟發式回溯算法的鐵路編組站調車場股道活用研究

馬 亮，張曉霞，郭 進

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

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

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

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

1 調車場股道活用問題描述及求解思路

調車場股道按照用途分為如下幾類[11]：

(1)供列車編組計劃規定的到站或去向的車輛解體、集結、編組用的線路，包括直達、直通、區段、摘掛以及小運轉列車集結、解編用的線路和編發線；

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

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

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

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

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

調車場存車狀態的變化不僅和車輛的方向(車種)有關，還與車輛在車列中的順位有直接關系，所以在為到解車列“開口”劃分車組時應以車列的順位編組內容為依據。

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

在制定調車場股道活用方案時，應該盡量使得同特征的到達車組在一條股道上集結。而且低等級特征車組盡量不要影響高等級特征車組的集結。

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

在為車組選擇集結股道時應優先考慮露頭原則，其次再選擇低級別的股道，這樣既能降低股道的混用率，也能減少出發車列的編組調車鉤數。

定義5由能夠容納某到達車組的活用股道構成的集合稱為此車組的可行活用股道集。根據可行活用股道集中各股道的存車狀態及到達車組特征按照股道活用規則劃分為若干等級股道群。

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

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

每條調車場股道應盡量集結同特征的車組，這樣才能實現“一掛編組”，達到解體照顧編組的目的，所以任何時候都要使得股道混亂度最小。

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

2 調車場股道活用整數規劃模型

2.1 常量

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

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

到達車列并不是整列溜放，而是根據車輛的順位、去向(車種)劃分為車組。不同的劃分方法會產生不同的調車場股道存車狀態，最終會影響股道活用方案的優劣。為了達到解體照顧編組目的，應該盡量將編入同一出發車列的車輛劃分為一組，剩余車輛再按照列車編組計劃歸為一組，最后再按照去向(車種)劃分為一組。

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

(2)劃分車組

(3)模型變量

2.3 調車場車流動態變化

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

(1)調車場車流初始狀態

調車場初始狀態并不是階段開始時刻調車場的現車狀態，而是編組完畢時刻不晚于第一個到達車組溜放開始、車流來源都是編組場現車的出發車列編組完畢并轉線而導致調車場車流減少的狀態。

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

( 1 )

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

(2)調車場車流增加狀態

?i=1，…，m

( 2 )

(3)調車場車流減少狀態

?j=1，…，n

( 3 )

2.4 目標函數

調車場股道活用的目的是使得階段計劃密切聯系實際調車作業，提高階段計劃的兌現率，加快調車作業效率。要想使得調車作業效率最高，應該盡量使得同種特征的車組在一條股道上集結。

( 4 )

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

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

( 5 )

2.5 約束條件

任何時刻車組集結都應該滿足股道容量限制。

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

( 6 )

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

( 7 )

3 啟發式回溯算法

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

3.1 變量取值動態排序啟發式

3.2 二次分解車組

3.3 啟發式回溯算法

3.4 算法時間復雜度分析

4 算例分析

4.1 算例求解

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

表1 調車場股道數據

表2 階段內計劃到達列車數據

表3 階段內計劃出發列車數據

表4 階段內貨物列車編組計劃數據

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

圖1 啟發式回溯算法求解過程

4.2 結果分析

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

表5 到達車組股道集結方案即股道活用方案

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

4.3 與基本回溯算法比較

以式( 4 )為目標函數設計基本回溯算法，從圖2可得當求解時間達到20 min時股道混亂度之和最少為740，所以基本回溯算法效率和質量遠低于啟發式回溯算法。

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

5 結論

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

參考文獻：

[1]孫玉明,李紅漩.編制編組站調車場線路固定使用方案的探討[J].鐵道運輸與經濟,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]任勇.駝峰調車場線路固定使用方案的研究[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]陳伯羽.鐵路調車場線路固定使用方案優選方法研究[J].鐵道科學與工程學報,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]黎浩東.鐵路編組站魯棒階段計劃編制及調整研究[D].北京:北京交通大學,2012.

[5]王琦.不確定環境下編組站階段計劃優化研究[D].北京:北京交通大學,2010.

[6]王明慧,趙強.編組站智能調度系統階段計劃優化模型及算法研究[J].鐵道學報,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]王世東,鄭力,張智海,等.編組站階段計劃自動編制的數學模型及算法[J].中國鐵道科學,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]薛峰.編組站調度系統配流協同優化理論與方法研究[D].成都:西南交通大學,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]呂國英,任瑞整,錢宇華.算法設計與分析[M].北京:清華大學出版社,2006:211-226.

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