基于Dijkstra算法的人員疏散模型

馬磊 李欣 陳滿

摘要：本文設計了一個緊急疏散計劃，首先，將盧浮宮的圖形設計地圖進行三維建模，得到7盧浮宮的空間實體坐標圖。然后利用圖論理論建立最短路徑模型，并利用Dijkstra算法分別計算從四個區域到四個出口的最短距離。四個最短距離中最長的一個所花費的時間是所有人被疏散到安全區域的時間，得出每個區域的入口和出口之間的最短距離，確保工作人員可以盡快到達每個入口和出口以幫助訪客撤離。

關鍵詞：三維建模 最短路徑 人員疏散逃逸 Dijkstra算法

一、問題重述

為了在緊急情況下快速找到逃生的最佳途徑，建立了一個模型：

（l）使用rnatlab提取建立了每個區域的Dijkstra算法，并將通過3D建模獲得的每個區域的階梯節點帶入Matlab軟件中，以獲得這三個區域中每個區域的最短路徑。

（2）當僅使用四個主要入口和出口時，需要解決人群安全逃離盧浮宮的最佳路線問題，并建立模型以找到離開博物館的最佳路線。

（3）分析了該模型的優缺點，以及未來的工作。

二、問題分析

1.將盧浮宮的圖片導入3D軟件進行3D建模，我們得到了一個虛構的3D模型。由于通過使用每個平面圖生成三維模型，因此可以在模型中反映盧浮宮中的每個階梯節點的位置通過軟件的智能生成，可以獲得每個樓梯的三維坐標點。

2.將整個盧浮官展廳分為人口和出口，并且從出口的距離將這些部分分成四個三維部分每個部分有五層，找到每個區域中的最短路徑。構建Dijkstra算法。最短路徑問題可以直接應用于解決生產中的許多問題，例如管道鋪設過程中的線路選擇。設備更新，線路布置，工廠布局，甚至一些整數和動態編程問題也可歸因于最短路徑問題。

三、模型建立與求解

1.最短路徑

要找到最短路徑，首先我們需要找到每個節點之間的距離。這里我們使用歐氏距離來求解兩個節點之間的距離。

我們為每個地區尋找的最短路徑是離開盧浮宮的最快時間。假設盧浮宮同時收到緊急疏散通知時通知后，人員在盧浮宮內均勻分布。當人們同時開始離開時，最短的疏散路徑可以反映離開盧浮宮的最快時間。在所有四個區域完成疏散動作后選擇每個區域中的最短路徑。選擇基于這四條路徑的最長路徑，這反映了離開盧浮宮的時間，這四條路徑是最佳路線。

在分區的基礎上，我們建立了每個區域的Dijkstra算法，并將通過3D建模獲得的每個區域的階梯節點帶入Matlab軟件中，以獲得這三個區域中每個區域的最短路徑。比較三條路徑，最長的路徑代表所有盧浮宮人員撤離所需的最短時間。matlab軟件生成的每個區域的路由和長度如下：

其他區域的最短線與此區域相同。由于C區域有兩個出口，因此在軟件生成過程中形成兩條最短路徑，這兩條路徑是不同出口的最短路徑。A區C區三個區域B區的路徑為341.8。最長的路徑是B，長度是345.8。當速度恒定時，長度可以代表時間（上述模型只能在人口分布均勻的情況下考慮）。

四、模型優缺點

優點：

1.我們將盧浮宮博物館分為四個區域，并設計了四個區域的疏散方案，與整體設計疏散方案相比，計算量減少了一半。

2.當我們構建模型時，考慮最簡單到最復雜，首先建立最簡單的最短路徑模型，然后逐步優化模型，利于思想的擴展。

缺點：

1.使用歐幾里德距離來計算兩個相鄰入口和出口之間的距離，忽略相鄰樓梯之間可能的拐點，導致錯誤。

2.當我們計算最短路徑時，忽略了從訪客到相鄰人口和出口的距離，對結果有影響。

我們建立的模型易于理解，可根據需要自由重組和規劃。首先，認為可用于交通網絡的路徑優化問題。在模型中，可以考慮幾個人的流密度因子，分別代表了前后擁擠逃逸速度影響的權重，以及左右人員擁擠逃逸速度的影響。通過調節這兩個因素.權重可用于疏散交通。最短路徑模型可用于廣泛的應用，例如施工的管道施工，行車路線的GPS導航規劃等。

參考文獻

[1] Jin Zeren. Yan Xin， Li Yue.Study on pedestrian flowevacuation simulation based on cellular automata[J].Journal ofTongji University（Natural Science）.2018 ，46（08）： 1026-1034.

[2]Wu You. Anahrsis of the architecture and urban renewal ofthe Lens branch of the Louvre Museum in France [J]. ChineseMuseum，2017 （01）： 114-118.

[3]YANG Jianfang， GAO Yan. WANG Hongjie.Enlergency evacuationmodel and algorithm for multistory buildingsLJ].Journal of SysteInSimulation.2014， 26（02）： 267-273.

[4]LIU Wei， XING Zhixiang， CHANG Jianguo.Safe evacuationsilnulation for different personnel characteristics[J].Fire Science andTechnology， 2010， 29（04）： 297-300.