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

Geomatics Science and Technology 测绘科学技术, 2020, 8(3), 123-131 Published Online July 2020 in Hans. http://www.hanspub.org/journal/gst https://doi.org/10.12677/gst.2020.83015

Research on Evacuation Path Planning Based on Indoor Hypergraph Network Model

Lei Xue, Xingfing Wang

China University of Mining and Technology, Xuzhou Jiangsu

thstth

Received: Jul. 8, 2020; accepted: Jul. 21, 2020; published: Jul. 28, 2020

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 in-formation 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 evacua-tion 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 comprehen-sive 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日

文章引用: 薛磊, 王行风. 基于室内超网络模型的疏散路径规划研究[J]. 测绘科学技术, 2020, 8(3): 123-131. DOI: 10.12677/gst.2020.83015

薛磊，王行风

摘 要

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

关键词

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/

Open Access 1. 引言

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

2. 室内超网络模型

2.1. 超图理论

超图[7] [8] H=(V,E)是一个二元关系对，设V={v1,v2,v3,?,vn}是一个有限集，V的元素

v1,v2,v3,?,vn称为超图的节点；设E={e1,e2,e3,?,em}是超图的超边集合，元素

=eiv,v,?,v}(i{=i1i2ij1,2,?,m)称为超图的边，且节点和超边之间满足下列关系：

① ei≠φ(i=1,2,3,?,m) ②

?i=1ei=V

m图1所示是一个无向超图示例，其中节点集V={v1,v2,v3,v4,v5,v6,v7,v8}，超边集E={e1,e2,e3,e4,e5}，

e1={v3,v4,v5}，e2={v5,v8}，e3={v6,v7,v8}，e4={v2,v3,v7}，e5={v1,v2}。可以看出，超图中的超边不

限制所含节点个数，在保证网络结构完整的同时对边进行整合提高了模型的整体性。

DOI: 10.12677/gst.2020.83015

124

测绘科学技术

薛磊，王行风

Figure 1. Example of undirected hypergraph 图1. 无向超图示例

2.2. 室内超网络结构

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

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

2) 区块网络层(Hyper-block)：即楼层中的区块域，是对同一楼层中的区域划分，划分依据一般是区域功能或者位置排列特点。 3) 空间对象(Objects)，具体包括： ① 封闭空间(Room)：由墙体、门窗、天花板、地面等组成的封闭或半封闭空间。 ② 通道(Corridor)：具有连通其他室内独立空间对象的功能。 ③ 门(Door)：控制封闭空间和通道之间的连通性。 ④ 楼层通道(F-connection)：连通不同楼层的室内结构，如电梯、楼梯、扶梯等。 ModelFloorF-connectionStairsElevators……Block-connectionCorridor 1Corridor 2……DoorDoor 1Door 1……CorridorCorridor 1Corridor 2……Hyper-FloorFloor1Floor2……BlockHyper-BlockBlock ABlock B……RoomObjectsRoom 1Room 2…… Figure 2. Schematic diagram of indoor super network struc-ture division 图2. 室内超网络结构划分示意图 DOI: 10.12677/gst.2020.83015 125 测绘科学技术 薛磊，王行风

2.3. 室内语义表达

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

1) 路径复杂度

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

Rout_complexity={HyperEdge_degrees(Node_degree)} (1)

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

2) 路径拥挤度

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

Rout_crowd={cr_type,cr_range} (2)

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

3) 突发情况

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

Rout_accident={ac_range} (3)

其中，ac_range为突发事件的影响区域，即网络模型中受突发事件影响的节点集合，

ac_range={v1,v2,?,vn}。

4) 路径复杂程度函数

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

Fcm(Vm)= Hyper_degrees(Node_degree) (4)

其中，Fcm(Vm)表示路径复杂度函数，Vm代表路径中涉及的节点集合，Hyper_degrees代表超边的度；Node_degrees代表节点的度。

b) 路径拥挤度函数

Fcw(vi,vj)=βD(vi,vj) (5)

其中，Fcw(vi,vj)表示路径拥挤度函数；D(vi,vj)是路径的距离权值；β是拥挤系数，通过疏散仿真模拟获得。

c) 突发事件函数

Vn中节点可通行??1, (6) Fac(Vn)=?→0,V中节点不可通行?n?其中，Fac(Vn)为突发事件影响的成本函数，Vn为受突发事件影响的节点集合，Fac(Vn)=1节点可通行，

Fac(Vn)→0节点不可通行。

d) 超边权值函数

超边权值D′的基本计算公式为：

D′=

DOI: 10.12677/gst.2020.83015

126

测绘科学技术

αcmFcm(vi,vj)+αcwFcw(Vm)αacFac(Vn),∑αk=1,αk∈(0,1),k∈{CM,CW,AC} (7)

薛磊，王行风

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

D=*??αcmFcm(Vm)(vi,vj)+αcwFcw?αacFac(Vn) (8)

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

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

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

2) 确定起始点S和目标点E，定义一个集合(CloseList)用于存放已遍历点；再定义一个集合(RoutList)用于存放最优路径，并初始化集合。 3) 根据超网络模型中节点和超边的集合和属性信息，计算改进的超边权值D*。 4) 判断S和E是否同层，若是则采用同层算法；反之则采用分层算法。 5) 将计算得到的RoutList集合结果输出并可视化显示。至此，算法结束。 开始获取室内网络数据设置起始点S和目标点E初始化RoutList集合和CloseList集合为空集距离路径复杂程度路径拥挤程度突发事件计算改进的超边权值D*,更新室内网络N在起始楼层i中，搜索起始点S与楼层联系点C的最优路径集合R1 S和E是否在同一楼层Y同层计算：搜索起始点S到目标点E的最优路径得到起始点S到目标点E的最优路径集合RoutList结束分搜索楼层联系点c与目标楼层j的楼层层联系点C’之间的最优楼层通道集计合R0算 在目标楼层j中，搜索目标点E与楼层联系点C’的最优路径集合R2 Figure 3. Flow chart of the improved Dijkstra algorithm 图3. 改进的Dijkstra算法流程图 4. 室内超网络模型验证及分析 4.1. 实验区域 本文选择某单位的学院行政楼作为研究区域，其整体外观如图4所示，该建筑地上共有5层，其中 DOI: 10.12677/gst.2020.83015 127 测绘科学技术