ABSTRACT

In order to study the organization and visualization of indoor network models for emergency evacuation scenarios, this paper introduces hypergraph theory on the basis of graph theory, and designs the data organization method of Hypergraph Network Model, and describes semantic information of the path complexity, path congestion degree, and emergency events involved in emergency evacuation scenarios. Indoor Hypergraph Network Model is constructed and applied to indoor emergency path planning research. The feasibility of the Indoor Hypergraph Network Model was verified through experiments, and based on this model, the indoor emergency evacuation path planning algorithm group experiment was carried out. Experimental results show that the indoor emergency evacuation path planning algorithm in this paper can effectively synthesize the effects of path complexity, path congestion degree, and emergencies, and obtain comprehensive and reasonable path planning results.

Keywords:GIS, Indoor Path Planning, Hypergraph, Indoor Network Model, Emergency Evacuation

基于室内超网络模型的疏散路径 规划研究

薛磊，王行风

中国矿业大学，江苏 徐州

收稿日期：2020年7月8日；录用日期：2020年7月21日；发布日期：2020年7月28日

摘 要

为了研究面向应急疏散场景的室内网络模型组织与可视化方式，本文在图论的基础上引入超图理论，设计了超网络模型的数据组织方式，并对应急疏散场景中涉及的路径复杂度、路径拥挤程度、突发事件进行了语义信息描述，构建了室内超网络模型并将其应用于室内应急路径规划研究。通过实验验证了室内超网络模型的可行性，并基于此模型进行了室内应急疏散路径规划算法分组实验，实验结果表明，本文的室内应急疏散路径规划算法能有效综合路径复杂度、路径拥挤程度、突发事件的影响，得到较为合理的路径规划结果。

关键词 :GIS，室内路径规划，超图，室内网络模型，应急疏散

Copyright © 2020 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

近年来，我国城市化快速发展的步伐导致大型公共建筑的数量和规模与日俱增，一旦发生突发事故，由于室内信息不明确，环境不熟悉以及群众恐慌心理等，很可能造成人员和财产的严重损害。因此众多学者对室内网络模型的构建及应急疏散应用等领域进行了深入的研究 [1] [2]。基于图论的室内网络模型研究最为广泛。Kwan等采用最短路径算法，为在建筑物内由于突发事件被困的人提供最佳疏散路径 [3]；Lee在考虑室内单元间的逻辑关系的基础上，提出了结点—关系结构模型 [4]，并将其用于最短路径分析中；Mandloi和Thill提出了一种综合了室内环境及室外交通网络，可用于路径导航的三维空间模型 [5]；Zhou等人通过整合室内空间实体的几何、拓扑和语义特征，提出了一种符合人类认知的室内空间位置模型 [6]。这些模型虽然能够描述室内空间结构以及单元之间的拓扑关系，但是当面向复杂网络时，却存在空间结构被切割、模型语义信息不完整的问题。因此，构建更详细更多维的室内空间模型，以及面向应急疏散场景的科学合理的室内路径规划研究就显得尤为重要。

2. 室内超网络模型

2.1. 超图理论

超图 [7] [8] $H=\left(V,E\right)$ 是一个二元关系对，设 $V=\left\{v_1,v_2,v_3,\cdots ,v_n\right\}$ 是一个有限集，V的元素 $v_1,v_2,v_3,\cdots ,v_n$ 称为超图的节点；设 $E=\left\{e_1,e_2,e_3,\cdots ,e_m\right\}$ 是超图的超边集合，元素 $e_i=\left\{v_{i_1},v_{i_2},\cdots ,v_{i_j}\right\}\left(i=1,2,\cdots ,m\right)$ 称为超图的边，且节点和超边之间满足下列关系：

① $e_i\ne \varphi \left(i=1,2,3,\cdots ,m\right)$ ② ${\displaystyle {\cup }_{i=1}^m{e}_i}=V$

