基于A*搜索算法的城軌聯鎖系統仿真研究

張銘瑤 ，向美柱

（西南交通大學 信息科學與技術學院，成都 611756）

計算機聯鎖系統是城市軌道交通控制系統的重要子系統，它控制著站場進路中信號機、道岔和軌道電路之間的安全關系，以確保行車安全。隨著城市軌道交通控制系統的智能化發展，對聯鎖系統的要求越來越高，聯鎖軟件中進路搜索方法和效率也成為重要的研究課題。現有的計算機聯鎖系統采用的進路搜索方法主要有進路表式搜索方法[1]、帶導向標志的搜索方法[2]、深度優先搜索算法[3]、廣度優先搜索算法[4]以及二叉樹遍歷[5]等，這些方法相對成熟，但搜索效率卻不高。基于進路表的搜索方法由人工編制聯鎖表，工作繁復，容易出錯；基于算法的進路搜索可以用于進路表自動生成工具，幫助自動生成進路表，再人工校對，從而提高進路表生成效率[6]。基于傳統算法的搜索多數情況會遍歷進路上所有分支，在站場復雜時會搜索到很多擴展節點，增加了程序執行時間。本文將A*搜索算法應用到聯鎖進路搜索過程中，利用啟發信息指導搜索，使搜索沿著目標方向進行，避免盲目性搜索，從而提高搜索效率。

1 聯鎖數據結構

1.1 城軌站場的圖結構

圖1是西南交通大學城市軌道交通控制實驗室地鐵1號線的局部信號平面布置圖，軌道電路、信號機和道岔這3類信號設備是聯鎖進路上的主要設備。

如果把信號機、軌道電路和道岔看成一個個設備節點，那么根據它們之間的位置關系就可以將各設備節點連接起來，構成設備節點圖[7]，拓撲結構圖，如圖2所示。

圖1 157站-西山梁站信號平面布置圖

圖2 拓撲結構圖

拓撲結構圖是由頂點（圖2中用藍色圓表示）和邊（兩個頂點間的連接線）構成的圖結構，其中，頂點為3種類型的信號設備，邊用來表示頂點之間的連接關系。基于這種圖結構，可以構建站場型數據結構來存儲各信號點的信息。

1.2 基于鏈表的站場型數據結構

所謂站場型數據結構，就是把每個設備對象看成一個個節點，然后依據其在信號平面布置圖的位置來構建設備節點圖，節點在圖中的位置與實際站場圖中設備的位置相對應[8]。每個設備節點都由兩部分組成：數據域（Data標記區域）和指針域（Prev表示前向指針，Next表示后向指針），具體結構設計，如圖3所示。

圖3 信號設備節點結構

其中，數據域用來存放該節點設備的數據屬性，指針域用來存儲該節點與相鄰節點的連接關系，根據節點類型來確定指針數目。對于信號機和軌道電路，其前方或者后方最多與一個設備存在連接關系，因此其前向指針和后向指針各設置一個即可；對于道岔，其前方或者后方可能與一個或兩個信號設備有連接，因此需要為其設計兩個前向指針和兩個后向指針。

為了方便站場中進路的雙向搜索，采用基于雙向鏈表的存儲結構來構建站場型數據結構。根據各設備節點在信號平面布置圖中的位置關系將各設備節點通過指針連接起來[9]，構建如圖4所示的基于雙向鏈表的站場型數據結構圖，通過指針可以實現進路的雙向搜索。

圖4 基于雙向鏈表的站場型數據結構圖

2 進路搜索算法的設計

2.1 進路搜索算法比較

目前，應用較為廣泛的基于圖的進路搜索算法主要有深度優先搜索算法、廣度優先搜索算法和啟發式搜索算法。

（1）深度優先搜索算法是一種盲目搜索算法，搜索沿著狀態空間的某一條單一路徑從起點開始向下搜索，只有當搜索到一個沒有后繼節點的節點時，才考慮替代路徑。其缺點是，搜索深度可能無限深，或者深度超出可能的深度范圍。為了避免這種情況，使用深度優先搜索時往往給定一個深度界限，任何節點只要達到這個界限，就視為沒有后繼節點處理。但即使規定了深度界限，深度優先搜索也不能保證一定找到最優路徑。

（2）廣度優先搜索也是盲目搜索算法，搜索以接近起始節點的程度為依據來擴展節點，搜索是逐層進行的。相比深度優先，廣度優先搜索可以保證只要存在最優路徑就一定可以搜索到。但對于結構復雜、擴展節點相對較多的鐵路站場來說，廣度優先并不是一種好的選擇。

