梁藝凡，譚麗，馮挺

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

1 概述

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

2 A*算法

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

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

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

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

f′(n)——起始節(jié)點經(jīng)由n到目標節(jié)點的估計代價；

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

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

h′(n)——n到目標節(jié)點的最優(yōu)路徑的估計代價；

h(n)——n到目標節(jié)點的最優(yōu)路徑的實際代價。

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

3 基于A*算法的進路搜索策略

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

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

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

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

3.2 數(shù)據(jù)結構的實現(xiàn)

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

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

3.3 A*進路搜索算法的搜索流程

進路搜索程序需要完成的具體任務如下：

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

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

(3)若能建立進路，在與該進路有關的所有變量模塊中設置占用標志，即鎖閉敵對進路；

(4)指明與進路相關道岔的位置；

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

設起始節(jié)點為S，目標節(jié)點為M，X為搜索中遇到的任意節(jié)點，搜索范圍為：{xM

圖1 A*進路搜索算法搜路流程

4 實驗及算法性能分析

4.1 實驗平臺搭建

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

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

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

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

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

圖3 進路表窗口

4.2 算法性能分析

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

(1)有效性

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

(2)高效性

圖4 兩種算法多次辦理同一進路的時間曲線

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

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

圖5 兩種算法辦理多條進路的時間曲線

(3)占用空間

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

(4)可靠性

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

(5)通用性

傳統(tǒng)搜路法和A*搜路算法均基于站場型數(shù)據(jù)結構，修改容易，可移植性強；通過對多個不同的站場圖進行實驗，用A*搜路算法均能準確的搜出所需基本進路，其通用性得到了驗證。

5 結論

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

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

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

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

[4] 王曉明，郭進，姚琨嵐.鐵路車站信號選路中圖論應用的研究[J].鐵道學報，1989，11(2):52-57.

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

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

[7] 王瑞峰.鐵路信號運營基礎[M].北京:中國鐵道出版社，2008:85-93.

[8] Michael MAIN， Walter SAVITCH.數(shù)據(jù)結構與面向對象程序設計[M].劉東，張麗，譯.北京:清華大學出版社，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.