一種基于堆棧遍歷的聯(lián)鎖表自動(dòng)生成算法

金 云，蕢凱騰，鐘朱婷，虞乾儷

(通號(hào)萬全信號(hào)設(shè)備有限公司，杭州 310000)

在軌道交通相關(guān)的領(lǐng)域中，信號(hào)系統(tǒng)都是保障安全不可或缺的一個(gè)系統(tǒng)。而聯(lián)鎖表等相關(guān)聯(lián)鎖數(shù)據(jù)又是信號(hào)系統(tǒng)的重中之重。本文通過對(duì)于前人實(shí)踐經(jīng)驗(yàn)的總結(jié)，通過計(jì)算機(jī)的可視化技術(shù)，把聯(lián)鎖界面顯示、聯(lián)鎖表自動(dòng)生成、聯(lián)鎖軟件數(shù)據(jù)自動(dòng)生成通過一個(gè)軟件進(jìn)行實(shí)現(xiàn)，本文基本對(duì)信號(hào)設(shè)備的抽象、把信號(hào)設(shè)備轉(zhuǎn)化為系統(tǒng)能夠識(shí)別的數(shù)據(jù)結(jié)構(gòu)，再使用基于網(wǎng)絡(luò)拓?fù)鋱D的堆棧遍歷的核心算法，對(duì)于聯(lián)鎖表的自動(dòng)生成展開了進(jìn)一步的探索。

1 信號(hào)設(shè)備的抽象

軟件繪制站場(chǎng)圖，基于內(nèi)部定義的信號(hào)設(shè)備模式來進(jìn)行繪制顯示，信號(hào)設(shè)備主要分為3 種，分別為信號(hào)機(jī)，道岔和區(qū)段。軟件內(nèi)部定義的區(qū)段單指無岔區(qū)段，道岔為道岔和道岔區(qū)段的集合。繪圖時(shí)的所有道岔都是單動(dòng)道岔，系統(tǒng)通過道岔的屬性來設(shè)置雙動(dòng)道岔和同區(qū)段道岔。信號(hào)機(jī)需要設(shè)置以下屬性：1）信號(hào)機(jī)按鈕類型屬性，可以進(jìn)行列車按鈕屬性、調(diào)車按鈕屬性、延續(xù)按鈕屬性等始終端的設(shè)置。2）信號(hào)機(jī)類型，差置信號(hào)機(jī)、并置信號(hào)機(jī)、盡頭型信號(hào)機(jī)等，用來參與進(jìn)路生成的判斷。所有的道岔、區(qū)段和信號(hào)機(jī)都具備咽喉屬性，根據(jù)實(shí)際相關(guān)進(jìn)行配置。

2 網(wǎng)絡(luò)拓?fù)溥\(yùn)算

網(wǎng)絡(luò)拓?fù)溥\(yùn)算需要計(jì)算以下的相關(guān)信息。

信號(hào)機(jī)：1）信號(hào)機(jī)的防護(hù)設(shè)備；2）信號(hào)機(jī)防護(hù)設(shè)備的被防護(hù)位置；3）信號(hào)機(jī)的接近設(shè)備；4）信號(hào)機(jī)接近設(shè)備的被接近位置。

區(qū)段：區(qū)段的連接點(diǎn)為兩個(gè)，分別為左邊連接點(diǎn)和右邊連接點(diǎn)，每個(gè)連接點(diǎn)分別記錄所連接的設(shè)備以及連接設(shè)備的被連接位置，防護(hù)信號(hào)機(jī)的信息、接近信號(hào)機(jī)的信息。

道岔：道岔的連接點(diǎn)為3 個(gè)，分別為岔前連接點(diǎn)、定位連接點(diǎn)和反位連接點(diǎn)。每個(gè)連接點(diǎn)分別記錄所連接的設(shè)備以及連接設(shè)備的被連接位置，防護(hù)信號(hào)機(jī)的信息、接近信號(hào)機(jī)的信息。

在繪圖時(shí)，記錄區(qū)段的邊界點(diǎn)為兩個(gè)，分別為左邊界點(diǎn)和右邊界點(diǎn)。記錄道岔的邊界點(diǎn)為3 個(gè)，分別為岔前邊界點(diǎn)、定位邊界點(diǎn)和反位邊界點(diǎn)。記錄信號(hào)機(jī)的中心點(diǎn)以及信號(hào)機(jī)的旋轉(zhuǎn)角度。按照信號(hào)機(jī)的中心點(diǎn)和旋轉(zhuǎn)角度完成信號(hào)機(jī)的繪制，定義信號(hào)機(jī)中心點(diǎn)向信號(hào)機(jī)燈位的方向?yàn)樾盘?hào)機(jī)的后方。反方向?yàn)樾盘?hào)機(jī)的前方。

