曹朋朋 張晶晶 許志強(qiáng) 喬俊杰

(西安電子科技大學(xué)機(jī)電工程學(xué)院 陜西 西安 710000)

一種基于GIS的鐵路設(shè)備維修路線規(guī)劃方法

曹朋朋 張晶晶 許志強(qiáng) 喬俊杰

(西安電子科技大學(xué)機(jī)電工程學(xué)院 陜西 西安 710000)

針對鐵路設(shè)備的維修管理進(jìn)行研究。在總結(jié)某站基于GIS的鐵路設(shè)備維修管理系統(tǒng)應(yīng)用經(jīng)驗的基礎(chǔ)上，論述基于GIS的鐵路設(shè)備維修路線的規(guī)劃方法。其中包括空間數(shù)據(jù)庫的設(shè)計、地理信息數(shù)據(jù)質(zhì)量保證、地理信息平臺的開發(fā)、對經(jīng)典Dijkstra算法的優(yōu)化及對優(yōu)化后算法的效率分析等內(nèi)容。實際應(yīng)用表明該方法能夠解決鐵路設(shè)備維修路線規(guī)劃問題，為鐵路設(shè)備維修行車指揮提供決策支持，為提高鐵路設(shè)備維修效率提供有效途徑。

地理信息系統(tǒng) 鐵路 設(shè)備維修 路線規(guī)劃

0 引 言

信息技術(shù)快速發(fā)展的成果在各方面為人們的生產(chǎn)和生活服務(wù)[1]，GIS也在人們的生產(chǎn)和生活中也扮演著舉足輕重的角色[2-3]。在信息化快速發(fā)展取得眾多成果的同時，人們已越來越重視鐵路設(shè)備維修管理的信息化。在保障行車安全和提高列車作業(yè)效率方面，合理、有效的鐵路設(shè)備維修管理是重中之重[4]。

在鐵路設(shè)備維修中，維修路線選擇多是由調(diào)度人員根據(jù)經(jīng)驗設(shè)計路徑方案。由于人工處理的局限性，在路線選擇的時候往往不能對多方面信息進(jìn)行系統(tǒng)全面的考慮，尤其是時間、地形地貌、高程等信息。地理信息系統(tǒng)可對空間數(shù)據(jù)及相關(guān)屬性信息進(jìn)行有效的管理[5]。地理信息技術(shù)的出現(xiàn)為鐵路設(shè)備維修管理提供了新的支撐手段。

本文針對鐵路設(shè)備維修中路線規(guī)劃的問題，提出一種基于GIS的鐵路設(shè)備維修路線規(guī)劃方法。該方法對經(jīng)典Dijkstra算法優(yōu)化并將其應(yīng)用于GIS，避免了傳統(tǒng)方式中僅憑人工經(jīng)驗進(jìn)行鐵路設(shè)備維修路線選擇的弊端。該方法能夠在鐵路設(shè)備維修中為行車指揮提供決策支持，從而為縮短鐵路設(shè)備維修工作周期提供一個非常有效的途徑。

1 基于GIS的鐵路設(shè)備維修路線規(guī)劃方法

通常路線規(guī)劃問題最終可歸結(jié)為在一定條件下的最短路徑問題[6]。在最短路徑規(guī)劃方面的算法中，Dijkstra算法在單源最短路徑求解問題上是比較經(jīng)典的算法。本文在該經(jīng)典算法的基礎(chǔ)上對其進(jìn)行優(yōu)化。對該算法的優(yōu)化主要集中在兩個方面，一方面在存儲結(jié)構(gòu)上采用鄰接表，另一方面在算法結(jié)構(gòu)上采用最小堆。

1.1 基于GIS的路線規(guī)劃方法概述

本文在GIS的基礎(chǔ)上，通過對經(jīng)典算法的優(yōu)化給出了實現(xiàn)鐵路設(shè)備維修管理路線規(guī)劃的方法。圖1為基于GIS的鐵路設(shè)備維修路線規(guī)劃方法的示意。本文的基礎(chǔ)工作是對經(jīng)典Dijkstra算法優(yōu)化和空間數(shù)據(jù)庫的設(shè)計。在此基礎(chǔ)之上，再從電子地圖中獲取道路信息，并在空間數(shù)據(jù)庫中存入道路信息。在進(jìn)行路徑規(guī)劃時，從空間數(shù)據(jù)庫加載道路信息，通過優(yōu)化后的算法獲得最短路徑。然后以特殊路段的限制條件來過濾不符合時間限制的路徑，直至得到符合條件的路徑或沒有該限制條件下的可行路徑。利用這種方法獲取到最優(yōu)路徑后，將鐵路設(shè)備維修路線規(guī)劃結(jié)果通過GIS平臺呈現(xiàn)給用戶。

