基于Dijkstra算法的突發(fā)事件下列車(chē)最短徑路的設(shè)計(jì)與實(shí)現(xiàn)

文/張海艷

1.引言

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

2.Dijkstra算法求最短徑路

2.1 Dijkstra算法基本思想

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

圖1 有向圖

2.2 Dijkstra算法流程圖

如圖2所示。

圖2 Dijkstra算法流程圖

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

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

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

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

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

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

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

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

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

圖4 繞過(guò)障礙點(diǎn)的最短路徑

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

圖5 繞過(guò)障礙線路的最短路徑

5.結(jié)論

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

引用出處

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

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