图1所示是一个无向超图示例，其中节点集 $V=\left\{v_1,v_2,v_3,v_4,v_5,v_6,v_7,v_8\right\}$，超边集 $E=\left\{e_1,e_2,e_3,e_4,e_5\right\}$，$e_1=\left\{v_3,v_4,v_5\right\}$，$e_2=\left\{v_5,v_8\right\}$，$e_3=\left\{v_6,v_7,v_8\right\}$，$e_4=\left\{v_2,v_3,v_7\right\}$，$e_5=\left\{v_1,v_2\right\}$。可以看出，超图中的超边不限制所含节点个数，在保证网络结构完整的同时对边进行整合提高了模型的整体性。

图1. 无向超图示例

2.2. 室内超网络结构

基于超网络理论，本文将室内空间划分为由节点集合和超边集合组成的室内超网络模型 $G=\left(V,E\right)$，其中V表示节点集合，包括室内空间中抽象成点元素的各种对象，如房间节点、门节点、通道交点等；E表示超边集合，即联系室内空间对象之间的弧段集合。室内空间可以划分为以下结构(如图2)：

1) 超网络层(Hyper-floor)：即各楼层，将整个建筑物划分为不同的楼层结构，由水平结构和垂直结构组成。

2) 区块网络层(Hyper-block)：即楼层中的区块域，是对同一楼层中的区域划分，划分依据一般是区域功能或者位置排列特点。

3) 空间对象(Objects)，具体包括：

① 封闭空间(Room)：由墙体、门窗、天花板、地面等组成的封闭或半封闭空间。

② 通道(Corridor)：具有连通其他室内独立空间对象的功能。

③ 门(Door)：控制封闭空间和通道之间的连通性。

④ 楼层通道(F-connection)：连通不同楼层的室内结构，如电梯、楼梯、扶梯等。

图2. 室内超网络结构划分示意图

2.3. 室内语义表达

为了丰富室内超网络模型的语义信息，使其更加贴合实际，本文引入了路径复杂度、路径拥挤度和突发事件三方面信息 [9]。并采用数据库关系表来存储和表达室内空间结构和室内对象的空间关系 [10]。

1) 路径复杂度

路径复杂度主要通过节点度来体现的，其语义表达为：

$\text{Rout\_complexity}=\left\{\text{HyperEdge\_degrees}\left(\text{Node\_degree}\right)\right\}$ (1)

其中，HyperEdge_degrees表示网络中超边的度，Node_degree表示网络中节点的度。

2) 路径拥挤度

突发事件发生时，关键路径上的拥挤程度将成为影响人员路径选择的重要决策因素之一。室内导航环境拥挤程度的语义描述为：

$\text{Rout\_crowd}=\left\{\text{cr\_type},\text{cr\_range}\right\}$ (2)

其中，cr_type表示室内网络的拥挤程度，可通过疏散仿真模拟得到；cr_range表示发生拥堵情况的区域。

3) 突发情况

网络模型中的突发事件语义表达为：

$\text{Rout\_accident}=\left\{\text{ac\_range}\right\}$ (3)

其中，ac_range为突发事件的影响区域，即网络模型中受突发事件影响的节点集合， $\text{ac\_range}=\left\{v_1,v_2,\cdots ,v_n\right\}$。

4) 路径复杂程度函数

根据室内网络语义信息描述，将路径复杂度、路径拥挤度、突发事件函数以及超边权值定义如下：

a) 路径复杂度函数

$F_{cm}\left(V_m\right)=\text{Hyper\_degrees}\left(\text{Node\_degree}\right)$ (4)

其中， $F_{cm}\left(V_m\right)$ 表示路径复杂度函数，V_m代表路径中涉及的节点集合，Hyper_degrees代表超边的度；Node_degrees代表节点的度。

b) 路径拥挤度函数

$F_{cw}\left(v_i,v_j\right)=\beta D\left(v_i,v_j\right)$ (5)

其中， $F_{cw}\left(v_i,v_j\right)$ 表示路径拥挤度函数； $D\left(v_i,v_j\right)$ 是路径的距离权值； $\beta$ 是拥挤系数，通过疏散仿真模拟获得。

c) 突发事件函数

