梁藝凡，譚麗，馮挺

(1.蘭州交通大學(xué)自動(dòng)化與電氣工程學(xué)院， 蘭州 730070；2.廣州鐵路(集團(tuán))公司，廣東深圳 518000)

1 概述

計(jì)算機(jī)聯(lián)鎖系統(tǒng)是鐵路行車指揮的關(guān)鍵系統(tǒng)之一，有著保證行車安全和提高行車效率的重要作用，其主要功能是接受調(diào)度計(jì)劃進(jìn)行進(jìn)路控制，完成作業(yè)辦理。進(jìn)路搜索作為計(jì)算機(jī)聯(lián)鎖系統(tǒng)的核心模塊，直接影響了進(jìn)路控制的正確、安全、高效性。目前應(yīng)用于鐵路現(xiàn)場(chǎng)的計(jì)算機(jī)聯(lián)鎖系統(tǒng)有DS6-K5B、EI32-JD、HJ04A等，其進(jìn)路搜索方法主要采用帶導(dǎo)向標(biāo)志和優(yōu)先策略的傳統(tǒng)搜路法，改進(jìn)的深度優(yōu)先、廣度優(yōu)先搜索和Dijkstra算法，以及相關(guān)理論研究采用二叉樹(shù)遍歷進(jìn)行搜索等[1]。經(jīng)現(xiàn)場(chǎng)應(yīng)用發(fā)現(xiàn)，上述方法均搜索效率低、占用資源大。為了提高進(jìn)路辦理效率，本文研究采用A*算法搜索進(jìn)路。

2 A*算法

A*算法是用于求解靜態(tài)路網(wǎng)中最短路的智能算法，使用啟發(fā)函數(shù)對(duì)待擴(kuò)展節(jié)點(diǎn)進(jìn)行最優(yōu)選擇，使得所擴(kuò)展的節(jié)點(diǎn)少于其他同類搜索算法，因此更加高效，加之其啟發(fā)函數(shù)設(shè)計(jì)靈活，易于實(shí)現(xiàn)的特點(diǎn)，A*算法在智能交通、機(jī)器人路徑搜尋等方面有著廣泛應(yīng)用。車站信號(hào)平面布置圖按照接發(fā)車方向可以抽象為有向圖，應(yīng)用A*算法進(jìn)行路徑搜索是可行的。

A*算法在搜索時(shí)將當(dāng)前待擴(kuò)展節(jié)點(diǎn)保存在open列表中，對(duì)其按照啟發(fā)函數(shù)值進(jìn)行排序，選擇f值最小的節(jié)點(diǎn)壓入closed列表，并產(chǎn)生此節(jié)點(diǎn)的所有后繼壓入open中，作為下次的擴(kuò)展對(duì)象。在搜索中不斷更新open和closed列表，以確保當(dāng)前保存的是已擴(kuò)展的起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最優(yōu)路徑上的節(jié)點(diǎn)[2]。其啟發(fā)函數(shù)為

f′(n)=g′(n)+h′(n)

式中n——搜索中遇到的任意中間節(jié)點(diǎn)；

f′(n)——起始節(jié)點(diǎn)經(jīng)由n到目標(biāo)節(jié)點(diǎn)的估計(jì)代價(jià)；

g′(n)——起始節(jié)點(diǎn)到n的最優(yōu)路徑的估計(jì)代價(jià)；

g(n)——起始節(jié)點(diǎn)到n的最優(yōu)路徑的實(shí)際代價(jià)；

h′(n)——n到目標(biāo)節(jié)點(diǎn)的最優(yōu)路徑的估計(jì)代價(jià)；

h(n)——n到目標(biāo)節(jié)點(diǎn)的最優(yōu)路徑的實(shí)際代價(jià)。

當(dāng)h′(n)≤h(n)時(shí)，稱h′(n)是可采納的，此時(shí)搜索的點(diǎn)數(shù)多、效率低，但能確保得到最優(yōu)解(若存在最優(yōu)解)[3]。

3 基于A*算法的進(jìn)路搜索策略

3.1 啟發(fā)函數(shù)的設(shè)計(jì)

