基于优化方法的区域疏散路径规划研究

慕　楠，宋卫国，霍非舟

(中国科学技术大学火灾科学国家重点实验室，合肥，230026)



基于优化方法的区域疏散路径规划研究

慕楠，宋卫国*，霍非舟

(中国科学技术大学火灾科学国家重点实验室，合肥，230026)

摘要:由于各种灾害的频频发生，对于区域整体及局部的疏散规划方案的研究具有迫切性和必要性。基于传统的迪杰斯特拉算法和回溯法的思想，对矩阵化的地图信息进行处理和计算，得到满足最大疏散人数、总体最短疏散路径、最短疏散时间等优化条件的优化方案。最后将这种方法运用到实际中，得出了某大学校区的路径选择方案。

关键词:疏散;迪杰斯特拉算法;回溯法;优化

0　引言

随着中国经济建设的高速发展，城镇化脚步的迈出，各地的各式建筑和工厂有如雨后春笋般蓬勃生长。与此同时，火灾等灾害事故也不断发生。在2013年1月6日，位于上海市沪南路2000号的上海农产品中心批发市场内发生重大火灾，造成6人死亡，12人受伤［1］。在2014年11月16日，山东省寿光市化龙镇裴岭村龙源食品有限公司发生了火灾，造成18人死亡、13人受伤［2］。

2008年5月12日，在四川省阿坝藏族羌族自治州汶川县发生里氏8.0级地震，地震造成69227人遇难，374643人受伤，17923人失踪［3］。这是近年来发生的影响力最大的一次地震，造成的伤亡程度非常巨大。在灾区的一些工程和大型商品贸易集散地，一次次小小的余震，就能让不知向何处疏散的民众伤亡惨重。疏散指导方案和疏散指示系统的建立和健全，在地震来临之际，对于有效地减少人员伤亡，具有十分重要的意义。

2011年3月11日，位于日本福岛的一所核电站的1号反应堆所在的建筑物爆炸后，2号机组也在随后发生了泄漏。核电站的3号机组同时也面临着爆炸危险。2011年3月13日，日本将21万人次进行了紧急疏散转移［4］。

2015年1月1日，正当新年的钟声敲响时，在上海的浦东区外滩处，却有36个生命再也没有见到新年的曙光。由于疏散引导不够，疏散应急预案不完善，民众对于实时信息的不知情等一系列因素，都导致了这场悲剧的发生。

综上所述，研究人员在疏散行为研究领域深入工作，具有强烈的迫切性，对于建筑结构的设计和疏散指导方案的制定都有极为重要的意义。Galea［5］等人利用buildingEXODUS软件研究了火灾情况下的人员行为和人员疏散情况。Wu［6］等人在2010年就2008年发生的汶川大地震的疏散视频进行了研究，分析了疏散人数和疏散时间的关系。Ma［7］等人在2013对德国“爱的大游行”发生的拥挤踩踏事故做了深入的分析。Zhang［8］等人在2008年对一个教室的疏散进行了实验研究和多格子模型模拟。Fang［9］等人在2010年对于一个建筑物的出口选择行为进行了实验和模拟的双重研究，接下来又在2012年对于高层建筑的楼梯疏散行为进行了实验研究［10］。他们还在2012年，将消防器材的影响耦合在多格子模型中，对于疏散行为进行了深入的模拟研究［11］。David［12］在2012年对于大尺度的交通工具疏散策略进行了研究。Fang［13］等人在2011年在研究一个体育馆的疏散场景中提出了一个时间等待模型来改善时空利用的效率。他们还在2011年利用蚁群优化算法进行了多目标的疏散路径研究［14］。在2013提出一种时空效率模型，对于行人流和交通流的疏散运动进行研究［15］。Montz［16］等人在2013年，提出了一种模型，来评估疏散过程中灵活响应的有效性。Kantawong［17］在2012年利用自适应路径算法和RFID技术对于疏散路径选择进行了探讨。Lim［18］等人在2015年从疏散时间、疏散路径的个数、发生堵塞的概率等关系入手，讨论了疏散路径的可靠性问题。Ma［19］等人在2013年研究了在紧急疏散情况下，行人和车辆的协调关系，对于我们后续研究有指导意义。

