一種基于圖和鄰接表的站場圖模型設計方法

賈積禹，崔佳諾

（1．北京全路通信信號研究設計院集團有限公司，北京 100070；2．北京市高速鐵路運行控制系統工程技術研究中心，北京 100070）

1 概述

計算機聯鎖系統中參與聯鎖邏輯運算的數據包括靜態數據和動態數據兩大類，對應了靜態數據結構和動態數據結構，數據結構的類型不僅影響聯鎖程序的結構，還直接關系到聯鎖邏輯運算的復雜度、運算時間等系統參數。目前，靜態數據主要采用聯鎖表的數據結構進行存儲，聯鎖表的數據結構中，主要描述了進路與對象（道岔、信號機、區段）之間的關系[1]。

隨著社會不斷發展，既有鐵路車站的改造和升級必不可少，當新增需求與信號設備在站場中的位置相關時，通常有以下兩種方式進行處理。其一，是對靜態數據結構進行修改，更新既有聯鎖表數據結構，在聯鎖表中增加新需求所需的設備信息或信號設備之間的制約關系，聯鎖表數據結構的頻繁更新，會導致數據配置容易出錯[2]，增加程序的存儲空間；其二，在計算機聯鎖軟件的核心邏輯中，根據進路與信號設備之間的制約關系進行邏輯判斷來獲取指定信號設備的相關信息，通過復雜邏輯判斷間接獲取車站內指定信號設備的信息，存在一定的安全風險。

本文針對上述兩種方法的不足，在既有聯鎖表的基礎上，提出一種用于計算機聯鎖邏輯運算的站場圖模型設計方法，該站場圖模型存儲了站場的信號設備信息及其之間的連接關系。通過站場圖模型獲取計算機聯鎖邏輯運算所需的信號設備信息，可以避免聯鎖表數據結構的頻繁更新，提高聯鎖系統的可靠性；同時信號設備信息采用站場拓撲圖直接獲取的方式，無需進行邏輯判斷獲取信號設備信息，提高聯鎖系統的安全性。

2 站場圖模型的選擇

鐵路車站站場圖模型是以圖的方式描述站場中信號設備之間的關系，圖是由頂點的有窮非空集合和頂點之間邊的集合組成，通常表示為：G(V,E)，其中，G表示一個圖，V是圖G中頂點的集合，E是圖G中邊的集合。目前在國內外車站站場圖模型的研究中，無向圖模型有功能點模型、承載點模型，有向圖模型有道岔組頂點模型、軌道頂點模型、進路沖突模型等，研究人員根據需求選擇不同的站場圖模型進行建模，以實現預期目標[3-4]。

功能點模型將道岔、渡線交點、絕緣節、站線等具有特定功能的點抽象為頂點建立鐵路車站站場圖，能對站場中信號設備信息及連接關系進行表示；承載點模型[5-6]將不同屬性的設備抽象并定義為銜接點，銜接不同屬性線路的銜接點與銜接點之間線路抽象為承載點而構建的模型，有利于記錄不同屬性設備之間的聯系；道岔組頂點模型[7]將必然同時使用的道岔分為一組，簡化計算，有利于計算車站咽喉通過能力；軌道頂點模型的權值賦值機制可以有效的避免迂回進路，同時保證盡量使用平行進路；進路沖突模型描述進路之間的沖突關系，可以方便計算進路之間的沖突程度，但缺乏對具體道岔、線路設備的描述。

為了描述鐵路車站站場中具有特定功能的設備，并獲取信號設備的相關信息，故選取無向圖模型中的功能點模型作為鐵路車站站場圖建模方法，將絕緣節、道岔中心點作為圖的頂點，將連接兩個頂點之間的軌道作為頂點之間的邊，功能點模型的站場圖模型可表示為G(V,E)，其中V為站場中功能點的集合，定義為V={vi|i=0,1,…,Nv},頂點包含了站場圖中的絕緣節和道岔中心點；E為功能點模型中頂點之間的邊的集合，定義為E={eij|i,j=0,1,…,Nv}。

本文以圖1所示為例，站場由區段、道岔、信號機、絕緣節組成，其中，信號機依附于絕緣節設置，道岔中心點使用數字表示，絕緣節使用“J”進行標識。

圖1 信號平面布置Fig.1 Signal layout

根據上述方法，采用功能點模型，按照圖1所示的信號設備及其之間的聯系，建立站場圖模型結構，如圖2所示。

圖2 站場型結構Fig.2 Structure of station/yard model

其中，絕緣節和道岔作為站場型數據結構中的頂點，頂點之間的軌道區段作為邊。當頂點類型為絕緣節類型時，只能與兩個頂點進行連接；當頂點類型為道岔類型時，必須有3個頂點與其連接。

3 站場圖模型的數據結構

站場圖模型與圖的結構類似，屬于圖論模型[8]，圖的各頂點之間通常存在多對多的關系。圖形結構在計算機中可以使用鄰接矩陣、鄰接表、十字鏈表、鄰接多重表、邊集數組等進行表示，不同的存儲結構有各自的優缺點和適用范圍[9]。根據站場圖模型的頂點和邊之間的對應關系，是一個邊稀疏的圖形結構，為了減少存儲空間的浪費，本設計采用了鄰接表的存儲結構對站場型數據進行存儲。

