基于二維坐標(biāo)信息進(jìn)路搜索算法研究

謝 林，楊 揚(yáng)

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

基于二維坐標(biāo)信息進(jìn)路搜索算法研究

謝 林，楊 揚(yáng)

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

二維坐標(biāo)信息進(jìn)路搜索算法，運(yùn)用CAD提取各個(gè)節(jié)點(diǎn)坐標(biāo)的思路，從有向圖的角度對進(jìn)路進(jìn)行研究，通過面向?qū)ο蟮乃枷雽⒏鱾€(gè)節(jié)點(diǎn)連接起來形成站場型數(shù)據(jù)結(jié)構(gòu)，以此為基礎(chǔ)設(shè)計(jì)出一套通用進(jìn)路搜索程序，能夠快速高效地搜到目標(biāo)節(jié)點(diǎn)，提高進(jìn)路搜索效率。

坐標(biāo)；CAD；有向圖；面向?qū)ο?/p>

隨著鐵路運(yùn)輸?shù)目焖侔l(fā)展，計(jì)算機(jī)聯(lián)鎖技術(shù)已廣泛運(yùn)用于車站信號控制領(lǐng)域。其主要功能是處理進(jìn)路內(nèi)的道岔、信號機(jī)和軌道電路之間的安全聯(lián)鎖關(guān)系，在保證安全的前提下提高運(yùn)輸效率。

進(jìn)路搜索是計(jì)算機(jī)聯(lián)鎖的核心部分，搜索時(shí)間的長短直接影響了進(jìn)路控制的正確性、安全性和高效性。目前運(yùn)用廣泛的進(jìn)路搜索算法主要有采用帶導(dǎo)向標(biāo)志和優(yōu)先策略的傳統(tǒng)搜路法，改進(jìn)的深度優(yōu)先、廣度優(yōu)先搜索和Dijkstra 算法，以及相關(guān)理論研究采用二叉樹遍歷進(jìn)行搜索[1]，實(shí)驗(yàn)證明，上述搜索算法在功能上基本能滿足要求，但是搜索的時(shí)間冗余度太大，多數(shù)情況下會遍歷所有分支，程序執(zhí)行時(shí)間較長。本文在分析鐵路車站信號特性的基礎(chǔ)上，利用CAD2013對車站進(jìn)行建模，并設(shè)計(jì)程序提取各個(gè)節(jié)點(diǎn)的坐標(biāo)信息，利用面向?qū)ο笏枷脒B接信號設(shè)備，形成靜態(tài)數(shù)據(jù)庫。在前期準(zhǔn)備的基礎(chǔ)上，提出基于坐標(biāo)信息的進(jìn)路搜索算法，把其應(yīng)用到實(shí)際搜索過程中，能夠全面高效地完成進(jìn)路的搜索。

1 站場型數(shù)據(jù)結(jié)構(gòu)建模

利用站場型數(shù)據(jù)結(jié)構(gòu)，在辦理一條進(jìn)路時(shí)，根據(jù)下發(fā)的進(jìn)路操作命令，如果符合操作要求，便為進(jìn)路搜索程序指明進(jìn)路的始端模塊首址和終端模塊的首址，立即啟動進(jìn)路搜索程序，從站場型數(shù)據(jù)結(jié)構(gòu)中搜出與進(jìn)路有關(guān)的全部模塊，再從模塊中找出進(jìn)路聯(lián)鎖程序所需的數(shù)據(jù)，就可以構(gòu)成進(jìn)路表[2]。圖1為某鐵路車站局部信號平面布置圖，可以看出，鐵路車站站場是由多個(gè)信號設(shè)備按照一定的順序鏈接起來。在實(shí)際建模過程中，對應(yīng)每一個(gè)信號、道岔、區(qū)段設(shè)計(jì)一個(gè)靜態(tài)數(shù)據(jù)庫，按照6502電氣集中組合排列中順序構(gòu)建相鄰各個(gè)模塊之間的連接關(guān)系，將圖1中相鄰的模塊進(jìn)行連接，形成相應(yīng)的站場型數(shù)據(jù)結(jié)構(gòu)。結(jié)果如圖2所示。

