文/張海艷

1.引言

突發(fā)事件（比如：①自然災(zāi)害：暴風(fēng)雨、洪澇、地震、暴雪、臺風(fēng)等導(dǎo)致的線路故障或車站能力不足②事故災(zāi)難導(dǎo)致的線路故障或車站能力不足③其他因素）的影響，對鐵路運輸造成了巨大的經(jīng)濟損失。研究突發(fā)事件下列車運行徑路選擇問題，有助于在突發(fā)事件下快速找出最短路徑，及時完成鐵路客貨運輸任務(wù)，減少突發(fā)事件給鐵路運輸帶來的一系列損失。

2.Dijkstra算法求最短徑路

2.1 Dijkstra算法基本思想

Dijkstra算法是典型的單源最短路徑算法，用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。主要特點是以起始點為中心向外層擴展，直到擴展到終點為止[1]。Dijkstra算法計算一個點到其他各點最短路徑時，其算法復(fù)雜度是O（n2），n為網(wǎng)絡(luò)頂點數(shù)[2]。Dijkstra算法的基本思想：令P=（K，R）為一個帶有權(quán)重的有向圖（如圖1所示），設(shè)集合K={0，1，2，3，4}，將集合K分成兩個組別，第一組設(shè)為集合M，M={已求出最短路徑的頂點}，初始時M中只有源節(jié)點，當(dāng)每求出一條最短路徑時，就將應(yīng)的頂點加入集合M 中，直到全部的頂點都加入集合M 中；第二組是設(shè)為集合N，N={未確定最短路徑的頂點}。在加入過程中，總保持從源節(jié)點K到M 中各頂點的最短路徑長度不大于從源節(jié)點K到N中任意頂點間的最短路徑長度。

圖1 有向圖

2.2 Dijkstra算法流程圖

如圖2所示。

圖2 Dijkstra算法流程圖

3.開發(fā)環(huán)境與系統(tǒng)功能設(shè)計

VisualStudio2012以Windows平臺應(yīng)用開發(fā)環(huán)境，它具有一套完整的開發(fā)工具集，支持多種語言，本文系統(tǒng)選擇C#語言進行編程實現(xiàn)，在具備ArcGISEngine的開發(fā)環(huán)境條件下，結(jié)合VS工具箱中的ArcGIS的相關(guān)控件，實現(xiàn)界面的整體布局，在布局完之后，添加License控件獲得ArcGISEngine的許可。通過所需要的功能分析，將所有的功能大體劃分成了3個模塊，分別是窗體創(chuàng)建、地圖操作與工具欄和路徑查詢。對每個模塊下面的具體功能又做了分支，對每個分支又進行了詳細的闡述，得出最終的成果。窗體創(chuàng)建：包括地圖導(dǎo)出和空間查詢兩個窗體。地圖導(dǎo)出窗體涉及導(dǎo)出設(shè)置和導(dǎo)出路徑兩方面的內(nèi)容，根據(jù)導(dǎo)出設(shè)置里的輸出分辨率選擇用戶所需要的分辨率，選擇導(dǎo)出路徑，則可以將地圖按照圖片的格式輸出?？臻g查詢窗體主要根據(jù)地圖上的圖層要素，通過空間查詢窗體，選擇要查詢的圖層，查詢結(jié)果將在主窗體高亮顯示。地圖操作與工具欄：地圖操作主要包括鷹眼、制圖的查看及右鍵菜單的實現(xiàn)。鷹眼功能主要實現(xiàn)用戶可以在鷹眼窗體中控制主地圖的顯示范圍，制圖的查看功能為主窗體地圖和制版地圖的同步顯示，為后續(xù)功能的完善做好鋪墊，右鍵菜單主要針對圖層，主要對圖層進行移除、主地圖縮放至圖層及打開圖層的屬性表等功能。工具欄主要是對地圖的操作，如對地圖的放大縮小工具、測量工具等，本文對路徑分析專門設(shè)計了路徑分析工具條，點擊路徑顯示圖標(biāo)，可以在地圖上顯示所查找的路徑。地圖的基本操作主要利用TOCControl和MapControl控件來實現(xiàn)。路徑查詢：包括最短路的查詢、繞過故障線路和繞過故障車站的最短路的查詢?nèi)矫娴膬?nèi)容。在菜單欄里選擇起始點按鈕，在地圖上標(biāo)記起始點，進行最短路的查詢，同樣，在菜單欄里選擇故障車站和故障線路按鈕，可以得到繞過故障車站和故障線路的最短路徑。在解決方案資源管理器中右擊鐵路應(yīng)急處置系統(tǒng)，添加類，在添加新項里選擇ArcGIS里的ExtendingArcObjects、選擇BaseTool、新建AddNetBarriesTool類和AddNetStopsTool類，用于在地圖上添加站點和障礙點[4]。同樣，在添加新項里選擇ArcGIS里的ExtendingArcObjects，選擇BaseCommand，新建ShortPathSolveCommand類，用于最短路分析。