圖1 基于GIS的鐵路設(shè)備維修路線規(guī)劃方法示意圖

1.2 經(jīng)典Dijkstra算法

Dijkstra算法在求解最短路徑方面是一種較好的算法[7-8]。它適用的情況是所有弧段的權(quán)值均大于或等于零。其算法思想步驟如下：

① 帶權(quán)值的有向圖使用鄰接矩陣AdjMat來表示，用AdjMat[i][j]來表示弧段上的權(quán)值。若AdjMat[i][j]等于∞，則表示弧段不存在，亦即頂點vi與vj間不存在直接相連的弧段。集合V為所有節(jié)點的集合，已找到從源點v出發(fā)的最短路徑終點組成的集合為集合S，集合S的初始狀態(tài)為空集。用LocVex(G,v)來表示起點v在圖中的位置。從源點v出發(fā)到圖中其余頂點vi的可能達(dá)到的最短路徑初值為：

D[i]=AdjMat[LocVex(G,v)][i]vi∈V

(1)

② 選擇vj使得：

D[j]=min{D[j]|vj∈V-S}

(2)

vj就是當(dāng)前求得的一條從v出發(fā)的最短路徑的終點。令：

S=S∪{vj}

(3)

③ 修改從v出發(fā)到集合{V-S}上任一頂點vk可達(dá)的最短路徑長度。如果：

D[k]>D[j]+AdjMat[j][k]

(4)

則修改D[k]為：

D[k]=D[j]+AdjMat[j][k]

(5)

④ 反復(fù)執(zhí)行n-1次步驟②和步驟③，即可按最短路徑長度的逐增順序依次求得從起點v到圖中其他剩余頂點的最短路徑。

1.3 Dijkstra算法優(yōu)化

在面對頂點較多的電子地圖求最短路徑的問題時，算法的效率是關(guān)鍵。本文對經(jīng)典Dijkstra算法的優(yōu)化主要集中在兩個方面，一方面在存儲結(jié)構(gòu)上采用鄰接表，另一方面在算法結(jié)構(gòu)上采用最小堆數(shù)據(jù)結(jié)構(gòu)。

(1) 算法結(jié)構(gòu)優(yōu)化

本文利用最小堆對算法結(jié)構(gòu)進(jìn)行優(yōu)化，如下所示為優(yōu)化的基本步驟：

① 用鄰接表AdjList表示帶權(quán)的有向圖G?；《?vi,vj>上的權(quán)值用AdjList(i,j)表示。若弧段不存在，則將AdjList(i,j)賦值為∞。用D[i]表示從起點v0到圖中各個頂點vi的最短路徑長度，用LocVex(G,v0)來表示v0在圖中的位置。D[i]可能的初值為：

D[i]=AdjList[LocVex(G,v0),i]v0∈V

(6)

② 若圖中的頂點個數(shù)為n，則新建一個空的最小堆，同時為最小堆MinHeap[n+1]申請存儲空間。最小堆中的每個元素MinHeap[i]均包含兩層含義，第一層含義是該頂點的編號，另一層的含義是從源點到該頂點弧段的權(quán)值。

③ 初始化最小堆：向上述的最小堆中逐次插入有向圖G中的各個元素，具體如下：

MinHeap[n+1]←(i,D[i]) 0≤i≤n

(7)

其中編號為i的最小堆元素的值用D[i]表示。

④ 刪除堆中的源點v0：

MinHeap[n+1]→v0

(8)

⑤ 最后，判斷上述最小堆是否已為空。若最小堆已經(jīng)不包含任何元素，則計算最短路徑已完成，跳出程序。否則刪除關(guān)鍵值最小的元素，也就是將堆頂元素vi刪除。然后對最小堆中其余的元素重新進(jìn)行一次堆調(diào)整，使之依然是一個最小堆。

堆調(diào)整的方法：依次判斷堆中的剩余元素，假設(shè)某元素vk，若：

D[i]+AdjList(vi,vk)

(9)

則修改D[k]為：

D[k]=D[i]+AdjList(vi,vk)

(10)

若最小堆中某元素的值D[k]被修改，在這種情況下需要重新調(diào)整堆，使其仍舊滿足最小堆的性質(zhì)。然后在所有元素均被輸出的條件沒有滿足前，重復(fù)執(zhí)行步驟⑤直至堆中不含任何元素。

對于有e條邊和n個頂點的圖，由以上論述可知經(jīng)典Dijkstra算法的時間復(fù)雜度是O(n2)，而優(yōu)化后的時間復(fù)雜度僅為Ο(nlogn+e)。

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

