人群密集公共场所疏散算法设计研究*

李智成，李 锋，莫乐群

（广东交通职业技术学院，广州510650）

人群密集公共场所疏散算法设计研究*

李智成，李 锋，莫乐群

（广东交通职业技术学院，广州510650）

通过统计行人交通参数数据规律和特点，设计大型公共场所行人交通状态评价方式，提出利用元胞自动机模型模拟人群个体行为和群体效应，再利用遗传迭代算法淘汰适应度低下人员节点，经粒子群算法计算逃生路径，生成全局最优子图，形成疏散方案和紧急预案。仿真实验证明，新算法疏散效率较高，为建立完善、科学城市应急体系提供决策与参考。

元胞自动机；遗传算法；粒子群算法；疏散模型

1 引言

近几年来公共场所突发事件层出不穷。在宏观上，国家政治、经济高速发展伴随着社会危机的爆发期；在微观上，公共场所人群密集，行人对环境陌生，突发事件容易造成群死群伤事件，并且人员密度越大，事故发生几率越高，伤亡和财产损失越严重。如何对行人交通监控、管理和疏散成为目前研究的热点和难点[1-2]。

在紧急疏散时，行人受到惊吓或对新环境陌生，个体行为既具有趋众性，也表现出很大的个体差异，其逃生方向和速率是一个不断变化的过程[3]。为准确模拟不同个体逃生方式，通过统计行人交通参数数据规律和特点，设计大型公共场所行人交通状态评价方式，提出利用元胞自动机模型模拟人群个体行为和群体效应，通过遗传迭代算法模拟人群在具体疏散过程中的动态变化，并淘汰适应度低下的人员节点（模拟人员受伤或者死亡），经粒子群算法计算逃生路径，生成全局最优子图，形成疏散方案和紧急预案。

2 疏散模型与算法

2.1 疏散模型

公共场所突遇突发事件时，疏散过程受人员之间和人与环境之间的相互影响，人群会出现聚集阻塞、自动队列、趋众性、震荡和协作等现象，其逃生速度和方向是一个不断变化的过程[4-5]。为模拟人群疏散方式，业界提出元胞自动机、流体力学、社会力等仿生疏散模型。其中，流体力学模型为减少计算复杂度，不考虑流体质点之间的摩擦和碰撞导致的能量损失，将疏散人流看为无粘性的流体运动，在人流量较少时模拟精确，不适合密集公共场所人员建模[6]。社会力模型主要考虑疏散人群之间的社会属性，即人的宏观流动，忽略人的个体行为，将个体逃生方式简单地看成是人流的匀速运动，模拟效果与真实情况差距较大[7-8]。元胞自动机模型将疏散空间划分为网格，网格中的元胞通过相互作用和动态演化模拟人群个体行为和群体效应。在紧急疏散中，人群会因过度惊吓在逃生时出现推搡、冲撞、踩踏等事件，为反映个体逃生方式和人员状态，文章通过遗传算法模拟人群疏散过程中的个体动态变化，并淘汰适应度低下的人员节点，以此检验疏散方案效率和公共场所建筑设计与布局的合理性。

论文通过统计行人交通参数数据规律和特点，结合大型公共场所行人交通应急疏散的建筑布局特征，如广场、步道、楼梯等，设计大型公共场所行人交通状态评价方法，将元胞自动机模型、遗传算法和粒子群算法有机融合，提出密集人群公共场所交通状态评价与疏散算法，从而计算逃生路径，形成疏散方案，让疏散人员通过团结互助，有方向，有组织，有秩序地逃离事故现场，并以此检验和改进公共场所建筑设计与布局的合理性。

2.2 疏散算法

要计算疏散人员的最优逃生路径，在数学建模上可以转变为求解单源多目的路径排列组合的优化算法问题[9]。求解全局最优算法有Dijkstra最短路径算法、蚁群算法和粒子群算法等。最短路径算法只是计算行人与逃生出口之间的最短通路，而不是全局最佳路径，会出现指引行人逃向事故现场的现象。蚁群算法简单地利用路径信息素正向反馈机制择径，当信息素过浓时算法提早收敛，导致所有蚂蚁（即行人）都走到同一路径，导致拥塞。粒子群算法将寻找最优问题的每个解对应搜索空间的每个行人，称为粒子。每个粒子的初始化向量代表行人位置和逃生速率，每个行人通过寻找附近粒子的最优解更新自己逃生方向和速率，迭代生成全局最优解，计算逃生路径，生成全局最优子图。

