鐵路編組站調車場股道運用回溯算法及其改進型的分析與比較

蔣繼磊

摘 要： 通過改進型回溯算法的使用，結合鐵路編組站調車場股道車流運行實際情況，基于動態配流的方式，建立變量取值動態排序的改進型回溯算法。研究結果證實，在鐵路編組站調車場股道優化運用中采用改進型回溯算法可以提高算法的求解效率，并能夠使同去向車流盡量集結于一條股道，降低鐵路編組站內調車場股道其他車流集結對出發列車車流集結的影響。在鐵路編組站調車場股道中，應用改進型回溯算法能夠有效解決既有鐵路編組站調車場股道車流不均衡、車流密集到達的情況，提升算法求解效率，避免在鐵路編組站調車場股道中發生越區干擾與交叉干擾的情況，從而發揮積極的應用價值。

關鍵詞： 鐵路編組站； 改進型回溯算法； 股道運用； 動態配流

中圖分類號： TN081?34 文獻標識碼： A 文章編號： 1004?373X（2017）07?0124?03

Analysis and comparison of backtracking algorithm used in switchyard track in

railway marshalling station with its improved one

JIANG Jilei

（Signal & Communication Research Institute， China Academy of Railway Sciences， Beijing 100081， China）

Abstract： The improved backtracking algorithm of the variable value dynamic sorting was established in combination with the practical traffic operation situation of the switchyard track in the railway marshalling station and dynamic traffic assignment method. The research results confirm that the improved backtracking algorithm used in the switchyard track optimization of the railway marshalling station can improve the solving efficiency of the algorithm， assemble the traffic of the same direction into a track， and reduce the effect of the traffic assembling of the switchyard track in the railway marshalling station on that of the departing trains. The improved backtracking algorithm can solve the situations of the unbalance traffic and dense traffic arrival of the switchyard track in railway marshalling station， improve the solving efficiency of the algorithm， and avoid the overshooting?area interference and cross?area interference existing in the switchyard track in the railway marshalling station， which plays a positive application value.

Keywords： railway marshalling station； improved backtracking algorithm； track utilization； dynamic traffic assignment

0 引 言

在鐵路編組站的調車場股道管理方面，應用基本回溯算法不能滿足處理調車場股道車流不均衡、密集到達的需求，降低算法計算效率，使鐵路編組站調車場容易產生車流集結、交叉干擾的問題，影響鐵路編組站調車場股道車流的正常運行[1?3]。在鐵路編組站中，做好調車場股道管理工作，不僅是編組站辦理改編作業的關鍵，也對通過車站的車流發揮“蓄洪”作用，提高解編調車作業效率，靈活運用調車場股道，在動態配流基礎上活用鐵路編組站中調車場股道，避免造成車站堵塞[4?6]。在實際研究中，能夠在為編組站車場股道實現動態配流的基礎上，還可綜合考慮鐵路編組站調車場的存車狀態變化，以及調車場股道容量及股道車輛解編作業時序限制，能夠設計“開口”算法，建立階段時間內的鐵路編組站調車場股道活用整數優化模型，實現車流隨解編作業變化。

1 鐵路編組站調車場股道車流變化情況

在既有鐵路編組站內，其調車場股道車流是動態變化的，主要表現為調車場股道存車會隨著到達車組解體以及出發車列編組而有所增減。因此在實際調車場股道管理中，為能夠保障調度安全，可以采用雙推單溜以及單推單溜的車輛解體方式，各車組調車系統溜放作業不會重疊，互不干擾。然而，由于在鐵路編組站調車場股道中已經事先確定好車輛在調車場股道內的位置，而編尾可以同時編組幾列出發車列，故此在編組站內也需要考慮編組作業對股道狀態變化的影響。在傳統的調車場股道管理中，應用的算法是以出發車流來源為調車場車流變化的依據，協同優化配流和調車場股道，將不同方向的車流盡量流入不同的股道，從而增加解體鉤數與編組鉤數；但是并沒有充分考慮在車列中解編作業以及車輛的順位還需完善算法。對此，亟待優化設計鐵路編組站調車場股道的管理辦法，運用改進型回溯算法計算分析調車場股道車流運行情況，從而在優化鐵路編組站調車場股道中的車流運行方案中發揮積極影響。

2 設計基于鐵路編組站調車場股道運用的改進型

回溯算法

2.1 算法原則

隨著解編作業動態變化，綜合考慮鐵路編組站調車場車流變化，可以應用改進型回溯算法設計調車場股道活用整數優化模型，并在采取此算法時確保每次選擇調車場內優先級最高的股道[7]。具體來說，也就是當調車場內沒有股道可以容納車組時回溯，在最終無解時進行車組二次分解，直到確保此鐵路編組站內所有的車組都可以有集結股道并達到最優。

2.2 設計變量取值動態改進型排序

對于車組[SZDik，]如果在調車場股道當前時刻[t∈TE]滿足調車場股道換長限制約束（式1），也滿足調車場股道重量限制（式2），則可行活用股道集表示為[Yikt，]為能夠進一步使任何時刻鐵路編組站調車場股道混亂度最小（式3），及任何時刻車組選擇股道優先級最大（式4）的需求，可以在實際中，根據現場成熟經驗對車組[SZDik]集結股道變量[htDik]取值進行改進型排序。

