王文波，馬學霞

（1.浙江眾合科技股份有限公司，杭州 310052；2.卡斯柯信號有限公司，上海 200071）

鐵路車站計算機聯(lián)鎖軟件進路搜索算法研究

王文波1，馬學霞2

（1.浙江眾合科技股份有限公司，杭州 310052；2.卡斯柯信號有限公司，上海 200071）

計算機聯(lián)鎖軟件的關鍵技術是聯(lián)鎖軟件數(shù)據(jù)結(jié)構(gòu)的選取和進路搜索算法的優(yōu)化。針對常用數(shù)據(jù)結(jié)構(gòu)對聯(lián)鎖軟件的制約和進路搜索算法對搜索效率的影響，本文基于站場型數(shù)據(jù)結(jié)構(gòu)，優(yōu)化了進路搜索算法，以站場舉例為對象，詳細論述了采用高度搜索算法搜索基本進路和變更進路的過程，該過程表明高度搜索算法克服了廣度和深度優(yōu)先算法的不足，搜索目標明確、搜索過程高效準確。

進路搜索算法；數(shù)據(jù)結(jié)構(gòu)；計算機聯(lián)鎖

鐵路車站聯(lián)鎖系統(tǒng)用于判斷站內(nèi)軌道電路的空閑與占用、轉(zhuǎn)換并鎖閉道岔、控制信號開放與關閉及控制進路的建立與解鎖。目前我國車站主要采用電氣集中聯(lián)鎖和計算機聯(lián)鎖。因計算機聯(lián)鎖具有高可靠性、高安全性、維護工作量小、占地面積小、便于和其他信號系統(tǒng)相連等優(yōu)點[1]，計算機聯(lián)鎖正處于大力發(fā)展并逐步代替電氣集中聯(lián)鎖的階段。

計算機聯(lián)鎖軟件采用模塊化方法設計，可分為人機會話層、聯(lián)鎖邏輯運算層和執(zhí)行表示層，層次結(jié)構(gòu)如圖1所示。人機會話層完成操作信息、表示信息以及維護與管理信息的處理；聯(lián)鎖運算層完成基本聯(lián)鎖運算、特殊聯(lián)鎖操作、自動檢測和故障診斷，實現(xiàn)與其它系統(tǒng)的聯(lián)鎖功能。執(zhí)行層完成控制命令的輸出和表示信息的輸入。聯(lián)鎖邏輯運算模塊是聯(lián)鎖運算層的核心，完成進路搜索、建立、鎖閉和解鎖。進路搜索的效率和準確性依賴于搜索算法，而搜索算法的選取取決于聯(lián)鎖軟件采用的數(shù)據(jù)結(jié)構(gòu)[2]。

圖1 軟件的層次結(jié)構(gòu)

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

聯(lián)鎖數(shù)據(jù)量是很大的，它們在計算機中的存儲和組織方式稱為數(shù)據(jù)結(jié)構(gòu)[3]。數(shù)據(jù)有靜態(tài)數(shù)據(jù)和動態(tài)數(shù)據(jù)之分，相應有靜態(tài)數(shù)據(jù)結(jié)構(gòu)和動態(tài)數(shù)據(jù)結(jié)構(gòu)。靜態(tài)數(shù)據(jù)結(jié)構(gòu)是程序編寫的基礎，精心選擇的數(shù)據(jù)結(jié)構(gòu)決定著進路搜索算法的選取，合理高效的進路搜索算法可以帶來更高的運行效率，影響到軟件復雜度等[4]。目前計算機聯(lián)鎖常用的數(shù)據(jù)結(jié)構(gòu)主要有：進路表型數(shù)據(jù)結(jié)構(gòu)、二叉樹型數(shù)據(jù)結(jié)構(gòu)和站場型數(shù)據(jù)結(jié)構(gòu)。

1.1 進路表型數(shù)據(jù)結(jié)構(gòu)

按照進路中包含的信號點數(shù)據(jù)屬性將數(shù)據(jù)放入一個數(shù)據(jù)表便構(gòu)成進路表數(shù)據(jù)結(jié)構(gòu)。將所有進路匯總在一個表中便形成總進路表數(shù)據(jù)結(jié)構(gòu)。總進路表簡單明了，易于學習，當站場股道、道岔不多、結(jié)構(gòu)簡單時，總進路表并不復雜，但當站場龐大，總進路就會劇增，尤其當站場改建或擴建時，總進路完全就需要重新編制，因此進路表數(shù)據(jù)結(jié)構(gòu)不適應于較大的車站和車站的改建[5]。

