杜文文，楊 揚(yáng)

（西南交通大學(xué) 信息科學(xué)與技術(shù)學(xué)院，成都 611756）

進(jìn)路處理是計(jì)算機(jī)聯(lián)鎖系統(tǒng)的核心功能，進(jìn)路搜索的主要目的是便于進(jìn)路處理。目前，已有多種進(jìn)路搜索研究方法，如廣度優(yōu)先[1]、改進(jìn)深度優(yōu)先[2]及其它啟發(fā)式算法[3]等。Dijkstra 算法是一種較為成熟的最短路徑算法，其典型應(yīng)用是解決距離最短、時間最少和花費(fèi)最低的問題[4]。但傳統(tǒng)Dijkstra 算法求解最短路徑會耗費(fèi)大量存儲空間和計(jì)算時間，易陷入局部最優(yōu)[5]的問題。為減少搜索深度，本文提出一種基于改進(jìn)Dijkstra 算法的進(jìn)路搜索算法。改進(jìn)后的Dijkstra 算法效率高，且簡單易讀。

本文建立車站站場圖簡化模型，采用有向圖描述站場拓?fù)浣Y(jié)構(gòu)；在數(shù)據(jù)存儲結(jié)構(gòu)和優(yōu)先級隊(duì)列2個方面，對傳統(tǒng)Dijkstra 算法進(jìn)行改進(jìn)，采用廣度優(yōu)先的搜索方式，并編制仿真程序驗(yàn)證將改進(jìn)Dijkstra算法用于進(jìn)路搜索的有效性。

1 站場拓?fù)浣Y(jié)構(gòu)的有向圖建模

有向圖由頂點(diǎn)集和連接任意2 個頂點(diǎn)之間的邊集組成，頂點(diǎn)集表示數(shù)據(jù)元素的集合，邊集為連接2 個頂點(diǎn)之間的指向關(guān)系[6]。將鐵路站場圖抽象為有向圖，站場進(jìn)路搜索問題即可轉(zhuǎn)化為有向圖的遍歷問題[7]。

站場進(jìn)路搜索具有方向性。在搜索過程中，先確定好進(jìn)路起始和終止信號機(jī)，從起始信號機(jī)到終止信號機(jī)之間經(jīng)過的路徑稱為搜索進(jìn)路，一條完整進(jìn)路包含進(jìn)路類型、方向和道岔信息等相關(guān)內(nèi)容[8]。完成進(jìn)路搜索后，將搜索結(jié)果保存為文件，以便于進(jìn)路處理。

圖1 為某鐵路站場平面布置圖。由圖可知，鐵路車站信號設(shè)備之間有前后連接關(guān)系。為了建立站場模型，對站場設(shè)備進(jìn)行簡化，抽象定義為不同屬性的信號設(shè)備，主要考慮軌道電路、道岔和信號機(jī)3 種設(shè)備。道岔和信號機(jī)作為頂點(diǎn)，軌道電路作為邊，盡頭線和安全線則以相連的道岔或信號機(jī)設(shè)備作為頂點(diǎn)，整個站場設(shè)備的拓?fù)浣Y(jié)構(gòu)可抽象為一個網(wǎng)狀結(jié)構(gòu)[8]。

圖1 某鐵路站場平面布置

圖2 某鐵路站場局部有向圖模型

2 Dijkstra 算法的改進(jìn)

2.1 傳統(tǒng)Dijkstra 算法

Dijkstra 算法是經(jīng)典的最短路徑算法，用于計(jì)算正權(quán)圖的單源最短路徑，即對于給定源節(jié)點(diǎn)，可求解自起始節(jié)點(diǎn)到其它所有節(jié)點(diǎn)的最短路徑[9]。最短路徑不僅指傳統(tǒng)意義上的距離最短，也可定義為代價最低，主要用于路網(wǎng)規(guī)劃、旅行商問題、公交車線路規(guī)劃以及社會能源分配等方面[10]。最短路徑模型可以描述為：表示s到t的最短路徑；其中，i與j表示s到t這條路徑上的中間節(jié)點(diǎn)；D(i,j)表示i到j(luò)的最短路徑。

在實(shí)際應(yīng)用中，傳統(tǒng)Dijkstra 算法主要存在3 個不足之處[11]：（1）若數(shù)據(jù)存儲采用鄰接矩陣，對于大型稀疏矩陣會造成空間浪費(fèi)，計(jì)算時間代價也高；（2）在算法迭代過程中，若節(jié)點(diǎn)所在鏈表或數(shù)組是無序的，每次搜索都將遍歷全部節(jié)點(diǎn)，會影響搜索效率；（3）不適用于解決節(jié)點(diǎn)數(shù)目龐大的問題。

2.2 優(yōu)化方法