車站信號(hào)平面布置圖主要反映了站場(chǎng)線路的布置和接發(fā)車方向，以及主要信號(hào)設(shè)備的名稱編號(hào)和位置。若將道岔和信號(hào)機(jī)節(jié)點(diǎn)抽象為圖的頂點(diǎn)(道岔分岔前、岔后頂點(diǎn)，并置調(diào)車信號(hào)機(jī)用2個(gè)頂點(diǎn)表示)，軌道區(qū)段則成為連接這些頂點(diǎn)的邊。那么對(duì)于特定的接發(fā)車方向，可以將信號(hào)平面布置圖看作一個(gè)有向圖G[4]。G=(V，E)，其中V={v1，v2，…，vn}，為G中頂點(diǎn)的集合；E={e1，e2，…，en}，為G中邊的集合。

設(shè)vi為搜索中遇到的任意節(jié)點(diǎn)，坐標(biāo)為(xi，yi)；vj為目標(biāo)節(jié)點(diǎn)，坐標(biāo)為(xj，yj)。為了滿足h′(n)≤h(n)，保證算法的完備性和最優(yōu)性，將h′(n)的值定義為兩節(jié)點(diǎn)間的歐幾里得距離?？紤]到列車沿鋼軌直線走行的限制，令g′(vi)=4*abs(yi-yj)，增強(qiáng)優(yōu)先擴(kuò)展的節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)在同一股道的可能性。則啟發(fā)函數(shù)為：f′(vi)=g′(vi)+h′(vi)=sqrt((xi-xj)∧2+(yi-yj)∧2)+4*abs(yi-yj)。

根據(jù)所設(shè)計(jì)啟發(fā)函數(shù)的構(gòu)造特點(diǎn)，設(shè)K為G的距離矩陣，用于存儲(chǔ)G中所有節(jié)點(diǎn)兩兩間的f′(n)值。K滿足kij=d(vi，vj)，其中i≥0，j≤n-1；對(duì)于i=j，有kij=0；且滿足d(vi，vj)=d(vj，vi)，即kij=kji，K為對(duì)稱矩陣[5]。對(duì)待擴(kuò)展節(jié)點(diǎn)排序時(shí)，通過(guò)讀取K的部分值即可得到待擴(kuò)展節(jié)點(diǎn)的f′(n)值，總體上節(jié)省了程序執(zhí)行時(shí)間。

3.2 數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)

聯(lián)鎖程序需要大量的靜態(tài)數(shù)據(jù)為基礎(chǔ)，對(duì)數(shù)據(jù)庫(kù)的構(gòu)建，一般有進(jìn)路表型數(shù)據(jù)結(jié)構(gòu)和站場(chǎng)型數(shù)據(jù)結(jié)構(gòu)。進(jìn)路表型數(shù)據(jù)結(jié)構(gòu)的優(yōu)點(diǎn)是搜路方便，根據(jù)操作命令從總進(jìn)路表中選取即可；缺點(diǎn)是總進(jìn)路表編制繁瑣、容易出錯(cuò)，占用存儲(chǔ)空間大，修改困難[6]。站場(chǎng)型數(shù)據(jù)結(jié)構(gòu)的優(yōu)點(diǎn)是動(dòng)態(tài)生成進(jìn)路表，占用存儲(chǔ)空間小，容易修改；缺點(diǎn)是進(jìn)路辦理約束多，程序?qū)崿F(xiàn)復(fù)雜，搜索耗時(shí)多。

綜合兩者的優(yōu)點(diǎn)，當(dāng)由于平行渡線而產(chǎn)生多條進(jìn)路時(shí)，將確定的基本進(jìn)路編制成“基本進(jìn)路表”，再采用更適合A*算法的改進(jìn)的站場(chǎng)型數(shù)據(jù)結(jié)構(gòu)進(jìn)行其余進(jìn)路的搜索。在搜索時(shí)若判定始終端在基本進(jìn)路表中，則直接讀取進(jìn)路；否則采用A*搜路算法搜索進(jìn)路。這樣沖淡了上述兩種數(shù)據(jù)結(jié)構(gòu)各自的優(yōu)缺點(diǎn)，既簡(jiǎn)化了A*搜路算法程序，保留了站場(chǎng)型數(shù)據(jù)結(jié)構(gòu)的優(yōu)點(diǎn)，又僅是對(duì)基本進(jìn)路進(jìn)行進(jìn)路表編制，占用存儲(chǔ)空間較小。

