基于鄰接表和改進深度搜索的進路搜索研究

劉儒琛，孫眾人，張尚崇

（蘭州交通大學，蘭州 730070）

計算機聯鎖系統(tǒng)中存儲的車站數據包含動態(tài)數據和靜態(tài)數據，其中靜態(tài)數據主要采用聯鎖表的結構存儲。隨著社會發(fā)展，當既有車站需要改造升級時，需要將新增或變更的信號設備數據寫入車站靜態(tài)數據中。傳統(tǒng)聯鎖表結構在插入或刪除數據時操作繁瑣，可能導致數據一致性問題，且聯鎖表結構占用空間較多，當車站規(guī)模增大時會造成不利影響。此外，傳統(tǒng)進路搜索算法是對聯鎖表中存儲的全部進路進行篩選，導致搜索效率低。

針對以上問題，本文在傳統(tǒng)鄰接表的基礎上提出了一種基于無向圖的站場圖存儲模型，并基于該模型重新設計了利用改進的深度優(yōu)先搜索算法的進路搜索模型。該站場圖模型用于存儲站場內的信號設備數據和設備間的連接關系，具有存儲空間小、數據修改快捷的優(yōu)點；進路搜索模型具有簡單可靠、算法時間復雜度低的優(yōu)點。

1 站場圖模型

1.1 模型選擇

站場圖模型采用圖的方式描述車站內信號設備間的關系。將站場內的信號設備定義為圖的節(jié)點，將站場內的股道定義為圖的邊，通常表示為G(V,E)，其中，G表示一個站場圖，V是圖G中節(jié)點的集合，即信號設備；E是圖G中邊的集合，即股道。

目前，站場圖模型按選取節(jié)點不同可分為功能點模型和承載點模型等，根據拓撲圖屬性可分為無向圖和有向圖模型。功能點模型是將站場內的信號機、絕緣節(jié)、道岔中心點等具有特定功能的點定義為節(jié)點，將連接節(jié)點的股道定義為邊。承載點模型是將絕緣節(jié)、道岔、渡線交點等線路交叉點和連接點定義為銜接點，銜接點間的線路定義為承接點。為了對站場中的信號設備進行詳細分析，本文采用無向圖功能點模型，將信號機、道岔中心點、絕緣節(jié)等作為圖的節(jié)點，將連接兩個節(jié)點之間的股道作為節(jié)點之間的邊。

本文示例部分如圖1 所示，站場由信號機、道岔、絕緣節(jié)和軌道區(qū)段組成。其中道岔中心點用對應道岔編號的數字表示，信號機和絕緣節(jié)一同布置，圖中不再畫出絕緣節(jié)，通過信號機標識表示信號機和絕緣節(jié)。

圖1 車站平面布置Fig.1 Station layout

將圖1 所示站場圖按功能點模型進行重構，不考慮信號設備的形狀與大小，根據信號設備及區(qū)段關系構建模型，如圖2 所示。信號機和道岔作為圖的節(jié)點，軌道區(qū)段作為圖的邊。當信號機作為節(jié)點時該點連接2 個節(jié)點，有2 條邊；當道岔作為節(jié)點時，連接3 個節(jié)點，有3 條邊。

圖2 站場模型Fig.2 Station model

1.2 模型的數據結構

站場圖模型為無向圖的結構，且具有節(jié)點多、邊相對較少的特點，是一種邊稀疏的圖。為優(yōu)化存儲結構，減少存儲浪費，故此采用鄰接表的結構儲存站場圖模型數據。

鄰接表由節(jié)點數組和線性表組成，其中節(jié)點數組為一維數組，用來存儲圖的節(jié)點，同時每個數組元素還需存儲指向第一個鄰接點的指針；線性表采用單鏈表，用于存儲每個節(jié)點的鄰接點。每個節(jié)點數組分為數據域和鏈域，數據域用于存儲節(jié)點的信息，鏈域存儲該節(jié)點直向第一個鄰接點的指針。線性表分為鄰接點域、數據域和鏈域，鄰接點域存儲該節(jié)點的鄰接點在圖中的位置，數據域存儲邊的相關信息，鏈域存儲該節(jié)點的下一條邊。