調車場股道重量限制約束：

[cqeDik≤rqeYht Dikt，?k=1，2，…，hZi，?i=1，2，…，h，?t∈TE] （1）

式中：[cqeDik]表示鐵路編組站某一時刻的股道；[rqeYht]表示在鐵路編組站調車場股道的剩余重量。

調車場股道換長限制：

[cVeDik≤rVeYmt Dikt，?k=1，2，…，hZi，?i=1，2，…，h，?t∈TE] （2）

式中：[cVeDik]表示某一時刻的股道；[rVeYmt]表示調車場股道剩余換長。

任何時刻鐵路編組站調車場股道混亂度最小：

[maxr1=t∈TEn=1lTZYnt] （3）

任何時刻車組選擇股道優先級最大：

[maxr2=i=1mj=1mZipriDjk] （4）

2.3 運用基本回溯算法分解調車場股道車組

在鐵路編組站調車場股道管理運用中采用基本回溯算法，若沒有股道能夠容納某一車組，則需要回溯。在動態改進型排序計算無解時，可以對這一車組進行二次分解，并記錄之前車組的調度決策，具體方法如下：

（1） 獲取調車場股道內等級最高的股道集。

（2） 在股道集中選擇出剩余容量最大的股道，并將其組成新的股道集；若新的股道集大于1，則在鐵路編組站調車場內可以選取隨機股道運用，繼續轉入下一步。

（3） 可以在調車場內根據車輛順位，依次累加鐵路編組站內車輛的換長與軸重。

2.4 改進型回溯算法

（1） 在鐵路編組站調車場股道管理運用中，針對所有到達車列進行基于“開口”劃分車組，得到車列集合，從而可以獲取觸發后的調車場車流初始狀態。

（2） 如果在調車場股道車輛調度達到求解時間上限，則返回調車場股道運用方案，計算出各車組集結股道及目標函數的最優值。

（3） 依次選擇到達車列的某個車組的特征，通過回溯觸發獲取鐵路編組站調車場股道車流減少的狀態。

（4） 可以對集結股道變量進行實例化，觸發獲取鐵路編組站內調車場股道車流的增加狀態。

（5） 記錄前面車組股道集結方案，并依次進行回溯計算，若無解，可以按照改進型算法對車組進行二次分解，再按照部分解繼續進行搜索計算。

3 算法應用實例及其比較分析

3.1 實際案例

在某路網型編組站調車場[n]小時股道運用期間，基于鐵路編組站內車列以及車組順位編組的內容，在到達車列順位編組中，使得最左邊的車輛可以最靠近駝峰，而在調車場股道順位編組中，使得最右邊車輛最靠近駝峰。其實際的股道被固定使用，而對于其各活用股道的屬性，以及各階段開始時刻的存車情況見表1。

在此路網型編組站[n]小時調車場計劃到達和出發列車數據，見表2。

在此路網型編組站內[n]小時期間貨物列車編組計劃，如表3所示。

3.2 改進型回溯算法與基本回溯算法計算過程數據比較

在此路網型鐵路編組站調車場股道運用中，可以通過計算機程序求解，充分考慮當前調車場股道內所有車組集結后對后續車組的影響，計算分析所有車組可行股道的最優解。兩種類型回溯算法的求解過程，如表4所示。

通過對表4中的數據比較分析可得，改進型回溯算法的求解時間效率是基本回溯算法求解時間效率的100倍左右，并且在此情況下，改進型回溯算法調車場股道混亂度之和也比基本回溯算法調車場股道混亂度之和減少100左右。在既有鐵路編組站調車場股道管理中，可以運用改進型回溯算法計算分析調車場股道的車流運行情況，從而優化鐵路編組站調車場股道中的車輛運行方案，活用調車場股道，使其產生積極應用價值。

4 結 論

綜上所述，在我國目前的鐵路編組站調車場股道運用管理中，可以積極采用改進型回溯算法，使之有效應對既有鐵路編組站調車場股道車流不均衡、車流密集到達的情況，有效解決傳統回溯算法應用鐵路編組站調車場管理中的車流集結、交叉干擾的問題，提升改進型回溯算法的求解效率，避免發生越區干擾與交叉干擾的情況，提升編組站調車場股道的綜合運用效率。

參考文獻

[1] 馬亮，張曉霞，郭進，等.基于啟發式回溯算法的鐵路編組站調車場股道活用研究[J].鐵道學報，2016，38（8）：16?22.

[2] 馬亮，郭進，陳光偉，等.基于約束程序累積調度的編組站靜態配流模型研究[J].鐵道學報，2014，36（1）：8?15.

[3] 曾鳴.鐵路集裝箱中心站物流系統資源調配優化與仿真研究[D].成都：西南交通大學，2015.

[4] 馬亮，郭進，陳光偉，等.編組站靜態配流的約束傳播和啟發式回溯算法[J].西南交通大學學報，2014，49（6）：1116?1122.

[5] 邦佳.編組站階段計劃編制問題研究[D].北京：北京交通大學，2012.

[6] 劉引濤.基于回溯算法的計算機機箱線路板排列問題的分析研究[J].現代電子技術，2014，37（18）：84?85.

[7] 戴圣法，魏慶國，魏中海.基于回溯搜索算法的導聯選擇腦機接口研究[J].現代電子技術，2016，39（13）：10?14.