發(fā)布時間：2018-11-19所屬分類：科技論文瀏覽：1次
摘 要： 【摘要】本文主要研究了單源最短路徑優(yōu)化節(jié)點的技術和方法，并將其運用于事故的應急救援中，同時提出了技術支持系統(tǒng)中最短路徑可視化的優(yōu)化結構框架。結合單源最短路徑算法，在地理信息系統(tǒng)中以數(shù)字高程模型和衛(wèi)星影像數(shù)據(jù)為基礎，針對事故危險區(qū)域開發(fā)出人
【摘要】本文主要研究了單源最短路徑優(yōu)化節(jié)點的技術和方法，并將其運用于事故的應急救援中，同時提出了技術支持系統(tǒng)中最短路徑可視化的優(yōu)化結構框架。結合單源最短路徑算法，在地理信息系統(tǒng)中以數(shù)字高程模型和衛(wèi)星影像數(shù)據(jù)為基礎，針對事故危險區(qū)域開發(fā)出人員疏散和救援的最短路徑可視化算法。此項技術完善了應急救援路徑自動化選擇模式，為事故中迅速展開人員疏散和組織有效的應急救援工作提供強有力的技術支持。
【關鍵詞】事故,應急救援,最短路徑,可視化
1研究的背景與意義
在生產(chǎn)經(jīng)營活動中，無論是在生產(chǎn)、運輸過程中還是在儲存、經(jīng)營、使用環(huán)節(jié)，都可能發(fā)生重大安全生產(chǎn)事故，造成重大人員傷亡和財產(chǎn)損失。如2005年3月29日晚，在淮安境內(nèi)高速公路，因交通事故誘發(fā)液氯泄漏，造成29人死亡，疏散群眾1萬多人。2010年7月，南京市地下丙烯管道泄漏爆燃，造成22人死亡，120多人受傷住院。當發(fā)生重大事故時，如果能及時快速組織人員疏散撤離，將會減少和避免大量人員傷亡。但要做到這一點，需要確定最短撤離路徑和救援路徑。
本文重點研究了疏散及救援最短路徑的計算優(yōu)化算法，基于單源最短路徑的經(jīng)典算法—迪杰斯特拉(Dijkstra)算法，通過優(yōu)化算法節(jié)點，轉(zhuǎn)換道路節(jié)點圖層為帶權有向圖，運用Dijkstra優(yōu)化節(jié)點算法并提出了事故疏散救援時最佳路徑，同時將已確定的事故模型及最短路徑的算法與地理信息系統(tǒng)(GIS)相結合，形成可視化最短路徑結果圖示化展示。
2主要技術與方法概述
近年來，許多最短路徑算法研究已被用于解決實際問題，例如，聯(lián)合國救援組織在2010年的海地地震中，運用結合了最短路徑算法的地理信息系統(tǒng)制定應急救援路線計劃[1-9]。本文分析和優(yōu)化基于Dijkstra最短路徑的算法，提出了針對節(jié)點優(yōu)化的Dijkstra最短路徑算法的優(yōu)化方案，并通過地理信息系統(tǒng)實現(xiàn)了最短路徑優(yōu)化算法的可視化問題，討論了必要的證明和應用條件。該方案已在公路信息系統(tǒng)中應用，并取得了滿意的效果。
2.1節(jié)點定義
在實際運用中，首先需要根據(jù)現(xiàn)場道路情況，構建出道路的節(jié)點圖層和道路圖層。節(jié)點：道路的交叉點。節(jié)點圖層的數(shù)據(jù)庫格式為：節(jié)點ID，X，Y節(jié)點ID：表示節(jié)點本身。在數(shù)據(jù)庫中，一般只需要儲存節(jié)點ID和節(jié)點坐標(如果不儲存節(jié)點ID，GIS系統(tǒng)可以通過空間地理查詢功能來獲得)，儲存節(jié)點坐標可以在進行最短路徑計算和繪制路線時提高運算速度。在計算最短路徑的初始化階段，在儲存的道路圖層記錄基礎上，通過道路起點、終點、交叉點、道路長度和道路路況系數(shù)建立道路的鄰接矩陣，以便計算最短路徑。使用公式來取值：
2.2算法優(yōu)化
Dijkstra核心算法步驟中對最小權值路徑的計算需要確定節(jié)點，針對此步驟，對節(jié)點使用情況進行優(yōu)化，分為已標記節(jié)點、臨時標記節(jié)點和未標記節(jié)點，在計算過程中直接選擇未標記節(jié)點，可以節(jié)約大量計算時間，只需要運算一次就可以按照權值對相關臨時節(jié)點進行升序排列。
2.3算法圖解
如圖1，以一個帶權有向圖來說明Dijkstra優(yōu)化節(jié)點算法的計算過程。應急救援的最短路徑問題，一般是解決從應急救援隊出發(fā)地點到事故發(fā)生地點的最短路徑問題，因此，我們把其簡化為搜尋兩個節(jié)點之間的最短路徑問題。Dijkstra優(yōu)化節(jié)點算法，需要確定一個道路節(jié)點為起點，在事故應急救援中，一般設應急救援隊伍的出發(fā)點附近的道路節(jié)點為起點，設為s1;終點在事故應急救援中，一般為離事故發(fā)生地點最近的道路節(jié)點，設為s6。
初始狀態(tài)：S是已計算出最短路徑的頂點集合，U是未計算出最短路徑的頂點的集合。第1步：將源點s1放入S中。此時，S={s1(0)},U={s2(∞),s3(2),s4(0),s5(6),s6(20)}。注：s3(2)表示s3到起點s1的距離是2。第2步：將頂點s3加入到S中。上一步操作之后，U中頂點s3到起點s1的距離最短;因此，將s3加入到S中，同時更新U中頂點的距離。
以頂點s2為例，之前s3到s1的距離為∞;但是將s3加入到S之后，s2到s1的距離為3=(s2,s3)+(s3,s1)。此時，S={D(0)，s3(2)},U={s2(15),s4(12),s5(6),s6(20)}。重復以上步驟，并不斷修正U集合中的路徑值。最后得到：S={s1(0),s2(15),s3(2),s4(10),s5(6),s6(12)}。因此，從源點s1到終點s6的最短路徑為12，見下表。
3最短路徑展示技術
展示最短路徑需要結合運用測繪、遙感、計算機模擬仿真技術、地理信息系統(tǒng)(GIS)等多種技術，主要包括以下內(nèi)容：
3.1三維場景數(shù)據(jù)的制作
三維場景數(shù)據(jù)庫是最短路徑展示技術中的基礎和前提，而三維場景數(shù)據(jù)的制作是目前測繪行業(yè)先進技術的綜合體現(xiàn)。多種類型數(shù)據(jù)的疊加形成三維場景數(shù)據(jù)，它包括矢量數(shù)據(jù)、影像數(shù)據(jù)、模型數(shù)據(jù)、地形數(shù)據(jù)等。在本項目研究的實例中，采用的是數(shù)字高程模型(DigitalElevationModal，簡稱DEM)數(shù)據(jù)，其中遙感數(shù)據(jù)采用精確到1m的IKONOS衛(wèi)星遙感影像數(shù)據(jù)，通過將數(shù)字高程模型、衛(wèi)星影像數(shù)據(jù)、三維地形數(shù)據(jù)和三維模型數(shù)據(jù)疊加，最后生成三維場景數(shù)據(jù)從而實現(xiàn)對真實世界的虛擬實現(xiàn)。其中，三維地形數(shù)據(jù)的加工過程，如圖2。
除了三維地形數(shù)據(jù)外，還需要制作三維模型數(shù)據(jù)。為了清楚表現(xiàn)地表上的各種建筑設施，比如道路沿路的居民區(qū)、加油站等建筑設施，需要通過三維模型數(shù)據(jù)來建立。而融合了航空遙感、地形、三維地形、三維模型數(shù)據(jù)，并且需要使用先進的數(shù)據(jù)打包技術才能夠最終制作成三維場景數(shù)據(jù)。三維場景數(shù)據(jù)的制作過程，如圖3。
3.2三維系統(tǒng)功能集成
最短路徑展示技術發(fā)揮了GIS強大的空間處理能力，由傳統(tǒng)的二維空間擴展到三維空間，使用戶能夠更直觀的感受建筑、道路、山體等三維目標。并且實現(xiàn)了在三維空間中對目標物體的查詢和定位。依托GIS系統(tǒng)，在發(fā)生突發(fā)事故時，可以針對事故進行事故影響范圍模擬，計算生成三維空間地理模型，并對事故進行應急救援最短路徑方案設計。
例如，在某地發(fā)生泄漏事故后，可以對泄漏地點進行定位查詢、泄漏發(fā)生后影響范圍在三維場景中的展現(xiàn)、泄漏周邊應急救援物資及消防、醫(yī)療救援力量的查詢定位，綜合分析后自動展示出人員撤離的最短路徑以及救援人員的最短救援路徑。如圖4展示了醫(yī)療救援最短路徑(以白色線顯示)。
4結論
本文研究了基于Dijkstra算法的最短路徑節(jié)點優(yōu)化方案，提出了在危險化學品泄漏事故應急救援中應用最短路徑的技術手段，并將最短路徑的算法與地理信息系統(tǒng)相結合，通過圖示化展示出最短路徑。此技術手段可以有效迅速組織事故影響區(qū)域內(nèi)人員的疏散撤離，為減少和避免大量人員傷亡提供了技術支持。
參考文獻
[1]EWDijkstra.ANoteonTwoProblemsinConnexionwithGraphs[J].NumerischeMathematics,1959,1(1):269-271
[2]KMehlhorn,PSanders.AlgorithmsandDataStructures:TheBasicToolbox[J].Springer-Verlag,2008,45(2):245-258
[3]GGallo,SPallottino.ShortestPathAlgorithms[J].AnnalsofOperationsResearch,1988,13(1):1-79
[4]BVCherkassky,AVGoldberg,TRadzik.ShortestPathsAlgorithms:TheoryandExperimentalEvaluation[J].MathematicalProgramming,1996,73(2):129-174
[5]FBZhan.ThreeFastestShortestPathAlgorithmsonRealRoadNetworks:DataStructuresandProcedures[J].JournalofGeographicInformationandDecisionAnalysis,1997,1(1):69-82
[6]FBZhan,CENoon.ShortestPathAlgorithms:anEvaluationUsingRealRoadNetworks[J].TransportationScience,1998,32(1):65-73
[7]JLGalan-Garcia,GAguilera-Venegas,MAGalan-Garcia.ANewProbabilisticExtensionofDijkstra'sAlgorithmtoSimulateMoreRealisticTrafficFlowinaSmartCity[J].AppliedMathematics&Computation,2015,(267):780-789
[8]SXWang.TheImprovedDijkstra’sShortestPathAlgorithmandItsApplication[J].ProcediaEngineering,2012,(29):1186-1190
[9]SYang,CLi.AnEnhancedRoutingMethodwithDijkstraAlgorithmandAHPAnalysisinGIS-basedEmergencyPlan[J].InternationalConferenceonGeoinformatics,2010:1-6
交通方向期刊推薦：《人民公交》力爭動員社會各方力量共同參與建設，通過加大“公交優(yōu)先”的宣傳，形成良好的社會輿論氛圍，使之成為社會共識。讀者對象：政府相關部門、公交運營企業(yè)、公交配套產(chǎn)業(yè)、公交車輛及零部件生活企業(yè)、大專院校和科研院所等公交行業(yè)相關人員。