圖的結(jié)構(gòu)與其他數(shù)據(jù)結(jié)構(gòu)相比是較復(fù)雜的。因為其中任意的兩個頂點之間都有可能存在弧段，并且這種弧段還很可能是有方向的[9]。因此用圖中的數(shù)據(jù)元素在存儲區(qū)中的物理位置來體現(xiàn)其中頂點間的相互關(guān)系是不可行的。換言之，圖是不能按順序映像存儲結(jié)構(gòu)來存儲。實踐中，常用鄰接多重表、十字鏈表、鄰接矩陣和鄰接表等來存儲圖[10-11]。

由于鄰接多重表和十字鏈表存儲結(jié)構(gòu)不容易實現(xiàn)，這有可能會增加程序的不確定性。實現(xiàn)起來較為簡單是鄰接矩陣和鄰接表存儲結(jié)構(gòu)，因而這兩種存儲結(jié)構(gòu)使用頻率較高。經(jīng)典Djikstra算法采用的是鄰接矩陣存儲結(jié)構(gòu)，對于有e條邊和n個頂點的圖其空間復(fù)雜度為Ω(n2)。本文在利用鄰接表進(jìn)行優(yōu)化后，其空間復(fù)雜度為Ω(n+e)。

2 最優(yōu)路徑規(guī)劃在GIS中的應(yīng)用

最優(yōu)路徑規(guī)劃在GIS中的實現(xiàn)主要包括創(chuàng)建空間數(shù)據(jù)庫和優(yōu)化后的Dijkstra的算法在GIS中進(jìn)行路徑規(guī)劃的應(yīng)用。在進(jìn)行路徑規(guī)劃時，從空間數(shù)據(jù)庫加載道路信息，通過優(yōu)化后的算法獲得最短路徑，最終將鐵路設(shè)備維修路線規(guī)劃結(jié)果通過GIS平臺呈現(xiàn)給用戶。

2.1 創(chuàng)建空間數(shù)據(jù)庫

在GIS中，存儲空間道路信息的圖層主要包括道路弧段圖層和道路節(jié)點圖層。在圖層中引入節(jié)點和弧段的概念來表示現(xiàn)實世界中的道路情況，這樣將現(xiàn)實中的道路轉(zhuǎn)化為數(shù)據(jù)結(jié)構(gòu)中的帶權(quán)有向圖。有向圖中的頂點表示道路的交叉口，有向圖中的弧段表示道路交叉口間的道路，有向圖中弧段上的權(quán)值表示道路交叉口間的距離。

(1) 地理信息數(shù)據(jù)的近似處理

由于真實世界中的道路的變化具有不規(guī)則性，使得提取道路弧段圖層沒有創(chuàng)建道路節(jié)點圖層那么容易。比如弧度很小的彎曲道路，通常當(dāng)做直線進(jìn)行處理，對于弧度較大的彎曲道路則看作兩條直線道路的相交。通過這些近似處理后用線段將道路表達(dá)出來，從而可獲得電子地圖文件[12]。

(2) 空間數(shù)據(jù)庫的創(chuàng)建

根據(jù)1.1節(jié)所述算法的數(shù)據(jù)需求，進(jìn)行最短路徑規(guī)劃的前提是從電子地圖中將道路信息提取出來。道路弧段圖層的數(shù)據(jù)和道路節(jié)點圖層的數(shù)據(jù)需要保存到空間數(shù)據(jù)庫中，在空間數(shù)據(jù)中建立道路弧段圖層表和道路節(jié)點圖層表是存儲這兩類圖層信息的基礎(chǔ)。

道路弧段圖層的表結(jié)構(gòu)如表1所示。道路ID是道路弧段的唯一標(biāo)識。由上文可知，一條道路弧段有起始點與終止點和一定長度。表中的限制時間為該段道路不允許通過的起止時間點。

表1 道路弧段圖層表結(jié)構(gòu)

考慮維修路線規(guī)劃的實際需要，例如在路線的彎道轉(zhuǎn)向時需要了解該節(jié)點的名稱及位置，故此增加道路節(jié)點圖層。各條道路弧段的相交點存入該圖層有利于計算和顯示道路最短路徑。表2為道路節(jié)點圖層的表結(jié)構(gòu)，節(jié)點ID為主鍵是圖中節(jié)點的唯一標(biāo)識，此外一個節(jié)點還包含節(jié)點名稱、坐標(biāo)等信息。

表2 道路節(jié)點圖層表結(jié)構(gòu)

