基于鄰接表和改進(jìn)深度搜索的進(jìn)路搜索研究

劉儒琛，孫眾人，張尚崇

（蘭州交通大學(xué)，蘭州 730070）

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

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

1 站場(chǎng)圖模型

1.1 模型選擇

站場(chǎng)圖模型采用圖的方式描述車站內(nèi)信號(hào)設(shè)備間的關(guān)系。將站場(chǎng)內(nèi)的信號(hào)設(shè)備定義為圖的節(jié)點(diǎn)，將站場(chǎng)內(nèi)的股道定義為圖的邊，通常表示為G(V,E)，其中，G表示一個(gè)站場(chǎng)圖，V是圖G中節(jié)點(diǎn)的集合，即信號(hào)設(shè)備；E是圖G中邊的集合，即股道。

目前，站場(chǎng)圖模型按選取節(jié)點(diǎn)不同可分為功能點(diǎn)模型和承載點(diǎn)模型等，根據(jù)拓?fù)鋱D屬性可分為無向圖和有向圖模型。功能點(diǎn)模型是將站場(chǎng)內(nèi)的信號(hào)機(jī)、絕緣節(jié)、道岔中心點(diǎn)等具有特定功能的點(diǎn)定義為節(jié)點(diǎn)，將連接節(jié)點(diǎn)的股道定義為邊。承載點(diǎn)模型是將絕緣節(jié)、道岔、渡線交點(diǎn)等線路交叉點(diǎn)和連接點(diǎn)定義為銜接點(diǎn)，銜接點(diǎn)間的線路定義為承接點(diǎn)。為了對(duì)站場(chǎng)中的信號(hào)設(shè)備進(jìn)行詳細(xì)分析，本文采用無向圖功能點(diǎn)模型，將信號(hào)機(jī)、道岔中心點(diǎn)、絕緣節(jié)等作為圖的節(jié)點(diǎn)，將連接兩個(gè)節(jié)點(diǎn)之間的股道作為節(jié)點(diǎn)之間的邊。

本文示例部分如圖1 所示，站場(chǎng)由信號(hào)機(jī)、道岔、絕緣節(jié)和軌道區(qū)段組成。其中道岔中心點(diǎn)用對(duì)應(yīng)道岔編號(hào)的數(shù)字表示，信號(hào)機(jī)和絕緣節(jié)一同布置，圖中不再畫出絕緣節(jié)，通過信號(hào)機(jī)標(biāo)識(shí)表示信號(hào)機(jī)和絕緣節(jié)。

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

將圖1 所示站場(chǎng)圖按功能點(diǎn)模型進(jìn)行重構(gòu)，不考慮信號(hào)設(shè)備的形狀與大小，根據(jù)信號(hào)設(shè)備及區(qū)段關(guān)系構(gòu)建模型，如圖2 所示。信號(hào)機(jī)和道岔作為圖的節(jié)點(diǎn)，軌道區(qū)段作為圖的邊。當(dāng)信號(hào)機(jī)作為節(jié)點(diǎn)時(shí)該點(diǎn)連接2 個(gè)節(jié)點(diǎn)，有2 條邊；當(dāng)?shù)啦碜鳛楣?jié)點(diǎn)時(shí)，連接3 個(gè)節(jié)點(diǎn)，有3 條邊。

圖2 站場(chǎng)模型Fig.2 Station model

1.2 模型的數(shù)據(jù)結(jié)構(gòu)

站場(chǎng)圖模型為無向圖的結(jié)構(gòu)，且具有節(jié)點(diǎn)多、邊相對(duì)較少的特點(diǎn)，是一種邊稀疏的圖。為優(yōu)化存儲(chǔ)結(jié)構(gòu)，減少存儲(chǔ)浪費(fèi)，故此采用鄰接表的結(jié)構(gòu)儲(chǔ)存站場(chǎng)圖模型數(shù)據(jù)。

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

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

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

2 進(jìn)路搜索模型

2.1 數(shù)學(xué)模型構(gòu)建