為了能將各個(gè)模塊鏈接起來，方便進(jìn)路搜索程序進(jìn)行搜索，將每個(gè)模塊空間進(jìn)行擴(kuò)展，分成數(shù)據(jù)場和指針場兩部分，用數(shù)據(jù)場存放相應(yīng)的數(shù)據(jù)，指針場存放該模塊的首地址，利用雙向鏈表將各個(gè)模塊鏈接起來[3]。對于區(qū)段和信號機(jī)，只涉及到兩個(gè)搜索方向(假設(shè)從左往右搜索為正方向)，一般設(shè)置兩個(gè)指針場，前向節(jié)點(diǎn)prev和后項(xiàng)節(jié)點(diǎn)next，對于道岔區(qū)段，它有3個(gè)鏈接節(jié)點(diǎn)，為了方便形成雙向鏈表，并在搜索時(shí)不會出現(xiàn)死循環(huán)，需設(shè)4個(gè)指針場，岔前節(jié)點(diǎn)prev，岔后節(jié)點(diǎn)next和正向搜索彎股節(jié)點(diǎn)pfz和反向搜索彎股節(jié)點(diǎn)pfw。連接結(jié)果如圖3和圖4所示。其中，實(shí)線箭頭表示正方向連接，虛線箭頭表示反方向連接，當(dāng)指針沒有連接對象時(shí)指向NULL。

圖1 某鐵路車站局部信號平面布置圖

圖2 站場型數(shù)據(jù)結(jié)構(gòu)圖

如果在站場圖中有超限絕緣區(qū)段，必須檢查超限絕緣。對于交叉渡線，按照6502的設(shè)計(jì)理念，當(dāng)一組道岔動作在反位時(shí)必須將另一組道岔防護(hù)在正位，因此在連接過程中將兩個(gè)道岔組合的位置換過來，可以防止在搜索過程中漏掉需要防護(hù)道岔對應(yīng)的軌道區(qū)段。

站場模型建好以后需要用CAD對各個(gè)節(jié)點(diǎn)的坐標(biāo)信息進(jìn)行提取，以便完成靜態(tài)數(shù)據(jù)庫。為了方便節(jié)點(diǎn)坐標(biāo)的存儲，設(shè)計(jì)一段簡單的LISP程序語言，自動地將提取的坐標(biāo)信息保存在Excel表格中。

圖3 各模塊之間的連接關(guān)系（下接圖4）

圖4 各模塊之間的連接關(guān)系（上接圖3）

2 進(jìn)路搜索算法設(shè)計(jì)

2.1 進(jìn)路搜索目標(biāo)及任務(wù)

一條進(jìn)路是由若干個(gè)信號機(jī)、道岔、軌道區(qū)段組成的列車在車站內(nèi)運(yùn)行時(shí)所經(jīng)過的路徑。進(jìn)路的始終端是由始端按鈕和終端按鈕決定，一條完整的進(jìn)路必須搜索出進(jìn)路上所有有關(guān)的信息，包括進(jìn)路類型、進(jìn)路方向、經(jīng)過的道岔、占用的軌道區(qū)段、敵對信號機(jī)和防護(hù)信號機(jī)。根據(jù)按下的始終端按鈕，判斷按鈕是否能配對，形成有效的輸入，然后根據(jù)輸入進(jìn)行搜索。

2.2 搜索策略分析

輸入正確的始終端信息后，理論上可以形成多條搜索路徑，如何少走分支，快速有效地找到最佳的搜索路徑是問題研究的關(guān)鍵。其中最主要的影響因素取決于道岔節(jié)點(diǎn)，在搜索過程中遇到對向道岔，將會出現(xiàn)兩個(gè)搜索方向，如果能快速地確定搜索方向就會在很大程度上節(jié)省程序執(zhí)行時(shí)間，提高運(yùn)行效率。

