鐵路車站聯(lián)鎖軟件進路搜索算法優(yōu)化

羅耀云

（蘭州鐵道設(shè)計院有限公司，甘肅蘭州 730030）

目前，我國新建及改造車站信號控制系統(tǒng)均采用計算機聯(lián)鎖系統(tǒng)，其可靠運行不僅依賴于硬件系統(tǒng)，更依賴于聯(lián)鎖軟件，進路控制是聯(lián)鎖軟件的核心功能。進路控制包括進路建立和進路解鎖兩大任務(wù)。進路建立可分為進路搜索、道岔轉(zhuǎn)換、選排一致性檢查、聯(lián)鎖條件檢查、進路鎖閉、信號開放、信號保持等階段。進路搜索是進路控制的基礎(chǔ)和關(guān)鍵環(huán)節(jié)，其準(zhǔn)確高效性將決定整個聯(lián)鎖軟件的安全性和執(zhí)行效率。如何準(zhǔn)確高效地完成進路搜索取決于聯(lián)鎖軟件所采用的進路搜索算法，而進路搜索算法的實現(xiàn)又依賴于所采用的數(shù)據(jù)結(jié)構(gòu)。目前主要采用基于總進路表和站場型兩種數(shù)據(jù)結(jié)構(gòu)建立進路搜索算法[1-3]?；诳傔M路表的進路搜索適用于規(guī)模較小、進路數(shù)量較少、長期不進行改建或擴建的車站?；谡緢鲂蛿?shù)據(jù)結(jié)構(gòu)的進路搜索則不受上述限制，其搜索算法有DFS 算法和廣度優(yōu)先搜索（Breadth First Search，BFS）算法。文獻[4]及文獻[5]提出的基于DFS 算法圖匹配在搜索增廣路時不會出現(xiàn)“花”的情況；文獻[6]、文獻[7]、文獻[8]采用DFS 加約束條件的站場遍歷算法；文獻[9]采用有向無環(huán)圖與二叉樹結(jié)合的進路搜索算法，系統(tǒng)功能不完善。這些算法均存在回溯搜索的問題。針對此問題，提出一種DFS 高度無往返優(yōu)化算法，提高進路搜索效率。

1 聯(lián)鎖軟件數(shù)據(jù)結(jié)構(gòu)

鐵路車站計算機聯(lián)鎖數(shù)據(jù)是指在聯(lián)鎖計算機中參與運算的所有數(shù)據(jù)，它們在計算機中的存儲和組織方式稱為數(shù)據(jù)結(jié)構(gòu)。目前，常用總進路表數(shù)據(jù)結(jié)構(gòu)和站場型數(shù)據(jù)結(jié)構(gòu)。進路表是把進路相關(guān)的各項數(shù)據(jù)納入到一個數(shù)據(jù)表中構(gòu)成的。將車站中包括迂回進路在內(nèi)的所有進路匯總在一起，即為總進路表。對于進路數(shù)多的較大規(guī)模車站，總進路表是相當(dāng)龐大的，尤其當(dāng)車站改建或擴建時需對總進路表進行大量修改，非常繁瑣，不利于站場的改建與擴建。站場型數(shù)據(jù)結(jié)構(gòu)就是根據(jù)站場信號布置平面圖，將各信號設(shè)備所對應(yīng)的數(shù)據(jù)模塊按照其在信號設(shè)備平面布置圖中的位置鏈接而構(gòu)成的[10-12]。數(shù)據(jù)結(jié)構(gòu)模塊原理如圖1 所示。此數(shù)據(jù)結(jié)構(gòu)采用雙向鏈表形式，即由前一模塊能搜索到與其邏輯相鄰的后一模塊，同樣從后一模塊也能搜索到前一模塊，每個數(shù)據(jù)模塊至少需要兩個指針域來存放與其邏輯上相鄰模塊的首址。結(jié)構(gòu)原理如圖1（a）所示，地址原理如圖1（b）所示，鏈接原理如圖1（c）所示。

圖1 數(shù)據(jù)結(jié)構(gòu)模塊原理圖

