基于疏散计划的最短路最大流分配算法初探

朱雪丽

（山东省工会管理干部学院，山东 济南 250100）

基于疏散计划的最短路最大流分配算法初探

朱雪丽

（山东省工会管理干部学院，山东 济南 250100）

随着突发事件的不断发生，大规模的人群疏散越来越受到人们的关注。突发事件往往伴随着人群恐慌、拥堵等一系列现象，这一系列的不确定性往往导致疏散不利，造成不必要的财产损失和人员伤亡。Dijkstra算法目前被认为是求无负权网路最短路问题的最好方法，很多情况下，通过科学制定疏散计划进行有效的疏散，可以减少意外事件发生时人群的疏散时间，减少人员伤亡及财产损失。

灾害疏散节点；容量约束；Dijkstra算法

一、问题提出

目前，人类正面临越来越多的自然灾害威胁，如地震、海啸、火山爆发、泥石流、飓风等，此外，还有人为灾难，如恐怖袭击、战争等。由于人口密度大，突发意外往往会因为疏散不利造成巨大的社会损失，带来严重的人员伤亡，影响社会的发展。这些自然灾害往往让人们措手不及，而且难以避免，但是，人类可以通过先进的技术手段，提前预测并通报这些灾害，事先制定疏散计划并组织人员有效疏散，从而有效降低灾害损失及伤亡。因此，现在很多单位和学校越来越重视模拟疏散演练。

以近年来世界上发生过的意外灾害为例。1992年8月24日，“安德鲁”飓风以240公里/小时的风速席卷迈阿密以南的霍姆斯特德一带。飓风所到之处，建筑物遭到严重损毁。在“安德鲁”飓风肆虐的几天里造成了20多人死亡，1500万人受伤。8月25日，“安德鲁”飓风225公里/小时的速度越过墨西哥湾，向路易斯安那州第一大城市新奥尔良市方向呼啸而去，25日夜至26日凌晨，袭击了路易斯安那州的沿海城镇。[1]虽然在飓风来临之前，人们就做了许多防范措施，但损失还是非常惨重。由于没有有效的疏散计划，公路上车辆堵塞，寸步难行，造成了巨大的混乱，影响了道路畅通，极大的影响了受害群众的疏散。

疏散是指将密集的人员、物资等分散转移的行为。面对突如其来的自然灾害及人为灾难，制定有效的疏散计划是非常有必要的。疏散大部分是在紧急事故中才有的现象，包括地震、海啸、火灾、恐怖袭击等一系列突发状况，当然也有非紧急状况，如放学等。制定疏散计划的目的就是能够在紧急情况发生之前，或发生时能做到有条不紊的撤离，减少人员及财产损失。只有平时做好各项准备，遇到意外灾害时才能有效撤离，达到预期的目的。

意外灾害是无法避免的，但我们可以通过有效的疏散安排来减少财产损失及人员伤亡。在众多突发事件中，由于没有有效的进行疏散，造成了大量的人员伤亡，总结起来，失效疏散都是因为拥挤、恐慌或其他原因，没有及时疏散到安全地带，造成不必要的伤亡，因此，对疏散计划的研究具有重要意义。

二、模拟情境下疏散计划的制定

现给定如下参数：一个疏散网络，即一个有向图G=(N，E)；每个节点和每条边均有容量约束(非负整数)；每条边的运行时间(非负整数)；撤离人员数和他们的初始位置(源)；撤离目的地(汇)。

输出：疏散计划的组成包括一系列起点-终点路线和每条路线的撤离调度。路线安排应按照各边的容量约束，以每条疏散路线各边的最小容量为准。

目的：尽量缩短疏散时间，即从开始疏散到最后一个疏散对象到达目的地的时间。疏散时间的减少能有效保护生命、财产的安全，保证稳步、有效、危险性最小的疏散[2]。

情境描述：假设现有三个节点有受灾群众，节点编号为N1、N2、N8，图中标明各节点的最大容量。如（N1,50），表示N1节点的最大容量为50。三个节点现有受灾群众分别为10、5、15。箭头方向代表疏散路径，图中数据分别为（通道最大容量，通过所需时间）。如N1-N3节点为（7,1）代表本条路径的最大通过能力为7，通过本条路径需时1分钟。