遍歷整個(gè)道岔和區(qū)段列表，如果兩個(gè)設(shè)備的邊界點(diǎn)之間的距離小于10 個(gè)像素，則認(rèn)為兩個(gè)設(shè)備是相連的，記錄相關(guān)的信息到各自的連接點(diǎn)信息中。道岔和區(qū)段遍歷完成后，整個(gè)信號(hào)平面圖的道岔和區(qū)段即可組成一幅網(wǎng)絡(luò)拓?fù)鋱D，可以通過任何一個(gè)設(shè)備，找到其余的關(guān)聯(lián)設(shè)備。

遍歷整個(gè)信號(hào)機(jī)列表，如果信號(hào)機(jī)的中心點(diǎn)和道岔或者區(qū)段的邊界點(diǎn)距離小于10 個(gè)像素，且該設(shè)備處在信號(hào)機(jī)的后方，則認(rèn)為信號(hào)機(jī)是防護(hù)該設(shè)備的。如果信號(hào)機(jī)的中心點(diǎn)和道岔或者區(qū)段的邊界點(diǎn)的距離小于10 個(gè)像素，且該設(shè)備處在信號(hào)機(jī)的前方，則認(rèn)為信號(hào)機(jī)為接近該設(shè)備的。分別記錄防護(hù)和接近信息到相應(yīng)的設(shè)備中。

由此可見，1 架信號(hào)機(jī)最多防護(hù)1 個(gè)設(shè)備，接近1 個(gè)設(shè)備。1 個(gè)道岔最多被3 架信號(hào)機(jī)防護(hù)，最多被3 架信號(hào)機(jī)接近。1 個(gè)區(qū)段最多被2 架信號(hào)機(jī)防護(hù)，最多被2 架信號(hào)機(jī)接近。至此，整個(gè)網(wǎng)絡(luò)拓?fù)鋱D數(shù)據(jù)生成完畢。

3 堆棧方式遍歷網(wǎng)絡(luò)拓?fù)鋱D

信號(hào)設(shè)備中，區(qū)段為單方向設(shè)備，從一邊進(jìn)入，只能從另一邊離開。道岔如果從岔前進(jìn)入，則可以分為定位方向或者反位方向兩種情況離開。道岔如果從定位或者反位進(jìn)入，則只能從岔前離開。信號(hào)機(jī)作為進(jìn)路遍歷的開始條件和結(jié)束條件，控制進(jìn)路能夠按照要求自動(dòng)生成。

利用堆棧后進(jìn)先出的特性，構(gòu)造一個(gè)記錄當(dāng)前設(shè)備屬性和當(dāng)前設(shè)備位置的堆棧。以任意一架信號(hào)機(jī)為始端，按照堆棧的方式，遍歷全部信號(hào)機(jī)。每次遍歷如圖1 所示。

4 基本聯(lián)鎖表生成

列車進(jìn)路：同一咽喉區(qū)內(nèi)搜索到第一架列車信號(hào)機(jī)(非反向進(jìn)路信號(hào)機(jī))時(shí)作為終端信號(hào)機(jī)。如果是反向信號(hào)機(jī)，則將反向信號(hào)機(jī)的接近區(qū)段也列為進(jìn)路中的區(qū)段。如果為同向信號(hào)機(jī)，則不另外添加其接近區(qū)段為進(jìn)路中的區(qū)段。

調(diào)車進(jìn)路：在同一咽喉區(qū)內(nèi)搜索到第一架同向單置調(diào)車信號(hào)機(jī)作為終端信號(hào)機(jī)，或搜索到第一架非單置含調(diào)車屬性的反向信號(hào)機(jī)作為終端信號(hào)機(jī)。

敵對(duì)信號(hào)：1）進(jìn)路中不能作為終端的信號(hào)機(jī)為敵對(duì)信號(hào)；2）若終端信號(hào)機(jī)與始端信號(hào)機(jī)方向相反，則該終端信號(hào)機(jī)為敵對(duì)信號(hào)；3）若進(jìn)路終端為差置信號(hào)機(jī)，則以另一架差置信號(hào)機(jī)為終端的進(jìn)路始端信號(hào)機(jī)為敵對(duì)信號(hào)；4）以進(jìn)路中敵對(duì)信號(hào)為終端，搜索到的進(jìn)路始端信號(hào)機(jī)(匹配的進(jìn)路與該進(jìn)路重合的道岔位置要求一致)為敵對(duì)信號(hào)。若搜索到的始端信號(hào)機(jī)存在多條進(jìn)路時(shí)，說明是條件敵對(duì)，那么把某組關(guān)鍵道岔位置作為該敵對(duì)信號(hào)的條件；5）若本進(jìn)路是調(diào)車進(jìn)路，與該調(diào)車進(jìn)路完全重合的列車進(jìn)路始端信號(hào)機(jī)為敵對(duì)信號(hào)。敵對(duì)條件為本調(diào)車進(jìn)路中任何一個(gè)道岔所在的正確位置。