2.2 優(yōu)化后的Dijkstra算法在GIS中的應(yīng)用

優(yōu)化后的Dijkstra算法在GIS中的應(yīng)用如圖2所示。首先根據(jù)用戶設(shè)定的起始點和終點，利用優(yōu)化后的Dijkstra算法進(jìn)行初次最優(yōu)路徑規(guī)劃，若最優(yōu)路徑中不包含特殊路段，則顯示最優(yōu)路徑規(guī)劃結(jié)果。若最優(yōu)路徑中包含特殊路段，這種情況下有兩種情況，其一是最優(yōu)路徑中所包含的特殊路段限制時間區(qū)間不包含預(yù)估通過時間，這種情況下則直接顯示最優(yōu)路徑規(guī)劃結(jié)果。另一種情況是最優(yōu)路徑中所包含的特殊路段限制時間區(qū)間包含預(yù)估通過時間，這種情況下則過濾掉上述的特殊路徑，然后再次進(jìn)行最優(yōu)路徑規(guī)劃，當(dāng)有路徑可用時則顯示最優(yōu)路徑規(guī)劃結(jié)果。

圖2 最優(yōu)路徑規(guī)劃在GIS中的應(yīng)用

再次進(jìn)行最優(yōu)路徑規(guī)劃時，過濾掉前次規(guī)劃的路徑中所包含的具有時間沖突的特殊路段，并將這些特殊路段在地圖中標(biāo)記為禁止駛?cè)肼范?限制路段)。若在當(dāng)前限制條件下(限制時間區(qū)間與預(yù)估通過時間沖突)，沒有可行結(jié)果，則退出路徑路徑搜索，提示“當(dāng)前限制條件下沒有可用的路徑”。

圖3為基于GIS的鐵路設(shè)備維修路線規(guī)劃界面，該GIS平臺除包含最優(yōu)路徑規(guī)劃功能外還包含地理信息系統(tǒng)的常用功能，如地圖縮放、測量工具、地物屬性查看工具等。

圖3 基于GIS的鐵路設(shè)備維修路線規(guī)劃界面

圖3中給出了鐵路設(shè)備維修路線規(guī)劃的效果，節(jié)點3至節(jié)點6的道路為規(guī)劃出的維修路線中的某段。其中實線為最優(yōu)路線，節(jié)點3至節(jié)點4與節(jié)點5至節(jié)點6之間均避開了不滿足限制條件的特殊路段，避開的路段如圖中虛線所示。

2.3 算法效率分析

為了驗證上述優(yōu)化后的Dijkstra算法的有效性與可行性，現(xiàn)利用jvisualvm對其執(zhí)行內(nèi)存和執(zhí)行時間進(jìn)行分析。分別將優(yōu)化前后的算法應(yīng)用于某站基于GIS的鐵路設(shè)備維修管理系統(tǒng)中，進(jìn)行效率分析。

(1) 測試環(huán)境

采用的測試環(huán)境如表3所示。

表3 測試環(huán)境

(2) 分析方法

圖4為堆內(nèi)存監(jiān)視圖。在jvisualvm中通過監(jiān)視“使用的堆”字節(jié)數(shù)的變化情況，可得在進(jìn)行鐵路設(shè)備維修路徑規(guī)劃過程內(nèi)存的占用情況。圖5為CPU時間圖。通過抽樣器可根據(jù)“線程CPU時間”的“增量”得到最優(yōu)路徑規(guī)劃線程執(zhí)行一次路徑規(guī)劃所消耗的時間。

圖5 線程CPU時間圖

(3) 結(jié)果分析

根據(jù)2.3節(jié)中(2)所述分析方法，使用弧段數(shù)分別為1 000、3 000、6 000、10 000的數(shù)據(jù)進(jìn)行測試。各組數(shù)據(jù)的測試結(jié)果平均值如表4所示。

表4 優(yōu)化前后的算法效率分析

根據(jù)表4可得執(zhí)行內(nèi)存分析圖與執(zhí)行時間分析圖，分別如圖6與圖7所示。圖6與圖7中虛線表示優(yōu)化后，實線表示優(yōu)化前，顯然優(yōu)化后的Dijkstra算法在空間效率上占用內(nèi)存較少，在時間效率上用時較短，具有比較明顯的優(yōu)勢。

圖6 執(zhí)行內(nèi)存分析圖

圖7 執(zhí)行時間分析圖

3 結(jié) 語

本文針對鐵路設(shè)備維修路線規(guī)劃進(jìn)行研究，將優(yōu)化后的Dijkstra算法應(yīng)用于GIS中，并通過對算法優(yōu)化前后執(zhí)行效率的分析得出以下結(jié)論：

