蔣文燕

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

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

1 基于二叉樹的進(jìn)路搜索算法及研究

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

1.1.1 站場信號設(shè)備的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

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

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

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

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

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

圖3 站場二叉樹模型

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

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

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

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

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

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

1.2.1 搜索策略分析

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

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

1.2.2 搜索約束條件

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

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

圖5 搜索方式判定流程圖

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

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

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

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

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

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

正向進(jìn)路搜索流程圖如圖6所示，逆向進(jìn)路搜索流程圖如圖7所示。

圖6 正向進(jìn)路搜索流程圖

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

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

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

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

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

按照人機(jī)界面的設(shè)計(jì)原則，用shape、line、image分別表示信號機(jī)、軌道、道岔，每個(gè)信號機(jī)旁設(shè)計(jì)一個(gè)按鈕。因?yàn)椴捎昧硕鏄涞乃阉厮惴?，所以將信號機(jī)、道岔和軌道都在公共模塊中定義成了節(jié)點(diǎn)。

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

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

圖7 逆向進(jìn)路搜索流程圖

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

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

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

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

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

圖9 軟件工作流程

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

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

2.4.3 進(jìn)路搜索模塊

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

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

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

圖11 進(jìn)路元素條件檢查程序流程圖

2.4.4 進(jìn)路執(zhí)行模塊

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

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

2.4.5 進(jìn)路解鎖模塊

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

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

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

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

3 結(jié)束語

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

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

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

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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