3.3 A*進(jìn)路搜索算法的搜索流程

進(jìn)路搜索程序需要完成的具體任務(wù)如下：

(1)按下進(jìn)路始終端按鈕后只能選出一條基本進(jìn)路，要選擇變通進(jìn)路需人工按壓變通按鈕[7]；

(2)檢查所選出進(jìn)路的敵對(duì)進(jìn)路是否建立；

(3)若能建立進(jìn)路，在與該進(jìn)路有關(guān)的所有變量模塊中設(shè)置占用標(biāo)志，即鎖閉敵對(duì)進(jìn)路；

(4)指明與進(jìn)路相關(guān)道岔的位置；

(5)形成一個(gè)進(jìn)路表供聯(lián)鎖處理程序使用。

設(shè)起始節(jié)點(diǎn)為S，目標(biāo)節(jié)點(diǎn)為M，X為搜索中遇到的任意節(jié)點(diǎn)，搜索范圍為：{xM

圖1 A*進(jìn)路搜索算法搜路流程

4 實(shí)驗(yàn)及算法性能分析

4.1 實(shí)驗(yàn)平臺(tái)搭建

計(jì)算機(jī)聯(lián)鎖系統(tǒng)軟件用于實(shí)現(xiàn)人機(jī)界面信息處理、基本聯(lián)鎖控制及執(zhí)行、自動(dòng)檢測(cè)與診斷等功能。為方便實(shí)現(xiàn)，在保證核心功能的前提下，用Visual C++6.0進(jìn)行編程，實(shí)現(xiàn)了簡(jiǎn)化的計(jì)算機(jī)聯(lián)鎖軟件，設(shè)備狀態(tài)通過(guò)變量設(shè)置虛擬實(shí)現(xiàn)。通過(guò)此仿真軟件辦理列、調(diào)車進(jìn)路，驗(yàn)證A*進(jìn)路搜索算法的可行性；并在同一臺(tái)PC機(jī)上實(shí)現(xiàn)兩個(gè)聯(lián)鎖仿真軟件，兩者僅在進(jìn)路搜索程序上有所區(qū)別，分別使用A*搜路算法和傳統(tǒng)搜路法。編寫測(cè)試代碼分別對(duì)兩者的進(jìn)路辦理時(shí)間進(jìn)行測(cè)試顯示，比對(duì)算法效率。

對(duì)各設(shè)備的結(jié)構(gòu)體定義中，除了包括節(jié)點(diǎn)ID號(hào)、空間坐標(biāo)、左右節(jié)點(diǎn)ID號(hào)等體現(xiàn)鏈接關(guān)系的信息外，還要對(duì)其各種特性用“0”“1”碼分別描述，得出每個(gè)節(jié)點(diǎn)十六進(jìn)制的特性編碼，用來(lái)反映設(shè)備的狀態(tài)及確定所辦進(jìn)路性質(zhì)、能否建立進(jìn)路等。

對(duì)open列表采用最小二叉堆(class BinaryHeap)來(lái)實(shí)現(xiàn)，最小二叉堆很容易找到最小元素，并在移除最小元素時(shí)仍然保持為一個(gè)有效最小二叉堆[8]。將closed列表定義為一個(gè)一維變長(zhǎng)數(shù)組，用vector來(lái)實(shí)現(xiàn)。對(duì)矩陣K采用壓縮存儲(chǔ)的方法，只將K的下三角中的元素按行優(yōu)先的順序存儲(chǔ)在一個(gè)一維數(shù)組double heur[ ]中，讓每?jī)蓚€(gè)對(duì)稱的元素共享一個(gè)存儲(chǔ)空間，節(jié)約近一半的存儲(chǔ)空間。

實(shí)驗(yàn)界面如圖2所示，圖中白光帶表示已選出進(jìn)路，此時(shí)X4信號(hào)機(jī)開(kāi)放，亮綠燈。道岔狀態(tài)如圖左上角所示，進(jìn)路所經(jīng)過(guò)的道岔均已鎖閉，為紅燈。圖3為點(diǎn)擊菜單“進(jìn)路表”后彈出的窗口，記錄了所辦進(jìn)路的進(jìn)路表。實(shí)驗(yàn)證明，A*搜路算法能夠快速正確的搜出所需基本進(jìn)路，自動(dòng)生成進(jìn)路表。