侵限：檢查進(jìn)路中道岔定位和反位是否存在侵限絕緣。

圖1 進(jìn)路生成遍歷設(shè)備邏輯Fig.1 Logic of device traversal for route generation

1) 當(dāng)進(jìn)路中的道岔(道岔A)定位存在侵限絕緣節(jié)時(shí)，如果道岔A 在進(jìn)路中的狀態(tài)是反位時(shí)，則檢查道岔A 定位直連的關(guān)聯(lián)道岔(道岔B)的狀態(tài)和位置。

a. 如果道岔B 的岔前和道岔A 相連，則道岔B 所在的區(qū)段為該進(jìn)路的侵限區(qū)段。

b. 如果道岔B 的定位和道岔A 相連，則當(dāng)?shù)啦鞡 處在定位時(shí)，道岔B 所在的區(qū)段為該進(jìn)路的條件侵限區(qū)段。

c. 如果道岔B 的反位和道岔A 相連，則當(dāng)?shù)啦鞡 處在反位時(shí)，道岔B 所在的區(qū)段為該進(jìn)路的條件侵限區(qū)段。

2) 當(dāng)進(jìn)路中的道岔(道岔A)反位存在侵限絕緣節(jié)時(shí)，如果道岔A 在進(jìn)路中的狀態(tài)是定位時(shí)，則檢查道岔A 反位直連的關(guān)聯(lián)道岔(道岔B)的狀態(tài)和位置。

a. 如果道岔B 的岔前和道岔A 相連，則道岔B 所在的區(qū)段為該進(jìn)路的侵限區(qū)段。

b. 如果道岔B 的定位和道岔A 相連，則當(dāng)?shù)啦鞡 存在定位時(shí)，道岔B 所在的區(qū)段為該進(jìn)路的條件侵限區(qū)段。

c. 如果道岔B 的反位和道岔A 相連，則當(dāng)?shù)啦鞡 存在反位時(shí)，道岔B 所在的區(qū)段為該進(jìn)路的條件侵限區(qū)段。

迎面進(jìn)路：1）當(dāng)存在兩個(gè)咽喉時(shí)，列車進(jìn)路終端為股道信號(hào)機(jī)時(shí)，股道信號(hào)機(jī)另一端信號(hào)機(jī)如果存在列車進(jìn)路終端，添加列車股道。如果存在調(diào)車進(jìn)路終端，添加調(diào)車股道；2）當(dāng)存在兩個(gè)咽喉時(shí)，調(diào)車進(jìn)路終端為股道信號(hào)機(jī)時(shí)，股道信號(hào)機(jī)另一端信號(hào)機(jī)如果存在列車進(jìn)路終端，添加列車股道。

帶動(dòng)道岔：檢查進(jìn)路中道岔區(qū)段是否存在同區(qū)段且非進(jìn)路中的道岔。若該道岔反位和進(jìn)路中的同區(qū)段道岔相連，則帶動(dòng)該道岔至定位。若該道岔定位和進(jìn)路中的同區(qū)段道岔相連，則帶動(dòng)該道岔至反位。

5 結(jié)束語

用上述方法實(shí)現(xiàn)的聯(lián)鎖表自動(dòng)生成邏輯，能夠滿足聯(lián)鎖表自動(dòng)生成的很大一部分需求。對(duì)于一些用戶的特殊需求，例如進(jìn)路外道岔按照帶動(dòng)道岔還是防護(hù)道岔做邏輯、調(diào)車進(jìn)路是否需要包含最后一個(gè)無岔區(qū)段、進(jìn)路的可用性等，都可以在人機(jī)配置界面中人工修改，以滿足客戶的特殊需求。聯(lián)鎖表生成的判定條件可以進(jìn)行特殊拓展，滿足特定條件下的特殊需求。相關(guān)程序已經(jīng)在實(shí)際的項(xiàng)目中得到應(yīng)用，該邏輯能夠遍歷站場(chǎng)中的所有基本進(jìn)路，滿足無遺漏、無重復(fù)的目標(biāo)，用戶只需要通過確認(rèn)生成數(shù)據(jù)內(nèi)容，最終通過軟件導(dǎo)出標(biāo)準(zhǔn)聯(lián)鎖表和聯(lián)鎖軟件使用的二進(jìn)制數(shù)據(jù)。數(shù)據(jù)生成的便利性、準(zhǔn)確性、數(shù)據(jù)來源的統(tǒng)一性得到用戶贊賞。