3 基于元胞自动机的人员疏散模型

3.1 行人交通拥堵评价方式

采用视频检测器采集行人交通状态，行人交通状态由行人密度、速度和流量三个参数决定。其中密度是单位面积中人数，速度是人员步行速度，流量是单位时间内经过总人数，三者关系如下：

根据Togawa推导的疏散时间公式为：

在一定时期内，行人交通状态数据具有较好的稳定性和规律性。当某日行人交通数据突然大幅偏离正常趋势，系统即判为拥堵产生，拥堵程度评价方式为：

3.2 基于元胞自动机模型设计

元胞自动机(cellular automata，简称CA)是指在离散和有限状态下由元胞组成的元胞空间，并按照指定规则演化的动力学系统。在元胞自动机模型中空间被划分为网格，处于网格中的每一单元叫做元胞，所有元胞遵循相同规则变化，通过大量元胞的相互作用模拟群体效应和演化过程。论文通过元胞的相互作用和动态演化模拟疏散过程中人群的个体行为和群体效应。

在建模中，文章基于元胞自动机模型将公共场所空间划分成0.3m×0.3m（拥挤时个人所占据的空间）正方形网格，每个网格分为有人占据和无人占据两种状态。当发生拥堵和应急疏散时，行人沿着网格从一节点移动至下一邻居节点，从而模拟人群逃生路径。

考虑应急疏散时行人会表现出相当的趋众性，文章引入D描述人与人之间的相互影响程度。初始时所有元胞相互影响程度D均为0，当邻居疏散人员从节点n成功逃逸至下一节点m时，则节点m对源节点n影响值加1，从而定义下一节点m对原节点n的选择概率为：

其中，(x,y)是安全出口坐标。

3.3 遗传算子设计

遗传迭代算法能很好地模拟人群疏散过程中的个体动态变化，并淘汰适应度低下的人员节点。文章定义交叉概率Pc为：

3.4 逃生路径算法设计

疏散人员最佳择径可以转变为求解单源多目的路径排列组合优化问题，利用粒子群算法迭代求精计算全局最优解。定义公共场所共有k个逃生出口，结合式（4）元胞选择概率，元胞粒子找到下一粒子后按照式（8）和（9）更新当前位置和速率。

4 仿真测试

4.1 测试环境

实验选取广州某步行街道进行仿真测试，共设置疏散出口10处，见图1。测得近30天平均人流量182/min人次，其中某日测得两处人流量达243/min和256/min人次，超出预设范围，系统判为拥堵产生。

图1 仿真实验拓扑图

4.2 测试结果

仿真实验将元胞空间划分为1000×600网格，疏散人数为1826人次，密度按实际情况部署，人员疏散速率为1m/s，初始化遗传总群300，最大遗传代数200，交叉概率Pc＝0.8，变异概率Pm＝0.02，粒子群算法惯性权重Wmax=0.9，Wmin=0.4。疏散效率见图2所示。

图2 疏散效率对比图

在实际疏散过程中，行人按照逃生指示牌进行疏散，部分行人受趋利避害效应和趋众性影响，导致大量人员涌向①、②、③和④出口，产生新的拥堵，疏散效率较低，全程共花费116秒。新算法基于粒子群全局择优思想，疏散效率较高，在30s内疏散近60%人员，总疏散时间为94秒。新算法利用元胞自动机模型和遗传算法仿真行人疏散状态，计算的逃生失败、受伤和死亡人数均为0，和实际情况相吻合。

5 结束语

文章提出基于元胞自动机的人员疏散模型，利用遗传算法淘汰适应度低下人员节点，经粒子群算法计算逃生路径，疏散效率较高，具有一定的应用价值，可以为建立完善、科学的城市应急体系提供决策与参考。

[1]孙德山.元胞自动机研究进展[J].五邑大学学校（自然科学版），2011（4）:22-28.Sun Deshan.Research progress of Cellular Automata[J].University of WuYi University （Natural Science Edition）,2011(4):22-28.

