發布時間：所屬分類：科技論文瀏覽：1次
摘 要： 【摘要】本文主要研究了單源最短路徑優化節點的技術和方法，并將其運用于事故的應急救援中，同時提出了技術支持系統中最短路徑可視化的優化結構框架。結合單源最短路徑算法，在地理信息系統中以數字高程模型和衛星影像數據為基礎，針對事故危險區域開發出人
【摘要】本文主要研究了單源最短路徑優化節點的技術和方法，并將其運用于事故的應急救援中，同時提出了技術支持系統中最短路徑可視化的優化結構框架。結合單源最短路徑算法，在地理信息系統中以數字高程模型和衛星影像數據為基礎，針對事故危險區域開發出人員疏散和救援的最短路徑可視化算法。此項技術完善了應急救援路徑自動化選擇模式，為事故中迅速展開人員疏散和組織有效的應急救援工作提供強有力的技術支持。
【關鍵詞】事故,應急救援,最短路徑,可視化
1研究的背景與意義
在生產經營活動中，無論是在生產、運輸過程中還是在儲存、經營、使用環節，都可能發生重大安全生產事故，造成重大人員傷亡和財產損失。如2005年3月29日晚，在淮安境內高速公路，因交通事故誘發液氯泄漏，造成29人死亡，疏散群眾1萬多人。2010年7月，南京市地下丙烯管道泄漏爆燃，造成22人死亡，120多人受傷住院。當發生重大事故時，如果能及時快速組織人員疏散撤離，將會減少和避免大量人員傷亡。但要做到這一點，需要確定最短撤離路徑和救援路徑。
本文重點研究了疏散及救援最短路徑的計算優化算法，基于單源最短路徑的經典算法—迪杰斯特拉(Dijkstra)算法，通過優化算法節點，轉換道路節點圖層為帶權有向圖，運用Dijkstra優化節點算法并提出了事故疏散救援時最佳路徑，同時將已確定的事故模型及最短路徑的算法與地理信息系統(GIS)相結合，形成可視化最短路徑結果圖示化展示。
2主要技術與方法概述
近年來，許多最短路徑算法研究已被用于解決實際問題，例如，聯合國救援組織在2010年的海地地震中，運用結合了最短路徑算法的地理信息系統制定應急救援路線計劃[1-9]。本文分析和優化基于Dijkstra最短路徑的算法，提出了針對節點優化的Dijkstra最短路徑算法的優化方案，并通過地理信息系統實現了最短路徑優化算法的可視化問題，討論了必要的證明和應用條件。該方案已在公路信息系統中應用，并取得了滿意的效果。
2.1節點定義
在實際運用中，首先需要根據現場道路情況，構建出道路的節點圖層和道路圖層。節點：道路的交叉點。節點圖層的數據庫格式為：節點ID，X，Y節點ID：表示節點本身。在數據庫中，一般只需要儲存節點ID和節點坐標(如果不儲存節點ID，GIS系統可以通過空間地理查詢功能來獲得)，儲存節點坐標可以在進行最短路徑計算和繪制路線時提高運算速度。在計算最短路徑的初始化階段，在儲存的道路圖層記錄基礎上，通過道路起點、終點、交叉點、道路長度和道路路況系數建立道路的鄰接矩陣，以便計算最短路徑。使用公式來取值：
2.2算法優化
Dijkstra核心算法步驟中對最小權值路徑的計算需要確定節點，針對此步驟，對節點使用情況進行優化，分為已標記節點、臨時標記節點和未標記節點，在計算過程中直接選擇未標記節點，可以節約大量計算時間，只需要運算一次就可以按照權值對相關臨時節點進行升序排列。
2.3算法圖解
如圖1，以一個帶權有向圖來說明Dijkstra優化節點算法的計算過程。應急救援的最短路徑問題，一般是解決從應急救援隊出發地點到事故發生地點的最短路徑問題，因此，我們把其簡化為搜尋兩個節點之間的最短路徑問題。Dijkstra優化節點算法，需要確定一個道路節點為起點，在事故應急救援中，一般設應急救援隊伍的出發點附近的道路節點為起點，設為s1;終點在事故應急救援中，一般為離事故發生地點最近的道路節點，設為s6。
初始狀態：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最短路徑展示技術
展示最短路徑需要結合運用測繪、遙感、計算機模擬仿真技術、地理信息系統(GIS)等多種技術，主要包括以下內容：
3.1三維場景數據的制作
三維場景數據庫是最短路徑展示技術中的基礎和前提，而三維場景數據的制作是目前測繪行業先進技術的綜合體現。多種類型數據的疊加形成三維場景數據，它包括矢量數據、影像數據、模型數據、地形數據等。在本項目研究的實例中，采用的是數字高程模型(DigitalElevationModal，簡稱DEM)數據，其中遙感數據采用精確到1m的IKONOS衛星遙感影像數據，通過將數字高程模型、衛星影像數據、三維地形數據和三維模型數據疊加，最后生成三維場景數據從而實現對真實世界的虛擬實現。其中，三維地形數據的加工過程，如圖2。
除了三維地形數據外，還需要制作三維模型數據。為了清楚表現地表上的各種建筑設施，比如道路沿路的居民區、加油站等建筑設施，需要通過三維模型數據來建立。而融合了航空遙感、地形、三維地形、三維模型數據，并且需要使用先進的數據打包技術才能夠最終制作成三維場景數據。三維場景數據的制作過程，如圖3。
3.2三維系統功能集成
最短路徑展示技術發揮了GIS強大的空間處理能力，由傳統的二維空間擴展到三維空間，使用戶能夠更直觀的感受建筑、道路、山體等三維目標。并且實現了在三維空間中對目標物體的查詢和定位。依托GIS系統，在發生突發事故時，可以針對事故進行事故影響范圍模擬，計算生成三維空間地理模型，并對事故進行應急救援最短路徑方案設計。
例如，在某地發生泄漏事故后，可以對泄漏地點進行定位查詢、泄漏發生后影響范圍在三維場景中的展現、泄漏周邊應急救援物資及消防、醫療救援力量的查詢定位，綜合分析后自動展示出人員撤離的最短路徑以及救援人員的最短救援路徑。如圖4展示了醫療救援最短路徑(以白色線顯示)。
4結論
本文研究了基于Dijkstra算法的最短路徑節點優化方案，提出了在危險化學品泄漏事故應急救援中應用最短路徑的技術手段，并將最短路徑的算法與地理信息系統相結合，通過圖示化展示出最短路徑。此技術手段可以有效迅速組織事故影響區域內人員的疏散撤離，為減少和避免大量人員傷亡提供了技術支持。
參考文獻
[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
交通方向期刊推薦：《人民公交》力爭動員社會各方力量共同參與建設，通過加大“公交優先”的宣傳，形成良好的社會輿論氛圍，使之成為社會共識。讀者對象：政府相關部門、公交運營企業、公交配套產業、公交車輛及零部件生活企業、大專院校和科研院所等公交行業相關人員。
