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

馬磊 李欣 陳滿

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

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

一、問題重述

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

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

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

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

二、問題分析

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

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

三、模型建立與求解

1.最短路徑

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

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

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

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

四、模型優(yōu)缺點

優(yōu)點：

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

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

缺點：

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

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

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

參考文獻

[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.