[2]郭玉荣,郭磊,肖岩.基于元胞自动机理论的紧急人员疏散模拟[J].湖南大学学报,2011(11),25-29.Guo Yurong,Guo Lei,Xiao Yan.Emergency Evacuation Simulation Based on Cellular Automata Theory[J].Journal of HuNan University,2011(11),25-29.

[3]束钰,陈全.基于元胞自动机对大型商贸场所火灾过程的模拟分析[J].天津理工大学学报,2011(1):80-84.Su Yu,Chen Quan.Simulation Analysis of Fire Process in Large Commercial Places Based on Cellular Automata[J].Journal of Tianjin University of Technology,2011(1):80-84.

[4]崔喜红,李强,陈晋,陈春晓.大型公共场所人员疏散模型研究一考虑个体特性和从众行为[J].自然灾害学报,2005(6):133-140.Cui Xihong,Li Qiang,Chen Jin,Chen Chunxiao.A Study on IndividualCharacteristicsand Conformity Behaviorin Large-scale Public Space Evacuation Models[J].Journal of Natural Disasters,2005(6):133-140.

[5]孟晓静,杨立中,李健.基于元胞自动机的城市区域火灾蔓延概率模型探讨[J].中国安全科学学报,2008(2):28-33.Meng Xiaojing,Yang Lizhong,Li Jian.Discussion on the Probability Model of Fire Spread in Urban Areas Based on Cellular Automata[J].Journal of Chinese Security Science,2008(2):28-33.

[6]孟俊仙,周淑秋,饶敏.大型建筑内人员疏散计算机仿真研究评述[J].计算机应用与软件，2008(3):159-161.Meng Junxian,Zhou Shuqiu,Rao Min.A review of Computer Simulation Study on Evacuation of Personnel in Large Buildings [J].Computer Application and Software,2008(3):159-161.

[7]许爱军,张文金,易丹.基于VRML的虚拟现实技术及应用[J].计算机与数字工程,2009(04):186-189.Xu Aijun,Zhang Wen Jin,Yi Dan.Based on VRML Virtual Reality Technology and Application[J].Computer and Digital Engineering,2009(04):186-189.

[8]杨立中,方伟峰,黄锐,邓志华.基于元胞自动机的火灾中人员逃生的模型[J].科学通报,2002(12):896-900.Yang Lizhong,Fang Weifeng,Huang Rui,Deng Zhihua.Model of Evacuation of Personnel Based on Cellular Automata[J].Science Bulletin,2002(12):896-900.

[9]谭惠丽,邱冰,刘慕人,孔令江.房间内人群疏散过程的元胞自动机研究[J].广西师范大学学报(自然科学版),2004(4):1-4.Tan Huili,Qiu Bing,Liu Muren,Kong Lingjiang.Study on Cellular Automata in the Evacuation Process of People in the Room[J].Journal of Guangxi Normal University(Natural Science Edition),2004(4):1-4.

Research on Evacuation Algorithm in Public Places

Li Zhicheng，Li Feng，Mo Lequn
(Guangdong Communication Polytechnic,Guangzhou 510650,China)

Through the statistics of pedestrian traffic parameter data rules and characteristics,a public traffic evaluation model is designed,and the cellular automaton model is used to simulate the behavior of the individual and public effect,using genetic algorithm to eliminate unsuitable grid nodes,using particle swarm algorithm to calculate the escape path.The simulation results show that the new algorithm has high efficiency,and can provide a reference for government to make evacuation plans.

Cellular automata;Genetic algorithm;Particle swarm optimization;Evacuation model

10.3969/j.issn.1002-2279.2017.05.015

TP393

A

1002-2279-（2017）05-0057-04

（1）广东省大学生科技创新培育专项资金项目（项目编号：pdjh2017b0621）；（2）全国交通运输职业教育教学指导委员会2015年交通运输职业教育科研项目（项目编号：2015B21）；（3）广东省高等职业技术教育研究会重点课题（项目编号：GDGZ15Z007）；（4）中国交通教育研究会教育科学研究课题（项目编号：1402-136）

李智成（1996—），男，广东省广州人，学生，主研方向：网络工程。

李 锋（1981—），男，广东省龙川县人，硕士，讲师，主研方向：计算机工程。

莫乐群（1976—），男，广东省广州人，硕士，副教授，主研方向：信息系统与信息安全。