2.3 搜索策略設(shè)計(jì)

車站信號平面布置圖主要反映了站場線路的布置，接發(fā)車的方向和主要信號設(shè)備的名稱與位置。可以將道岔和信號機(jī)節(jié)點(diǎn)抽象為圖的頂點(diǎn)，那么軌道區(qū)段就成為連接這些頂點(diǎn)的邊，因此整個(gè)站場圖就可以抽象成一幅有方向的平面圖。在定義靜態(tài)數(shù)據(jù)結(jié)構(gòu)時(shí)，在數(shù)據(jù)場里定義一個(gè)點(diǎn)類的成員變量，用來記錄當(dāng)前節(jié)點(diǎn)在站場的二維坐標(biāo)信息，那么對于特定的一條進(jìn)路，根據(jù)按下的始終端按鈕對應(yīng)的坐標(biāo)信息就可以形成一個(gè)有向線段，唯一確定一個(gè)搜索方向。避免了不必要的分支搜索，節(jié)省程序執(zhí)行時(shí)間。

設(shè)vi為一條進(jìn)路的始端節(jié)點(diǎn)，對應(yīng)的坐標(biāo)為（xi, yi），目標(biāo)節(jié)點(diǎn)為vj，對應(yīng)的坐標(biāo)為（xi, yi），vk為若干中間節(jié)點(diǎn)，對應(yīng)的坐標(biāo)為（xk, yk）。首先判斷xi和yi的大小，確定搜索方向，若xi＜yi，則為正向搜索，若 xi＞yi為反向搜索。當(dāng)遇到道岔時(shí)（此時(shí)xk為道岔），判斷該道岔是順向道岔還是對向道岔，若為順向道岔，搜索方向不變，直股搜索。若為對向道岔，比較yk與yj的大小，同時(shí)為了避免搜出八字迂回進(jìn)路，若yk＞yj并且道岔為捺型道岔，或者yk＜yj并且道岔為撇型道岔，彎股搜索，其余情況搜索方向不變都為直股搜索。搜索流程如圖5所示。

圖5 二維坐標(biāo)信息算法搜索流程圖

特殊情況下：

（1）如果要選擇變通進(jìn)路，根據(jù)要求必須指明變更點(diǎn)，因此可以將變通進(jìn)路分解成兩步來搜索。

（2）對于有通過進(jìn)路的車站，如果要用一次辦理的方法（按下通過按鈕，再按下始端按鈕）辦理通過進(jìn)路，根據(jù)兩個(gè)按鈕的坐標(biāo)信息，在程序內(nèi)部自動轉(zhuǎn)換成分段辦理的操作方法由遠(yuǎn)及近的排出發(fā)車進(jìn)路和接車進(jìn)路。以圖2的站場型模型為例：

（1）當(dāng)排列一條S3到4G的接車進(jìn)路時(shí)，根據(jù)始端按鈕LAS3和終端按鈕LAX4的坐標(biāo)信息，可以唯一地確定一條搜索路徑。

（2）排列一條SLII到X10的通過進(jìn)路，自動轉(zhuǎn)換成由SLII-XII的接車進(jìn)路和從SII-X10的發(fā)車進(jìn)路。

（3）2G占用時(shí)，排列SI到D2的變通進(jìn)路，指明變更點(diǎn)為D6或者X10，搜索過程可以分解成兩步來處理。如圖6所示。

圖6 不同情形下的搜索策略

2.4 算法性能分析

傳統(tǒng)的搜索策略中主要運(yùn)用深度或者廣度優(yōu)先搜索方法對節(jié)點(diǎn)進(jìn)行遍歷，為了減少搜索次數(shù)需要對某些道岔設(shè)置導(dǎo)向標(biāo)志，一次搜索到達(dá)死節(jié)點(diǎn)時(shí)需要返回上一次搜索到的道岔位置，重新進(jìn)行搜索。因此需要不停地記錄前一道岔的位置。這種思想在一定程度上可以避免多余分支的搜索，但是仍然不可避免地浪費(fèi)許多不必要的搜索時(shí)間，節(jié)點(diǎn)存儲情況復(fù)雜，而且需要設(shè)置很多中間變量記錄道岔位置，程序設(shè)計(jì)相對復(fù)雜。與之相比較，基于二維坐標(biāo)信息的搜索算法在時(shí)間冗余度和程序設(shè)計(jì)的簡便性上有很大的提高。