在前人研究的基础之上，我们基于传统的迪杰斯特拉算法和回溯法的思想，对矩阵化的地图信息进行处理和计算，得到最大疏散人数、总体最短疏散路径、最短疏散时间等优化条件的优化方案。

1　数学方法及理论分析

主要采取的步骤如下。

1.1初始地图信息矩阵化

首先是真实地图的网格化，将地理地图信息和网格划分进行重叠后，各个居民区(疏散起始点)和避难所(疏散结束点)均抽象为地图信息上面的一系列点，由这些点组成了地图矩阵。目标矩阵主要以整数构成，不同的数值代表不同的信息。其中，我们以非零数值代表抽象点的序列号，当抽象点为疏散起始点时，其值为正，意为其处于高势能处;反之，当抽象点为疏散结束点时，其值为负，意为其处于低势能处;另外，我们以0代表构成疏散路径的各个节点。将矩阵信息按照一定的格式全都写入相应的文件中，以准备在程序的第一阶段进行读入。

1.2迪杰斯特拉算法

根据迪杰斯特拉算法［20］，计算矩阵中各个格点到其他格点的最短距离，存储在距离矩阵中。读取并识别地图信息，提取每个疏散起始点到每个疏散结束点的最小距离。迪杰斯特拉算法是由荷兰计算机科学家迪杰斯特拉于1959年提出的，是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。迪杰斯特拉算法是一个经典的算法，是极具代表性的距离计算算法。

1.3根据最小距离矩阵

计算分解初始矩阵。具体的算法是，对于每一个起始节点i，如果矩阵中前一个元素C［i］［j］的值小于后一个元素C［i］［j+1］的值，那么则赋给D ［i］［j］=1，否则D［i］［j］=0。以此类推，如果D ［i］［n］小于D［i］［1］，则D［i］［n］=1，否则D［i］［n］=0。

1.4矩阵分解算法

初始矩阵的元素信息形式是，所有的元素均为0或者1，并且每一行至少有一个1，不能全为0。分解目标是将初始矩阵分解成为一系列子矩阵，这些矩阵满足的条件是，矩阵大小与原矩阵相同，矩阵元素均为0或者1，最关键的，每一行有且仅有1个1，这些1必须都是原矩阵中对应位置的1。具体的我们通过回溯法来实现矩阵的分解。

Golomb［21］早在1965年的时候就提出了回溯法，并且对于这种搜索算法进行了详细且易于理解的讲解，它是通过试探来实现探索优选的算法，在初始状态，我们会设定回溯的优选条件。在探索过程中，假如下一级的探索结果并不能满足优选条件，我们就会在此处返回上一级，对其他子节点进行探索，而这个返回的点就被称作回溯点。

利用回溯法，结合排列组合算法的思想，对分解初始矩阵进行第一次遍历之后，可以完成第一个分解矩阵的生成和输出。再回溯找寻第二个、第三个，以此类推。按照这种思想，我们可以将原有矩阵分解成一系列每一行只有一个1的矩阵。

1.5路径优化方案

主要采用穷举比较法，将上一步得到的分解输出矩阵逐个读入，然后将该矩阵元素与居民区(疏散起始点)的居民分布矩阵进行一定的计算，在满足避难所(疏散结束点)的负载情况下，确定最优路径优化方案。主要的优化方式有以下几种:最大疏散人数、总体最短疏散路径、最短疏散时间。

2　案例一:简单区域的疏散路径规划案例

主要考虑最大疏散人数方案、总体最短疏散路径方案和最短疏散时间三种方案。用简单的图片信息，描绘出居民区和避难所的位置，在此图上叠加网格信息，将地图信息抽象化。

图1　案例一地图信息Fig.1 Map information of Case 1

2.1基本情况描述

