基于拓撲圖論策略的城市軌道交通信號設備布置方法研究

萬 霞，王長林

(西南交通大學 信息與科學技術學院，成都 610031)

近年來，伴隨著我國城市化進程的加快以及經濟的高速發展，城市人口快速增長，城市規模日益擴大，許多大城市的地面交通己經無法適應日益增長的客運需求。由于城市軌道交通系統具有快速、便捷、大運量的特點，因此許多城市己經確定了以軌道交通作為公共交通骨干的戰略。

城市軌道交通信號項目實施過程中，由于信號設備量大，程序繁瑣，大大降低了進度。因此，設計具有針對性的信號設備應用模型在城市軌道交通中起著非常重要的作用，直接影響著工程的效率。

本文通過分析和研究各個信號設備之間的關系，并結合拓撲圖論的相關策略，建立城市軌道交通信號設備基礎線路數據的拓撲結構，方便后續拓展應用功能的開發和研究。

1 圖論拓撲結構

圖論通過將具體事物抽象成圖形的形式來描述具有某種關系的系統，并根據圖的性質進行分析，提供研究各種系統的巧妙方法。本文采用矢量圖形拓撲結構組織信號設備和線路數據信息，如圖1所示，使圖元數據的層次性更強，對圖元的操作也變得容易很多。

在解圖論問題的算法中，經常需要從圖的某一點出發，系統訪問圖的其余頂點，且使每一個頂點最多被訪問一次，這一過程稱為圖的搜索。圖的搜索是人工智能中一種重要而且有力的解決問題的方法。最典型的圖搜索方法有3種[3]。包括：寬度優先搜索，深度優先搜索，啟發式搜索。

2 城市軌道交通信號設備應用模型

2.1 圖元化處理

圖元化處理是將現實存在的需要處理的事物，抽象成具有某些特殊屬性的圖元來表示和處理。

此處以信號機為例說明。信號機是指引列車在線路上運行的主要信號設備，機車上的司機根據信號機的不同顯示來決定列車是否可以前行、前行的速度級別。將信號機實體用函數對象來進行定義和實現，在城市軌道交通中信號機分為單顯示信號機、三顯示信號機和虛擬信號機共3種類型。其圖元化處理后的圖形表示圖如圖2所示。

圖2 信號機圖元化處理

圖元化處理不僅僅是完成了各種信號設備的圖元表示，還包括對各種圖形設備的快速創建、復制、粘貼、刪除等基本的操作功能。

2.2 基于矢量圖形拓撲結構的信息數據模型

結合圖論和拓撲結構理論，本文采用的信息數據模型是根據地鐵站場平面特性，將地理信息系統（GIS—Geographic Information System）數據模型進行平面化處理，構建地鐵信號設備系統的信息數據模型。

本文根據車站站場圖將各個常量模塊聯結起來就形成了站場形數據結構圖。本文測試站段線路數據結構圖如圖3所示。

圖3 線路信息數據結構圖

圖3中的數據模塊為節點，節點與節點之間的聯結為鏈接。以K(n)作為節點的代號，其中 是相應監控對象的名稱。之后添加的信號設備對象都會依附在這些節點上，再增加一個位置偏移量來區別相對位置和關系，這樣形成一個完整的信息系統。

因此，構建的線路數據拓撲結構主要包括：軌道區段信息、道岔區段信息和它們的連接關系。其中，軌道區段信息和道岔區段信息是用節點來表示的，它們的連接關系是用線來表示的，線路信息數據結構本質上是節點的鏈接表，如圖4所示。

圖4 數據模塊的鏈接圖

根據節點鏈接圖就可以生成站場形數據結構。每個節點所占區域劃分成數據場df和指針場 pf兩部分。數據場存放該節點的常量，指針場存放相鄰節點首地址。指針場定義了兩個指針sp和xp，sp表示上行方向上該節點的后輩節點首地址，xp表示下行方向上該節點的后輩節點首地址，當沒有鄰節點時即沒有后輩節點的節點，則在相應的指針場中記入“0”。對于道岔節點來說，有3個指針場：

（1）岔前指針場，用來存放岔前鄰節點的首地址；

（2）岔后直股指針場，用來存放岔后直股鄰節點的首地址；

（3）岔后彎股指針場，用來存放岔后彎股鄰節點的首地址。

2.3 基于拓撲圖論搜索的設備布置模型

根據拓撲圖論的思想，將信號設備數據結構與線路拓撲數據關聯。將信號設備數據放到線路拓撲數據結構中，在節點數據中包含道岔，在邊數據結構中包含信號機、計軸、應答器等。基于拓撲圖論搜索的設備布置模型是城市軌道交通信號設備應用模型的核心，模型結構圖如圖5所示。

圖5 基于拓撲圖論搜索的設備布置模型

2.3.1 基于矢量拓撲結構的遍歷搜索

根據信號設備布置模型的要求，需查找到布置設備約束條件中的特定信號設備。為了解決這個問題，在圖論的算法中選擇了圖的搜索算法。

在一個圖G中搜索算法的基本思路：從一個頂點v1開始，給它一個“標記”，N(v1)。然后給v1的鄰點標記，再給它的鄰點的鄰點標記，如此等等。最典型的搜索方法有3種，即深度優先搜索（DFS）、廣度優先搜索（BFS）和啟發式搜索（HS）。

根據之前建立的信息數據拓撲結構，本文結合了廣度優先搜索BFS和啟發式搜索HS來設計搜索算法，基本思想是：從v0開始，依次訪問v0的所有鄰點v1，v2，…，vl，然后依次訪問與v1鄰接的所有頂點，已經訪問過的頂點不再訪問，依次繼續搜索，直到所有的頂點都被訪問為止[1]；當搜索到某個節點時，進行條件布置判斷，若成立，則搜索周圍的設備，再進一步進行條件判斷。

