計(jì)算機(jī)聯(lián)鎖系統(tǒng)進(jìn)路表自動(dòng)生成算法

陳 光，楊 揚(yáng)

（西南交通大學(xué) 信息科學(xué)與技術(shù)學(xué)院，成都 610031）

計(jì)算機(jī)聯(lián)鎖系統(tǒng)進(jìn)路表自動(dòng)生成算法

陳 光，楊 揚(yáng)

（西南交通大學(xué) 信息科學(xué)與技術(shù)學(xué)院，成都 610031）

簡(jiǎn)述了通過讀取基礎(chǔ)站場(chǎng)數(shù)據(jù)，對(duì)站場(chǎng)數(shù)據(jù)中的信號(hào)設(shè)備的屬性和位置坐標(biāo)進(jìn)行分析，用一種方法將鐵路信號(hào)設(shè)備進(jìn)行位置關(guān)聯(lián)，從而建立計(jì)算機(jī)聯(lián)鎖系統(tǒng)中的站場(chǎng)型數(shù)據(jù)結(jié)構(gòu)。提出一種基于站場(chǎng)型數(shù)據(jù)結(jié)構(gòu)的進(jìn)路表自動(dòng)生成算法，該算法是結(jié)合有向圖的拓?fù)浣Y(jié)構(gòu)、二叉樹、深度優(yōu)先搜索的一種進(jìn)路表自動(dòng)生成算法。本文給出算法的完整描述。

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

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

1 信號(hào)設(shè)備位置關(guān)聯(lián)并構(gòu)造站場(chǎng)數(shù)據(jù)型結(jié)構(gòu)

在設(shè)計(jì)之初所獲得的站場(chǎng)基礎(chǔ)數(shù)據(jù)來自于鐵路CAD軟件，該軟件所生成的數(shù)據(jù)包括信號(hào)設(shè)備的類型、設(shè)備位置坐標(biāo)、設(shè)備所獨(dú)具的屬性等。這些數(shù)據(jù)排列是無序的，并不是按照設(shè)備所在站場(chǎng)里從上咽喉到下咽喉的順序排列，這種數(shù)據(jù)結(jié)構(gòu)不利于進(jìn)路搜索，由此，在進(jìn)路搜索之前需確定信號(hào)設(shè)備左右位置關(guān)系并構(gòu)造站場(chǎng)型數(shù)據(jù)結(jié)構(gòu)。

1.1 確定信號(hào)設(shè)備位置關(guān)系

在站場(chǎng)中設(shè)備的位置關(guān)系主要有3種，分別是左側(cè)相鄰、右側(cè)相鄰、不相鄰。 設(shè)備位置關(guān)系的確定需設(shè)備的關(guān)鍵位置坐標(biāo)及結(jié)合一種關(guān)聯(lián)方法，關(guān)鍵位置坐標(biāo)如圖1所示，具體方法主要分為以下幾步：

（1）找出所有的道岔區(qū)段，一個(gè)道岔區(qū)段可能包含一個(gè)道岔，也可能包含多個(gè)道岔。

（2）在找出所有的道岔區(qū)段后，通過比對(duì)該道岔區(qū)段中道岔basepoint點(diǎn)的橫坐標(biāo)和縱坐標(biāo)，以及道岔的開口屬性，確定該道岔區(qū)段內(nèi)道岔之間的位置關(guān)系，同時(shí)也能確定該道岔區(qū)段最左端、最右端的設(shè)備類型及ID。

（3）通過將調(diào)車信號(hào)機(jī)的basepoint坐標(biāo)與道岔區(qū)段最左側(cè)或最右側(cè)的道岔設(shè)備的normalpoint、fromalpoint、reversepoint坐標(biāo)進(jìn)行比較，確定出信號(hào)機(jī)左側(cè)相鄰和右側(cè)相鄰的設(shè)備類型及ID。

圖1 信號(hào)機(jī)、道岔、股道關(guān)鍵點(diǎn)坐標(biāo)

（4）將列車兼調(diào)車信號(hào)機(jī)basepoint與股道的leftpoint、rightpoint坐標(biāo)進(jìn)行比對(duì)，從而完成所有設(shè)備位置關(guān)聯(lián)。

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

1.2 站場(chǎng)型數(shù)據(jù)結(jié)構(gòu)[1]

通過上節(jié)闡述的設(shè)備位置關(guān)聯(lián)后，便可構(gòu)造站場(chǎng)型數(shù)據(jù)結(jié)構(gòu)。站場(chǎng)型數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)塊像站場(chǎng)一樣格局進(jìn)行聯(lián)接，把信號(hào)設(shè)備比作一個(gè)信號(hào)結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)，如圖2所示。

