聯(lián)鎖進(jìn)路敵對(duì)信號(hào)的搜索算法設(shè)計(jì)

1、212計(jì)算機(jī)測(cè)量與控制.2009.17(1Computer Measurement &Control 設(shè)計(jì)與應(yīng)用收稿日期:2008205211;修回日期:2008206212?；痦?xiàng)目:國(guó)家自然科學(xué)基金資助項(xiàng)目(60674042。作者簡(jiǎn)介:祝庚(19752,男,湖南衡陽(yáng)人,講師,博士生,主要從事計(jì)算機(jī)控制技術(shù)、混合控制系統(tǒng)設(shè)計(jì)等方向的研究。文章編號(hào):167124598(20090120212203中圖分類號(hào):TP27315文獻(xiàn)標(biāo)識(shí)碼:A聯(lián)鎖進(jìn)路敵對(duì)信號(hào)的搜索算法設(shè)計(jì)祝庚1,2(11東莞理工學(xué)院軟件學(xué)院,廣東東莞523808;21華南理工大學(xué)自動(dòng)化科學(xué)與工程學(xué)院,廣東廣州510640摘要:分析了

2、鐵路信號(hào)計(jì)算機(jī)聯(lián)鎖系統(tǒng)中進(jìn)路敵對(duì)信號(hào)的定義及處理生成問(wèn)題,借助聯(lián)鎖進(jìn)路表闡述了敵對(duì)信號(hào)與進(jìn)路搜索之間的約束關(guān)系;結(jié)合站場(chǎng)有向圖和鄰接矩陣,利用數(shù)學(xué)圖論知識(shí),提出了一種進(jìn)路敵信號(hào)搜索算法和k 步進(jìn)路擴(kuò)散生成算法,給出了算法步驟流程并通過(guò)類C 語(yǔ)言實(shí)現(xiàn)算法全過(guò)程。算法在實(shí)際工程項(xiàng)目中進(jìn)行了應(yīng)用,并對(duì)實(shí)際的站場(chǎng)實(shí)例進(jìn)行了算法仿真模擬,提供了部分鐵路站場(chǎng)進(jìn)路和敵對(duì)信號(hào)實(shí)例數(shù)據(jù)。關(guān)鍵詞:聯(lián)鎖進(jìn)路表;敵對(duì)信號(hào);代價(jià)矩陣;站場(chǎng)拓?fù)鋱DDesign of Search Algorithm in Interlock Route s H ostile SignalZhu Geng 1,2(11Software Co

3、llege ,Dongguan University of Technology ,Dongguan 523808,China ;21College of Automation Science and Engineering ,South China University of Technology ,Guangzhou 510640,China Abstract :This paper analyzes t he definition of route s hostile signal and t he problem to dispose or generate it in railway

4、 signal computer interlock system.Wit h t he interlock route ,it expounds t he restriction relationship between hostile signal and route searching.Using direc 2tional graph of t he railway station and mat hematic knowledge of t heory of graph and adjacency matrix ,a k 2steps route s hostile signal s

5、earch algorit hm and a k 2steps route pervasion generating algorit hm are put forward ,whose processing flows are given out and are realized by a com 2puter language like C.The algorit hms are applied in material project s and simulated by an instance of a practice railway station.At last ,a part of

6、 instance data of railway station route and it s hostile signal are given out wit h t his algorit hm.K ey w ords :interlock route ;hostile signal ;cost matrix ;topology graph of railway station0引言鐵路信號(hào)計(jì)算機(jī)聯(lián)鎖控制系統(tǒng)應(yīng)確?？刂普緢?chǎng)進(jìn)路中的道岔、信號(hào)機(jī)、軌道電路之間的安全聯(lián)鎖關(guān)系,其主要實(shí)現(xiàn)的聯(lián)鎖運(yùn)算功能和操作有進(jìn)路選路、進(jìn)路開(kāi)放、轉(zhuǎn)岔、一致性檢查、人工解鎖與取消、故障(區(qū)段解鎖等6502電氣集中

7、的重要功能1。進(jìn)路敵對(duì)信號(hào)生成是生成進(jìn)路的前提和約束條件,因此提出一種敵對(duì)信號(hào)搜索算法和與此對(duì)應(yīng)的k 步進(jìn)路生成算法流程,并在參加開(kāi)發(fā)的HJ 04A 鐵路信號(hào)聯(lián)鎖系統(tǒng)中進(jìn)行了應(yīng)用。1敵對(duì)信號(hào)處理111敵對(duì)信號(hào)的定義敵對(duì)信號(hào)是指在本進(jìn)路建立后不能用道岔位置區(qū)分的,同時(shí)建立會(huì)危及行車安全的進(jìn)路2。通常所填的敵對(duì)信號(hào)為這些不得建立的進(jìn)路的始端信號(hào),敵對(duì)信號(hào)描述還包括:敵對(duì)進(jìn)路性質(zhì)即以敵對(duì)信號(hào)為始端的進(jìn)路是列車進(jìn)路還是調(diào)車進(jìn)路;道岔位置是指以敵對(duì)信號(hào)為始端的進(jìn)路要求道岔在所寫(xiě)位置時(shí)才屬敵對(duì)進(jìn)路。聯(lián)鎖進(jìn)路中對(duì)應(yīng)的敵對(duì)信號(hào)是其他同時(shí)要運(yùn)行的進(jìn)路的敵對(duì)信號(hào),它的敵對(duì)信號(hào)并集成為其他待生成進(jìn)路的約束非擴(kuò)展節(jié)點(diǎn)

8、,否則生成的進(jìn)路將與敵對(duì)信號(hào)對(duì)應(yīng)的進(jìn)路互為敵對(duì)進(jìn)路而危害行車安全。在HJ04A 工程應(yīng)用中,許多設(shè)備和邏輯結(jié)構(gòu)均采用簡(jiǎn)單的文件結(jié)構(gòu)形式表示,進(jìn)路、信號(hào)機(jī)、道岔、軌道電路、敵對(duì)信號(hào)等重要結(jié)構(gòu)采用數(shù)據(jù)基來(lái)表示。例如,敵對(duì)信號(hào)數(shù)據(jù)基用二進(jìn)制文件格式DD 1DA T 表示,敵對(duì)表DD 包括的字段主要為信號(hào)機(jī)下標(biāo)列表|道岔列表(道岔編號(hào),道岔位置,進(jìn)路狀態(tài),|表示可選項(xiàng)。例如沒(méi)有敵對(duì)信號(hào)時(shí),信號(hào)機(jī)填-1、道岔填-1、道岔位置填-1。112敵對(duì)信號(hào)處理如果將站場(chǎng)信號(hào)機(jī)、道岔等設(shè)備抽象為圖的節(jié)點(diǎn),軌道、路段或區(qū)段抽象為連接節(jié)點(diǎn)的邊,站場(chǎng)拓?fù)鋱D可以轉(zhuǎn)化為網(wǎng)絡(luò)圖結(jié)構(gòu)3。同時(shí)可以充分利用成熟的圖論理論來(lái)解決進(jìn)路搜

9、索和敵對(duì)信號(hào)搜索問(wèn)題,并結(jié)合邊的運(yùn)行代價(jià)求解最優(yōu)化問(wèn)題。將站場(chǎng)分為不同的咽喉區(qū),如上行區(qū)、公共區(qū)和下行區(qū),這樣將整個(gè)站場(chǎng)對(duì)應(yīng)的無(wú)向圖簡(jiǎn)化為尺寸較小的有向圖減少算法計(jì)算的復(fù)雜性。值得注意的是進(jìn)路的方向性將直接影響到求解其對(duì)應(yīng)敵對(duì)信號(hào)的結(jié)果。求解咽喉區(qū)內(nèi)基本進(jìn)路的敵對(duì)信號(hào)時(shí),可以依次搜索和判斷進(jìn)路中的節(jié)點(diǎn)是否為其敵對(duì)信號(hào),并將其簡(jiǎn)化為對(duì)應(yīng)有向圖中敵對(duì)節(jié)點(diǎn)的搜索問(wèn)題。求解長(zhǎng)調(diào)進(jìn)路的敵對(duì)信號(hào)時(shí),考慮它是由若干個(gè)不同的基本進(jìn)路獨(dú)立組合連接而成,不妨設(shè)長(zhǎng)調(diào)進(jìn)路CDJL =JBJL1JBJL n ,則其敵對(duì)求解信號(hào)函數(shù)滿足DDXH (CDJL =DDXH (JBJL1DDXH (JBJL n 等式。因此下面

10、只考慮基本進(jìn)路生成及其敵對(duì)信號(hào)生成問(wèn)題,在建立進(jìn)路時(shí),需要利用進(jìn)路搜索算法進(jìn)行處理,并要求它不得與聯(lián)鎖進(jìn)路表中包含的多條同時(shí)段進(jìn)路互為敵對(duì)進(jìn)路,同時(shí)間段開(kāi)放的進(jìn)路在站場(chǎng)圖中不得交叉、重疊和共用相同道岔。通過(guò)利用相應(yīng)進(jìn)路敵對(duì)信號(hào)生成算法求解其對(duì)應(yīng)的敵對(duì)信號(hào),并將該進(jìn)路的詳細(xì)數(shù)據(jù)項(xiàng)添加到聯(lián)鎖進(jìn)路表中,而在某進(jìn)第1期祝庚:聯(lián)鎖進(jìn)路敵對(duì)信號(hào)的搜索算法設(shè)計(jì)213路計(jì)劃完成或取消后應(yīng)將其對(duì)應(yīng)聯(lián)鎖進(jìn)路表中的記錄調(diào)入歷史進(jìn)路表中生成日志文件,并且將對(duì)應(yīng)記錄從聯(lián)鎖表中刪除。113k步進(jìn)路搜索算法目前進(jìn)路搜索算法一般有深度優(yōu)先、廣度優(yōu)先及其他智能搜索算法,而且基于圖的進(jìn)路生成算法需要聯(lián)鎖進(jìn)路表的敵對(duì)信號(hào)作為約束必

11、要搜索條件,進(jìn)路搜索進(jìn)路初始節(jié)點(diǎn)到終端節(jié)點(diǎn)的可行通路或最優(yōu)通路。下面提出一種k步進(jìn)路擴(kuò)散搜索算法,并使用代價(jià)矩陣替代鄰接矩陣來(lái)產(chǎn)生優(yōu)化進(jìn)路,它的思想是基于邊的最小代價(jià)擴(kuò)散。算法從進(jìn)路始端沿其有向最小代價(jià)邊擴(kuò)散,有多條等值最小代價(jià)邊則同時(shí)擴(kuò)散,直至搜索到進(jìn)路終端或者無(wú)法擴(kuò)散時(shí)結(jié)束,算法具體搜索步驟如下所示4。Step1:一步搜索時(shí),從始端S尋找下一步的待搜索集SD1,令圖的一步已經(jīng)搜索點(diǎn)集為F1=S、對(duì)未搜索點(diǎn)集及權(quán)值矩陣進(jìn)行調(diào)整,其中Fi表示第i步的擴(kuò)散點(diǎn)集。Step2:二步搜索時(shí),令S P1=S D1-D,D為當(dāng)前聯(lián)鎖進(jìn)路表中的敵對(duì)信號(hào)并集,進(jìn)行集合差運(yùn)算是因?yàn)閿硨?duì)信號(hào)點(diǎn)不能再進(jìn)行繼續(xù)搜索,

12、否則將與該敵對(duì)節(jié)點(diǎn)對(duì)應(yīng)的進(jìn)路敵對(duì)。對(duì)S P1進(jìn)行優(yōu)化排序修正處理或不處理,并將結(jié)果賦值給二步擴(kuò)散點(diǎn)集F2,令F=F1F2,F為多步已搜索點(diǎn)集的并集。將所有本次進(jìn)行過(guò)擴(kuò)散邊的權(quán)調(diào)整為無(wú)窮大的數(shù)值避免下次重復(fù)擴(kuò)散,而對(duì)于F中沒(méi)有擴(kuò)散的邊對(duì)應(yīng)的權(quán)值減去本次擴(kuò)散消耗的最小代價(jià),說(shuō)明這些節(jié)點(diǎn)邊進(jìn)行了等待消耗。Step3:對(duì)F中的所有節(jié)點(diǎn)進(jìn)行類似Step1和Step2處理,得到第三步擴(kuò)散點(diǎn)集F3,令F=FF3,只所以對(duì)F而不是Fi進(jìn)行擴(kuò)散搜索,是因?yàn)樗惴ㄒ笠阉阉鼽c(diǎn)集均能夠按權(quán)值最小進(jìn)行發(fā)散性擴(kuò)散搜索,它采用一種從開(kāi)始點(diǎn)按權(quán)值量進(jìn)行發(fā)散搜索的方法,從而保證搜索進(jìn)路具有擴(kuò)散代價(jià)最優(yōu)性。Step4:進(jìn)行k步搜

13、索后,令F=FFk,若已搜索集F 中包含進(jìn)路目標(biāo)終端T,則計(jì)算S到T的所有路徑為可生成的進(jìn)路,有多條時(shí)可計(jì)算最優(yōu)進(jìn)路或作業(yè)調(diào)度計(jì)劃。若已搜索完站場(chǎng)拓?fù)鋱D或Fk為空集仍未尋找到T,則說(shuō)明當(dāng)前S與T 之間不存在可行的進(jìn)路,算法結(jié)束。值得注意的是在最小擴(kuò)散步數(shù)對(duì)應(yīng)的Fk中出現(xiàn)T時(shí),其對(duì)應(yīng)的進(jìn)路具有最小代價(jià)性,若要產(chǎn)生其他預(yù)備的進(jìn)路,算法仍然可以再擴(kuò)散多步來(lái)產(chǎn)生其他較高代價(jià)的進(jìn)路,從而為進(jìn)路調(diào)度提供更多的可行方案。2敵對(duì)信號(hào)的搜索生成算法211敵對(duì)信號(hào)生成算法設(shè)計(jì)根據(jù)進(jìn)路對(duì)應(yīng)的分區(qū)站場(chǎng)拓?fù)鋱D、進(jìn)路及車列狀態(tài)確定分區(qū)有向圖G,并產(chǎn)生對(duì)應(yīng)的鄰接矩陣A和代價(jià)矩陣W。進(jìn)路的結(jié)構(gòu)可采用鏈表和類等方法表示,其基本

14、進(jìn)路JBJL結(jié)構(gòu)主要包括進(jìn)路的始端信號(hào)機(jī)S、終端信號(hào)機(jī)T、進(jìn)路方向(進(jìn)站或出站Dir、經(jīng)過(guò)道岔列表J gDC、經(jīng)過(guò)區(qū)段列表J gQD、迎面進(jìn)路YmJL、進(jìn)路狀態(tài)(接、發(fā)及調(diào)車Flag等。求解敵對(duì)信號(hào)中需要判斷進(jìn)路中的節(jié)點(diǎn)是否為其他進(jìn)路的始端信號(hào)時(shí)利用過(guò)程IsStart XH,若始端信號(hào)為道岔時(shí)還要判斷其他進(jìn)路與本進(jìn)路是否共用了道岔,只有滿足條件的始端信號(hào)才為敵對(duì)信號(hào),通常用防護(hù)道岔路段的信號(hào)機(jī)表示其敵對(duì)信號(hào)。結(jié)合k步進(jìn)路搜索算法和圖論的一些基本知識(shí),下面提出一種聯(lián)鎖進(jìn)路敵對(duì)信號(hào)生成算法的搜索流程:Step1:確定基本進(jìn)路所在分區(qū)的有向圖G,鄰接矩陣A 和代價(jià)矩陣W,需要提供的站場(chǎng)設(shè)備數(shù)據(jù)基文件

15、包括道岔DD1DA T、信號(hào)機(jī)XHJ1DA T、區(qū)段QD1DA T文件,同時(shí)需要聯(lián)鎖進(jìn)路表L S。Step2:利用k步進(jìn)路搜索算法產(chǎn)生待求解敵對(duì)信號(hào)的進(jìn)路,求得基本進(jìn)路JBJL=ks_SearchJL(G,A,S,T,并產(chǎn)生進(jìn)路的區(qū)段列表、經(jīng)過(guò)道岔列表等數(shù)據(jù),若進(jìn)路為長(zhǎng)調(diào)進(jìn)路時(shí)則分解為若干個(gè)基本進(jìn)路,對(duì)各個(gè)基本進(jìn)路逐個(gè)進(jìn)行處理后取并集。Step3:根據(jù)進(jìn)路的方向和狀態(tài)修正分區(qū)的有向圖G和鄰接矩陣A及代價(jià)矩陣W,設(shè)初始進(jìn)路敵對(duì)信號(hào)集為空集,即DD=。從進(jìn)路始端開(kāi)始到終端結(jié)束,逐一調(diào)用IsStart XH判斷進(jìn)路節(jié)點(diǎn)是否為其他進(jìn)路的始端信號(hào),若是且其為信號(hào)機(jī)節(jié)點(diǎn)將其添加到DD中,若始端信號(hào)為道岔節(jié)

16、點(diǎn)則調(diào)用Is2 ShareDC為真,將其路段防護(hù)信號(hào)機(jī)添加到DD中,否則進(jìn)入下次循環(huán)。Step4:進(jìn)路的終端T是其迎面進(jìn)路信號(hào),需將其作為敵對(duì)信號(hào)處理,將其添加到DD中。Step5:令J L1D=DD,即DD為進(jìn)路J L的敵對(duì)信號(hào)集,并將進(jìn)路J L添加到聯(lián)鎖進(jìn)路表,令D=DJ L1D作為下次進(jìn)路生成的條件,其中D為聯(lián)鎖進(jìn)路表中進(jìn)路敵對(duì)信號(hào)的并集,算法結(jié)束。212算法類語(yǔ)言實(shí)現(xiàn)敵對(duì)信號(hào)搜索算法在實(shí)現(xiàn)時(shí)主要考慮下列的幾個(gè)過(guò)程或函數(shù),可以通過(guò)類C語(yǔ)言對(duì)它們進(jìn)行描述和實(shí)現(xiàn),具體描述如下5。21211判斷是否為敵對(duì)進(jìn)路始端信號(hào)IsStart XH(JBJL,Node,A/3JBJL為基本進(jìn)路,Node是

17、進(jìn)路中的節(jié)點(diǎn),A為鄰接矩陣3/Int rd=InDegree(Node,A;/計(jì)算節(jié)點(diǎn)的入度If(rd=1ruturn flase;elseruturn true;21212判斷是否為公用道岔IsShareDC(JBJL,Node,Aint num=0;int i=1;flag=flase;/若為道岔節(jié)點(diǎn)且為其他進(jìn)路始端信號(hào)if(IsStart XH(JBJL,Node,A=Trueand(Node is in JBJL1DC num=InDegree(JBJL,Node,A-1;/若有其他入分支while(i=num/搜索經(jīng)過(guò)Node的其他進(jìn)路JL T=SearchNext(Node,A;i

18、f(JL T1DCJBJL1DC/公用道岔flag=true;breakelsei+;return flag;elsereturn flase;21213求基本進(jìn)路ks_SelectJL(&G,W,S,T,JL/3G為有向圖、W為代價(jià)矩陣、S為始端、T為終端,JL為進(jìn)路列表3/214計(jì)算機(jī)測(cè)量與控制第17卷Init(G,L S,time;/初始化聯(lián)鎖進(jìn)路表If(S=-1or T=-1return-1;/始終端空則失敗F=S;/搜索初始值While(not T in F and i=limit step/搜索條件D=L SDD(L S;/取聯(lián)鎖進(jìn)路表敵對(duì)信號(hào)并SD=Search(G,A,F,W;

19、/下步待擴(kuò)散集SDSP=SD-D;/敵對(duì)節(jié)點(diǎn)不能擴(kuò)散SP擴(kuò)散尋找最小代價(jià)ci邊擴(kuò)散到FiIf(Fi=nullbreak;/不能擴(kuò)散則結(jié)束i+;/否則繼續(xù)擴(kuò)散F=FFi;/統(tǒng)計(jì)已擴(kuò)散集修正W,G中無(wú)擴(kuò)散邊代價(jià)減cicos t=cos t+ci;/修正總消耗代價(jià)JL=SearchLJ(F,S,T;/擴(kuò)散集中求k步最優(yōu)路徑修改道岔、信號(hào)機(jī)等設(shè)備狀態(tài)Chk Y iZhiXin(JL;/進(jìn)路一致性檢查OpenJL(JL;/開(kāi)放JL進(jìn)路ks_SearchDD(&G,JL,A;/求敵對(duì)信號(hào)AddL S(L S,JL/添加進(jìn)路到聯(lián)鎖表ReFresh Graph(G;/刷新站場(chǎng)圖形21214求進(jìn)路敵對(duì)信號(hào)ks_

20、SearchDD(&G,JL,A/DD=;/初始化敵對(duì)信號(hào)為空S=SearchStart(JL,A,&G;/求進(jìn)路始端T=SearchEend(JL,A,&G;/求進(jìn)路終端Node=SearchNext(JL,S;/S的后續(xù)節(jié)點(diǎn)While(NodeTif(IsStart XH(JL,Node,A=trueif(Node in JL1XHJ/若為信號(hào)機(jī)DD=DDNode;/Node為敵對(duì)信號(hào)/否則調(diào)用判斷是否公用道岔函數(shù)elseif(IsShareDC(JL,Node,A=ture/尋找其防護(hù)信號(hào)機(jī)F HXHJ=IsF HXHJ(JL.Node,G;DD=DDF HXHJ;/F HXHJ為敵對(duì)信

21、號(hào)Node=SearchNext(JL,Node;/尋找下一節(jié)點(diǎn)DD=DDT;/T為迎面敵對(duì)信號(hào)JL.D=DD;/求進(jìn)路敵對(duì)信號(hào)集return DD;/返回?cái)硨?duì)值3H J04A系統(tǒng)仿真HJ04A鐵路信號(hào)計(jì)算機(jī)聯(lián)鎖控制系統(tǒng)在揚(yáng)子石化、鞍鋼等企業(yè)鐵路站場(chǎng)得到了推廣應(yīng)用,它具有可靠的故障-安全性等特征6。下面以一下行咽喉區(qū)的站場(chǎng)拓?fù)鋱D來(lái)演示k步進(jìn)路搜索及敵對(duì)信號(hào)算法的應(yīng)用情況,站場(chǎng)情況如圖1所示。圖中以D、X或S開(kāi)頭的標(biāo)號(hào)為信號(hào)機(jī)名稱,例如SA、D2、X2,數(shù)字表示道岔編碼,如2/4為2號(hào)到4號(hào)道岔,以數(shù)字開(kāi)頭和G結(jié)尾的標(biāo)號(hào)為區(qū)段編號(hào),軌道上的豎線或斜線代表區(qū)段的分割線。圖1中SA到X2的進(jìn)路有3條

22、并且編號(hào)為101103,例如101號(hào)進(jìn)路順序經(jīng)過(guò)道岔3/4,2/5,(6,13,18/19,(表示道岔的反位,經(jīng)過(guò)區(qū)段為1DG,3-5DG,6-13DG,13 -19DG,2G,其接車進(jìn)路敵對(duì)信號(hào)D2,X2,而對(duì)應(yīng)反方向X2到SA發(fā)車進(jìn)路敵對(duì)信號(hào)D11,D3,D1,SA。咽喉區(qū)內(nèi)的調(diào)車進(jìn)路通常是某基本進(jìn)路的一段,其進(jìn)路搜索和敵對(duì)信號(hào)求解采用同樣的算法,例如X6到D4調(diào)車進(jìn)路經(jīng)過(guò)道岔(10,9,8,7,經(jīng)過(guò)區(qū)段為10DG,9-16DG,8DG,7-15DG,其敵對(duì)信號(hào)為D7,D6,D5,D4 。圖1HJ04A部分站場(chǎng)拓?fù)涫疽鈭D若站場(chǎng)已經(jīng)開(kāi)放了一些進(jìn)路,這時(shí)聯(lián)鎖進(jìn)路表中敵對(duì)信號(hào)較多,其他進(jìn)路在選擇時(shí)將以其敵對(duì)