計算機聯鎖系統進路表自動生成算法

陳 光，楊 揚

（西南交通大學 信息科學與技術學院，成都 610031）

計算機聯鎖系統進路表自動生成算法

陳 光，楊 揚

（西南交通大學 信息科學與技術學院，成都 610031）

簡述了通過讀取基礎站場數據，對站場數據中的信號設備的屬性和位置坐標進行分析，用一種方法將鐵路信號設備進行位置關聯，從而建立計算機聯鎖系統中的站場型數據結構。提出一種基于站場型數據結構的進路表自動生成算法，該算法是結合有向圖的拓撲結構、二叉樹、深度優先搜索的一種進路表自動生成算法。本文給出算法的完整描述。

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

隨著鐵路全面建設及逐步提速，計算機聯鎖系統角色越來越重要，正逐步取代繼電器聯鎖系統，其主要功能是通過計算機控制并處理進路上的道岔、信號機、軌道電路之間的聯鎖關系。進路表是計算機聯鎖系統重要數據之一，排列著該站場的所有進路信息。目前，進路表多數是由人工編寫審核，其工作量繁重而且容易造成人為錯誤，需多次審核才能達到實際工程要求。本文通過總結前人經驗及成果，對進路表自動生成算法開展進一步探索。

1 信號設備位置關聯并構造站場數據型結構

在設計之初所獲得的站場基礎數據來自于鐵路CAD軟件，該軟件所生成的數據包括信號設備的類型、設備位置坐標、設備所獨具的屬性等。這些數據排列是無序的，并不是按照設備所在站場里從上咽喉到下咽喉的順序排列，這種數據結構不利于進路搜索，由此，在進路搜索之前需確定信號設備左右位置關系并構造站場型數據結構。

1.1 確定信號設備位置關系

在站場中設備的位置關系主要有3種，分別是左側相鄰、右側相鄰、不相鄰。 設備位置關系的確定需設備的關鍵位置坐標及結合一種關聯方法，關鍵位置坐標如圖1所示，具體方法主要分為以下幾步：

（1）找出所有的道岔區段，一個道岔區段可能包含一個道岔，也可能包含多個道岔。

（2）在找出所有的道岔區段后，通過比對該道岔區段中道岔basepoint點的橫坐標和縱坐標，以及道岔的開口屬性，確定該道岔區段內道岔之間的位置關系，同時也能確定該道岔區段最左端、最右端的設備類型及ID。

（3）通過將調車信號機的basepoint坐標與道岔區段最左側或最右側的道岔設備的normalpoint、fromalpoint、reversepoint坐標進行比較，確定出信號機左側相鄰和右側相鄰的設備類型及ID。

圖1 信號機、道岔、股道關鍵點坐標

（4）將列車兼調車信號機basepoint與股道的leftpoint、rightpoint坐標進行比對，從而完成所有設備位置關聯。

通過上述步驟后，每個設備都找到了與其相鄰的左右設備，并把相鄰設備的類型及ID記錄在該設備的屬性中，因此，站場中所有設備通過這種形式間接地關聯在一起。

1.2 站場型數據結構[1]

通過上節闡述的設備位置關聯后，便可構造站場型數據結構。站場型數據結構是指數據塊像站場一樣格局進行聯接，把信號設備比作一個信號結點的數據結構，如圖2所示。

每個信號結點又由信號結點主要屬性、左側信號結點數據塊、右側信號結點數據塊組成。信號結點屬性主要存儲著該設備的主要特征，例如：道岔屬性存儲著該道岔的名字、所屬區段、開口方向等，而左右側信號結點數據塊主要存儲著與該設備相鄰的設備類型及ID。

對于道岔設備比較特殊，其信號結點除圖3所示外，還需記錄道岔反位所鏈接的設備類型及ID。

2 進路搜索算法

進路就是由起始信號機、終端信號機、若干個道岔及道岔位置、軌道區段組成的列車在車站內行車時所經過的通路[1]。

圖2 信號平面圖及站場型數據結構示例

圖3 信號結點

以站場型數據結構為基礎的進路搜索按照走迷宮的方式進行探索，以確定的入口去搜尋可能的對應的出口，以道岔的開口方向決定著該進路的搜索走向，根據入口信號點的類型決定著進路的終端類型，要求準確地搜索出各種類型的基本進路。進路搜索不重復、進路不遺漏是進路表自動生成算法的核心內容[2]。

下面進路搜索算法結合了圖搜索、二叉樹、棧結構，來處理進路搜索中的一些問題以及給出自動生成的進路表的格式規范。

2.1 二叉樹結構與圖搜索相結合

二叉樹是樹的一種，從圖論的角度來說是一張連通的無環圖，并且每一個頂點的度數不大于2，是一種非線性結構，二叉樹的結點分為根節點和葉結點，二叉樹的子樹有左子樹和右子樹之分，并且二者順序不可以顛倒[3]。

二叉樹在計算機中的存儲可以采用鏈式存儲結構和隊列存儲結構，鏈式存儲應用較為廣泛，其節點由一個數據元素和分別指向其左、右子樹的兩個分支構成。

通過對比，站場型數據結構與二叉樹數據結構的形狀相似，因此，可以考慮通過二叉樹的形式進行站場型數據結構模型的建立[4]，以圖2為基礎，所建立的模型如圖4所示。