將站場中的設備信息存儲入鄰接表中，將信號機、道岔、絕緣節(jié)等信號設備的信息存入節(jié)點數組的數據域，由鏈域指向與節(jié)點相連的邊。利用鄰接表存儲數據簡潔明了，當需要更改信號設備時，只需要對數組和線性表進行操作，改變數據間的連接方式，增加或刪減節(jié)點即可，操作簡易。

為實現站場圖模型的功能，如搜索列車進路、更改信號設備信息等，鄰接表中的數據域需要包含多項內容。不同信號設備節(jié)點所包含數據不同，信號機節(jié)點中應包含：信號機名稱、信號機類型（接車、調車、發(fā)車）、信號機方向（正向、反向）和距信號樓中心距離；道岔節(jié)點中應包含：道岔名稱、道岔號數、道岔限速、渡線類型（撇型、捺型）和距信號樓中心距離；堵頭絕緣節(jié)節(jié)點中應包含：絕緣節(jié)名稱、設備類型和距信號樓中心距離。鄰接點中應包含：區(qū)段編號、區(qū)段長度和道岔方向（岔前、岔后定位、岔后反位）等。

2 進路搜索模型

2.1 數學模型構建

進路搜索是從進路起點，按聯鎖關系逐步搜索后續(xù)節(jié)點。站場圖模型采用鄰接表結構，在進路搜索時由進路起點開始，依次訪問節(jié)點的鄰接點中的數據并存入進路搜索模型中，最終搜索到進路終點。現定義進路搜索模型中節(jié)點V和邊E的屬性如下。

1）V是站場圖G中信號設備的集合，如公式（1）、（2）所示。

公式中：

xi為節(jié)點vi距信號樓中心距離。以車站信號樓中心為0 坐標處，|xi|隨站場內信號設備距信號樓中心距離增大而增大，信號樓左側節(jié)點的xi為該節(jié)點距信號樓中心距離的負值，信號樓右側節(jié)點的xi為該節(jié)點距信號樓中心距離的正值，車站內各信號設備從左向右xi值依次增大。

mi表示節(jié)點vi的類型，如公式（3）所示。

搜索進路時不同類型的節(jié)點有不同的進路搜索行為，即根據搜索到的節(jié)點的mi值不同需要采取不同應對措施。當mi為0 時，終止搜索或經由該節(jié)點繼續(xù)搜索；當mi為1 時分兩個方向進行搜索；當mi為2 時終止搜索。

2）E是站場圖G中股道的集合，如公式（4）、（5）所示。

公式中：

ti為邊ei的股道類型，定義如公式（6）所示。

li為邊ei的長度，根據ti進行判定。當ti＝0時，li＝xb－xa；當ti＝1 或2 時，li根據渡線長度公式進行計算。

ui為邊ei的占用標識符，當ui＝0 時表示邊ei未被占用，當ui＝1 時表示邊ei已被占用。

2.2 數學模型建立

為提高車站作業(yè)效率，盡量減少列車走行時間，應使搜索出來的進路最短，同時減少進路對車站的切割，減小對其他作業(yè)的影響。用f表示進路長度，F表示進路，如公式（7）所示。

進路搜索模型的目標函數如公式（8）所示。

在搜索進路時應滿足以下約束條件：

1）股道占用檢測

搜索出來的進路需要保證未被占用，進路中的所有股道都應處于空閑狀態(tài)，如公式（9）所示。

2）迂回進路限制

為減少列車走行時間，搜索進路可產生平行進路，但不考慮變更進路。搜索進路時應避免產生“八字”迂回進路，即進路中只能存在一種渡線類型，一條進路不能同時經過撇型渡線和捺型渡線。設進路搜索中第一個ti≠0 的邊ei，取該邊的ti為ta，如公式（10）所示。

在搜索進路時，若當前渡線與進路第一條渡線類型不同，應終止搜索。

由此，進路搜索模型如公式（11）所示。

約束條件如公式（12）、（13）所示。

3 進路搜索算法