$F_{ac}\left(V_n\right)=\{\begin{array}{l}1,V_n中节点可通行\\ \to 0,V_n中节点不可通行\end{array}$ (6)

其中， $F_{ac}\left(V_n\right)$ 为突发事件影响的成本函数， $V_n$ 为受突发事件影响的节点集合， $F_{ac}\left(V_n\right)=1$ 节点可通行， $F_{ac}\left(V_n\right)\to 0$ 节点不可通行。

d) 超边权值函数

超边权值 $D^{\prime }$ 的基本计算公式为：

$D^{\prime }=\frac{{\alpha }_{cm}{F}_{cm}\left(v_i,v_j\right)+{\alpha }_{cw}{F}_{cw}\left(V_m\right)}{{\alpha }_{ac}{F}_{ac}\left(V_n\right)},{\displaystyle \sum {\alpha }_k}=1,{\alpha }_k\in \left(0,1\right),k\in \left\{\text{CM},\text{CW},\text{AC}\right\}$ (7)

其中， ${\alpha }_{cm}$ 为路径复杂度(cm)的权重系数， ${\alpha }_{cw}$ 为拥挤度(cw)的权重系数， ${\alpha }_{ac}$ 为突发事件(ac)的权重系数。通过归一化处理后得到改进的超边权值 $D^{*}$ ：

$D^{*}=\frac{{\alpha }_{cm}{F}_{cm}^{\ast }\left(v_i,v_j\right)+{\alpha }_{cw}{F}_{cw}^{\ast }\left(V_m\right)}{{\alpha }_{ac}{F}_{ac}^{\ast }\left(V_n\right)}$ (8)

3. 应急疏散路径规划方法

在应急疏散寻径计算与优化领域，应用较为广泛的算法包括Dijkstra算法 [11] [12]、蚁群算法 [13]、粒子群算法 [14] 等。其中，Dijkstra算法是一种单源最短路径算法，是解决图论中最短路径问题的经典应用，因此本文选择对Dijkstra算法进行改进，并在路径规划时兼顾距离、路径复杂度、拥挤度和突发事件四个因素。算法流程如图3。

1) 在室内超网络模型的基础上，构建完整的室内网络数据。

2) 确定起始点S和目标点E，定义一个集合(CloseList)用于存放已遍历点；再定义一个集合(RoutList)用于存放最优路径，并初始化集合。

3) 根据超网络模型中节点和超边的集合和属性信息，计算改进的超边权值D^*。

4) 判断S和E是否同层，若是则采用同层算法；反之则采用分层算法。

5) 将计算得到的RoutList集合结果输出并可视化显示。至此，算法结束。

图3. 改进的Dijkstra算法流程图

4. 室内超网络模型验证及分析

4.1. 实验区域

本文选择某单位的学院行政楼作为研究区域，其整体外观如图4所示，该建筑地上共有5层，其中第一层的结构与其他楼层具有一定的差别，第二层到顶层的结构大致相同。根据超网络结构划分依据和超网络模型构建原理，对实验区域进行结构提取，构建相应的三维网络通道模型，如图5。为进行对比，本文也将点―弧段模型引入室内空间。室内超网络模型与点―弧段模型相比，节点数保持不变，新增了超边概念，超边的数量较少，但是超边中节点之间的连接关系没有发生改变或删减，在保证拓扑关系不变的情况下，整合了室内网络的语义信息一定程度上保证了室内空间结构的完整性。如表1。

图4. 实验区域

图5. 超网络模型

表1. 超网络模型与经典节点弧段模型比较

4.2. 疏散模拟

为了获得路径拥挤程度函数的参数 值，本文利用Pathfinder软件进行模拟，根据《建筑设计防火规范》GB 50016-2014，行政楼属于办公建筑，因此疏散人员密度设为5 m²/人。研究区域内大多数是身体康健的成年人，在模拟中只考虑中青年人群，速度区间为1.1~1.3 m/s。根据模拟得到的人员密度和人员速度变化数据(如表2所示)，将路径拥挤程度划分为四个层次：流畅、微堵、拥堵、瘫痪，则路径拥挤程度的成本函数 $F_{cr}\left(v_i,v_j\right)$ 的系数 $\beta$ 分别取值为1、2、4、8。

