杜文文，楊 揚

（西南交通大學 信息科學與技術學院，成都 611756）

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

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

1 站場拓撲結構的有向圖建模

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

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

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

圖1 某鐵路站場平面布置

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

2 Dijkstra 算法的改進

2.1 傳統(tǒng)Dijkstra 算法

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

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

2.2 優(yōu)化方法

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

2.2.1 存儲結構優(yōu)化

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

表1 鄰接表數據結構定義

2.2.2 隊列結構優(yōu)化

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

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

3 算法設計

3.1 進路搜索策略

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

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

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

3.2 變量及數據結構定義

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

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

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

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

表2 站場圖CSV 數據格式

表3 站場圖邊數組格式

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

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

3.3 算法搜索流程

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

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

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

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

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

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

（6）結束遍歷，返回初始化Dijkstra_Node 數組信息。

4 實例仿真分析

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

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

4.1 單路徑直股搜索

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

4.2 多路徑直股搜索

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

圖4 D14—D28 進路搜索設置與結果顯示界面

圖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é)點數為3，目標值為575.2，結果如圖6 及圖7 所示。

圖6 SF—XI 進路搜索設置與結果顯示界面

圖7 SF—XI 進路搜索路徑

4.3 彎股搜索

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

圖8 D2—D34 進路搜索設置與結果顯示界面

圖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）考慮最短路徑，搜索結果為：Path=D2—2—D4—D14—D16—D22—26—28—D28—D30—30—D32—32—D34，路徑長度為959 m，道岔節(jié)點數為5，目標值為867.2；結果如圖8 及圖9 所示。

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

5 結束語

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