如图1所示是一片住宅区域，主要有四个居民点，分别为居民楼A、居民楼B、居民楼C、居民楼D。每个居民楼的居住人数分别为100人，200人，300人，400人。同时，在这些居民楼的周围有一个大型的广场，最多可同时容纳600人;一所小学，最多可同时容纳700人;在距离居住聚集地较远处，还有一个中型的公园，最多可同时容纳800人。这三个地点，在发生紧急情况下，都可以选取为临时的避难所。在发生火灾、地震、化学气体泄漏等重大危急事故时，仅从室内疏散到室外已经不能保证人员的生命安全。逃生人员需要在引导员的帮助下，选择安全有效的路径，从室外疏散至大型的避难所。在研究这个疏散过程中，我们的基本的思路就是先不考虑个体的运动状态，每个人取相同的疏散速度，来研究宏观的人员疏散路径选择行为。

2.2地图信息抽象化

图1所示的是真实的地图信息，需要经过预处理才能变成我们程序可以计算的地图。这里我们借鉴元胞自动机的离散化思想，用一系列小方格覆盖整个地图，使得每个居民点和避难点(居民楼和避难所的中心点)都能落在唯一确定的小方格内。这里，我们规定，人员疏散的路径只能沿着此时刻所在点的四邻域方向进行，且在这种情况下，不考虑人员后退情况。人员的运动选择方向就只有“前”、“左”、“右”三个方向。

所谓四领域，就是指人员所在方格的相邻方格只能是“上”、“下”、“左”、“右”四个方向的最近方格，如图2所示。而考虑人员运动方向，不能后退，则人员的下一步运动的方格只能是考虑运动方向的“前”、“左”、“右”(注:此处的“前”、“左”、“右”方向是对于人员自身而言，并非前文中的提到的实际方向“上”、“下”、“左”、“右”)。

图2　四邻域方向Fig.2 Direction of 4 adjoining points

图3　四领域中的运动方向Fig.3 Moving direction of 4 adjoining points

2.3矩阵分解

在原始地图上叠加网格线，将它划分成一个个的小方格，得到该地图的信息矩阵Map如图4，其中1～4的正整数表示居民区，－1～－3的负整数表示避难所，0代表其他格点:

利用迪杰斯特拉算法，计算每个居民楼到每个避难所的最小距离矩阵C:

图4　地图的网格化Fig.4 Gridding of map

对于每一个起始节点i，如果矩阵中前一个元素Cij的值小于后一个元素Cij+1的值，那么则赋给Dij=1，否则Dij=0。以此类推，如果Din小于Di1，则Din=1，否则Din=0。因此，D矩阵如下所示:

将D矩阵进行分解，每个子矩阵每一行只有一个1，代表了每个疏散起始点只有一个选择。对应的子矩阵的个数为，2×2×2×2=16个(将每一行1的个数相乘) :

在矩阵分解的基础上，进行路径优化选择。

2.4最大疏散人数方案

居民楼人数矩阵

避难所人数矩阵

计算矩阵I和矩阵Case的乘积，得到新的矩阵的每一项元素的数值不能超过J矩阵中对应项元素的数值。再将这每一项元素的数值求和，得到总的疏散人数。依次遍历所有的Case矩阵，找到疏散人数最大时所对应的Case矩阵。最终选择:

图5　最大疏散人数方案Fig.5 Case of maximum evacuation population

2.5总体最短疏散路径方案

计算每种Case下的总体疏散路径，通过比较，得出总体疏散路径最短的那个Case。最终选择:

图6　总体最短疏散路径方案Fig.6 Case of minimum evacuation paths in total

2.6最短疏散时间方案

计算Case矩阵和time矩阵的乘积，求得每个Case的最大疏散时间。再将所有Case的疏散时间进行对比，找出最小的Case。最终选择:

图7　最短疏散时间方案Fig.7 Case of minimum evacuation time

