羅耀云

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

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

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

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

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

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

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

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

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

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

2.1 進(jìn)路DFS算法

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

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

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

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

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

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

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

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

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

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

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

3 驗(yàn)證結(jié)果

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

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

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

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

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

圖6 變更進(jìn)路上位機(jī)運(yùn)行顯示界面截圖

圖5 不同高度上位機(jī)運(yùn)行顯示界面截圖

3.2 現(xiàn)場(chǎng)實(shí)測(cè)驗(yàn)證

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

表3 軟件運(yùn)算耗時(shí)統(tǒng)計(jì)表

4 結(jié)束語

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