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

萬 霞，王長林

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

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

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

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

1 圖論拓撲結(jié)構(gòu)

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

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

2 城市軌道交通信號設(shè)備應用模型

2.1 圖元化處理

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

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

圖2 信號機圖元化處理

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

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

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

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

圖3 線路信息數(shù)據(jù)結(jié)構(gòu)圖

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

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

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

根據(jù)節(jié)點鏈接圖就可以生成站場形數(shù)據(jù)結(jié)構(gòu)。每個節(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 基于拓撲圖論搜索的設(shè)備布置模型

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

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

2.3.1 基于矢量拓撲結(jié)構(gòu)的遍歷搜索

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

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

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

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

由線路數(shù)據(jù)拓撲結(jié)構(gòu)信息得到數(shù)據(jù)結(jié)構(gòu)圖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。則轉(zhuǎn)(4)，否則轉(zhuǎn)下一步。

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

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

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

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

2.3.2 信號設(shè)備布置原理分析

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

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

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

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

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

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

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

圖6 進路搜索算法流程圖

3 模型仿真與驗證

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

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

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

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

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

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

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

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

圖7 編輯道岔屬性框圖

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

圖8 信號設(shè)備布置結(jié)果圖

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

3.2 進路信息Excel表生成

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

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

圖9 完善信號機屬性圖

圖10 進路信息Excel表圖

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

4 結(jié)束語

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

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

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

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