1.2 二叉樹型數(shù)據(jù)結(jié)構(gòu)

二叉樹采用多重鏈表結(jié)構(gòu)，是非線性數(shù)據(jù)結(jié)構(gòu)的一種。其節(jié)點由一個數(shù)據(jù)元素和左右兩個分支子樹構(gòu)成，形成鏈表結(jié)構(gòu)。站場中信號點間的連接關系又不完全具有二叉樹的特點，故二叉樹型數(shù)據(jù)結(jié)構(gòu)不能很好地應用于站場。

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

站場型數(shù)據(jù)結(jié)構(gòu)就是根據(jù)站場信號布置平面圖，把各信號點數(shù)據(jù)模塊按照其在信號平面布置圖中的位置鏈接構(gòu)成，其本質(zhì)是節(jié)點的鏈接表。具有以下優(yōu)點：

（1）在數(shù)據(jù)結(jié)構(gòu)中的任何地方增加或刪除節(jié)點，只需修改節(jié)點指針域中的地址，不影響節(jié)點的物理地址，方便站場改建或擴建時聯(lián)鎖數(shù)據(jù)的修改；

（2）節(jié)點的鏈接只是在邏輯上有序的，與節(jié)點在存儲器中的實際物理地址無關，這種數(shù)據(jù)結(jié)構(gòu)可以用計算機輔助設計自動生成；

（3）基于根據(jù)進路辦理命令的數(shù)據(jù)結(jié)構(gòu)生成的進路表存在于RAM中，進路表隨著進路辦理而建立，隨著進路解除而刪除，占用RAM空間小；同時該靜態(tài)數(shù)據(jù)庫占用ROM空間小，有利于檢測。

2 進路搜索算法研究

進路搜索算法是調(diào)度集中和計算機聯(lián)鎖系統(tǒng)軟件的重要部分，該軟件研究的重點內(nèi)容是如何準確高效搜索出符合操作意圖的進路，即通過始終端按鈕選出一條基本進路（當列車進路的同一個始端和同一個終端存在兩條或兩條以上進路時，一般把對平行作業(yè)影響小、走行距離短、經(jīng)過道岔少的進路定為基本進路，其余進路定為變更進路[6]）而非變更進路或迂回進路，若要選出變更進路，則需另加按鈕條件，指明變更點。

本文采用的站場平面布置圖如圖2所示，本站場下行接車口有兩個方向：東郊方向和北京方向，防護接車進路的信號機分別為XD和X，股道端有出站信號機SⅡ、SⅢ、S4和S5，咽喉區(qū)有調(diào)車D1至D17共9架信號機。數(shù)字代表道岔，如1/3號道岔。道岔區(qū)段軌道電路名稱在圖中不標注，如1/3號道岔區(qū)段默認名稱為1-3DG；無岔區(qū)段在圖中標注，如IAG，1/19WG?，F(xiàn)以該站場平面布置圖介紹進路搜索算法。

2.1 廣度優(yōu)先搜索策略

廣度優(yōu)先搜索策略基于樹的層次遍歷方法，搜索過程從始端節(jié)點出發(fā)，按照站場的層次結(jié)構(gòu)逐層搜索目標節(jié)點，當在該層搜索不到目標節(jié)點時轉(zhuǎn)向下層繼續(xù)搜索，直到搜索到目標節(jié)點為止，例如搜索D11至4G的調(diào)車進路，將會搜索到S5、SⅢ、D17、SⅡ后才能搜索到S4。這種搜索方法方向不確定，當目標節(jié)點在站場較深層時搜索量將會相當巨大，搜索過程中會有大量節(jié)點數(shù)據(jù)的入棧和出棧，造成搜索效率低下。

2.2 深度優(yōu)先搜索策略

深度優(yōu)先搜索和廣度優(yōu)先搜索策略相反，其類似于樹的先序遍歷的過程。深度優(yōu)先搜索算法會選擇一條路徑搜索到這條路徑的盡頭節(jié)點，當搜索不到目標節(jié)點時再逐層退回搜索，直到搜索到目標節(jié)點為止。這種搜索算法相對于廣度搜索方法搜索路徑較為明確，但這種算法會選擇一條路徑走到底，即不管通過這條路徑能否找到目標節(jié)點都要進行試探，因此，當目標節(jié)點在較淺層時也會造成找不到目標節(jié)點而需一步步回溯搜索的缺陷，不利于搜索效率的提高，不是一種理想的搜索算法。