圖2 聯(lián)鎖仿真軟件上位機(jī)顯示

圖3 進(jìn)路表窗口

4.2 算法性能分析

目前常用的幾種進(jìn)路搜索方法中，Dijkstra算法性能較好，傳統(tǒng)搜路法應(yīng)用最為廣泛。Dijkstra算法毫無(wú)選擇地向四周擴(kuò)展，遍歷計(jì)算的節(jié)點(diǎn)很多，搜索效率較低。若圖的節(jié)點(diǎn)數(shù)為n，邊數(shù)為m，邊的權(quán)值為c，搜索效率較高的基于Bucket優(yōu)先級(jí)隊(duì)列的Dijkstra算法的時(shí)間復(fù)雜度為O(m+nc)，而A*算法的時(shí)間復(fù)雜度為O(n′)，n′為A*算法搜索中擴(kuò)展的節(jié)點(diǎn)數(shù)，效率明顯優(yōu)于Dijkstra算法，且A*算法遍歷保存的節(jié)點(diǎn)數(shù)量不多，節(jié)省存儲(chǔ)空間[9]?，F(xiàn)將A*搜路算法與傳統(tǒng)搜路法從以下幾個(gè)方面進(jìn)行比較，詳細(xì)分析A*搜路算法的性能。

(1)有效性

傳統(tǒng)搜路方法經(jīng)過(guò)多年實(shí)踐驗(yàn)證，其有效性不言而喻。A*搜路算法使用歐幾里得距離作為估價(jià)值，必然小于或等于實(shí)際距離，滿足可采納性，能夠得到最優(yōu)解。且經(jīng)實(shí)驗(yàn)驗(yàn)證，A*搜路算法能夠搜出所需的基本進(jìn)路，證明了其可行與準(zhǔn)確，即有效。

(2)高效性

圖4 兩種算法多次辦理同一進(jìn)路的時(shí)間曲線

由于聯(lián)鎖軟件的高實(shí)時(shí)性，使用微秒級(jí)精確度的QueryPerformanceCounter函數(shù)來(lái)測(cè)試進(jìn)路辦理時(shí)間，為便于記錄，將換算結(jié)果換算為毫秒輸出。實(shí)驗(yàn)結(jié)果如圖4、圖5的MATLAB擬合曲線所示。圖4為多次辦理同一條進(jìn)路(D4-XⅠ)兩者的用時(shí)曲線；圖5為辦理多條不同進(jìn)路兩者的用時(shí)曲線。由圖4可見(jiàn)，傳統(tǒng)搜路法由于擴(kuò)展節(jié)點(diǎn)多，遍歷節(jié)點(diǎn)的累積時(shí)間差較大，相較之下，A*搜路算法的搜索時(shí)間更加穩(wěn)定。由圖5

可見(jiàn)，當(dāng)所辦進(jìn)路經(jīng)過(guò)多個(gè)對(duì)向道岔時(shí)，兩者時(shí)間相差較大，A*搜路算法效率明顯高于傳統(tǒng)搜路法；當(dāng)所辦進(jìn)路經(jīng)過(guò)對(duì)向道岔不多時(shí)，兩者時(shí)間相差不大，A*搜路算法效率仍然高于傳統(tǒng)搜路法；當(dāng)所辦進(jìn)路不經(jīng)過(guò)對(duì)向道岔時(shí)，兩者時(shí)間相差不大，A*搜路算法效率有時(shí)會(huì)低于傳統(tǒng)搜路法。由此可得，當(dāng)站場(chǎng)復(fù)雜，咽喉區(qū)道岔數(shù)量多，平行進(jìn)路多時(shí)A*搜路算法的高效性會(huì)更加突出；當(dāng)站場(chǎng)簡(jiǎn)單時(shí)，A*搜路算法較傳統(tǒng)搜路法高效性優(yōu)勢(shì)體現(xiàn)不大。

圖5 兩種算法辦理多條進(jìn)路的時(shí)間曲線

(3)占用空間

