馬新宇MA Xin-yu

（武漢鐵路橋梁職業(yè)學院，武漢 430090）

1 鐵路站場數(shù)據(jù)結(jié)構(gòu)

鐵路車站信號設(shè)備通常由信號機、軌道區(qū)段、道岔、絕緣節(jié)等組成，且他們相互之間存在連接關(guān)系。信號機是一種用來表示固定信號意義的設(shè)備，對鐵路運輸生產(chǎn)起到指引作用。道岔設(shè)備存在于鐵路區(qū)間或鐵路車站，主要用來改變列車的運行方向。軌道電路通常安裝在鐵路車站內(nèi)，用來檢查某一區(qū)段是否空閑，通常我們使用軌道絕緣將軌道電路劃分為不同的區(qū)段，用以檢測軌道電路是否被列車占用。

我們以車站中心線為界，將車站劃分為左右兩個部分，分別稱為上行咽喉區(qū)域和下行咽喉區(qū)域。上行方面對應的是下行咽喉，下行方面對應的是上行咽喉。兩個咽喉區(qū)的拓撲模型建立方法是完全相同的，故只需討論其中一個咽喉區(qū)即可。將信號機、道岔、軌道區(qū)段等鐵路站場圖元按照一定的順序和規(guī)則連接起來，那么它們在站場中所處的位置及相互關(guān)系構(gòu)成站場的設(shè)備數(shù)據(jù)結(jié)構(gòu)，如圖1 所示。

圖1 站場數(shù)據(jù)結(jié)構(gòu)

2 鐵路車站站場數(shù)據(jù)拓撲建模

2.1 站場有向圖拓撲結(jié)構(gòu)

我們運用計算機讀取鐵路車站信號設(shè)備之間的連接關(guān)系從而實現(xiàn)對鐵路車站站場圖的遍歷。然而原始的站場圖無法直接被計算機識別，需要對其進行數(shù)據(jù)轉(zhuǎn)換，在此我們運用計算機圖論相關(guān)知識進行拓撲建模。一個有向圖G 通常表示為G=（V，E），其中，G 表示一個圖，集合V={v1，v2，…，vn}是包含n 個頂點的集合，集合E={e1，e2，…em}是包含m 條邊的集合，每一條邊ei都是集合V 的二元素子集{vi，vj}。如果把信號設(shè)備看作圖中的各個節(jié)點，信號設(shè)備之間的連接關(guān)系看作圖中的邊，那么整個站場網(wǎng)絡就可以被抽象成一個有向圖G=（V，E），其中V 表示信號設(shè)備集合，E 表示信號設(shè)備之間的連接關(guān)系集合。

盡管站場圖中各設(shè)備的連接沒有方向，但是車站的進路是有方向的。通過對鐵路站場的進路信息數(shù)據(jù)的研究發(fā)現(xiàn)，站場的進路辦理可以劃分為不同的咽喉進行。為加快計算機的運算速率，降低站場拓撲數(shù)據(jù)構(gòu)建的復雜度，我們將站場有向圖依據(jù)咽喉不同，并根據(jù)進路的方向性將站場圖按照下行方向建立模型，劃分為兩個規(guī)模較小的站場有向圖，依次構(gòu)建拓撲數(shù)據(jù)。所構(gòu)建的左咽喉區(qū)的有向圖模型如圖2 所示。

2.2 站場有向圖鄰接矩陣

生成有向圖之后，即確定了站場圖中設(shè)備之間的連接關(guān)系，接下來需要將有向圖進一步轉(zhuǎn)換為計算機可直接讀取識別的數(shù)據(jù)，再利用圖論的知識對站場圖元數(shù)據(jù)進行搜索。對有向圖中的數(shù)據(jù)存儲我們使用圖的鄰接矩陣實現(xiàn)。圖的鄰接矩陣不但可以表示有向圖中各個頂點之間是否有路徑直接連通，還可以表示兩頂點之間的有向圖的方向。在有向圖G 中，圖的節(jié)點集合V={v1，v2，…vn}，則鄰接矩陣表示為A=（aij）n×n，若aij=1，則表示vi有指向vj的邊；若aij=0，則表示vi無指向vj的邊。按照此中計算方法，得出圖2 中的左咽喉區(qū)有向圖拓撲圖的部分鄰接矩陣如圖3所示。

圖2 左咽喉區(qū)有向圖拓撲模型

圖3 左咽喉區(qū)有向圖鄰接矩陣（部分）

3 進路搜索算法研究與實現(xiàn)

3.1 深度優(yōu)先算法

通過建立站場信號平面布置圖拓撲結(jié)構(gòu)，我們可以將抽象的圖元信息數(shù)據(jù)轉(zhuǎn)換為相對具體的有向圖模型，將各個設(shè)備間的連接關(guān)系轉(zhuǎn)換為可供計算機讀取的數(shù)據(jù)信息，以便計算機可以快速讀取和識別。本文選擇了以鄰接矩陣法來進行有向圖數(shù)據(jù)的存儲。運用深度優(yōu)先搜索方法來進行站場圖元數(shù)據(jù)的遍歷。

深度優(yōu)先搜索算法又稱為DFS 算法，是一種從始端節(jié)點起按樹結(jié)構(gòu)的某一支不斷加深搜索深度，從一條道走到黑的搜索方法。相對于廣度優(yōu)先搜索算法而言，深度優(yōu)先搜索算法在運算過程中所消耗的內(nèi)存比較小，且在搜索的過程中對搜索的方向可以做一定的優(yōu)化和限制，比如在搜索道岔節(jié)點時，可以規(guī)定在搜索過程中是以定位優(yōu)先搜索還是以反位優(yōu)先搜索，增大搜索到目標節(jié)點的概率。但是深度優(yōu)先搜索方法也存在一定的弊端，在搜索的過程中如果在某一支路上找不到目標節(jié)點時，需要回溯到上一支路進行搜索，導致有時找到目標節(jié)點需要花費較多的時間。