（3）啟發式搜索利用啟發信息來指導搜索過程，不斷地將當前節點的估價值與其他節點的估價值進行比較，并對待擴展節點進行排序，然后選擇最有希望的節點進行擴展。相比于盲目搜索，啟發式搜索沿著目標方向擴展節點，能夠減少大量的搜索路徑，使搜索更加高效。本文采用啟發式搜索算法中的A*搜索算法進行進路搜索。

2.2 A*搜索算法

A*搜索算法利用啟發函數來決定待擴展節點，基本思想如下：

（1）假定存在啟發函數f(n)，并且可以通過f(n)確定下一步要擴展的最佳節點，由于f(n)表示起始節點到目標節點的接近程度，因此f(n)越小表示找到的節點狀態越好。

（2）選取f(n)最小的節點作為下一步要擴展的節點，假設可以產生這個擴展節點的全部后繼節點。

（3）直到下一個待擴展節點是目標節點時搜索結束。

A*搜索算法是一種最佳優先搜索算法，其特點在估價函數的定義上，為此需要重新定義A*搜索算法的估價函數f*(n)，如式（1）：

其中，f(n)—啟發函數，表示從起始節點經由節點n到達目標節點的最優路徑代價；g(n)—表示從起始節點到當前節點n的實際代價；h(n)—表示從當前節點n到達目標節點的最優路徑的估計代價值；

f*(n)—f(n)的某個估值，起始節點經由中間節點n到目標節點的估計代價；

g*(n)—g(n)的某個估值，起始節點到當前節點n的最優路徑的估計代價；

h*(n)—h(n)的某個估值，從當前節點n到達目標節點的最優路徑的估計代價。

式中，當g(n)≥g*(n)時，隨著算法執行到深層將會獲得更多的搜索信息，兩者的數值也會越來越接近，直到兩者數值相等找到最優路徑。如果對A*搜索算法估計函數中的啟發函數h(n)進行限制，使其滿足h*(n)≤h(n)，稱h*(n)是可采納的，此時只要存在最優解就一定可以找到該解。

2.3 A*搜索算法在進路搜索中的具體設計

2.3.1 A*搜索算法搜索策略

A*搜索算法使用open和closed列表來維護狀態。open表用來記錄已計算出估價值的待考察的節點，closed表用來記錄已經訪問過得節點。相比盲目搜索，A*搜索算法新增加的一步就是對open表中的節點狀態進行排序，排序依據起始節點到目標節點的接近程度的估價值。這樣，每一輪循環中open列表中都保存的是最有希望的節點。需要注意的是，每一個狀態節點都保留其祖先節點的信息，這樣做的目的：（1）可以隨時比較當前路徑是否是最佳路徑；（2）可以利用這些信息返回最終搜索到的路徑[10-11]。

C#中的List類是一種很好的用來存儲數組數據的列表，該類可以根據需求來動態地分配存儲空間，而且List類自帶添加、刪除、查找等方法，使用起來很方便，因此，open表和closed表均使用List類存儲。

2.3.2 啟發函數的設計

A*搜索算法利用啟發函數來決定下一步要擴展的節點，啟發函數直接影響搜索效率的，因此，啟發函數的設計在A*搜索算法中至關重要。

對于城軌鐵路站場，其結構相對簡單，節點設備幾十到幾百不等，搜索寬度不大，每個節點的后繼擴展節點至多只有兩個，每個節點設備在站場中位置相對固定，可以考慮采用歐幾里得距離來計算h(n)的值，但在遇到對向道岔時，還要考慮直股優先/彎股優先問題，因此給h(n)增加縱向分量，在遇到對向道岔時，會比較分岔處的兩節點的估價值，來指導搜索方向[12-13]。假設計算從起始節點S(xs, ys)到目標節點E(xe, ye)的估價值，設搜索過程中當前節點為n，坐標為（xn, yn），則對搜索過程中任意節點n的估價函數h(n)如式（2）：

式中， M—權值系數。

最終，確定啟發函數f(n)，如式（3）：

2.3.3 A*搜索算法流程圖設計

A*搜索算法的一般步驟為：

（1）把起始節點S存入open表中，將closed表置空。（2）重復以下過程，直到找到目標節點。如果open表為空，則宣告失敗。（3）選取open表中估價值最小的節點min作為最優節點，并將其存入closed表中。（4）如果min就是目標節點，那么成功搜索到目標節點，結束搜索。（5）如果min不是目標節點，則擴展其后繼節點ptemp，并存儲到open表中。（6）計算估價值f(n)，轉（2）。

