基于改進Dijkstra 算法的進路搜索研究

杜文文，楊 揚

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

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

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

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

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

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

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

圖1 某鐵路站場平面布置

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

2 Dijkstra 算法的改進

2.1 傳統(tǒng)Dijkstra 算法

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

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

2.2 優(yōu)化方法

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

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

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

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

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

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

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

3 算法設(shè)計

3.1 進路搜索策略

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

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

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

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

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

定義一個Dijkstra_Node 結(jié)構(gòu)體數(shù)組，其代碼框架如圖3 所示。該結(jié)構(gòu)體包含當(dāng)前點m_cur_node、父節(jié)點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é)點是否已被訪問，若該節(jié)點已被訪問則退出，進入下一循環(huán)；若未訪問，則需要先將此節(jié)點的訪問標(biāo)志設(shè)置為已訪問，再去訪問該節(jié)點的鄰接點。m_distance 為源節(jié)點到當(dāng)前節(jié)點的距離，m_turnout_node_num 為源節(jié)點到當(dāng)前節(jié)點所經(jīng)過的道岔數(shù)，m_f_weight_sum 為源節(jié)點到當(dāng)前節(jié)點的目標(biāo)函數(shù)值。

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

3.3 算法搜索流程

改進Dijkstra 算法中進路搜索的具體流程為：

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

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

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

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

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

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

4 實例仿真分析

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

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

4.1 單路徑直股搜索

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

4.2 多路徑直股搜索

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

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

圖5 D14—D28 進路搜索路徑

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

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

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

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

圖7 SF—XI 進路搜索路徑

4.3 彎股搜索

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

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

圖9 D2—D34 進路搜索控制臺

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

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

5 結(jié)束語

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