假設(shè)有3 個模塊a、b、c，其數(shù)據(jù)域為df，指針域為pf。不管它們在存儲器中的物理位置是否放在一起，只要將模塊b 的首址放在模塊a 的pf 中，將模塊c和模塊a 的首址放在模塊b 的兩個pf 中，模塊b 的首址放在模塊c 的pf 中，就能實現(xiàn)由模塊a 到模塊b、由模塊b 到模塊c 和由模塊c 到模塊b、由模塊b 到模塊a 的雙向搜索。若用圓圈表示數(shù)據(jù)模塊，圖1（c）就是圖1（b）的簡化圖鏈接原理圖。若模塊為終端模塊，則其中的一個指針域置為Φ（空）即可。

選取車站信號設(shè)備平面布置圖如圖2所示。按照圖1 所述數(shù)據(jù)模塊的構(gòu)成方法，將圖2 按照圖1（a）所示數(shù)據(jù)結(jié)構(gòu)原理圖，構(gòu)成各自的數(shù)據(jù)模塊。按圖1（c）所示模塊鏈接原理得到站場型數(shù)據(jù)結(jié)構(gòu)圖，如圖3所示。

圖2 車站信號設(shè)備平面圖

圖3 站場型數(shù)據(jù)結(jié)構(gòu)圖

2 基于DFS的優(yōu)化算法

2.1 進路DFS算法

鐵路車站計算機聯(lián)鎖系統(tǒng)進路搜索算法的核心是數(shù)據(jù)結(jié)構(gòu)，站場型數(shù)據(jù)結(jié)構(gòu)是可供選擇的基本數(shù)據(jù)結(jié)構(gòu)，將信號設(shè)備作為信號點并根據(jù)在平面圖中的位置進行連接，對站場中每個設(shè)備節(jié)點按其在平面布置圖中的實際縱向位置定義高度，按其實際橫向位置定義編號，并將各設(shè)備的高度信息存儲在各自節(jié)點的數(shù)據(jù)域中[13-15]。站場中處于同一水平線上的設(shè)備具有相同的數(shù)據(jù)節(jié)點高度，如圖3 所示，站場型數(shù)據(jù)結(jié)構(gòu)圖中的各節(jié)點縱向高度分布表如表1所示。

表1 節(jié)點高度分布表

建立站場型數(shù)據(jù)結(jié)構(gòu)后，站場進路的搜索問題就變成了圖中節(jié)點的搜索過程。DFS 算法是從始端節(jié)點開始逐層擴散搜索，當(dāng)這一層的節(jié)點未全部查詢前不會進行到下一層節(jié)點的搜索。DFS 類似于樹的先序遍歷的過程，搜索規(guī)則是：從始端模塊開始按照鏈接向前搜索，當(dāng)遇到分支模塊（對向道岔）時，一般情況下沿降低高度差方向搜索，直至搜索到目標(biāo)模塊或終端模塊，若該終端模塊是目標(biāo)模塊，則進路搜索完畢，否則返回到上一個分支模塊處沿另一方向搜索，直到搜索到目標(biāo)模塊為止[16]。這種搜索算法對選擇的某一條路徑會一直搜索到底，當(dāng)找不到目標(biāo)節(jié)點時返回到分支節(jié)點再選擇另一條路徑搜索到底，搜索方向不確定，如果目標(biāo)節(jié)點相對始端節(jié)點在較深層，則搜索量將相當(dāng)巨大。勢必會造成大量的回溯。

2.2 基于DFS高度無往返優(yōu)化算法

基于站場型數(shù)據(jù)結(jié)構(gòu)DFS 算法的基本規(guī)則是：

1）從始端模塊開始依次向前搜索，遇到分支模塊即對向道岔時，需沿導(dǎo)向標(biāo)方向優(yōu)先搜索。

2）無導(dǎo)向標(biāo)則比較當(dāng)前數(shù)據(jù)模塊的高度是否與終點目標(biāo)模塊的高度一致。若當(dāng)前節(jié)點與終點目標(biāo)模塊高度一致，沿縱方向即直股向前搜索；若當(dāng)前節(jié)點與終點的目標(biāo)模塊高度不一致，則朝著能縮小當(dāng)前模塊與目標(biāo)模塊高度差的后繼模塊向前搜索，直到找到目標(biāo)模塊。

3）最終計算機聯(lián)鎖軟件從進路搜索遇到的節(jié)點站場數(shù)據(jù)結(jié)構(gòu)中提取聯(lián)鎖關(guān)系所需的信息，并生成一條進路表，就完成了進路搜索任務(wù)。

