蔣文燕

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

城市軌道交通聯(lián)鎖的主要功能是進路處理，該功能由聯(lián)鎖程序完成[1]。而聯(lián)鎖程序的復雜度和占用空間大小又很大程度上取決于聯(lián)鎖數(shù)據(jù)結(jié)構(gòu)。一個好的聯(lián)鎖數(shù)據(jù)結(jié)構(gòu)還能使各功能模塊化，簡化搜索流程，提高程序執(zhí)行效率。為了解決計算機聯(lián)鎖中進路搜索存在的時間復雜度和內(nèi)存利用問題,結(jié)合站場結(jié)構(gòu)，建立一個好的聯(lián)鎖數(shù)據(jù)結(jié)，簡化聯(lián)鎖程序，優(yōu)化聯(lián)鎖系統(tǒng)很有必要。目前，提出的有基于有向圖的數(shù)據(jù)結(jié)構(gòu)，二叉樹與四叉鏈表的結(jié)合結(jié)構(gòu)[2],有向無環(huán)圖與二叉樹結(jié)合的結(jié)構(gòu)[3]，基于鄰接表的圖形數(shù)據(jù)結(jié)構(gòu)[4]。目前，使用的聯(lián)鎖表型數(shù)據(jù)結(jié)構(gòu)，在車站規(guī)模較大時，占用內(nèi)存空間較大，增加程序執(zhí)行時間，不利于車站規(guī)模擴大。另一種站場型數(shù)據(jù)結(jié)構(gòu)，占用內(nèi)存空間較小，但為了避免搜出迂回進路和平行進路，在設(shè)計搜索算法時要設(shè)計相應的搜索條件，這又增加了搜索程序的復雜度。本文結(jié)合二叉樹的結(jié)構(gòu)特點，對站場型數(shù)據(jù)結(jié)構(gòu)做了改進，把站場中的信號機，道岔，軌道區(qū)段都作為二叉樹節(jié)點。這樣在進路搜索時可以通過對進路上信號機的檢查實現(xiàn)同向及反向敵對信號的檢查。同時還在二叉樹的節(jié)點中加入了指向前面節(jié)點的父輩指針，既可以從根節(jié)點采用先序遍歷方式搜索到目標節(jié)點，也可以沿著二叉樹中任一節(jié)點沿著父輩節(jié)點搜索到目標節(jié)點，實現(xiàn)進路的逆向搜索。

1 基于二叉樹的進路搜索算法及研究

1.1 城軌沙盤2號線金頂站站場建模

1.1.1 站場信號設(shè)備的網(wǎng)絡(luò)拓撲結(jié)構(gòu)

圖1所示為城軌實驗室軌道交通二號線金頂集中站的站場平面布置圖。設(shè)計線路時設(shè)定了運行方向（上行和下行方向），一般情況下，列車從上行線路進站，下行線路出站，但也可根據(jù)線路運行情況的需要，辦理反方向的列車作業(yè)。

圖1 金頂站信號平面布置圖

地鐵集中站控制的主要信號設(shè)備有信號機、轉(zhuǎn)轍機和軌道電路，在信號平面布置圖中有3種設(shè)備類型，信號機、道岔、軌道。結(jié)合前面對站場數(shù)據(jù)結(jié)構(gòu)的分析對金頂集中站信號設(shè)備進行有向無環(huán)圖建模，如圖2所示。

圖2 站場有向無環(huán)圖建模

通過上面建立的有向無環(huán)圖搜索進路較為復雜，觀察發(fā)現(xiàn)在不存在三開道岔或更為復雜的道岔時，有向無環(huán)圖中節(jié)點的度數(shù)最多二，這與二叉樹結(jié)構(gòu)存在相似性，所以選擇在有向無環(huán)圖中建立二叉樹。選擇進路的起點T0406（T0401）為根建立二叉樹，并作為當前節(jié)點，若當前節(jié)點的度數(shù)為2，那么第1 條弧所指向的頂點為其左孩子, 第2條弧所指向的頂點為其右孩子, 若當前結(jié)點的度數(shù)為1, 則弧所指向的頂點為其左孩子, 若當前結(jié)點的度數(shù)為0, 則其為葉子結(jié)點, 以此類推。以節(jié)點T0406和節(jié)點T0401為根節(jié)點分別建立了兩棵二叉樹，如圖3所示。

圖3 站場二叉樹模型

由于兩棵二叉樹在雙動道岔處相交，為了便于區(qū)分，所以將雙動道岔節(jié)點在兩棵樹中被定義成了Dbdc1和Dbdc2，節(jié)點數(shù)據(jù)完全相同，只是名稱不同。