圖4 二叉樹建模圖

二叉樹的搜索可以采用圖的搜索策略，圖的搜索可分為廣度優先搜索、深度優先搜索、啟發式優先搜索，考慮到二叉樹的結構特性以及進路選排的技術要求，采用深度優先搜索較為合理。

深度優先搜索是在一張無向圖中的某一點發起搜索，下一次的訪問路徑不確定，一旦選中一條路徑后便要窮盡該路徑，找到結束的信號結點，如未找到則廢棄此路徑，返回路徑的分叉點去搜索另一條可行路徑。

在進路自動搜索的過程中，深度優先搜索的方向是由起始信號機防護的方向決定，一條進路的終端是根據起始信號機的屬性，及終端是并置、差置、列車兼調車信號機等不同情況來確定，這在計算機聯鎖系統的進路選排要求中有著明確的規定，在搜索的過程中會遇到多個道岔，這里視每個道岔為深度優先搜索的路徑分叉點，路徑分叉點需一種方法特殊處理來輔助進路的搜索，同時在進路自動搜索的過程中也要遵循直股優先以及同類渡線優先的原則。例如：以D1為始端的基本進路搜索，當確定以D1為始端的時候，信號機防護的是1-DG道岔區段，所以進路搜索的方向為上咽喉到下咽喉方向，通過D1信號結點屬性中存儲的信息，可找到D1右側相鄰的信號結點類型及ID，依次類推，當遇到D3時，此路徑終端已找到，完成此路徑搜索并返回路徑分叉點搜索另一路徑，搜索到D5完成此次以D3為始端的進路搜索。

2.2 道岔結點的棧存儲

道岔的處理是進路自動搜索的關鍵，道岔具有定位和反位兩種狀態，從而導致了搜索時始端信號確定后有多條搜索路徑，也就是說道岔是搜索路徑的分叉點，由于采取了深度優先搜索策略，需要一種方法來存儲當一條進路搜索失敗或者搜索結束時回退到哪一個分叉點，考慮到回退時應該從進路的后輩結點逐漸向起始結點回退，又由于棧有著后進先出的特點，所以采取棧結構存儲道岔結點，如圖5所示，輔助完成進路的搜索。

圖5 道岔的棧結構存儲

道岔又分為順向道岔和對向道岔，在搜索的過程中，與搜索方向對向的道岔進入棧結構，順向的道岔對路徑不造成影響，則不入棧。

2.3 進路格式要求

進路搜索結束后，需要按照一定格式輸出進路信息，便于計算機聯鎖主機讀取和使用，在一條進路信息中，進路的始端終端要明確表達出，用符號‘＞’表示進路的方向，同時進路所經過的道岔要給出道岔的位置狀態，如果道岔處于定位則用‘#1’來表示，如在反位則用‘#1^’這樣的符號與道岔名字的組合來表示。如圖2，D1到D3的進路表示如下：

D1＞D3 =[D1,D3] #1

3 算法實現

進路表自動生成算法已成功在計算機上實現，具體流程如圖6所示。

圖6 算法實現流程圖

進路表自動生成軟件是在Visual C++環境下實現的，通過讀取基礎站場數據文件SWJDATA.dat文件，最終生成進路表ROUT.txt，具體站場如圖7所示。

4 結束語

在計算機上成功地驗證了進路表自動生成算法，實現了進路表的自動生成，能夠遍歷出所有的基本進路，達到了不重復、不遺漏的設計要求。不足之處是對變更進路和長進路的處理不夠完善，進路表自動生成算法還需要進一步研究和探討。

圖7 仿真站場

[1]陳志穎，董 昱，楊 柳，李 亮.計算機聯鎖進路搜索算 法的分析與研究[J].鐵道通信信號，2007（4）.

[2]覃崇乾，吳芳美.一種搜索與交互相結合的聯鎖表自動生成 算法[J].上海鐵道大學學報，1999（12）.

[3]嚴蔚敏，吳偉民.數據結構[M].北京：清華大學出版社，2007.

[4]文武臣，王曉明.計算機聯鎖的數據結構及進路搜索算法[J].重慶工學院學報（自然科學版），2008（6）.

[5]朱 怡.基于計算機聯鎖的進路表搜索生成系統的設計與實現[D].上海：上海交通大學，2012.

責任編輯 方 圓

Automatic Generating Algorithm for accessing table of Computer Interlocking System

CHEN Guang, YANG Yang
( School of Information Sciences and Technology, Southwest Jiaotong University, Chendu 610031, China )

The paper analyzed the attribute and position of signal equipment by reading the based date of the station, made the railway signal equipment be position correlation, thereby established a station-type data structure of Computer Interlocking System, put forward an Automatic Generating Algorithm for accessing table of Computer Interlocking System based on station-type data structure. The Algorithm was combined with topology map and binary tree. The description for the Algorithm was given in detail.

Computer Interlocking System; accessing table; data structure; algorithm

U284.37；TP311

A

1005-8451（2015）05-0005-04

2014-10-17

中國鐵路總公司科技研究計劃項目（2013X012-A-1，2103X012-A -2，2014X008-A）。

陳 光，在讀碩士研究生；楊 揚，副教授。