2.4.1 時(shí)效性高

傳統(tǒng)的搜索算法不可避免地要經(jīng)過很多分支，以圖1站場為例，排列由SLII到4G的一條接車進(jìn)路，此時(shí)vi為SLII的節(jié)點(diǎn)，vj為S4的節(jié)點(diǎn)，傳統(tǒng)的搜索方法至少要搜索3次，由SLII到SI，SII或者SII， S3,最后才到S4，顯然搜索時(shí)間很長，而基于二維坐標(biāo)信息的進(jìn)路搜索算法根據(jù)始端節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)的位置以及道岔的類型，可以直接確定遇到道岔時(shí)搜索直股還是彎股，一次性搜到目標(biāo)節(jié)點(diǎn)，時(shí)效性非常高。

2.4.2 程序設(shè)計(jì)簡單

基于二維坐標(biāo)信息的進(jìn)路搜索程序可以一次性搜到目標(biāo)節(jié)點(diǎn)，不需要設(shè)置大量的中間變量來記錄道岔位置，同時(shí)它幾乎不會出現(xiàn)搜到死節(jié)點(diǎn)的情況，因此可以對搜索到的節(jié)點(diǎn)類型直接進(jìn)行壓棧操作，形成進(jìn)路表，而傳統(tǒng)的搜索程序會出現(xiàn)搜到死節(jié)點(diǎn)的情況，何時(shí)才能進(jìn)行節(jié)點(diǎn)的壓棧操作需要額外的寫附加程序進(jìn)行判斷，程序設(shè)計(jì)相對復(fù)雜。

3 結(jié)束語

二維坐標(biāo)信息的進(jìn)路搜索算法時(shí)效性較高，極大地節(jié)省了程序搜索時(shí)間，能夠有效地避免搜到死節(jié)點(diǎn)，使程序一次性搜到目標(biāo)節(jié)點(diǎn)，得到需要的進(jìn)路信息，對其進(jìn)行壓棧操作。由于程序設(shè)計(jì)的通用性，通過接口，以vs2010為開發(fā)平臺，為后期研究車站聯(lián)鎖表自動生成有很好的指導(dǎo)意義。

[1]梁藝凡，譚 麗，馮 挺.A*進(jìn)路搜索算法的研究與實(shí)現(xiàn)[J].鐵道標(biāo)準(zhǔn)設(shè)計(jì)，2013（2）.

[2]胡 媛，魏宗壽.采用DFS策略的進(jìn)路搜索算法研究[J].鐵路計(jì)算機(jī)應(yīng)用，2007，16（9）：4-6.

[3]楊 揚(yáng).車站信號控制系統(tǒng)[M].成都：西南交通大學(xué)出版社，2012.

[4]Oytun Eris,Ilhan Mutlu.Design of Signal Control Structures Using Formal Methods for Railway Interlocking Systems[C].11th International Conference on Control, Automation, Robotics and Vision，2010.

責(zé)任編輯 方 圓

Two-dimensional coordinate information based Route Searching Algorithm

XIE Lin, YANG Yang
( School of Information Science Technology, Southwest Jiaotong University, Chengdu 611756, China )

The two-dimensional coordinate information of the Route Searching Algorithm could be used to extract the coordinates of each node with CAD, study the route from the angle of directed graph, connect various nodes to form a data structure of station type through the object-oriented thought, on this basis, design a set of general route search procedure, which was able to search to the target node highly effective, and greatly improve the eff i ciency of route searching.

coordinate; CAD; directed graph; object-oriented

U29∶TP39

A

1005-8451（2015）08-0016-04

2014-12-16

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

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