萬 霞，王長林

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

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

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

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

1 圖論拓撲結構

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

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

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

2.1 圖元化處理

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

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

圖2 信號機圖元化處理

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

2.2 基于矢量圖形拓撲結構的信息數(shù)據(jù)模型

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

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

圖3 線路信息數(shù)據(jù)結構圖

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

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

圖4 數(shù)據(jù)模塊的鏈接圖

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

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

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

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

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

根據(jù)拓撲圖論的思想，將信號設備數(shù)據(jù)結構與線路拓撲數(shù)據(jù)關聯(lián)。將信號設備數(shù)據(jù)放到線路拓撲數(shù)據(jù)結構中，在節(jié)點數(shù)據(jù)中包含道岔，在邊數(shù)據(jù)結構中包含信號機、計軸、應答器等?；谕負鋱D論搜索的設備布置模型是城市軌道交通信號設備應用模型的核心，模型結構圖如圖5所示。

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

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

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

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

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

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

由線路數(shù)據(jù)拓撲結構信息得到數(shù)據(jù)結構圖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中得到訪問點時，再進行啟發(fā)式搜索（HS）判斷是否滿足信號設備布置原則，若滿足則插入新設備對象到信息數(shù)據(jù)庫中。

2.3.2 信號設備布置原理分析

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

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

表1 信號機布置實現(xiàn)

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

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

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

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

圖6 進路搜索算法流程圖

3 模型仿真與驗證

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

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

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

表2 編程實現(xiàn)功能表

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

（2）按照規(guī)定的形式將線路基礎數(shù)據(jù)信息寫成txt文件，系統(tǒng)將根據(jù)文件信息自動繪制線路基礎站場信息。

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

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

圖7 編輯道岔屬性框圖

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

圖8 信號設備布置結果圖

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

3.2 進路信息Excel表生成

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

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

圖9 完善信號機屬性圖

圖10 進路信息Excel表圖

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

4 結束語

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

[1]龔 劬.圖論與網(wǎng)絡最優(yōu)化算法[M].重慶：重慶大學出版社，2009：18-30.

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

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