進路搜索的關(guān)鍵是對基本進路和諸如平行進路、迂回進路等變更進路的處理，要求選基本進路時不能選出變更進路，選變更進路時不能選出基本進路。為達到此要求，結(jié)合舉例站場實際情況，需對進路搜索算法增加約束條件：

1）由于軟件搜索時經(jīng)過對向道岔存在兩個方向，對于站場型數(shù)據(jù)結(jié)構(gòu)，要求軟件進路搜索時僅沿著一個方向搜索，當(dāng)程序沿著列車發(fā)車方向運算時遇到的對向道岔較少，故約定所有進路搜索時優(yōu)先沿列車發(fā)車方向搜索。

2）當(dāng)設(shè)備節(jié)點高度不一致或存在辦理變更進路時，采用DFS 高度無往返優(yōu)化算法，為了選出滿足要求的進路，則根據(jù)需要增設(shè)直向股道優(yōu)先搜索的進路導(dǎo)向標(biāo)志模塊，即遇到對向道岔模塊時，需沿導(dǎo)向標(biāo)志模塊指向方向優(yōu)先搜索。

3 驗證結(jié)果

3.1 標(biāo)準(zhǔn)站仿真驗證

在圖3 的站場型數(shù)據(jù)結(jié)構(gòu)圖中，整個站場圖下行咽喉被轉(zhuǎn)化為43 個數(shù)據(jù)節(jié)點，包括6 個人為設(shè)定的虛擬節(jié)點與37 個站場實際設(shè)備節(jié)點。通過利用軟件編程建模圖2 所示站場圖，仿真上位機顯示界面參照國鐵集團發(fā)布的相關(guān)技術(shù)規(guī)范進行設(shè)計。進路搜索聯(lián)鎖軟件設(shè)計流程圖如圖4 所示。

圖4 進路搜索聯(lián)鎖軟件設(shè)計流程圖

當(dāng)基于站場型數(shù)據(jù)的節(jié)點高度相同時，按DFS優(yōu)化算法搜索進路不存在回溯搜索的問題，無需對比驗證[17-19]。選取不同高度站場型數(shù)據(jù)節(jié)點（D11 至D13）開始驗證搜索進路，進路鎖閉信號開放后在上位機界面顯示如圖5 白光帶所示，此時表示進路選排結(jié)束進路鎖閉；選取變更進路（X 至S3 以D11 為變更點）節(jié)點開始驗證搜索進路，進路鎖閉信號開放后在上位機界面顯示如圖6 白光帶所示。應(yīng)用這兩種算法，分別對舉例站場中的典型進路進行搜索，并監(jiān)測聯(lián)鎖機運算時間，查看軟件進路搜索節(jié)點數(shù)據(jù)如表2 所示。從表中可以得出優(yōu)化后，進路搜索節(jié)點數(shù)據(jù)減少，克服了回溯搜索不足的問題。

表2 進路搜索節(jié)點數(shù)據(jù)表

圖6 變更進路上位機運行顯示界面截圖

圖5 不同高度上位機運行顯示界面截圖

3.2 現(xiàn)場實測驗證

包神鐵路巴圖塔車站（含16股道、104組道岔）屬較大規(guī)模車站，利用DFS高度無往返優(yōu)化算法進行編程，選取不同高度及變更進路辦理進路并利用秒表監(jiān)測軟件運算耗時統(tǒng)計如表3 所示。由表中可以計算得，優(yōu)化后進路搜索平均耗時比原有提高了5.55%。

表3 軟件運算耗時統(tǒng)計表

4 結(jié)束語

利用站場型數(shù)據(jù)結(jié)構(gòu)，采用DFS 高度無往返優(yōu)化算法軟件編程進行進路搜索，能夠?qū)κ冀K端在不同高度及變更進路時正確完成進路搜索，優(yōu)化后進路搜索節(jié)點數(shù)據(jù)減少，未出現(xiàn)回溯重復(fù)搜索節(jié)點的問題。通過現(xiàn)場實測，驗證克服了回溯搜索導(dǎo)致的搜索量大、聯(lián)鎖軟件運算耗時增加的缺點，有效降低了大型復(fù)雜站場聯(lián)鎖軟件運行的耗時。