將A*搜索算法應用到進路搜索中，實際上是在A*搜索算法的基礎上加入城軌聯鎖的檢查條件，這里，主要是檢查搜索到的進路是否被占用。擴展節點時，通過始終端信號機節點的坐標先后位置來確定搜索方向，并結合節點類型和后繼節點的估價值來確定待擴展節點。考慮到搜索到的節點可能存在被占用的情況，該模塊中設計了一個存儲關鍵道岔節點的容器，若搜索到的節點被占用，則回退到最新存儲的道岔節點，沿其另一個子節點方向繼續搜索可替代進路。搜索流程，如圖5所示。

3 聯鎖仿真平臺的功能需求及模塊設計

搭建城軌聯鎖仿真平臺，主要功能包括：進路控制、道岔控制、信號機控制和軌道區段控制等。其中，進路控制是計算機聯鎖的核心功能，基于A*搜索算法的進路搜索模塊就是實現該功能的關鍵。考慮到操作人員可能希望看到A*搜索算法的搜索過程，仿真平臺要求顯示搜索過程中訪問到的節點。

根據仿真平臺的功能需要，將聯鎖功能劃分為3個主要模塊：

（1）站場初始化模塊：存儲各信號設備節點初始的相關信息，并將設備節點以鏈表的形式連接起來。（2）進路處理模塊：主要實現進路的選排（進路搜索）、進路鎖閉、進路解鎖以及道岔單獨操縱等功能。（3）命令顯示模塊：主要用于輸出當前執行的命令、錯誤提示信息以及進路搜索過程中搜索到的節點信息等。

聯鎖仿真平臺模塊結構圖，如圖6所示。

4 進路搜索測試

圖5 A*搜索算法流程

圖6 聯鎖仿真平臺模塊圖

在仿真平臺上進行進路選排測試，順序按下始終端信號機按鈕，檢查聯鎖條件后可對進路預選排，對選排成功的進路命令顯示區給出搜索過程中訪問的所有節點。經多次反復測試，選排進路過程中搜索到的節點基本上為進路上的節點，有效地避免了訪問到過多的擴展節點，從而提高了進路搜索效率。圖7為測試的兩條進路，選排成功后進路鎖閉，始端信號機開放。

圖7 進路選排測試

5 結束語

進路搜索是聯鎖系統的核心模塊，直接影響著進路控制的效率和正確性，因此進路搜索方法的效率至關重要，本文將A*搜索算法應用到進路搜索中，在算法中加入聯鎖條件的檢查，另外，考慮到搜索到的節點可能存在被占用情況，在算法中對關鍵道岔節點進行存儲，一旦搜索到的節點被占用，就會回退到關鍵道岔節點沿另一方向搜索。經過聯鎖仿真系統上進行驗證，該方法可以快速、準確地搜索到聯鎖進路，有效減少了搜索過程中擴展節點數目，能夠提高進路搜索效率。

[1]朱 怡. 基于計算機聯鎖的進路表搜索生成系統的設計與實現[D]. 上海：上海交通大學，2012.

[2]王文波 ，馬學霞. 鐵路車站計算機聯鎖軟件進路搜索算法研究[J]. 鐵路計算機應用，2016，25（4）：63-66.

[3]胡 媛，魏宗壽. 采用DFS策略的進路搜索算法研究[J]. 鐵路計算機應用，2007，16（9）：4-6.

[4]高利民，李文慧，孫 慧. 雙向廣度搜索算法在聯鎖進路自動生成中的應用[J]. 鐵路計算機應用，2007，16（5）：43-45.

[5]陳志穎，董 昱，楊 柳，等. 計算機聯鎖進路搜索算法的分析與研究[J]. 鐵道通信信號，2007（4）： 4-6.

[6]陳 光，楊 揚. 計算機聯鎖系統進路表自動生成算法[J].鐵路計算機應用，2015，24（5）：5-8.

[7]徐 鑫，陳光武. 計算機聯鎖軟件設計及進路搜索算法的研究與應用[J]. 鐵路計算機應用，2011，20（1）：49-52.

[8]文武臣，王曉明. 計算機聯鎖的數據結構及進路搜索算法[J].重慶工學院學報：自然科學版， 2008（6）：51-53.

[9]吳益芳. 進路搜索數據結構與算法研究[J]. 鐵路通信信號，2010，46（8）： 34-36.

[10]蔡自興，徐光祐. 人工智能及其應用[M]. 北京： 清華大學出版社，2010：63-75.

[11]羅 兵，梨花嵩，李敬民. 人工智能原理及應用[M]. 北京：機械工業出版社，2011：170-188.

[12]梁藝凡，譚 麗，馮 挺. A*進路搜索算法的研究與實現[J]. 鐵道標準設計，2013（2）：117-119+127.

[13]宋 巖. 基于A-Star算法的進路搜索研究[D]. 成都：西南交通大學， 2014.