每個(gè)信號(hào)結(jié)點(diǎn)又由信號(hào)結(jié)點(diǎn)主要屬性、左側(cè)信號(hào)結(jié)點(diǎn)數(shù)據(jù)塊、右側(cè)信號(hào)結(jié)點(diǎn)數(shù)據(jù)塊組成。信號(hào)結(jié)點(diǎn)屬性主要存儲(chǔ)著該設(shè)備的主要特征，例如：道岔屬性存儲(chǔ)著該道岔的名字、所屬區(qū)段、開口方向等，而左右側(cè)信號(hào)結(jié)點(diǎn)數(shù)據(jù)塊主要存儲(chǔ)著與該設(shè)備相鄰的設(shè)備類型及ID。

對(duì)于道岔設(shè)備比較特殊，其信號(hào)結(jié)點(diǎn)除圖3所示外，還需記錄道岔反位所鏈接的設(shè)備類型及ID。

2 進(jìn)路搜索算法

進(jìn)路就是由起始信號(hào)機(jī)、終端信號(hào)機(jī)、若干個(gè)道岔及道岔位置、軌道區(qū)段組成的列車在車站內(nèi)行車時(shí)所經(jīng)過的通路[1]。

圖2 信號(hào)平面圖及站場(chǎng)型數(shù)據(jù)結(jié)構(gòu)示例

圖3 信號(hào)結(jié)點(diǎn)

以站場(chǎng)型數(shù)據(jù)結(jié)構(gòu)為基礎(chǔ)的進(jìn)路搜索按照走迷宮的方式進(jìn)行探索，以確定的入口去搜尋可能的對(duì)應(yīng)的出口，以道岔的開口方向決定著該進(jìn)路的搜索走向，根據(jù)入口信號(hào)點(diǎn)的類型決定著進(jìn)路的終端類型，要求準(zhǔn)確地搜索出各種類型的基本進(jìn)路。進(jìn)路搜索不重復(fù)、進(jìn)路不遺漏是進(jìn)路表自動(dòng)生成算法的核心內(nèi)容[2]。

下面進(jìn)路搜索算法結(jié)合了圖搜索、二叉樹、棧結(jié)構(gòu)，來處理進(jìn)路搜索中的一些問題以及給出自動(dòng)生成的進(jìn)路表的格式規(guī)范。

2.1 二叉樹結(jié)構(gòu)與圖搜索相結(jié)合

二叉樹是樹的一種，從圖論的角度來說是一張連通的無環(huán)圖，并且每一個(gè)頂點(diǎn)的度數(shù)不大于2，是一種非線性結(jié)構(gòu)，二叉樹的結(jié)點(diǎn)分為根節(jié)點(diǎn)和葉結(jié)點(diǎn)，二叉樹的子樹有左子樹和右子樹之分，并且二者順序不可以顛倒[3]。

二叉樹在計(jì)算機(jī)中的存儲(chǔ)可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和隊(duì)列存儲(chǔ)結(jié)構(gòu)，鏈?zhǔn)酱鎯?chǔ)應(yīng)用較為廣泛，其節(jié)點(diǎn)由一個(gè)數(shù)據(jù)元素和分別指向其左、右子樹的兩個(gè)分支構(gòu)成。

通過對(duì)比，站場(chǎng)型數(shù)據(jù)結(jié)構(gòu)與二叉樹數(shù)據(jù)結(jié)構(gòu)的形狀相似，因此，可以考慮通過二叉樹的形式進(jìn)行站場(chǎng)型數(shù)據(jù)結(jié)構(gòu)模型的建立[4]，以圖2為基礎(chǔ)，所建立的模型如圖4所示。

圖4 二叉樹建模圖

二叉樹的搜索可以采用圖的搜索策略，圖的搜索可分為廣度優(yōu)先搜索、深度優(yōu)先搜索、啟發(fā)式優(yōu)先搜索，考慮到二叉樹的結(jié)構(gòu)特性以及進(jìn)路選排的技術(shù)要求，采用深度優(yōu)先搜索較為合理。

深度優(yōu)先搜索是在一張無向圖中的某一點(diǎn)發(fā)起搜索，下一次的訪問路徑不確定，一旦選中一條路徑后便要窮盡該路徑，找到結(jié)束的信號(hào)結(jié)點(diǎn)，如未找到則廢棄此路徑，返回路徑的分叉點(diǎn)去搜索另一條可行路徑。