從兩棵樹根節(jié)點到各葉子節(jié)點的所有路徑，也就是從洗象池站到金頂站折返線或停車線的所有路徑，這樣就將聯(lián)鎖程序中的進路搜索轉(zhuǎn)化成了二叉樹的遍歷了。

1.1.2 信號設(shè)備節(jié)點的數(shù)據(jù)結(jié)構(gòu)

二叉樹在存儲過程中，采用了鏈存儲結(jié)構(gòu)[5]。在站場的二叉樹模型中，每個信號設(shè)備都對應了一個二叉樹節(jié)點,每個節(jié)點都包含了數(shù)據(jù)域和指針域，因為涉及到逆向搜索，且在雙動道岔處會出現(xiàn)1個節(jié)點有2個父輩節(jié)點，所以其節(jié)點具體組成是由一個數(shù)據(jù)元素和4個指針元素構(gòu)成，4個指針元素分別指向其左右分支節(jié)點及左右父輩節(jié)點，所以表示二叉樹的鏈表至少有5個域：表示該設(shè)備屬性的數(shù)據(jù)域Nodedata、指向父輩節(jié)點的指針域Pleftparent、Prightparent和分別指向左右子節(jié)點的指針域Pleftchild、Prightchild，節(jié)點數(shù)據(jù)結(jié)構(gòu)，如圖4所示。父輩節(jié)點指針為前一節(jié)點的指針地址，根節(jié)點的父輩節(jié)點指針為空，除雙動道岔節(jié)點的Prightparent不為空外，其它節(jié)點的Prightparent為空，Pleftchild、Prightchild分別存儲該節(jié)點左右分支節(jié)點的指針地址，當節(jié)點不存在右孩子節(jié)點時，則Rightnode為空，葉子節(jié)點的左右子節(jié)點指針都為空。

圖4 站場二叉樹節(jié)點數(shù)據(jù)結(jié)構(gòu)

1.2 基于二叉樹的進路搜索算法設(shè)計

1.2.1 搜索策略分析

二叉樹的遍歷有遞歸和采用堆棧兩種，這里我們采用了堆棧的方式[6]。從起始節(jié)點開始按前序遍歷方式搜索，并將搜索到的節(jié)點壓入堆棧，當搜索到鄰站站臺對應的節(jié)點后則中止，將該條進路的所有元素寫入到數(shù)組中，直到搜索出以該節(jié)點開始的所有可用進路。

本文針對城軌實驗室二號線金頂集中站的線路情況，考慮到有接發(fā)車作業(yè)和進出折返線作業(yè)，所以設(shè)計了兩種搜索方式，正向搜索和逆向搜索。辦理金頂站的接車進路和進折返線進路以及進停止線進路時，采用正向搜索（上行方向）。其中，接車進路是以車站股道為終端節(jié)點，進折返線或停止線是以葉子節(jié)點為搜索的終端節(jié)點。辦理出折返線和發(fā)出進路時，則采用逆向搜索策略（下行方向）。這樣就需要在辦理進路時告訴搜索程序所辦理的進路類型，以便采用對應的搜索策略。

1.2.2 搜索約束條件

辦理進路后，從起始節(jié)點開始搜索，直到目標節(jié)點。通常都是將進路終端節(jié)點作為葉子節(jié)點，但在金頂站由于是站后折返，所以需要接車進站辦理乘客下車作業(yè)后才可進折返線。鑒于此種情況需要在股道節(jié)點處設(shè)置一個進路結(jié)束標志f。

出折返線、出停止線和發(fā)車作業(yè)都涉及到逆向搜索，這就需要在值班員按下始端按鈕后給出一個表示進路類型的信息，以便告訴程序該采取何種搜索方式。其邏輯流程圖，如圖5所示。

圖5 搜索方式判定流程圖

1.2.3 進路搜索算法

聯(lián)鎖表自動生成進路表的搜索算法是在啟動搜索程序后就將整個站場的所有進路搜索出來，并保存每條進路所征用元素，然后在排列進路時檢查改進路元素是否空閑，敵對進路是否建立。本文中提出的搜索算法的不同之處在于，它是在每次排列進路，車站值班員按下始端按鈕，啟動進路搜索程序，搜索出以該按鈕為始端的所有可用進路。在搜索時一旦檢查到某進路元素被征用或建立了敵對進路，則停止該條進路的搜索。若某進路可用，終端按鈕處閃爍，在值班員按下終端按鈕后，征用從始端到終端的進路元素，并開放始端信號機。