4.系統(tǒng)功能的設(shè)計與實現(xiàn)

4.1 屬性數(shù)據(jù)庫設(shè)計

本文系統(tǒng)是建立在ArcGISEngine平臺上的，在ArcCatalog10.2里建立地理數(shù)據(jù)庫：鐵路.gdb，在數(shù)據(jù)庫里建立要素數(shù)據(jù)集：各省省會及地級市、各省市界和鐵路線路。

4.2 系統(tǒng)主要功能的實現(xiàn)

啟動鐵路應(yīng)急處置系統(tǒng)，輸入用戶名、密碼及相對應(yīng)的驗證碼，即可進入系統(tǒng)主界面，點擊徑路分析模塊，列車運行徑路搜索與展示的主界面展示出來，主要由菜單欄、工具欄、鷹眼窗口、主地圖窗口、圖層控制等構(gòu)成。系統(tǒng)的主要功能包括兩方面的內(nèi)容，一是對地圖的一些基本操作，二是最短路徑的實現(xiàn)。其中，最短路徑的實現(xiàn)是本系統(tǒng)最為核心的功能，在擁有鐵路地圖數(shù)據(jù)資料的基礎(chǔ)上，在主窗口界面實現(xiàn)最短路的搜索與展示。界面顯示以神黃鐵路（神池南—黃驊港）為例，實現(xiàn)最短路徑的搜索與顯示。點擊菜單里的“起始點”按鈕，添加路徑的起始點，在地圖顯示光標(biāo)，可以在地圖上標(biāo)注起始點，點擊“求解路徑”按鈕，此時網(wǎng)絡(luò)工具條轉(zhuǎn)為可用狀態(tài)，點擊路徑生成，則在地圖上顯示神黃鐵路的最短路徑，如圖3所示。

圖3 神池南—黃驊港鐵路最短路徑

添加障礙點“滴流磴”，查詢路徑，得到繞過“滴流磴”的最短路徑如圖4所示。

圖4 繞過障礙點的最短路徑

添加障礙線路，查詢路徑，得到繞過障礙線路的最短路徑如圖5所示。

圖5 繞過障礙線路的最短路徑

5.結(jié)論

本文詳細闡述了Dijkstra算法的基本思想，實現(xiàn)了基于部分鐵路網(wǎng)的最短路徑的查詢功能。對突發(fā)事件下列車運行徑路的選擇起到至關(guān)重要的作用。我國的鐵路運輸優(yōu)先考慮最短路徑，其次才是迂回徑路和特定徑路。本文系統(tǒng)的最短路徑的查詢包括兩方面的內(nèi)容，一是繞過障礙車站的最短路徑查詢，主要考慮了實際運輸過程中車站運輸能力不足或車站能力產(chǎn)生故障等情況；二是繞過障礙線路的最短路徑的查詢，線路障礙涉及突發(fā)事件下的水害斷道、鐵路交通事故導(dǎo)致的線路區(qū)間能力不足等實際情況。

引用出處

[1]成惠.鐵路運輸特定經(jīng)由算法的研究與實現(xiàn)[D].中南大學(xué)，2007.

[2]李引珍，顧守淮.鐵路網(wǎng)絡(luò)兩頂點間最短路徑定向搜索算法[J].鐵道學(xué)報，1997，19(2):25-27.