鄰接表存儲結構由頂點數組和線性表組成。圖形結構中的所有頂點采用一個一維數組存儲，同時，在頂點數組中，每個數據元素還需存儲指向第一個鄰接點的指針，以便查找到該頂點的邊信息。圖中的每個頂點的所有鄰接點構成一個線性表，采用單鏈表進行存儲。

頂點數組中元素的數據結構包含：數據域(data)和鏈域(firstarc)，其中數據域用于存儲當前頂點的名稱或其他相關信息，鏈域用于指向鏈表中的第一個鄰接點；線性表中數據元素的數據結構包含：鄰接點域（adjvex）、數據域（info）、鏈域（nextarc），其中，鄰接點域用于存儲與頂點連接的點在圖中的位置，數據域用于存儲與邊相關的信息，鏈域用于存儲依附于當前頂點的下一條邊。

根據鄰接表的存儲方式，將站場型結構圖中的設備信息依次配置到頂點數組和鄰接點數組中，如圖3所示，頂點數組中的數據域（data）中存儲了站場中絕緣節和道岔的相關信息，鏈域（firstarc）中存儲了與絕緣節或道岔相連的第一條邊的指針。由于站場型結構圖中，每個頂點最多只能與3個頂點進行連接，線性表的結點最大數為3個。當絕緣節作為頂點時，線性表的結點數為1個或2個，當道岔作為頂點時，線性表的結點數為3個。

圖3 站場圖的鄰接表結構Fig.3 Adjacency list structure of station/yard diagram

站場型的數據結構的數據連接方式與站場的平面布置圖上特定功能點的連接方式是一一對應的，當站場的信號設備改變時，只需改變既有數據之間的連接方式，增加或減少頂點，很容易修改。

4 站場圖模型的需求實現

需求舉例：“列車進路滿足信號開放條件時，聯鎖應先將進路內的調車信號機帶動開放。”該需求實現過程中，應能查找列車進路內同向的調車信號機并對其進行控制。

既有聯鎖系統中，列車信號的開放無需將進路內的調車信號機帶亮，在既有的聯鎖表數據結構中缺少進路內調車信號機的信息。以下對基于站場圖模型實現新需求的方案進行詳細說明。

通過對新需求的理解和分析，新需求的關鍵點是找到進路內同向的調車信號機。站場型數據結構已經存儲了站場中的信號設備信息及其之間的連接關系，通過信號設備之間的連接關系和道岔相關信息即可查找到進路內的同向調車信號機。

為了能正確查找到站場中指定的信號設備信息，設計了鄰接表中的頂點和鄰接點，其數據結構如圖4所示，頂點的數據域包含：設備名稱、設備類型、設備索引、設備坐標；鄰接點的數據域包含：區段名稱、區段索引、區段方向、道岔開向。

圖4 頂點和鄰接點的數據域Fig.4 Data field for vertex and adjacent

聯鎖軟件所處理的對象主要有3類：信號機、道岔、區段。站場中的信號機信息包含于絕緣節信號設備數據結構中，道岔信息包含于道岔設備數據結構中，區段信息包含于鄰接點的數據結構中。絕緣節和道岔設備的數據結構如圖5所示，其中絕緣節信號設備數據結構包含：絕緣節名稱、絕緣節對應的信號機數量、信號機名稱、信號機類型、信號機方向、區間口類型；道岔設備的數據結構包含：道岔名稱、道岔類型。

圖5 基礎設備信息數據結構Fig.5 Infrastructure information data structure

通過頂點數據域中的設備索引，在基礎設備信號表中即能查找到指定信號設備的信息。

頂點和鄰接點的數據域中存儲了信號設備的相關信息，根據這些信息以及信號設備的連接關系，可以簡單、準確獲取站場中特定的信號設備并對其進行控制。

查找進路內調車信號機的流程如圖6所示，實現的功能為：通過進路代碼在站場型數據結構中查詢該進路內同向的調車信號機信息。

圖6 查找進路內調車信號機流程Fig.6 Flow chart of locating the shunting signal within the route

進路內調車信號機的查詢步驟如下。

第一步，通過進路聯鎖表獲取該進路始終端信號機對應的絕緣節名稱，即站場型結構圖中頂點的名稱。

第二步，在站場型結構圖中遍歷找到始端信號機對應絕緣節頂點，并記錄該頂點的數據域和鏈域。

第三步，在站場圖模型中，以始端信號機對應絕緣節頂點為起始點，結合進路內區段方向、區段內的道岔開向唯一確定進路內下一個鄰接頂點。

第四步，根據鄰接頂點設備信息，記錄進路內同向的調車信號機信息。

第五步，若鄰接頂點不是終端信號機對應絕緣節頂點，則重復第二步、第三步、第四步，繼續查找；否則，結束查找。

通過執行上述步驟，可將進路內的同向調車信號機記錄下來，并對記錄的信號設備進行控制。采用站場圖模型的方法，避免了更新聯鎖表數據結構，省去了數據配置的工作，同時也簡化了聯鎖應用邏輯的復雜度。站場圖模型存儲了更全面的信號設備信息，能適應更多新的需求，提升聯鎖系統的魯棒性。

5 結束語

站場圖模型的設計及站場型數據結構的建立，能可靠、安全的查找到站場中特定的信號設備。可以避免聯鎖表數據結構的頻繁更新，降低數據配置過程中出錯的可能性，減少聯鎖表占用的存儲空間，提高聯鎖系統的可靠性；同時也能避免復雜邏輯運算獲取特定信號設備信息的異常情況發生，提升聯鎖系統的安全性。