上述三种方案，第一种是比较关注在疏散过程中人员安全，力求在整个疏散过程中疏散出最多的人数，这是我们的主要目标，采用这种优化方法的实际意义也比较明确。第二种方案考虑的是总体的疏散路径，这对于在后续我们研究用交通工具进行疏散的时候有帮助，而且对于避难场所的安排和设计具有极高的参考价值。这会督促和提醒设计者们进行科学合理的布局和设计，最大限度地保障人员的生命安全。第三种方案是考虑疏散过程的时间成本，考虑这种优化方案是对应于那些灾害来得突然和激烈时，时间非常有限的场景。在这种场景下，抓住了时间就相当于抓住了生命。另外，在多重疏散场景耦合的情况下，疏散时间也是几位重要的中间环节参数，对于疏散规划者规划整体疏散方案具有十分重要的意义。这些优化条件当然不止我们上面提到的三种，其他的方案可能在一些特定场景下更为实用，不过我们现在仅讨论以上三种优化方案。

3　案例二:某大学校区的应急疏散路径选择

图8　某大学校区的地图Fig.8 Map of a university

表1　某大学校区的人员分布详情估算Table 1 Pedestrian distribution estimation of west campus of a university

图9　某大学校区的建筑分布图Fig.9 Building distribution map of a university

5个避难所的人员容纳设定(主要是通过避难所的大小，避难所的功能设定，主要是为了研究方便，能够容纳所有人数，所设定数字的实际意义不大)。

表2　某大学校区的避难所容量估计Table 2 Shelter capacity estimation of west campus of a university

4　结果与讨论

通过人员分布的表格描述，我们知道，某大学校区的人员主要分布在各个宿舍楼和实验办公室内。

图10显示的是最大疏散人数方案的疏散结果。我们可以看出，位于避难所人员容量第一位的第3避难所(东门)和第二位的第1避难所(北门)，分别被5、8、10和1、2、4疏散起始点选择。这两个疏散避难所能够接纳的人数分别为8160人和8000人。尤其是对于第10起始点，所在的人员并没有选择更近的第5避难所，而是选择了次近的第3避难所。原因一是我们设定的遍历模式是从第1避难所开始，按照顺序进行，如果第3避难所的容量足够，第10疏散起始点就会有限选择第3避难所;二是第3避难所的容量设定为最高10000人，受选择条件的限制，为了疏散人数的最大化，第10疏散起始点也会选择第3避难所作为目标疏散地。

图10　某大学校区的最大疏散人数方案Fig.10 Case of maximum evacuation population of a university

图11显示的是总体最短疏散路径方案。单从疏散起始点距离疏散避难所的距离而言，总体上较为均衡，这也就是保证了总部疏散路径最短的优化目的。但是在前面我们也提到了，虽然此方案的总体疏散路径是最短的，所有疏散者走路的总和最小，不过，第2避难所的实际达到人数超过了避难所的最大容量，超出的人员就不能进入避难所。一是如果他们选择去还未饱和的其他避难所，势必造成时间和空间上的延迟，危险程度增大;二是不能进入安全区域，人身和财产面临着巨大的威胁;三是强行涌入避难所，造成人员密度过大，在避难所内部引起新的安全隐患，造成拥挤和踩踏事故，这一点是我们极为担心发生的。

图12显示的是最小疏散时间方案。该方案的最核心的思想就是就近原则，离得越近，在疏散速度总体平均考虑的情况下，疏散时间就会最短。而要求得最短疏散时间方案，就要考虑木桶原理，意思是所有的疏散起始点，到目标起始点的最大疏散时间，就是该方案的疏散时间。所以我们求得的最小疏散时间方案，就是所有case中的最大疏散时间的最小值对应的疏散方案。与方案二相似的是，第4、第5避难所的实际达到人数大大超过其最大容量，超出的人员也是不能顺利进入避难所，选择其他避难所，也会造成时间和空间上的延误;而不能进入避难所，或者强行进入避难所，都会造成更大的安全隐患，不符合整体的利益。

图10～图12都显示了某大学校区在发生火灾地震等灾害情况下的紧急疏散情况，研究的方法简单易操作，对于疏散预警有指导意义。

通过表3可以发现，在只考虑总体最短疏散路径和最短疏散时间的方案中，人员疏散往往过于集中，导致某些疏散避难所的实际达到人数超过其最大容量，这样就会造成部分人群疏散不成功，引起更大的灾害事故。

