鐵路車站計算機聯鎖軟件進路搜索算法研究

王文波，馬學霞

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

鐵路車站計算機聯鎖軟件進路搜索算法研究

王文波1，馬學霞2

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

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

進路搜索算法；數據結構；計算機聯鎖

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

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

圖1 軟件的層次結構

1 聯鎖軟件數據結構

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

1.1 進路表型數據結構

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

1.2 二叉樹型數據結構

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

1.3 站場型數據結構

站場型數據結構就是根據站場信號布置平面圖，把各信號點數據模塊按照其在信號平面布置圖中的位置鏈接構成，其本質是節點的鏈接表。具有以下優點：

（1）在數據結構中的任何地方增加或刪除節點，只需修改節點指針域中的地址，不影響節點的物理地址，方便站場改建或擴建時聯鎖數據的修改；

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

（3）基于根據進路辦理命令的數據結構生成的進路表存在于RAM中，進路表隨著進路辦理而建立，隨著進路解除而刪除，占用RAM空間小；同時該靜態數據庫占用ROM空間小，有利于檢測。

2 進路搜索算法研究

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

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

2.1 廣度優先搜索策略

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

2.2 深度優先搜索策略

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

2.3 高度搜索策略

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

表1 設備節點高度分布表

3 進路搜索過程實現

3.1 進路搜索規則

圖3 站場形數據結構

圖2所示站場的站場形數據結構如圖3所示，其中，K表示設備節點的數據模塊，例如XD數據模塊表示為K(XD)。進路搜索時，首先根據進路操作命令找出進路的始端模塊和終端模塊，確定搜索方向，依據站場形數據結構沿著進路搜索方向找出與進路相關的所有模塊。當遇到分支模塊(對向道岔)時，比較分支模塊與終端模塊的高度，若高度一致，沿直股搜索；若高度不一致，則沿彎股搜索。例如辦理SⅢ至D7的調車進路，確定從進路始端向終端搜索，始端模塊是K(SⅢ)，終端模塊是K(D7)。由始端模塊出發找到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)。進路搜索程序從這些模塊中提取進路聯鎖程序所需的數據，并生成一個進路表，就完成了進路搜索任務。

3.2 基本進路搜索過程

當進路的始端模塊和終端模塊高度不一致時，此種進路搜索方法總是沿著遇到的第1個對向道岔形成的渡線向前搜索或者朝能縮小與終端模塊高度差的后繼模塊向前搜索。北京方向X進站信號機至IIIG接車有3條進路：經5/7道岔反位、9/11、13/15、21、23/25道岔定位；經9/11反位、5/7、1/3、13/15、21、23/25定位；經23/25反位、5/7、1/3、9/11、13/15、17/19定位，其中，第1條、第2條為變更進路，第3條為基本進路。按照上述搜索規則，在選基本進路時按壓進路始終端按鈕后就會搜出模塊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)模塊中加上“直股優先搜索”的導向標志，此時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Ⅲ),從而選出基本進路。若采用深度優先搜索算法，X至IIIG的進路則在搜索到K(25)時會沿直股搜索到K(D17)，該終端節點不是目標節點，則需回溯到K(25)沿彎股搜索才能找到目標節點K(SⅢ)。若采用廣度優先搜索算法，在搜索到K(17)時會首先沿彎股搜索K(19)，一直搜索下去直到搜索不到目標節點時才逐步退回，搜索工作量更加巨大。

3.3 變更進路搜索過程

對于變更進路采用從始端模塊至變更模塊、變更模塊至終端模塊進行分段搜索，搜索方法同基本進路。例如對于上述接車進路要選出經由5/7反位的變更進路，現以K(D11)充當變更模塊，因K(5)和K(9)已有直股優先的導向標志，故進路搜索路徑為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的調車進路也需反向搜索，搜索路徑為K(D11)……K(7)、K(5)……K(D3)。對于變更進路，廣度搜索算法和深度搜索算法搜索過程如同對基本進路的搜索，因搜索方向不確定也會造成回溯搜索，降低搜索效率。

3.4 進路搜索流程

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

圖4 進路搜索流程圖

4 結束語

采用站場型數據結構的聯鎖軟件擺脫了總進路表數據結構聯鎖軟件在站場改建和擴建時需大量修改總進路表的困擾。基于該數據結構的高度搜索算法，搜索目標明確，搜索方向確定，有效克服了廣度搜索算法逐層搜索和深度搜索算法回溯搜索導致的搜索量大、搜索效率低的缺點。通過C語言編程實現并驗證，該算法搜索路徑準確，能有效提高聯鎖軟件的進路搜索效率，優越性顯著，具有重要的現實意義和應用價值。

[1]趙志熙.計算機聯鎖系統技術[M].北京：中國鐵道出版社，2008.

[2]占自才，徐雪松.進路搜索的數據結構與算法及其仿真[J].鐵路運輸與經濟，2005，27（9）：73-74.

[3]文武臣,王曉明.計算機聯鎖的數據結構及進路搜索算法[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]陳志穎，董 昱，楊 柳，等.計算機聯鎖進路搜索算法的分析與研究[J].鐵道通信信號，2007，43（4）：4-5.

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

[7]王文波，米根鎖，岳麗麗.全電子聯鎖軟件設計與進路搜索算法優化[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

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

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