2.3 高度搜索策略

本文采用基于站場形數(shù)據(jù)結(jié)構(gòu)的高度搜索算法。高度搜索策略的基本思想是：基于站場形數(shù)據(jù)結(jié)構(gòu)，對站場中每個設備節(jié)點按實際縱向位置定義高度，按其實際橫向位置定義編號，這樣在站場中處于同一線上的設備就有相同的高度[7]，然后根據(jù)始終端節(jié)點橫向編號和縱向高度確定搜索方向和路徑。圖2站場的各設備節(jié)點縱向高度分布如表1所示。

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

3 進路搜索過程實現(xiàn)

3.1 進路搜索規(guī)則

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

圖2所示站場的站場形數(shù)據(jù)結(jié)構(gòu)如圖3所示，其中，K表示設備節(jié)點的數(shù)據(jù)模塊，例如XD數(shù)據(jù)模塊表示為K(XD)。進路搜索時，首先根據(jù)進路操作命令找出進路的始端模塊和終端模塊，確定搜索方向，依據(jù)站場形數(shù)據(jù)結(jié)構(gòu)沿著進路搜索方向找出與進路相關的所有模塊。當遇到分支模塊(對向道岔)時，比較分支模塊與終端模塊的高度，若高度一致，沿直股搜索；若高度不一致，則沿彎股搜索。例如辦理SⅢ至D7的調(diào)車進路，確定從進路始端向終端搜索，始端模塊是K(SⅢ)，終端模塊是K(D7)。由始端模塊出發(fā)找到K(25DG)、K(25)模塊，因K(25)模塊為分支模塊，通過比較K(25)和K(D7)的高度，確定沿彎股搜索，依次找到K(23)、K(17)、K(17-23DG)、K(D13)、K(9)、K(9-15DG)和K(15)，K(15)也是分支模塊，因其與終端模塊K(D7)具有相同高度，故沿直股搜索找到K(D9)，最終找到終端模塊K(D7)。進路搜索程序從這些模塊中提取進路聯(lián)鎖程序所需的數(shù)據(jù)，并生成一個進路表，就完成了進路搜索任務。

3.2 基本進路搜索過程

當進路的始端模塊和終端模塊高度不一致時，此種進路搜索方法總是沿著遇到的第1個對向道岔形成的渡線向前搜索或者朝能縮小與終端模塊高度差的后繼模塊向前搜索。北京方向X進站信號機至IIIG接車有3條進路：經(jīng)5/7道岔反位、9/11、13/15、21、23/25道岔定位；經(jīng)9/11反位、5/7、1/3、13/15、21、23/25定位；經(jīng)23/25反位、5/7、1/3、9/11、13/15、17/19定位，其中，第1條、第2條為變更進路，第3條為基本進路。按照上述搜索規(guī)則，在選基本進路時按壓進路始終端按鈕后就會搜出模塊K(X)、K(IAG)、K(D3)、K(5DG)、K(5)，因K(5)是第1個遇到的對向道岔，且與終端模塊K(SⅢ)高度不一致，則沿彎股搜索到K(7)、K(7DG)……K(13)，K(13)也是對向道岔，但其與終端模塊高度一致，故沿直股搜索到K(21DG)……，最終找到終端模塊K(SⅢ)。這時選出的是一條變更進路，不滿足選基本進路時不能選出變更進路的運營要求。為了解決此問題，我們可以在對向道岔K(5)和K(9)模塊中加上“直股優(yōu)先搜索”的導向標志，此時X至IIIG的接車進路搜索路徑就變成了K(X)、K(IAG)、K(D3)、K(5DG)、K(5)、K(3)……K(9)……K(23)，K(23)無導向標志且與終端模塊K(SⅢ)高度不一致，則沿彎股搜索到K(25)、K(25DG)、K(SⅢ),從而選出基本進路。若采用深度優(yōu)先搜索算法，X至IIIG的進路則在搜索到K(25)時會沿直股搜索到K(D17)，該終端節(jié)點不是目標節(jié)點，則需回溯到K(25)沿彎股搜索才能找到目標節(jié)點K(SⅢ)。若采用廣度優(yōu)先搜索算法，在搜索到K(17)時會首先沿彎股搜索K(19)，一直搜索下去直到搜索不到目標節(jié)點時才逐步退回，搜索工作量更加巨大。

3.3 變更進路搜索過程