（1）搜索開始，根據(jù)始端按鈕確定進路搜索方向；

（2）建立兩個堆棧，S1和S2，S1用于保存進路搜索過程中的元素，S2用于保存對向道岔節(jié)點；

（3）按照先序遍歷方式搜索；

（4）搜索出該始端按鈕可排的所有可能進路，如果沒有進路可用，則取消，否則按壓終端按鈕，排列進路。

正向進路搜索流程圖如圖6所示，逆向進路搜索流程圖如圖7所示。

圖6 正向進路搜索流程圖

2 城軌沙盤聯(lián)鎖軟件設(shè)計與實現(xiàn)

2.1 聯(lián)鎖系統(tǒng)總體框架

聯(lián)鎖系統(tǒng)設(shè)計分為人機界面設(shè)計和聯(lián)鎖軟件設(shè)計。如圖8所示，為聯(lián)鎖系統(tǒng)的總體結(jié)構(gòu)圖。

聯(lián)鎖軟件的主要功能模塊有初始化數(shù)據(jù)、進路搜索、進路執(zhí)行、進路鎖閉、進路解鎖、模擬/現(xiàn)場切換、串口通信模塊[7-8]。

2.2 聯(lián)鎖系統(tǒng)人機界面的設(shè)計

按照人機界面的設(shè)計原則，用shape、line、image分別表示信號機、軌道、道岔，每個信號機旁設(shè)計一個按鈕。因為采用了二叉樹的搜素算法，所以將信號機、道岔和軌道都在公共模塊中定義成了節(jié)點。

在工程加載函數(shù)中加入對定義的節(jié)點并初始化，然后設(shè)置相關(guān)控件的屬性。

2.3 聯(lián)鎖軟件工作流程

圖7 逆向進路搜索流程圖

圖8 聯(lián)鎖系統(tǒng)總體框架圖

該聯(lián)鎖系統(tǒng)的主要功能是通過二叉樹的搜索算法完成進路的選排、進路鎖閉、列車通過后進路自動解鎖等功能。具體工作流程，如圖9所示。

2.4 聯(lián)鎖軟件各功能模塊實現(xiàn)

2.4.1 模擬/現(xiàn)場切換模塊實現(xiàn)

在登陸窗體的加載模塊中添加了一個用于區(qū)分是模擬模式還是現(xiàn)場模式的布爾型變量，當它為真時進入現(xiàn)場模式，為假則進入模擬模式。

圖9 軟件工作流程

2.4.2 數(shù)據(jù)塊實現(xiàn)

基于二叉樹的搜索算法將進路中的信號設(shè)備相關(guān)數(shù)據(jù)都按節(jié)點數(shù)據(jù)塊的形式定義在程序中。整個數(shù)據(jù)塊中各節(jié)點按鏈表的形式存儲在內(nèi)存中，其存儲在邏輯上是有序的，物理上是無序的。數(shù)據(jù)的訪問是按程序指令找到始端節(jié)點，訪問其數(shù)據(jù)域，然后根據(jù)節(jié)點中的指針地址去搜索該節(jié)點的下一節(jié)點并訪問。這里采用Varptr()函數(shù)獲取變量所在處的內(nèi)存地址，即獲得了指向變量內(nèi)存位置的指針。

2.4.3 進路搜索模塊

程序根據(jù)操作指令找到進路始端節(jié)點，從始端節(jié)點開始搜索，搜索到每個節(jié)點時，先檢查節(jié)點對應的設(shè)備控件是否處于空閑狀態(tài)，若滿足則通過節(jié)點的Leftnode找到其左子節(jié)點地址，然后使用Copymemery()函數(shù)找到其左節(jié)點，再檢查左節(jié)點是否滿足條件，在這個過程中，若出現(xiàn)不滿足條件的節(jié)點在，則跳出該條進路的搜索，返回到最近的分叉節(jié)點從右子節(jié)點搜索。搜索出的可用進路需要返回其進路終端節(jié)點地址，并保存該進路上的所有節(jié)點。整體程序思路設(shè)計，如圖10所示。

圖10 搜索模塊整體程序設(shè)計思路流程圖

搜索模塊需要完成進路建立條件檢查，其中包括進路是否空閑，道岔是否鎖閉在敵對位置，敵對信號是否開放，軌道區(qū)段是否被征用。檢查進路元素是否滿足進路建立原則程序設(shè)計流程，如圖11所示。

圖11 進路元素條件檢查程序流程圖

2.4.4 進路執(zhí)行模塊

進路執(zhí)行模塊的功能就是根據(jù)操作指令，按照值班員的意圖將進路上的道岔轉(zhuǎn)換到正確位置，并鎖閉進路，然后開放始端信號機。