本文采用的搜索算法步驟如下：

由線路數據拓撲結構信息得到數據結構圖G每個頂點對象的鄰接表L(v)，建立一個先進先出的表（隊列）Q：

（1）T←φ，對所有的點 v∈V，N(v)←0 ，Q ← 0 ，i← 0 ，N(v)← 1 。

（2）對L(v)的每個頂點u，如都有N(u) ≠0。則轉(4)，否則轉下一步。

（3）L(v)中存在頂點u，使N(u)←0，則T←T∪{v, u}，Q←Q∪{ u}，i←i+1，N(u)←i=n–1，轉 (2)。

（4）若i+1或Q為空，停止，否則從Q中取排頭元素u，在Q中刪除u，v←u，轉(2)。

算法中，N(v)表示v的標號，即v被訪問的順序號。T表示輸出的圖。

當T中得到訪問點時，再進行啟發式搜索（HS）判斷是否滿足信號設備布置原則，若滿足則插入新設備對象到信息數據庫中。

2.3.2 信號設備布置原理分析

信號設備布置原理分析是模型的重要部分，也是工作量最大的部分。在此部分將對需要布置的全部信號設備逐個進行條件分析，然后確定是否滿足布置的要求。以信號機為例簡要說明布置原理分析。

信號機的布置與停車點、計軸、道岔、車擋和防護門等因素相關聯。實際應用時信號機的布置需遵循設備數量最少化原則。信號機布置規則簡表如表1所示。

表1 信號機布置實現

2.4 基于圖搜索的進路生成模型

在矢量拓撲理論的基礎上可以拓展更多的應用，如完成更多設備的自動布置功能、聯鎖進路表的生成功能、仿真實現功能等。以進路表的生成為例說明拓展應用的開發和研究的方便性。

此模型的核心是進路搜索模塊，進路搜索算法流程圖如圖6所示。

進路搜索模塊的其任務是根據進路表名稱從站場形數據結構中選出與該進路有關的節點及確定進路中各道岔應處的位置，然后將各節點的數據及道岔位置信息構成該進路的“暫態進路（數據）表”，作為后續聯鎖程序使用。

圖6 進路搜索算法流程圖

3 模型仿真與驗證

案例采用某實際地鐵站的信息，在Visual 2010仿真平臺上，對以上所建的城市軌道交通信號設備應用模型進行仿真和驗證。軟件實現過程中，編程完成的主要工作如表2所示。

案例中，根據拓撲圖論的理論思想，為了反映對象之間的關系，首先對地鐵站所涉及的研究對象進行圖元化處理，實現了軌道區段、道岔、信號機、計軸等研究對象的定義，并完善了這些對象的操作功能。

在基于拓撲結構的信息數據模型的基礎上，就可以按照規定的形式建立和完善地鐵站線路基本信息。信息輸入的方法可以分為2種：

表2 編程實現功能表

（1）根據界面的圖元快捷工具，繪制線路基礎數據信息；

（2）按照規定的形式將線路基礎數據信息寫成txt文件，系統將根據文件信息自動繪制線路基礎站場信息。

3.1 基于拓撲圖論搜索的信號設備布置

案例中要完成主要信號設備布置，首先需按照設定的格式輸入一些必要信息，如根據屬性框提示輸入道岔屬性信息如圖7所示。

圖7 編輯道岔屬性框圖

根據信息數據模型相關處理后，完成基于拓撲圖論搜索的設備布置，其仿真結果圖如圖8所示。

圖8 信號設備布置結果圖

分析仿真結果可知，通過此模型有效的實現了主要信號設備如信號機、計軸、應答器等的自動布置。布置結果和工程中手動設計的布置圖誤差很小，且通過系統可以手動來調整這些特殊情況下的設備布置。由此可見，采用圖論和拓撲結構處理數據后，可以在較短的時間內，較容易的實現復雜的信號設備布置關系。

3.2 進路信息Excel表生成

將城市軌道交通信息數據通過圖元化處理，以模塊的形式進行操作，再將各個模塊之間的關系采用拓撲結構組織，建立信息模型后，便于進行多種功能的擴展，如進路表。生成進路信息Excel表時，需要完善信號機的屬性，如圖9所示。

完善各個信號機的屬性后，經過基于圖搜索的進路生成模型，自動生成進路信息Excel表的仿真結果如圖10所示。

圖9 完善信號機屬性圖

圖10 進路信息Excel表圖

進路信息Excel表列舉了所有進路，并明確的反映了每一條進路所對應的設備的具體狀態。查看進路信息Excel表可知，由于城市軌道交通和大鐵站點的區別，使得進路信息Excel表與以往大鐵聯鎖表的表示方法具有很大區別。模型生成的進路信息Excel表更能明確的反映地鐵中重要的聯鎖邏輯關系。

4 結束語

本文通過對各個信號設備的研究，將拓撲圖論的相關策略運用到信號設備布置模型中，在較短的時間內實現了信號設備布置和進路信息Excel表生成，有效的減輕了信號項目實施者的工作強度。通過對實際地鐵站的仿真和驗證，說明了模型的可行性。因此基于圖論拓撲結構的城市軌道交通信號設備應用模型可以大大降低人力成本，提高工程的實施效率，模型具有一定的應用價值。

[1]龔 劬.圖論與網絡最優化算法[M].重慶：重慶大學出版社，2009：18-30.

[2]陸小紅．鐵路信號微機聯鎖仿真系統設計[D].成都：西南交通大學，2010.

[3]左淑利，吳芳美.基于圖搜索策略的車站運行仿真命令集的自動生成算法[J].上海鐵道大學學報．1999，20（2）.