表2. 路径拥挤层次划分及系数取值

4.3. 面向应急疏散的路径规划

为验证本文所提的室内应急疏散路径规划算法的有效性，按照表3中的条件设置了五组实验。在仅考虑单一因素的影响时，通过设置不同的权重系数控制变量。

表3. 应急疏散规划实验

1) 实验一

本实验不考虑路径复杂度、路径拥挤度以及突发事件因素，路径规划结果如图6(a)所示，路径为：e33{255, 235, 249, 248, 245, 244, 238, 242}→e1{231, 117, 72}→e121{72, 71, 68, 73}→e11{73, 74, 77}→e12{73, 86}，此时最优路径为距离总和最小的路径。

2) 实验二

本实验不考虑路径拥挤程度和突发事件影响，此时的路径规划结果主要受距离权值和路径复杂度影响。路径规划结果(图6(b))与实验一相同，此路径的复杂度为48。可以看出在考虑路径复杂度的情况下，经过楼梯(e1)的路线仍是最简单且距离短的路线。

3) 实验三

本实验不考虑路径复杂度和拥挤度，此时路径规划结果由距离权值和突发事件决定。路径规划结果如图7所示，路径为：e35{255, 315, 314}→e31{314, 318, 321, 341, 327, 330, 332, 333}→e3{334, 212, 85}→e131{85, 86}。可以看出，由于突发事件造成点236和点242不可通过，因此在路径搜索时绕开了经过点236和点242的路径，这表明本文的路径规划算法在突发事件发生时可以成功选择合理路径。

图6. 实验一(a)与实验二(b)结果

4) 实验四

本实验仅考虑路径拥挤程度对路径规划结果的影响，根据表2将路段e32、e30、e325分别设置为微堵、瘫痪、拥堵。路径规划结果如图8(a)所示，路径为：e33{255, 235, 249, 248, 245, 244, 238, 242}→e32{242, 236}→e322{236, 232}→e2{232, 116, 75}→e122{75, 74}→e11{74, 77}→e12{77, 86}。可以看出，虽然路径e32微堵，但是在路径e30瘫痪和路径e325拥堵的情况下，经过e32的路径仍然是综合耗费代价最少的路径。由此可见，本文在室内发生路径拥挤情况时，仍能计算得出合理有效的路径结果。

图7. 实验三结果

图8. 实验四(a)和实验五(b)结果

5) 实验五

本实验综合考虑距离大小，路径拥挤程度，路径复杂程度，和突发情况这些因素。路径规划结果如图8(b)所示，路径为：e35{255, 315, 314}→e31{314, 323, 311}→e4{311, 194, 110}→e12{110, 108, 105, 102, 99, 96, 93, 90, 87}。可以看出，多因素影响下，本文的室内应急路径规划算法能选择一条距离较短、路径拥挤度低、突发事件影响小、路径复杂度小的路线，得出更全面更合理的路径规划结果。

5. 结语

为解决传统的室内网络模型难以有效描述复杂网络结构的问题，本文引入了超网络理论，构建了室内超网络模型，并面向应急疏散场景进行了疏散路径规划研究，结果表明：室内超网络模型能表达复杂网络结构，提高了模型完整性，室内路径规划算法能有效考虑路径复杂程度、路径拥挤程度、突发事件的影响，得出更合理的路径规划结果。

室内网络模型研究领域还有很多问题值得深入研究，本文所构建室内超网络模型时采用的是手工方式，构建过程繁琐易出错，如何自动有效构建网络模型是下一步工作需要考虑的重点问题。

基金项目

“十三五”国家重点研发计划(室内混合智能定位与室内GIS技术) (2016YFB0502102)。

文章引用

薛 磊,王行风. 基于室内超网络模型的疏散路径规划研究
Research on Evacuation Path Planning Based on Indoor Hypergraph Network Model[J]. 测绘科学技术, 2020, 08(03): 123-131. https://doi.org/10.12677/GST.2020.83015

参考文献