由搜索模塊返回一個地址指針，按下終端按鈕啟動進路執(zhí)行模塊，在始終端都確定的情況下，修改軌道、道岔的表示及信號機的顯示，使進路設(shè)備都從空閑狀態(tài)變成鎖閉狀態(tài)。進路鎖閉后，延時10 s,在這10 s內(nèi)可以人工無延時解鎖進路。圖12是進路執(zhí)行模塊工作流程。

2.4.5 進路解鎖模塊

圖12 進路執(zhí)行模塊程序流程圖

進路解鎖分為列車通過后自動解鎖和人工解鎖兩種，這里自動解鎖分為分段解鎖和一次性解鎖，而人工解鎖又分為無延時解鎖和延時解鎖。分段解鎖只要列車每占用出清一個區(qū)段并占用下一區(qū)段后解鎖該區(qū)段；有延時解鎖是指在按下解鎖按鈕后檢查到列車已壓入接近軌，為保證安全，需要延時30 s確定列車未進入進路方可解鎖，若在這端時間內(nèi)列車已進入進路則進路無法解鎖。本設(shè)計中自動解鎖采用的是分段解鎖方式。

列車根據(jù)信號機顯示進入進路，列車壓入進路就關(guān)閉始端信號機，列車的運行由Timer()函數(shù)完成。根據(jù)列車位置程序?qū)⒘熊囌加貌⒊銮宓膮^(qū)段解鎖。由于界面設(shè)計上用的是Line、Shape、Image等控件表示的軌道、信號機、道岔，所以直接用這些控件的Bordercolor(fillcolor)的不同顏色來表示信號設(shè)備的不同狀態(tài)。進路解鎖模塊程序流程圖，如圖13所示。

圖13 進路解鎖模塊程序設(shè)計流程圖

3 結(jié)束語

搜索算法在聯(lián)鎖系統(tǒng)中是一個極其重要的部分，一個好的搜索算法不僅能提高程序訪問數(shù)據(jù)的效率，還能節(jié)省內(nèi)存空間。實現(xiàn)聯(lián)鎖程序與數(shù)據(jù)的獨立，簡化搜索程序，在保證安全的前提下有利于增強系統(tǒng)功能，提高系統(tǒng)工作效率。通過對基于二叉樹的城軌沙盤聯(lián)鎖系統(tǒng)的設(shè)計與實現(xiàn)，主要完成工作總結(jié)如下：

（1）對基于二叉樹的聯(lián)鎖系統(tǒng)進行了需求分析，提出了基于二叉樹的正向和逆向的進路搜索算法。構(gòu)造系統(tǒng)的整體結(jié)構(gòu)，并完成各功能模塊的設(shè)計；

（2）結(jié)合站場結(jié)構(gòu)和程序?qū)崿F(xiàn)的難易度，分析總結(jié)了不同數(shù)據(jù)結(jié)構(gòu)的優(yōu)缺點，提出二叉樹型的聯(lián)鎖數(shù)據(jù)結(jié)構(gòu)；

（3）對站場信號設(shè)備數(shù)據(jù)進行二叉樹建模，在VB軟件中完成了聯(lián)鎖系統(tǒng)人機界面的設(shè)計，實現(xiàn)相關(guān)聯(lián)鎖功能的設(shè)計。

參考文獻：

[1] 陳 璐. 城市軌道交通區(qū)域計算機聯(lián)鎖仿真系統(tǒng)研究[D]. 蘭州：蘭州交通大學，2013.

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

[3] 吳益芳. 進路搜索數(shù)據(jù)結(jié)構(gòu)與算法研究[J].鐵道通信信號，2010，46（8）：34-36.

[4] 彭建偉，殷人昆. 基于鄰接表結(jié)構(gòu)的進路搜索算法研究[J].計算機工程與設(shè)計，2006，27（18）：3400-3402.

[5] 徐紹軍.數(shù)據(jù)結(jié)構(gòu) [M].長沙：中南大學大學出版社，2004.

[6] 唐發(fā)根.數(shù)據(jù)結(jié)構(gòu)教程[M]. 2版.北京：北京航空航天大學出版社，2006.

[7] 謝 飛. 城市軌道交通沙盤車站聯(lián)鎖系統(tǒng)設(shè)計與實現(xiàn)[D].成都：西南交通大學，2013.

[8] 徐 鑫，陳光武.計算機聯(lián)鎖軟件設(shè)計及進路搜索的研究與應用[J].鐵路計算機應用，2011，20（1）：49-52.