3.1 改進的深度優(yōu)先搜索算法

車站站場圖模型的進路搜索問題實際上屬于無向圖的遍歷問題，傳統(tǒng)遍歷算法很多，如廣度優(yōu)先搜索算法（BFS）、深度優(yōu)先搜索算法（DFS）、Dijkstra 算法、啟發(fā)式算法等，但各算法都有各自的優(yōu)缺點。對BFS，其內存消耗較大；對DFS，若站場較長會導致進路搜索時間較長；對Dijkstra 算法，若站場模型節(jié)點較多會導致算法空間復雜度高；對啟發(fā)式算法，容易造成收斂過慢或過早收斂。因此，考慮到大部分鐵路站場長度有限且分支較少，采用鄰接表結構構建的站場圖模型，每個節(jié)點有2 ～3個鄰接點，與二叉樹結構有一定的相似性。且進路搜索模型應簡單可靠，搜索時間短。本文采用一種改進的DFS 搜索進路，改進如下。

雖然站場圖模型是無向的，但通過信號設備距信號樓中心距離可以實現進路的單向搜索，只能從進路起點向進路終點搜索，杜絕傳統(tǒng)DFS 會全圖搜索的問題，提高了進路搜索的速度。

3.2 搜索方法

1）確定起訖點和搜索方向

根據進路起點和終點的xi確定進路搜索方向。若終點的xi＞起點的xi，則向xi增大的方向搜索；若終點的xi＜起點的xi，則向xi減小的方向搜索。

2）進路連續(xù)原則

在搜索進路時應保證整條進路的連續(xù)性。基于鄰接表結構和DFS 算法，進路搜索只能從當前節(jié)點的鄰接點中選擇進路的下一節(jié)點，進而保證進路的連續(xù)性。

3）直股優(yōu)先原則

本文設計的站場圖模型中節(jié)點僅有一個坐標，不能判斷進路起點和終點是否在同一條水平線上，因此在搜索到道岔時需要對后續(xù)搜索方向進行判定。為滿足后續(xù)分析需要，當搜索到道岔且進路前方有兩個方向時，優(yōu)先選擇直股方向。

4）搜索行為判斷條件

當搜索到一個節(jié)點時，依次從鄰接表中讀取數據域和鏈域中的數據并存入vi和ei中，并依次作出判定。

a.檢索節(jié)點的設備類型，根據設備類型決定操作類型。當該節(jié)點為信號機時，終止搜索或跳轉至鄰接點；當該節(jié)點為道岔設備時，先校驗區(qū)段信息（保持當前進路搜索方向）后跳轉至對應鄰接點，當直股方向搜索完畢后，依次返回上一個道岔節(jié)點搜索彎股方向；當檢索到堵頭絕緣節(jié)時終止搜索，返回上一個道岔節(jié)點重新搜索。

b.檢索設備編號，對比當前節(jié)點與進路終點的設備編號，搜索到進路終點時，終止搜索并依次返回上一個道岔節(jié)點搜索彎股方向。

c.檢索節(jié)點距信號樓中心距離，判斷進路搜索方向是否正確。考慮到鐵路信號設備布置原則，若當前節(jié)點的xi＞進路終點的xi，可以認為進路搜索過遠，進路終點已被跳過或進路終點并不在當前股道上，終止搜索并依次返回上一個道岔節(jié)點重新搜索。

5）搜索結束條件

考慮到進路搜索時直股優(yōu)先，進路搜索完畢后從進路終點依次返回上一道岔節(jié)點重新搜索，因此當進路中的第一個道岔節(jié)點的彎股方向全部搜索完畢后，可視為進路起訖點間所有進路搜索完畢，對比所有進路長度并選出最短進路后進路搜索結束。

4 結束語

本文通過對車站結構分析，將車站站場圖轉化為一個無向圖并使用鄰接表結構存儲站場數據，利用鄰接表結構站場圖模型和改進的深度優(yōu)先搜索算法建立以最短路徑為目標的進路搜索模型。該算法和模型結合可以提高進路搜索速度，提高了搜索效率，方便適配移植到其他車站。