針對傳統(tǒng)Dijkstra 算法存在的不足，結(jié)合鐵路站場結(jié)構(gòu)特點(diǎn)，從數(shù)據(jù)存儲結(jié)構(gòu)和隊(duì)列結(jié)構(gòu)2 個方面改進(jìn)Dijkstra 算法。

2.2.1 存儲結(jié)構(gòu)優(yōu)化

Dijkstra 算法有2 種應(yīng)用廣泛的數(shù)據(jù)存儲結(jié)構(gòu)：鄰接表和鄰接矩陣。其中，鄰接矩陣會浪費(fèi)大量存儲空間，時間復(fù)雜度更高，而鄰接表可有效節(jié)省存儲空間[11]。鄰接表通常采用鏈表存儲，而站場圖拓?fù)浣Y(jié)構(gòu)較為簡單，每個節(jié)點(diǎn)的相鄰節(jié)點(diǎn)一般僅為1～3 個。若采用鏈表實(shí)現(xiàn)，程序設(shè)計(jì)相對復(fù)雜，因此使用數(shù)組存儲。程序設(shè)計(jì)中用2 維數(shù)組來實(shí)現(xiàn)，數(shù)組每1 個元素均為global_Node_Adj 類型，數(shù)據(jù)結(jié)構(gòu)定義如表1 所示。

表1 鄰接表數(shù)據(jù)結(jié)構(gòu)定義

2.2.2 隊(duì)列結(jié)構(gòu)優(yōu)化

對于傳統(tǒng)的Dijkstra 算法，依次在節(jié)點(diǎn)集中查找未遍歷過的節(jié)點(diǎn)、尋求最優(yōu)解的過程會極大地影響算法效率。為減少這種影響，采用優(yōu)先隊(duì)列(priority_queue)對節(jié)點(diǎn)集進(jìn)行有效排序，使插入或修改數(shù)據(jù)后，節(jié)點(diǎn)集仍能保持有序性。

優(yōu)化隊(duì)列結(jié)構(gòu)采用堆棧，以優(yōu)化每次查找離起始節(jié)點(diǎn)最近的節(jié)點(diǎn)的時間復(fù)雜度，而鄰接表能夠有效改善鄰接矩陣占用過多空間的問題，減少存儲空間的占用。

3 算法設(shè)計(jì)

3.1 進(jìn)路搜索策略

對于進(jìn)路搜索問題，確定好進(jìn)路的起始節(jié)點(diǎn)和終止節(jié)點(diǎn)后，如何快速有效地選擇一條最優(yōu)路徑是關(guān)鍵。當(dāng)遇到對向道岔節(jié)點(diǎn)時，結(jié)合站場有向圖拓?fù)浣Y(jié)構(gòu)的特點(diǎn)，若能避免迂回進(jìn)路，則可以大幅提高運(yùn)行效率[12]。搜索策略主要有廣度優(yōu)先搜索和深度優(yōu)先搜索；深度優(yōu)選搜索是根據(jù)節(jié)點(diǎn)查找其鄰接節(jié)點(diǎn)的過程，而廣度優(yōu)先搜索則是根據(jù)邊查找其鄰接點(diǎn)的過程。根據(jù)改進(jìn)Dijkstra 算法的特點(diǎn)，需要優(yōu)先確認(rèn)邊的信息，故采用廣度優(yōu)先搜索更為方便。

除考慮距離因素外，本文設(shè)計(jì)的進(jìn)路搜索算法還考慮了路徑經(jīng)過的道岔數(shù)目。理論上，搜索進(jìn)路時存在多種遍歷選擇，因此會產(chǎn)生多條搜索路徑。為盡量少占用軌道設(shè)備資源，少搜索分支，設(shè)置一個關(guān)鍵條件—搜索路徑上道岔節(jié)點(diǎn)數(shù)量較少；同時，在道岔節(jié)點(diǎn)數(shù)量一致的情況下，選擇列車進(jìn)路作業(yè)用時最少的路徑，即最短路徑。改進(jìn)Dijkstra 算法中，對邊進(jìn)行松弛操作是根據(jù)目標(biāo)函數(shù)值，目標(biāo)函數(shù)值為：

其中，α、β為權(quán)重系數(shù)，兩者之和為1；C是常量，其目的是考慮到道岔數(shù)與距離存在數(shù)量級差，故在將道岔數(shù)目放大一定比例的基礎(chǔ)上，合理分配權(quán)重。

3.2 變量及數(shù)據(jù)結(jié)構(gòu)定義