图11　某大学校区的总体最短疏散路径方案Fig.11 Case of minimum evacuation paths in total of a university

图12　某大学校区的最短疏散时间方案Fig.12 Case of minimum evacuation time of a university

表3　三种方案的各个避难所实际疏散人数和容量对比Table 3 Comparison of actual population evacuated and shelter capacity of three cases

5　结论

本文运用了迪杰斯特拉算法、矩阵分解回溯法、穷举优化等算法，在此基础上提出了一种路径规划的简单模型。将地图信息矩阵化的基础上，通过编程将矩阵进行分解，并依照一定的规则进行计算和选择，选出符合优化条件的矩阵。也就是说，得出一个符合优化条件的疏散方案。对于一个较为简单的案例，进行优化方案的设计，再将成功经验扩展至实际的情况，对一个大学校园疏散路径进行规划。

疏散路径优化的条件，考虑的维度，分别为最大疏散人数、总体最小疏散路径、最小疏散时间，对于同一个案例，给出了不同的优化方案。

对于三种疏散方案的对比结果进行分析，最大疏散人数方案能保证人员的最大疏散量，人员在各个避难所的分布较为均匀，一般不太会超出避难所的最大容量，但是会使得部分行人选择离自己较远的避难所，在时间紧迫的疏散情况下，容易造成危害。对于最小疏散路径方案，是个体最短疏散路径方案的延伸，符合人们的常识和习惯，但是这种方案在避难所分布不均匀的情况下，会造成个别避难所人员超过避难所的最大容量。对于最小疏散时间方案，比较适合于灾情紧急的情况下，在这种条件下分秒必争，时间就是生命，最小的疏散时间就意味着最大的安全。当然，该方案也可能会导致避难所的实际人数超出避难所的最大容量。

该疏散路径优化方法的最大优点是操作起来简单方便，对于不是很复杂的案例，都能很快给出多种优化结果。优化算法的理解和掌握也不是太难，但是在现阶段的经济建设情况下，意义非常重要。

各个优化方案，各有利弊，需要综合考虑，才能提出最合理的疏散方案。而在今后的研究过程中，要适当地考虑各种不同的灾害区域，以及灾害类型的不同属性，对于人员疏散产生的各种影响。还要考虑到人员类型和人员运动行为习惯等对于疏散的影响。

在真实的地区疏散中，道路的长度、通行能力和实时交通状况都对疏散有很大的影响，因此，该模型还不够完善。后续的目标是，引入相关参数，使得模型能够更加真实有效地完成疏散路径的优化过程。

参考文献

［1］百度百科: 1·6上海农产品批发市场火灾事故［EB/ OL］.http://baike.baidu.com/link? url=jhcu3vx2AB 0MsGCJeWVbPlDgPqWUVisAqVNjsHLLRWnEDDSs5 Y1rxOx5yxGMdnU0QRRvwJUXh4K5O_TZ1-Cyjq.

［2］山东寿光市化龙镇裴岭村龙源食品厂火灾现场图片-闽南网［EB/OL］.http://www.mnw.cn/news/china/ 821518.html.

［3］百度百科: 5·12汶川地震［EB/OL］.http://baike.baidu.com/view/3486152.htm? fromtitle=% E6% B1% B6%E5% B7% 9D% E5% 9C% B0% E9% 9C% 87＆fromid=2452700＆type=search.

［4］百度百科:福岛核电站泄漏［EB/OL］.http://baike.baidu.com/link? url=JFH8URcN-VI3n_QNWWhm5Vj rCAPa2N24aIhCCkxeFGR5UyBf4Bo_LU06Ul57FJFtzJ3 XACQKH9WIhll2wpZGGq.

［5］Gwynne S，et al.Modelling occupant interaction with fire conditions using the building EXODUS evacuation model ［J］.Fire Safety Journal，2001，36(4)，327-357.

［6］Yang XL，et al.Difference between real-life escape panic and mimic exercises in simulated situation with implications to the statistical physics models of emergency evacuation: The 2008 Wenchuan earthquake［J］.Physica A: Statistical Mechanics and its Applications，2011，390 (12 ) : 2375-2380.