现假设本地发生意外灾害，需要人员紧急撤离。若无疏散计划，那么在意外灾害发生的瞬间，各个节点的人群可能就会因突发意外造成的慌乱而纷纷涌至过道、出口，由于各节点及通道容量有限，若没有合理的疏散计划，就有可能造成拥堵甚至是踩踏事件的发生，造成疏散时间的浪费，进一步造成人员伤亡。现将疏散网络描述如下：

先找出三个节点的疏散路线。如在本例中，N1节点的疏散路线有两条，第一条：N1-N3-N4-N6-N10-N13，所需总时间为14分钟。第二条：N1-N3-N5-N7-N11-N14，所需总时间为15分钟。依次找出各节点的疏散路线。将受灾群众分组，制定疏散计划表如下：

注：路径中N（T）,T表示从本节点出发的时间。

在制定疏散计划表安排各条疏散路线的疏散人数时，必须以本条路线的最小边容量为依据，否则将造成通道拥挤。如在D组疏散路线中，N3-N4的容量为3，所以每次疏散人数最大为3。

以N1节点为例，因为N1-N3路线的最大容量为7，在节点N1内的10名受灾群众可以分两批疏散，第一批7人在第一时间撤离，第二批3人。N2节点的5名受灾群众可在第一时间撤离到N3节点。

思路：

1、将节点容量和边容量定义为一个时间序列，而不是一个固定的数字。对于一个给定节点Ni：可用节点容量(Ni,t)=t时刻节点Ni的可用容量。对于一条给定边Ni-Nj：可用边容量(Ni-Nj，t)=t时刻边Ni-Nj的可用容量。

2、运用Dijkstra算法了解容量限制，归纳最短路径算法。当所有节点均有疏散对象：

第一步：基于当前可用边容量和可用节点容量，寻找从源到汇花费最短时间的路径R。

第二步：计算路径R的实际流量

流量=min{路径R中源点的剩余疏散数量，可用边容量(路径R的所有边)，可用节点容量(路径R的所有节点)}。

第三步：保留路径R的容量。

R上每条边上的可用容量减少；R上每个接受节点的可用容量减少。

三、结束语

突发事件发生时，疏散往往伴随着高密度的人群、极度惊恐的情绪和极度混乱的环境等大量不确定因素，疏散难度较大，具有挑战性，因此，人们越来越关注大规模的人群疏散[3]。提前制定疏散计划并进行演练可以建立个人和联合的自我保护意识，可以估计撤离所需要的时间，使人们在面对突发的意外灾害时保持镇定，能够相对有条不紊的撤离，避免因疏导不善造成的财产损失及人员伤亡。

Dijkstra算法虽然目前被认为是求无负权网路最短路问题的最好方法，但是真正应用到疏散计划时却有欠缺，容易因流量约束受到限制，就好比在实际疏散过程中，虽然找到了最短路，但是由于大量人群或车辆涌向本条最短路，结果造成拥堵，反而不利于撤离。

在疏散网络中还有许多问题需要不断的探讨和研究。本例是在相对理想状态下展开的，各节点容量、各边最大容量是事先给出的，但是如何完善处理流量不确定的情况，仍需进一步研究。

[1]排行榜-自然大灾难集调查-记事排行榜-新榜网.

[2]姚斌，刘乃安，李元洲.论性能化防火分析中的安全疏散时间判据[J].火灾科学，2003，（05）.

[3]孟博,刘茂,孙晓磊,王丽,刘付衍华.基于智能体模拟的结构性疏散计划设计研究[J].南开大学学报（自然科学版），2011，（2）.

[4]麻省理工学院,Capacity Constrained Routing Algorithms For Evacuation Planning:A Summary of Results.

（责任编辑：赵扬）

X913.4

A

1008—6153（2013）03—0114—02

2013-04-18

朱雪丽（1987-），女，山东莱芜人，工程硕士，山东省工会管理干部学院教师。