改進(jìn)Dijkstra 算法使用廣度優(yōu)先搜索解決賦權(quán)有向圖單源最短路徑問題，最終得到一棵最短路徑樹。在Visual Studio 2019 IDE 中，采用C++編程語言實(shí)現(xiàn)進(jìn)路搜索算法，將生成進(jìn)路的相關(guān)數(shù)據(jù)存放于AllPathForRead.csv 文件。建立Matlab GUI 界面，通過MEX 文件實(shí)現(xiàn)C++與Matlab 的接口，在起點(diǎn)和終點(diǎn)文本框中輸入相應(yīng)節(jié)點(diǎn)時，Matlab GUI 通過回調(diào)函數(shù)自動遍歷找到搜索路徑。

自定義的站場圖數(shù)據(jù)格式如表2 所示，存儲為CSV 格式文件，包含起點(diǎn)字符串、起點(diǎn)類型、終點(diǎn)字符串、終點(diǎn)類型、距離。其中，起點(diǎn)、終點(diǎn)字符串為信號設(shè)備名稱，類型為自定義，默認(rèn)信號燈類型為1，道岔節(jié)點(diǎn)類型為2。

表3 是根據(jù)輸入CSV 重新生成的邊數(shù)組，在表2 基礎(chǔ)上,每個節(jié)點(diǎn)增加了數(shù)字索引，便于程序讀取。

定義一個Dijkstra_Node 結(jié)構(gòu)體數(shù)組，其代碼框架如圖3 所示。該結(jié)構(gòu)體包含當(dāng)前點(diǎn)m_cur_node、父節(jié)點(diǎn)m_parrent_node、是否訪問m_is_visited、距離m_ditance、訪問標(biāo)志、距離、道岔數(shù)、目標(biāo)函數(shù)值。

表2 站場圖CSV 數(shù)據(jù)格式

表3 站場圖邊數(shù)組格式

其中，訪問標(biāo)志用于判斷當(dāng)前節(jié)點(diǎn)是否已被訪問，若該節(jié)點(diǎn)已被訪問則退出，進(jìn)入下一循環(huán)；若未訪問，則需要先將此節(jié)點(diǎn)的訪問標(biāo)志設(shè)置為已訪問，再去訪問該節(jié)點(diǎn)的鄰接點(diǎn)。m_distance 為源節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的距離，m_turnout_node_num 為源節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)所經(jīng)過的道岔數(shù)，m_f_weight_sum 為源節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的目標(biāo)函數(shù)值。

當(dāng)前節(jié)點(diǎn)m_cur_node 是指能夠與源節(jié)點(diǎn)連通的節(jié)點(diǎn)，而m_parrent_node 就是每條路徑對應(yīng)節(jié)點(diǎn)的父節(jié)點(diǎn)。在初始化時，父節(jié)點(diǎn)的m_name 被初始化為“NOT”，代表當(dāng)前節(jié)點(diǎn)還沒有父節(jié)點(diǎn)。是否訪問標(biāo)志m_is_visited 用于確定該節(jié)點(diǎn)是否能被確定為最佳目標(biāo)值。在結(jié)構(gòu)體中，對m_f_weight_sum 進(jìn)行友元重載，其目的是后面優(yōu)先隊(duì)列出列時，以最小值為最高優(yōu)先級，因?yàn)镃++的優(yōu)先隊(duì)列默認(rèn)是最大值先出列。

3.3 算法搜索流程

改進(jìn)Dijkstra 算法中進(jìn)路搜索的具體流程為：

（1）定義元素為Dijkstra_Node 的優(yōu)先隊(duì)列，初始化Dijkstra_Node 數(shù)組信息；

（2）將源節(jié)點(diǎn)的目標(biāo)值設(shè)置為0，并將該節(jié)點(diǎn)壓入優(yōu)先隊(duì)列，判斷隊(duì)列信息是否為空；若為空，跳至（6）；

（3）隊(duì)列信息不為空，則保存源節(jié)點(diǎn)信息，并根據(jù)邊的指向，搜索下一個節(jié)點(diǎn)（即源節(jié)點(diǎn)的鄰節(jié)點(diǎn)）；

（4）獲得源節(jié)點(diǎn)到鄰節(jié)點(diǎn)的距離和道岔數(shù)，計(jì)算目標(biāo)值并進(jìn)行判斷，將目標(biāo)值較小的鄰接節(jié)點(diǎn)設(shè)置為目標(biāo)節(jié)點(diǎn)；

（5）依據(jù)判斷結(jié)果保存目標(biāo)節(jié)點(diǎn)信息，更新Dijkstra_Node 數(shù)組，將目標(biāo)節(jié)點(diǎn)作為源節(jié)點(diǎn)搜索下一節(jié)點(diǎn)，返回（3）；

（6）結(jié)束遍歷，返回初始化Dijkstra_Node 數(shù)組信息。

4 實(shí)例仿真分析

進(jìn)路按結(jié)構(gòu)特點(diǎn)可分為有環(huán)和無環(huán)2 類，無環(huán)進(jìn)路為單路徑直股搜索，有環(huán)進(jìn)路又可分為多路徑直股搜索和彎股搜索。