［7］Ma J，et al.New insights into turbulent pedestrian movement pattern in crowd-quakes［J］.Journal of Statistical Mechanics-Theory and Experiment，2013，02: P02028.

［8］Zhang J，et al.Experiment and multi-grid modeling of evac-uation from a classroom［J］.Physica A-Statistical Mechanics and its Applications，2008，387(27) : 5901-5909.

［9］Fang ZM，et al.Experiment and modeling of exit-selecting behaviors during a building evacuation［J］.Physica A-Statistical Mechanics and its Applications，2010，389 (4) : 815-824.

［10］Fang ZM，et al.Experimental study on evacuation process in a stairwell of a high-rise building［J］.Building and Environment，2012，47: 316-321.

［11］Fang ZM，et al.A multi-grid model for evacuation coupling with the effects of fire products［J］.Fire Technology，2012，48(1) : 91-104.

［12］VanLandegen LD，et al.Microsimulation of large-scale evacuations utilizing metro rail transit［J］.Applied Geography，2012，32(2) : 787-797.

［13］Fang ZX，et al.A proposed pedestrian waiting-time model for improving space time use efficiency in stadium evacuation scenarios［J］.Building and Environment，2011，46 (9) : 1774-1784.

［14］Fang ZX，et al.A multi-objective approach to scheduling joint participation with variable space and time preferences and opportunities［J］.Journal of Transport Geography，2011，19(4) : 623-634.

［15］Fang ZX，et al.A space–time efficiency model for optimizing intra-intersection vehicle–pedestrian evacuation movements［J］.Transportation Research Part C: Emerging Technologies，2013，31: 112-130.

［16］Montz T，et al.Assessing the effectiveness of flexible response in evacuations［J］.Natural Hazards Review，2012，14(3) : 200-210.

［17］Kantawong S.Development of fire evacuation path selective using adaptive routing algorithms and RFID traffic cone-based observation with shadowing method［A］.2012 9th International Conference on Electrical Engineering/E-lectronics，Computer，Telecommunications and Information Technology (ECTI-CON 2012)［C］.

［18］Lim GJ，et al.Reliability analysis of evacuation routes under capacity uncertainty of road links［J］.IIE Transactions，2015，47(1) : 50-63.

［19］Ma YL，et al.A study on simulation and optimization for personnel and vehicle coordination evacuation in Case of Emergency［J］.Journal of Theoretical and Applied Information Technology，2013，49(2) : 864-870.

［20］百度百科:迪杰斯特拉算法［EB/OL］.http://baike.baidu.com/link? url=mtVdWMWIo_iZHjPW4Onn22 LAIZMoKE7Qg9gFahOHa40MOp2PGqgStvhSNn1bjv w3kYB2fJXeA1-M6EtKCs6yr_.

［21］Golomb SW，Baumert LD.Backtrack programming［J］.Journal of the ACM，1965，12(4) : 516-524.

Study of area evacuation paths plan based on optimization methods

MU Nan，SONG Weiguo，HUO Feizhou
(State Key Laboratory of Fire Science，University of Science and Technology of China，Hefei 230026，China)

Abstract:Nowadays，more and more disasters occur frequently，so it is of vital urgency and necessity to make the overall and partial region evacuation planning.Based on the traditional Dijkstra algorithm and backtracking algorithms，we processed and calculated the matrix of map information.By the method，we obtained three optimization schemes of maximum evacuation population，minimum evacuation paths in total，and minimum evacuation time.Finally，this method was applied in a university，thereby the routing schemes of were obtained.

Keyword: Evacuation; Dijkstra; Backtracking; Optimization

通讯作者:宋卫国，E-mail: wgsong@ustc.edu.cn

作者简介:慕楠(1990-)，男，中国科学技术大学硕士研究生，主要研究方向为灾害条件下的人员疏散问题。

收稿日期:2015-03-05;修改日期: 2015-05-06

DOI:10.3969/j.issn.1004-5309.2015.03.08

文章编号:1004-5309(2015) -00176-09

中图分类号:X931

文献标识码:A