進(jìn)路搜索是從進(jìn)路起點(diǎn)，按聯(lián)鎖關(guān)系逐步搜索后續(xù)節(jié)點(diǎn)。站場(chǎng)圖模型采用鄰接表結(jié)構(gòu)，在進(jìn)路搜索時(shí)由進(jìn)路起點(diǎn)開始，依次訪問節(jié)點(diǎn)的鄰接點(diǎn)中的數(shù)據(jù)并存入進(jìn)路搜索模型中，最終搜索到進(jìn)路終點(diǎn)。現(xiàn)定義進(jìn)路搜索模型中節(jié)點(diǎn)V和邊E的屬性如下。

1）V是站場(chǎng)圖G中信號(hào)設(shè)備的集合，如公式（1）、（2）所示。

公式中：

xi為節(jié)點(diǎn)vi距信號(hào)樓中心距離。以車站信號(hào)樓中心為0 坐標(biāo)處，|xi|隨站場(chǎng)內(nèi)信號(hào)設(shè)備距信號(hào)樓中心距離增大而增大，信號(hào)樓左側(cè)節(jié)點(diǎn)的xi為該節(jié)點(diǎn)距信號(hào)樓中心距離的負(fù)值，信號(hào)樓右側(cè)節(jié)點(diǎn)的xi為該節(jié)點(diǎn)距信號(hào)樓中心距離的正值，車站內(nèi)各信號(hào)設(shè)備從左向右xi值依次增大。

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

搜索進(jìn)路時(shí)不同類型的節(jié)點(diǎn)有不同的進(jìn)路搜索行為，即根據(jù)搜索到的節(jié)點(diǎn)的mi值不同需要采取不同應(yīng)對(duì)措施。當(dāng)mi為0 時(shí)，終止搜索或經(jīng)由該節(jié)點(diǎn)繼續(xù)搜索；當(dāng)mi為1 時(shí)分兩個(gè)方向進(jìn)行搜索；當(dāng)mi為2 時(shí)終止搜索。

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

公式中：

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

li為邊ei的長度，根據(jù)ti進(jìn)行判定。當(dāng)ti＝0時(shí)，li＝xb－xa；當(dāng)ti＝1 或2 時(shí)，li根據(jù)渡線長度公式進(jìn)行計(jì)算。

ui為邊ei的占用標(biāo)識(shí)符，當(dāng)ui＝0 時(shí)表示邊ei未被占用，當(dāng)ui＝1 時(shí)表示邊ei已被占用。

2.2 數(shù)學(xué)模型建立

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

進(jìn)路搜索模型的目標(biāo)函數(shù)如公式（8）所示。

在搜索進(jìn)路時(shí)應(yīng)滿足以下約束條件：

1）股道占用檢測(cè)

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

2）迂回進(jìn)路限制

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

在搜索進(jìn)路時(shí)，若當(dāng)前渡線與進(jìn)路第一條渡線類型不同，應(yīng)終止搜索。

由此，進(jìn)路搜索模型如公式（11）所示。

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

3 進(jìn)路搜索算法

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

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

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

3.2 搜索方法

1）確定起訖點(diǎn)和搜索方向

根據(jù)進(jìn)路起點(diǎn)和終點(diǎn)的xi確定進(jìn)路搜索方向。若終點(diǎn)的xi＞起點(diǎn)的xi，則向xi增大的方向搜索；若終點(diǎn)的xi＜起點(diǎn)的xi，則向xi減小的方向搜索。

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

在搜索進(jìn)路時(shí)應(yīng)保證整條進(jìn)路的連續(xù)性。基于鄰接表結(jié)構(gòu)和DFS 算法，進(jìn)路搜索只能從當(dāng)前節(jié)點(diǎn)的鄰接點(diǎn)中選擇進(jìn)路的下一節(jié)點(diǎn)，進(jìn)而保證進(jìn)路的連續(xù)性。

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

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

4）搜索行為判斷條件

當(dāng)搜索到一個(gè)節(jié)點(diǎn)時(shí)，依次從鄰接表中讀取數(shù)據(jù)域和鏈域中的數(shù)據(jù)并存入vi和ei中，并依次作出判定。

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

b.檢索設(shè)備編號(hào)，對(duì)比當(dāng)前節(jié)點(diǎn)與進(jìn)路終點(diǎn)的設(shè)備編號(hào)，搜索到進(jìn)路終點(diǎn)時(shí)，終止搜索并依次返回上一個(gè)道岔節(jié)點(diǎn)搜索彎股方向。

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

5）搜索結(jié)束條件

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

4 結(jié)束語

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