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

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

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

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

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

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

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

0 引 言

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

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

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

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

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

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

本文在GIS的基礎(chǔ)上，通過對(duì)經(jīng)典算法的優(yōu)化給出了實(shí)現(xiàn)鐵路設(shè)備維修管理路線規(guī)劃的方法。圖1為基于GIS的鐵路設(shè)備維修路線規(guī)劃方法的示意。本文的基礎(chǔ)工作是對(duì)經(jīng)典Dijkstra算法優(yōu)化和空間數(shù)據(jù)庫(kù)的設(shè)計(jì)。在此基礎(chǔ)之上，再?gòu)碾娮拥貓D中獲取道路信息，并在空間數(shù)據(jù)庫(kù)中存入道路信息。在進(jìn)行路徑規(guī)劃時(shí)，從空間數(shù)據(jù)庫(kù)加載道路信息，通過優(yōu)化后的算法獲得最短路徑。然后以特殊路段的限制條件來過濾不符合時(shí)間限制的路徑，直至得到符合條件的路徑或沒有該限制條件下的可行路徑。利用這種方法獲取到最優(yōu)路徑后，將鐵路設(shè)備維修路線規(guī)劃結(jié)果通過GIS平臺(tái)呈現(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]等于∞，則表示弧段不存在，亦即頂點(diǎn)vi與vj間不存在直接相連的弧段。集合V為所有節(jié)點(diǎn)的集合，已找到從源點(diǎn)v出發(fā)的最短路徑終點(diǎn)組成的集合為集合S，集合S的初始狀態(tài)為空集。用LocVex(G,v)來表示起點(diǎn)v在圖中的位置。從源點(diǎn)v出發(fā)到圖中其余頂點(diǎn)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ā)的最短路徑的終點(diǎn)。令：

S=S∪{vj}

(3)

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

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

(4)

則修改D[k]為：

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

(5)

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

1.3 Dijkstra算法優(yōu)化

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

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

本文利用最小堆對(duì)算法結(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]表示從起點(diǎn)v0到圖中各個(gè)頂點(diǎn)vi的最短路徑長(zhǎng)度，用LocVex(G,v0)來表示v0在圖中的位置。D[i]可能的初值為：

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

(6)

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

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

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

(7)

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

④ 刪除堆中的源點(diǎn)v0：

MinHeap[n+1]→v0

(8)

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

堆調(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í)行步驟⑤直至堆中不含任何元素。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 算法效率分析

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

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

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

表3 測(cè)試環(huán)境

(2) 分析方法

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

圖5 線程CPU時(shí)間圖

(3) 結(jié)果分析

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

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

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

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

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

3 結(jié) 語

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

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

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

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

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

[2] 葛彬，尚建嘎，余芳文，等．一種融合WebGIS和Web3D技術(shù)的實(shí)時(shí)定位系統(tǒng)可視化框架[J]．計(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] 中國(guó)鐵路總公司．鐵路技術(shù)管理規(guī)程[M]．北京：中國(guó)鐵道出版社，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)：中國(guó)，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] 孫蘭會(huì)，成鋒，陸愈實(shí)．基于GIS的路徑規(guī)劃算法研究與實(shí)現(xiàn)[J]. 現(xiàn)代電子技術(shù)， 2016，39(5)：101-104,109.

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

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

[12] 楊康，李滿春，劉永學(xué)，等．遙感影像道路的多點(diǎn)同時(shí)快速進(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。國(guó)家自然科學(xué)基金項(xiàng)目(51505357，51605361)。曹朋朋，碩士生，主研領(lǐng)域：計(jì)算機(jī)輔助設(shè)計(jì)及虛擬現(xiàn)實(shí)技術(shù)。張晶晶，碩士生。許志強(qiáng)，碩士生。喬俊杰，碩士生。

TP3

A

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