(1) 本文所述的基于GIS的鐵路設(shè)備維修路線規(guī)劃方法，表明優(yōu)化后的Dijkstra算法應(yīng)用于GIS具有可行性和有效性。

(2) 這種方法所獲取的路徑不一定是權(quán)值總和最小的路線，而是避開了特殊路段時間限制的最優(yōu)路線。該方法不僅能滿足最優(yōu)路徑的選擇，而且空間效率上占用內(nèi)存較少，在時間效率上用時較短。

(3) 鐵路設(shè)備維修路線規(guī)劃依托于地理信息系統(tǒng)，能夠在盡可能減少人工干預(yù)的情況下完成維修路線的制定，為提高鐵路設(shè)備維修效率提供一個非常有效的途徑，這種方法具有廣泛的實際應(yīng)用價值。

[1] 陳煒，蘇厚勤，柴炯. 基于WebSocket技術(shù)水文資源監(jiān)管系統(tǒng)的研究與實現(xiàn)[J]. 計算機(jī)應(yīng)用與軟件，2016，33(3)：104-108,113．

[2] 葛彬，尚建嘎，余芳文，等．一種融合WebGIS和Web3D技術(shù)的實時定位系統(tǒng)可視化框架[J]．計算機(jī)應(yīng)用與軟件，2015，32(1)：68-70,117．

[3] Guzzi J, Caro G A D. From indoor GIS maps to path planning for autonomous wheelchairs[C]//IEEE/RSJ International Conference on Intelligent Robots and Systems. IEEE, 2016:4773-4779．

[4] 中國鐵路總公司．鐵路技術(shù)管理規(guī)程[M]．北京：中國鐵道出版社，2014．

[5] Kallel A, Serbaji M M, Zairi M. Using GIS-Based Tools for the Optimization of Solid Waste Collection and Transport: Case Study of Sfax City, Tunisia[J]. Journal of Engineering,2016,(2016-3-10), 2016, 2016(10):1-7.

[6] 北京理工大學(xué)．一種基于GIS的無人地面車輛自主行駛輔助系統(tǒng)：中國，201510093286．7[P]．2015-08-05.

[7] 嚴(yán)蔚敏，吳偉民．?dāng)?shù)據(jù)結(jié)構(gòu)[M]．北京：清華大學(xué)出版社，2007.

[8] 鄧俊輝．?dāng)?shù)據(jù)結(jié)構(gòu)(C++語言版)[M]．3版. 北京：清華大學(xué)出版社，2013.

[9] 孫蘭會，成鋒，陸愈實．基于GIS的路徑規(guī)劃算法研究與實現(xiàn)[J]. 現(xiàn)代電子技術(shù)， 2016，39(5)：101-104,109.

[10] 蔡俊，李欽富，王金泉．一種Dijkstra優(yōu)化算法的研究與實現(xiàn)[J]．信息技術(shù)，2011，35(4)：104-107.

[11] 姚亞峰，方賢進(jìn)，陳代梅．Dijkstra算法的一種高效率實現(xiàn)[J]．計算機(jī)與數(shù)字工程，2007，35(7)：21-22,44.

[12] 楊康，李滿春，劉永學(xué)，等．遙感影像道路的多點同時快速進(jìn)行提取方法[J]．遙感技術(shù)與應(yīng)用，2011，26(3)：294-302．

PATHPLANNINGFORRAILWAYEQUIPMENTMAINTENANCEBASEDONGIS

Cao Pengpeng Zhang Jingjing Xu Zhiqiang Qiao Junjie

(SchoolofElectro-MechanicalEngineering,XidianUniversity,Xi’an710000,Shaanxi,China)

On researching management of railway equipment maintenance, summarizing the application experience of railway equipment maintenance management system based on GIS in a station. This paper discusses the path planning of railway equipment maintenance based on GIS. Main content of the work included the design of spatial database, the quality assurance of geographic information data, the development of GIS platform, the optimization of the classical Dijkstra algorithm and analysis of the efficiency of the optimized algorithm. Practical application shows that this method can solve the path planning problem of railway equipment maintenance, provide decision support for command and an effective way to shorten the cycle of railway equipment maintenance.

GIS Railway Equipment maintenance Path planning

2017-02-24。國家自然科學(xué)基金項目(51505357，51605361)。曹朋朋，碩士生，主研領(lǐng)域：計算機(jī)輔助設(shè)計及虛擬現(xiàn)實技術(shù)。張晶晶，碩士生。許志強(qiáng)，碩士生。喬俊杰，碩士生。

TP3

A

10.3969/j.issn.1000-386x.2017.12.015