蔣繼磊

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

關(guān)鍵詞： 鐵路編組站； 改進型回溯算法； 股道運用； 動態(tài)配流

中圖分類號： TN081?34 文獻標(biāo)識碼： 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 引 言

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

1 鐵路編組站調(diào)車場股道車流變化情況

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

2 設(shè)計基于鐵路編組站調(diào)車場股道運用的改進型

回溯算法

2.1 算法原則

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

2.2 設(shè)計變量取值動態(tài)改進型排序

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

調(diào)車場股道重量限制約束：

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

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

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

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

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

任何時刻鐵路編組站調(diào)車場股道混亂度最?。?/p>

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

任何時刻車組選擇股道優(yōu)先級最大：

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

2.3 運用基本回溯算法分解調(diào)車場股道車組

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

（1） 獲取調(diào)車場股道內(nèi)等級最高的股道集。

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

（3） 可以在調(diào)車場內(nèi)根據(jù)車輛順位，依次累加鐵路編組站內(nèi)車輛的換長與軸重。

2.4 改進型回溯算法

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

（2） 如果在調(diào)車場股道車輛調(diào)度達到求解時間上限，則返回調(diào)車場股道運用方案，計算出各車組集結(jié)股道及目標(biāo)函數(shù)的最優(yōu)值。

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

（4） 可以對集結(jié)股道變量進行實例化，觸發(fā)獲取鐵路編組站內(nèi)調(diào)車場股道車流的增加狀態(tài)。

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

3 算法應(yīng)用實例及其比較分析

3.1 實際案例

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

在此路網(wǎng)型編組站[n]小時調(diào)車場計劃到達和出發(fā)列車數(shù)據(jù)，見表2。

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

3.2 改進型回溯算法與基本回溯算法計算過程數(shù)據(jù)比較

在此路網(wǎng)型鐵路編組站調(diào)車場股道運用中，可以通過計算機程序求解，充分考慮當(dāng)前調(diào)車場股道內(nèi)所有車組集結(jié)后對后續(xù)車組的影響，計算分析所有車組可行股道的最優(yōu)解。兩種類型回溯算法的求解過程，如表4所示。

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

4 結(jié) 論

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

參考文獻

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

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

[3] 曾鳴.鐵路集裝箱中心站物流系統(tǒng)資源調(diào)配優(yōu)化與仿真研究[D].成都：西南交通大學(xué)，2015.

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

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

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

[7] 戴圣法，魏慶國，魏中海.基于回溯搜索算法的導(dǎo)聯(lián)選擇腦機接口研究[J].現(xiàn)代電子技術(shù)，2016，39（13）：10?14.