在靜態(tài)數(shù)據(jù)的存儲(chǔ)上，除了所需的共同基礎(chǔ)數(shù)據(jù)，傳統(tǒng)搜路法需要存儲(chǔ)道岔類型、渡線類型等數(shù)據(jù)，A*搜路算法需要存儲(chǔ)各節(jié)點(diǎn)f′(n)值，兩者相差不大；對(duì)于搜索過(guò)程中所產(chǎn)生的動(dòng)態(tài)存儲(chǔ)空間，傳統(tǒng)搜路法搜索時(shí)遍歷的節(jié)點(diǎn)數(shù)要多于A*搜路算法，在所辦進(jìn)路復(fù)雜時(shí)尤為明顯?？傮w來(lái)說(shuō)，A*搜路算法更加節(jié)省存儲(chǔ)空間。

(4)可靠性

一個(gè)有效的算法其可靠性要通過(guò)程序的完善和強(qiáng)壯性來(lái)實(shí)現(xiàn)，A*搜路算法的程序編寫還不夠精良，和已經(jīng)實(shí)際運(yùn)行很多年的傳統(tǒng)搜路法相比，A*搜路算法的可靠性還需要在實(shí)際應(yīng)用中不斷完善增強(qiáng)。但在滿足仿真實(shí)驗(yàn)平臺(tái)的需求上，A*搜路算法的可靠性已達(dá)到預(yù)期效果。

(5)通用性

傳統(tǒng)搜路法和A*搜路算法均基于站場(chǎng)型數(shù)據(jù)結(jié)構(gòu)，修改容易，可移植性強(qiáng)；通過(guò)對(duì)多個(gè)不同的站場(chǎng)圖進(jìn)行實(shí)驗(yàn)，用A*搜路算法均能準(zhǔn)確的搜出所需基本進(jìn)路，其通用性得到了驗(yàn)證。

5 結(jié)論

由于A*算法本身的高效性及啟發(fā)函數(shù)的設(shè)計(jì)而具有的完備性，使得其應(yīng)用于車站進(jìn)路搜索成為可能。經(jīng)實(shí)驗(yàn)驗(yàn)證和分析，采用滿足進(jìn)路搜索需求的A*算法能夠快速準(zhǔn)確的搜出所需基本進(jìn)路，動(dòng)態(tài)生成進(jìn)路表。綜合各種性能的優(yōu)劣，總體來(lái)說(shuō)，A*進(jìn)路搜索算法在很多方面都優(yōu)于或等同于傳統(tǒng)搜路法，而其不足之處在當(dāng)前的仿真實(shí)驗(yàn)環(huán)境下也能夠克服，達(dá)到了提高進(jìn)路辦理效率的目的。

[1] 文武臣，王曉明.計(jì)算機(jī)聯(lián)鎖的數(shù)據(jù)結(jié)構(gòu)及進(jìn)路搜索算法[J].重慶工學(xué)院學(xué)報(bào)：自然科學(xué)版，2008，22(6):51-53.

[2] George F.LUGER.人工智能[M].史忠植，等，譯.北京:機(jī)械工業(yè)出版社，2006:96-103.

[3] 劉浩，鮑遠(yuǎn)律.A*算法在矢量地圖最優(yōu)路徑搜索中的應(yīng)用[J].計(jì)算機(jī)仿真，2008，25(4):253-256.

[4] 王曉明，郭進(jìn)，姚琨嵐.鐵路車站信號(hào)選路中圖論應(yīng)用的研究[J].鐵道學(xué)報(bào)，1989，11(2):52-57.

[5] 李明哲.圖論及其算法[M].北京:機(jī)械工業(yè)出版社，2010.

[6] 趙志熙.計(jì)算機(jī)聯(lián)鎖系統(tǒng)技術(shù)[M].北京:中國(guó)鐵道出版社，2008.

[7] 王瑞峰.鐵路信號(hào)運(yùn)營(yíng)基礎(chǔ)[M].北京:中國(guó)鐵道出版社，2008:85-93.

[8] Michael MAIN， Walter SAVITCH.數(shù)據(jù)結(jié)構(gòu)與面向?qū)ο蟪绦蛟O(shè)計(jì)[M].劉東，張麗，譯.北京:清華大學(xué)出版社，2007:480-484.

[9] B V Cherkassky， A V Goldberg and Tomasz Radzik. Shortest paths algorithms: Theory and Experimental Evaluation[R]. Technical Report 9321480， Computer Science Department， Stanford University， 1993.