基于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.