對于變更進路采用從始端模塊至變更模塊、變更模塊至終端模塊進行分段搜索，搜索方法同基本進路。例如對于上述接車進路要選出經(jīng)由5/7反位的變更進路，現(xiàn)以K(D11)充當變更模塊，因K(5)和K(9)已有直股優(yōu)先的導向標志，故進路搜索路徑為K(X)……K(5)、K(3)……K(9)、K(D13)……K(23)、K(25)……K(SⅢ)，從始端模塊K(X)開始未找到變更模塊K(D11)。對于這種由于導向標志而導致找不到目標模塊的情況，采用從終端向始端反向搜索的辦法。此時搜索路徑為K(SⅢ)……K(25)，K(25)與目標模塊即變更模塊K(D11)同高度，沿直股搜索找到K(21DG)……K(11)，K(11)同樣與K(D11)同高度，沿直股找到K(D11)，即變更模塊找到。再從此變更模塊開始尋找下一目標模塊即始端模塊K(X)，搜索路徑為K(D11)……K(7)、K(5)……K(X)，最后一個目標模塊找到，從而選出了變更進路，進路搜索成功。同理，D3至D11的調(diào)車進路也需反向搜索，搜索路徑為K(D11)……K(7)、K(5)……K(D3)。對于變更進路，廣度搜索算法和深度搜索算法搜索過程如同對基本進路的搜索，因搜索方向不確定也會造成回溯搜索，降低搜索效率。

3.4 進路搜索流程

進路搜索的流程如圖4所示。

圖4 進路搜索流程圖

4 結(jié)束語

采用站場型數(shù)據(jù)結(jié)構(gòu)的聯(lián)鎖軟件擺脫了總進路表數(shù)據(jù)結(jié)構(gòu)聯(lián)鎖軟件在站場改建和擴建時需大量修改總進路表的困擾?；谠摂?shù)據(jù)結(jié)構(gòu)的高度搜索算法，搜索目標明確，搜索方向確定，有效克服了廣度搜索算法逐層搜索和深度搜索算法回溯搜索導致的搜索量大、搜索效率低的缺點。通過C語言編程實現(xiàn)并驗證，該算法搜索路徑準確，能有效提高聯(lián)鎖軟件的進路搜索效率，優(yōu)越性顯著，具有重要的現(xiàn)實意義和應用價值。

[1]趙志熙.計算機聯(lián)鎖系統(tǒng)技術[M].北京：中國鐵道出版社，2008.

[2]占自才，徐雪松.進路搜索的數(shù)據(jù)結(jié)構(gòu)與算法及其仿真[J].鐵路運輸與經(jīng)濟，2005，27（9）：73-74.

[3]文武臣,王曉明.計算機聯(lián)鎖的數(shù)據(jù)結(jié)構(gòu)及進路搜索算法[J].重慶工學院學報：自然科學版，2008（6）：51-52.

[4]Michael T.Goodrich,Roberto Tamassia and Nikos Triandopoulos.Efficient authenticated data structures for graph connectivity and geometric search problems[J].Springer science business media.2011,60(3):505-552.

[5]陳志穎，董 昱，楊 柳，等.計算機聯(lián)鎖進路搜索算法的分析與研究[J].鐵道通信信號，2007，43（4）：4-5.

[6]王瑞峰.鐵路信號運營基礎[M].北京：中國鐵道出版社，2008.

[7]王文波，米根鎖，岳麗麗.全電子聯(lián)鎖軟件設計與進路搜索算法優(yōu)化[J].微計算機信息，2012，28（11）：234-236.

責任編輯 王 浩

Route Search Algorithm for Computer Interlocking System of railway station

WANG Wenbo1,MA Xuexia2
( 1.United Science &Technology Co.Ltd.,Hangzhou 310052,China;2.CASCO Signal Ltd.,Shanghai 200071,China)

Data structures selection and Route Search Algorithm are two key technologies of computer interlocking software.Because the common data structure constraints to interlocking software,and route search algorithm affects search effciency,this paper optimized the Route Search Algorithm based on station type data structures,used the example of yard as the object to discuss the researching course for basic route and alternate route by using Height Search Algorithm in detailed,which showed that the Height Search Algorithm overcame shortcomings of Breadth and Depth Priority Algorithm,the search goal was specifc and the search course was high-effciency and accurate.

Route Search Algorithm;data structures;computer interlocking

U284.362：TP39

A

1005-8451（2016）04-0063-04

2015-09-24

南京鐵道職業(yè)技術學院青年基金科研項目（YQ1403）。

王文波，助教；馬學霞，助理工程師。