基于元胞自动机和图论的博物馆紧急疏散路线规划

王洁琼

（山西农业大学软件学院 山西省晋中市 030801）

发生紧急情况时，为使在最短的时间内疏散最多的游客，需要以最合理的方式安排人员疏散。近年来，在行人流的仿真研究中，元胞自动机仿真技术已广泛应用于交叉路口的行人流，在行人流和疏散行人流的仿真研究中，其应用已较为成熟，岳昊等[1]基于元胞自动机仿真研究了行人疏散流中疏散人数、安全出口等因素对疏散时间的影响，元胞自动机模拟或定义系统中简单个体的微观行为特征，并在个体之间相互作用的条件下，实现系统整体宏观行为特征的模拟和研究。本文采用局部模拟的方法，估算出在疏散不同游客量时，不同通道类型（例如宽过道，窄过道和楼梯）所花费的时间，并且估计出场地内游客的整体疏散时间。

根据模拟的游客疏散结果生成紧急疏散计划。以游客的疏散时间分布和博物馆的疏散通道，展馆布局等数据为依据，建立图模型，估算每条路径的成本，以此规划游客的疏散路线。计算表明，明智地安排游客选择不同的路径比告诉他们每个人的最短路径更为重要，科学合理的规划逃生疏散路线为应对突发事件提供了必要的保障。

1 基于元胞自动机仿真模拟游客疏散情况

1.1 研究思路

为了获得最大的疏散人数，需要估计出每个疏散通道的疏散能力，并根据疏散能力的不同对游客进行疏散。本节首先使用元胞自动机模拟展厅中一定数量不同年龄比例的游客的疏散情况，获取相关数据。由于不同疏散通道的参数不同，因此修改元胞自动机模拟的疏散通道的参数，能够得到各种疏散通道的疏散情况的参数。根据元胞自动机多次模拟获得的数据对游客进行有效疏散。

1.2 研究方法

在X×Y 的二维离散网格系统中建立游客疏散的仿真模型。将移动区域划分为N 个相等的离散元胞空间。障碍物占据系统边界的元胞以形成房间的墙壁，而在墙上留下元胞空间作为房间的安全出口。在该系统中，每个空间位置只能容纳一位游客。游客疏散的模拟过程也被离散为多个相等时间步长。在一个时间步长中，游客只能移动一个或多个元胞，在本节仿真过程中，将残疾人，孕妇和老年游客的疏散速度定为1 格/秒，女性/中年游客的疏散速度定为2 格/秒，成人游客的疏散速度定为3 格/秒。游客不能穿过墙壁，只能从房间出口离开系统，仿真模型如图1所示。

模型在每个时间步长上的演化，游客可以等待或向八个方向移动如图2。当选择下一个移动位置时，游客将对可选位置做出预期得分（如公式1），选择最大预期得分的位置作为目标位置。

预期得分描述了下一个可选位置与游客目标位置的接近程度。通过游客间的排斥力和该位置对游客逃生的吸引力这两个参数相加得出。

图1：游客疏散仿真模型图

图2：8 个可移动的方向

游客疏散的目的地是安全出口。在游客疏散过程中，尽可能多的选择出口附近的位置作为其下一个时间步长的目标位置。对于展厅内的游客，距离安全出口越近的位置对其吸引力就越大。在计算预期得分时，首先要计算游客当前位置与安全出口之间的欧氏距离（如公式2）。当游客在一个有多个安全出口的展厅内疏散时，将距离安全出口的最近的距离值作为当前位置与安全出口之间的最短距离。

由此得出结论，时间成本与人数成线性增长如图3所示。

2 基于图论安排紧急疏散计划

2.1 研究思路

基于图论建立卢浮宫的图模型。具体是将房间设置为节点，将通道设置为图中的边，并将各个通道的最大疏散人口设置为该边的属性。然后，根据概率论估算每个房间的初始游客数。再将紧急疏散问题转化为控制房间人数的线性规划问题，解决该问题以获得最佳的紧急疏散计划。

2.2 研究方法

本节将卢浮宫的引导图转换成图模型。将每个房间都设置为该图中的一个节点，当有如图4所示的连接房间时，本节会将它们视为同一节点。

根据通过元胞自动机建立的模型估算出不同过道或楼梯的时间成本。具体来说，需要分别多次模拟宽过道，窄过道和楼梯的时间成本，再取其平均值。将这些平均值用于计算每个过道和楼梯的最大容量，最大容量则是该图模型上边的属性。

建立该图的邻接矩阵如表1所示。

在紧急情况下几乎不可能要求每个人都认真耐心地听从撤离安排，为了疏散全部人口，直接告诉游客走哪条路是更加高效的，这意味着控制离开和进入房间的人数更为重要。

具体来说，假设该图中有N 个节点，并且用x_i^t 表示在时间t 时第i 个房间的人数，并估计x_i^0 的初始值。游客可以通过连接房间的任何通道离开或进入该房间。因此，如果用Δx_ij^t 表示由于游客在第i 个房间和第j 个房间相连的通道中移动而引起的人数差异，则：

上式表示从第i 个房间离开到第j 个房间的人数等于从第j 个房间离开到第i 个房间的人数。对于当前时刻，该房间中的总人数由以下公式确定：

同时，为了疏散所有人，还需要计算在时刻t 分布在所有房间中的所有人的总和，即

为避免发生只疏散了靠近出口节点人员的情况，不能直接将上述计算出的总数最小化，而是为了鼓励远处展厅中的人移动到最终的出口节点，反复最小化以下总和来控制房间人口数量，以此达到疏散游客的目的，规划出博物馆游客的紧急疏散路线。

步骤2：查找除存储在出口节点列表外的其余节点，并将它们存储在另一个列表Nk中。

步骤3：对于出口节点列表中的所有节点，找到直接连接的节点并将其存储在出口节点列表中。

步骤4：返回步骤1，在步骤3 中生成出口节点列表，直到出口节点列表包括所有节点时停止递归。

3 结束语

本文采用元胞自动机模型对游客疏散进行大规模仿真，估算出各个通道时间成本。又通过图论建立游客疏散的图模型，最后通过目标函数优化为游客提供紧急疏散规划。此疏散路线规划模型可推广到其他大型人流密集场所，只需要根据该场所的具体信息，改变节点，边及其权值等具体数据，重新模拟运算，便可得到最佳的紧急疏散路线规划方案。

表1：此图的邻接矩阵的一部分

图3：时间成本与人数的关系

图4：卢浮宫局部导览图及对应图模型