3.2 算法的實現(xiàn)

3.2.1 符號定義

①數(shù)組Arr：存儲站場信號平面布置圖中的信號設(shè)備信息；

②數(shù)組Mar：存放鄰接矩陣；

③XN、XA、i、j：變量；

④數(shù)組ST：存放始端設(shè)備名稱；

⑤數(shù)組EN：存放終端設(shè)備名稱；

⑥XA、XN：用來存放當前設(shè)備的坐標。

3.2.2 算法描述

由于對左右咽喉區(qū)的建模方法完全一致，本文以左側(cè)咽喉區(qū)域為例進行有向圖的計算機存儲方法介紹。首先逐一對數(shù)組Arr 中的設(shè)備數(shù)據(jù)進行遍歷，讀取當前設(shè)備Arr[i]，依次分別讀取當前設(shè)備Arr[i]的前端、后端以及側(cè)端連接設(shè)備，將上述設(shè)備讀取到EN 中。查找在Arr 中EN 的下標j，讀取Arr[i]的X 坐標XA、EN 的X 坐標XN，對比XA和XN 的大小，如果XA>XN，表示Arr[i]在EN 的右端，則鄰接數(shù)組Mar[i][j]的值改為1；如果XAXN，表示Arr[i]在EN 的右端，則鄰接數(shù)組Mar[j][i]的值改為1；如果XA

①初始化狀態(tài)變量i=j=0、fro=beh=sid=true。

②讀取Arr 中下標為i 的設(shè)備Arr[i]。

③判斷Arr [i]的前端連接設(shè)備是否為空且狀態(tài)變量fro 的值不為真，如果是轉(zhuǎn)到⑤，否則轉(zhuǎn)到④。

④讀取Arr[i]的前端設(shè)備為EN，將狀態(tài)變量fro 的值改為假，用以標記當前設(shè)備前端連接設(shè)備已被訪問過。轉(zhuǎn)到?。

⑤判斷Arr [i]的后端連接設(shè)備是否為空且狀態(tài)變量beh 的值不為真，如果是轉(zhuǎn)到⑦，否則轉(zhuǎn)到⑥。

⑥讀取Arr[i]的后端設(shè)備為EN，將狀態(tài)變量beh 的值改為假，用以標記當前設(shè)備后端連接設(shè)備已被訪問過。轉(zhuǎn)到?。

⑦判斷Arr [i]的側(cè)端連接設(shè)備是否為空且狀態(tài)變量sid 的值不為真，如果是轉(zhuǎn)到⑨，否則轉(zhuǎn)到⑧。

⑧讀取Arr[i]的側(cè)端設(shè)備為EN，將狀態(tài)變量sid 的值改為假，用以標記當前設(shè)備側(cè)端連接設(shè)備已被訪問過。跳轉(zhuǎn)到?。

⑨i 的值自增1。

⑩判斷Arr 中下標為i 的元素是否為空。如果是，轉(zhuǎn)到?，否則轉(zhuǎn)到①。

?在數(shù)組Arr 中讀取EN 的下標j。

?讀取EN 的X 坐標XN；Arr[i]的X 坐標XA。

?判斷EN 和Arr[i]的坐標大小，如果XN>XA 轉(zhuǎn)到?，否則轉(zhuǎn)到?。

?將鄰接數(shù)組Mar[j][i]的值改為1。轉(zhuǎn)到④。

?將鄰接數(shù)組Mar[i][j]的值改為1。轉(zhuǎn)到④。

?初始化變量i=0；j=0。

?i 值是否小于Mar 數(shù)組長度，如果是轉(zhuǎn)到?，否則轉(zhuǎn)到?。

?j 值是否小于鄰接數(shù)組Mar 的長度，如果是，轉(zhuǎn)到?，否則轉(zhuǎn)到?。

?i 的值加1。

?Mar[i][j]的值是否為1，如果是，轉(zhuǎn)到?，否則轉(zhuǎn)到?。

?在Arr 中讀取i 的設(shè)備，存放到數(shù)組ST 中。

?在Arr 中讀取j 的設(shè)備，存放到數(shù)組EN 中。轉(zhuǎn)到?。

?j 值自增1。轉(zhuǎn)到?。

?結(jié)束。

按照上述方法計算左側(cè)咽喉區(qū)域的圖元數(shù)據(jù)如表1所示。

表1 小橋站左咽喉區(qū)設(shè)備圖元數(shù)據(jù)

4 結(jié)語

在實際的鐵路運輸生產(chǎn)環(huán)境中，具體采用哪一種站場數(shù)據(jù)拓撲結(jié)構(gòu)存儲、選用何種搜索算法需要根據(jù)車站的實際情況、設(shè)備的多少有針對性的設(shè)計。但無論采用何種方法，都要堅持提高搜索效率、節(jié)省存儲空間、使用便捷等原則，保證算法高效、數(shù)據(jù)結(jié)構(gòu)存儲合理、邏輯清晰等要求。本文通過對鐵路車站站場圖設(shè)備布置情況進行分析，運用計算機圖論的相關(guān)知識將車站信號平面布置圖抽象分為拓撲圖結(jié)構(gòu)，設(shè)計了適用于鐵路車站站場圖的進路搜索算法，算法設(shè)計上提高了內(nèi)存空間利用率，也提高了遍歷效率。