采用改進(jìn)Dijkstra 算法，對3 種類型進(jìn)路進(jìn)行搜索驗(yàn)證，并利用MATLAB GUI 實(shí)現(xiàn)路徑搜索結(jié)果的可視化。

4.1 單路徑直股搜索

以D14—D28 進(jìn)路為例，這條路徑不包含八字道岔，不存在迂回進(jìn)路，即有且只有1 種路徑選擇。結(jié)果顯示進(jìn)路X—SI 搜索到的最優(yōu)路徑為：D14—14—D16—D22—26—D28，路徑長度為335 m，道岔節(jié)點(diǎn)數(shù)為3，目標(biāo)值為328，如圖4 及圖5 所示。

4.2 多路徑直股搜索

以SF—XI 進(jìn)路為例，其起始和終止信號機(jī)均在同一股道上，但這2 條進(jìn)路均包含八字道岔，在搜尋過程中可有多條路徑選擇。以SF 為始端，XI 為終端，可有2 種路徑選擇：

圖4 D14—D28 進(jìn)路搜索設(shè)置與結(jié)果顯示界面

圖5 D14—D28 進(jìn)路搜索路徑

（1）SF—D6—6—D8—18—D20—22—XI

（2）SF—D6—6—8—D10/D12—10—16—18—D20—22—XI

其中，路徑（1）搜索到的道岔節(jié)點(diǎn)為3，路徑（2）搜索到的道岔節(jié)點(diǎn)為5，路徑（1）上道岔點(diǎn)節(jié)更少，且其長度小于路徑（2），因此路徑（1）為最優(yōu)選擇。采用改進(jìn)Dijkstra 算法,搜索到的最優(yōu)進(jìn)路為路徑（1），路徑長度為664 m，道岔節(jié)點(diǎn)數(shù)為3，目標(biāo)值為575.2，結(jié)果如圖6 及圖7 所示。

圖6 SF—XI 進(jìn)路搜索設(shè)置與結(jié)果顯示界面

圖7 SF—XI 進(jìn)路搜索路徑

4.3 彎股搜索

以D2—D34 為例，對于多路徑選擇的情況，先考慮少搜索分支，比較搜索路徑上道岔節(jié)點(diǎn)數(shù)目。若道岔節(jié)點(diǎn)數(shù)目相同，再考慮路徑最短的進(jìn)路，使用改進(jìn)Dijkstra 算法進(jìn)行進(jìn)路搜索，以尋找最優(yōu)路徑。結(jié)果如圖8 及圖9 所示。

圖8 D2—D34 進(jìn)路搜索設(shè)置與結(jié)果顯示界面

圖9 D2—D34 進(jìn)路搜索控制臺

以D2 為始端，D34 為終端，其路徑選擇有：

（1）D2—2—D4—D14—14—12—D18—20—X6—D32—3—D34

（2）D2—2—D4—D14—D16—D22—26—28—D28—D30—30—D32—32—D34

（3）D2—2—4—8—D12—D10—10—12—D18—20—X6—D32—32—D34

其中，路徑（1）搜索到5 個道岔節(jié)點(diǎn)，路徑（2）搜索到5 個道岔節(jié)點(diǎn)，路徑（3）搜索到7 個道岔節(jié)點(diǎn)；因此，路徑3 被剔除。剩下的路徑（1）和路徑（2）考慮最短路徑，搜索結(jié)果為：Path=D2—2—D4—D14—D16—D22—26—28—D28—D30—30—D32—32—D34，路徑長度為959 m，道岔節(jié)點(diǎn)數(shù)為5，目標(biāo)值為867.2；結(jié)果如圖8 及圖9 所示。

以上3 種類別進(jìn)路搜索的實(shí)驗(yàn)結(jié)果表明：改進(jìn)Dijkstra 算法可高效、正確地完成多種類別進(jìn)路搜索，效果較為滿意。

5 結(jié)束語

提出改進(jìn)Dijkstra 算法，采用鄰接表和優(yōu)先隊(duì)列的數(shù)據(jù)結(jié)構(gòu)，以Viusal Studio 2019 為開發(fā)平臺，在Matlab GUI 中通過接口進(jìn)行調(diào)用，實(shí)現(xiàn)鐵路站場進(jìn)路搜索不重復(fù)、不遺留。該算法應(yīng)用于進(jìn)路搜索的優(yōu)點(diǎn)主要有2 個方面：（1）算法程序與站場數(shù)據(jù)相互獨(dú)立，遍歷不同的站場圖只需修改站場數(shù)據(jù)即可，程序可移植性強(qiáng)；（2）算法設(shè)計(jì)提高了內(nèi)存空間利用率，縮短了搜索時間，提高了站場圖遍歷效率。