在進(jìn)路自動(dòng)搜索的過程中，深度優(yōu)先搜索的方向是由起始信號(hào)機(jī)防護(hù)的方向決定，一條進(jìn)路的終端是根據(jù)起始信號(hào)機(jī)的屬性，及終端是并置、差置、列車兼調(diào)車信號(hào)機(jī)等不同情況來確定，這在計(jì)算機(jī)聯(lián)鎖系統(tǒng)的進(jìn)路選排要求中有著明確的規(guī)定，在搜索的過程中會(huì)遇到多個(gè)道岔，這里視每個(gè)道岔為深度優(yōu)先搜索的路徑分叉點(diǎn)，路徑分叉點(diǎn)需一種方法特殊處理來輔助進(jìn)路的搜索，同時(shí)在進(jìn)路自動(dòng)搜索的過程中也要遵循直股優(yōu)先以及同類渡線優(yōu)先的原則。例如：以D1為始端的基本進(jìn)路搜索，當(dāng)確定以D1為始端的時(shí)候，信號(hào)機(jī)防護(hù)的是1-DG道岔區(qū)段，所以進(jìn)路搜索的方向?yàn)樯涎屎淼较卵屎矸较颍ㄟ^D1信號(hào)結(jié)點(diǎn)屬性中存儲(chǔ)的信息，可找到D1右側(cè)相鄰的信號(hào)結(jié)點(diǎn)類型及ID，依次類推，當(dāng)遇到D3時(shí)，此路徑終端已找到，完成此路徑搜索并返回路徑分叉點(diǎn)搜索另一路徑，搜索到D5完成此次以D3為始端的進(jìn)路搜索。

2.2 道岔結(jié)點(diǎn)的棧存儲(chǔ)

道岔的處理是進(jìn)路自動(dòng)搜索的關(guān)鍵，道岔具有定位和反位兩種狀態(tài)，從而導(dǎo)致了搜索時(shí)始端信號(hào)確定后有多條搜索路徑，也就是說道岔是搜索路徑的分叉點(diǎn)，由于采取了深度優(yōu)先搜索策略，需要一種方法來存儲(chǔ)當(dāng)一條進(jìn)路搜索失敗或者搜索結(jié)束時(shí)回退到哪一個(gè)分叉點(diǎn)，考慮到回退時(shí)應(yīng)該從進(jìn)路的后輩結(jié)點(diǎn)逐漸向起始結(jié)點(diǎn)回退，又由于棧有著后進(jìn)先出的特點(diǎn)，所以采取棧結(jié)構(gòu)存儲(chǔ)道岔結(jié)點(diǎn)，如圖5所示，輔助完成進(jìn)路的搜索。

圖5 道岔的棧結(jié)構(gòu)存儲(chǔ)

道岔又分為順向道岔和對(duì)向道岔，在搜索的過程中，與搜索方向?qū)ο虻牡啦磉M(jìn)入棧結(jié)構(gòu)，順向的道岔對(duì)路徑不造成影響，則不入棧。

2.3 進(jìn)路格式要求

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

D1＞D3 =[D1,D3] #1

3 算法實(shí)現(xiàn)

進(jìn)路表自動(dòng)生成算法已成功在計(jì)算機(jī)上實(shí)現(xiàn)，具體流程如圖6所示。

圖6 算法實(shí)現(xiàn)流程圖

進(jìn)路表自動(dòng)生成軟件是在Visual C++環(huán)境下實(shí)現(xiàn)的，通過讀取基礎(chǔ)站場(chǎng)數(shù)據(jù)文件SWJDATA.dat文件，最終生成進(jìn)路表ROUT.txt，具體站場(chǎng)如圖7所示。

4 結(jié)束語(yǔ)

在計(jì)算機(jī)上成功地驗(yàn)證了進(jìn)路表自動(dòng)生成算法，實(shí)現(xiàn)了進(jìn)路表的自動(dòng)生成，能夠遍歷出所有的基本進(jìn)路，達(dá)到了不重復(fù)、不遺漏的設(shè)計(jì)要求。不足之處是對(duì)變更進(jìn)路和長(zhǎng)進(jìn)路的處理不夠完善，進(jìn)路表自動(dòng)生成算法還需要進(jìn)一步研究和探討。

圖7 仿真站場(chǎng)

[1]陳志穎，董 昱，楊 柳，李 亮.計(jì)算機(jī)聯(lián)鎖進(jìn)路搜索算 法的分析與研究[J].鐵道通信信號(hào)，2007（4）.

[2]覃崇乾，吳芳美.一種搜索與交互相結(jié)合的聯(lián)鎖表自動(dòng)生成 算法[J].上海鐵道大學(xué)學(xué)報(bào)，1999（12）.

[3]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京：清華大學(xué)出版社，2007.

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

[5]朱 怡.基于計(jì)算機(jī)聯(lián)鎖的進(jìn)路表搜索生成系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D].上海：上海交通大學(xué)，2012.

責(zé)任編輯 方 圓

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

中國(guó)鐵路總公司科技研究計(jì)劃項(xiàng)目（2013X012-A-1，2103X012-A -2，2014X008-A）。

陳 光，在讀碩士研究生；楊 揚(yáng)，副教授。