基于行程距离最优及容量受限的避难所分配算法研究

李久刚，唐新明，刘正军，汪汇兵

1.武汉大学资源与环境科学学院，湖北武汉430079；2.国家测绘地理信息局卫星测绘应用中心，北京100830；3.中国测绘科学研究院，北京100830

1 引 言

各种自然灾害及事故灾难给人类造成了严重的人员伤亡和经济损失，并且大多数灾害过程中的人员伤亡是由于受灾人员得不到及时的科学疏散所造成的［1］。因此，在突发事件发生前或灾害发生过程中，有效地实施应急疏散策略对提高城市灾时应急响应能力具有非常重要的意义，应急避难场所科学分配就是策略之一。

应急疏散过程中的避难场所分配实际上也是划定避难场所空间服务范围的过程。目前，在划定设施服务范围方面，国内外已有学者做过相关研究，如雷达气象站、消防站以及特快列车车站等［2－5］，这些应用大多都是通过GIS软件的缓冲分析功能实现［6］。但这样划定的设施服务范围在空间上没有考虑到排他性，往往会产生重叠。而灾区人员（空间单元）针对避难所的分配具有明显的排他性。文献［7］采用网络最短距离分析和最短路径时间分析构建的Voronoi面域图，可以模拟出功能中心点辐射影响范围空间划分的实际情况，以及Thiessen多边形被广泛应用等［8－9］，在这些方法中考虑到服务范围的排他性，但未考虑设施的容量。并且这些方法都假设潜在需求在空间上是均匀分布的，其难以准确处理不均匀分布的需求。在综合对比上述方法的基础上，针对城市重大突发事件人员紧急疏散策略，提出一种基于替换插值机制的城市灾害避难所分配算法。该算法充分考虑到避难所的容量限制及城市居民在空间分布上的不均匀性，在保证所有被分配空间单元都能分配到唯一的避难所的基础上，避免避难所过度拥挤，减少总行程距离，并且尽可能维持单个避难所服务范围的空间连续，为应急疏散提供辅助决策。

2 避难所分配模型设计原则

首先，为了科学合理的将预计受灾人员分配到所有的避难场所去，在这里被分配的最小元素非居民个人，而是聚集了一些居民的居民社区（空间单元），即对居民社区来分配相应的避难所，由于单个居民社区的空间范围可能较大，可以将其划分为多个同等面积大小的网格，再将单个社区的人口按网格面积占社区面积比例进行分配，并假设空间单元内部的居民是均匀分布的。总之，被分配的空间单元范围越小，这种假设越合理。

其次，假设所有的避难所位置都已确定，而且总容量能够容纳所有居民。为了确定每个避难所的服务范围，必须考虑每个避难所的容量、居民的空间分布以及居民到达指定避难所的行程距离，应急疏散过程中每个空间单元应被指定到尽可能近的避难所。另外，所有避难所服务范围空间连续性也是必须考虑的因素。这就意味着每个避难所的服务范围形成一个同质区域，用单个多边形即可包括，而且这些多边形覆盖整个居民区，在空间上具有排他性。所以，为了科学合理地对避难所进行分配，避难所分配模型遵循以下三个设计原则：所有居民到其分配的避难所之间的距离总和尽可能最小；必须保证每个避难所被分配的总人口不能超出其已知最大设计容量；尽可能地使每个避难所分配的空间单元具有空间连续性。单个空间单元（如一个居民区）在算法中作为一个需求点来处理，而每个避难所则代表居住区内的一个点。所以，根据设计原则，定义该模型的目标函数。

2.1 总行程距离最小化

式中，V为总行程距离，即所有分配空间单元中的所有预计受灾人员到其所分配的避难所之间的行程距离总和；M为避难所数量；N为空间单元数量；i和j分别为避难所和空间单元编号；rj为空间单元j内居民的数量；tij为从空间单元j到避难所i的行程距离，即空间单元j中心点到避难所i点之间的直线距离，用式来表示，式中tij也称欧氏距离，xi和yi表示避难所i配的坐标值，当避难所i分配给空间单元j，则xij＝1，否则xij＝0；对于每一个，以确保每个空间单元都能且只能分配到一个避难所。

2.2 各避难所分配总人数不超限

设cmaxi为避难所i的最大容量，容量控制定义如下

表示每个避难所计划容量为其最大设计容量与最大空间单元人数之差，这就保证当避难所未达到计划容量时，任何空间单元都可以直接分配给该避难所，实际情况下，cmaxi和rj通常都是已知的，而cplai可由式（3）来决定。

2.3 保持空间连续性

空间连续性即分配到同一避难所的空间单元是连续的，并位于同一个多边形空间范围内。对于每个避难所，由一个单链表记录分配到的空间单元。在该单链表中，元素（即分配到的空间单元序号）按照使用该避难所的优先级排列，且避难所的容量应尽可能地充分利用，并且通过链表，结合替换插值方法，可以尽可能地保证避难所分配的空间单元保持空间连续性。单链表定义如下：① 如果xij＝1，则空间单元j在避难所i的单链表里，且在单链表中的编号为indexij；②如果xijn＝1，xijm＝1，且tijn＜tijm，则indexijn＜indexijm，这表明空间单元距离避难所越近，越能够优先分配到避难所；③如果xijn＝1，xijm＝1，tijn＝tijm，且rjn≤rjm，则indexijn＜indexijm，这表明当距离相等时，空间单元人数越少，越能够优先分配到避难所。

3 模型核心算法

3.1 构建思想

为单个空间单元选择避难场所时，其原理是当满足下列插入条件中任何一条时，一个空间单元a可以分配到避难所S，即被插入避难所S的单链表中，式中jlast表示避难所S的单链表中的最后一个空间单元。三个条件分别为：①cactS≤cplaS；②cactS＞cplaS且tSjlast＞tSa；③cactS＞cplaS，tSjlast＝tSa，rjlast＞ra。条件①表示避难所S有剩余容量，且式（3）确保插入后cacti≤cmaxi，即实际人数小于最大容量。条件②和条件③表示空间单元a比已插入避难所S链表中的其他空间单元拥有更高的优先级。对每一个空间单元j，算法在所有避难所i中按照tij的升序寻找满足一个插入条件的避难所。如果第一最近避难所i1符合条件，则采用直接插入，即直接将j插入到i1的单链表中，且xi1j＝1；否则采用替换插入，调整空间单元和避难所之间的关联关系，减少总行程成本，并保持服务范围的空间连续性，替换插入的原理后面详细阐述。

3.2 替换插值原理

当某一空间单元最近的避难所容纳不了该单元内的总人口时，则利用空间替换插值机制为其指定到其他合理避难所。替换插值的过程如图1所示。

图1 替换差值原理图Fig.1 Schematic diagram of shift insertion

图中有3个避难所，S1、S2和S3，每个避难所都被分配了一些空间单元。图1（a）中黑色的空间单元a尚未分配到任何避难所，且tS1a＜tS2a＜tS3a。如果S1满足一个插入条件，则a被插入到S1的单链表中，即直接插入。否则，如果S1和S2都不满足任何插入条件，只有S3满足一个插入条件，则a被分配给S3如图1（b）。但是，把a分配给S3会妨碍S3的空间连续性，而且可能增加总行程成本。因此，就应该寻找一个称之为替换单元的空间单元，如图1（c），这个空间单元必须已经分配给S1或S2，且与S3的服务范围相邻，并将之插入到S3。这时，S1或S2中被替换单元占用的容量可以空出并分配给a，如图1（d）。在这里，直接插入或替换插入必须最大程度地节约行程成本。根据这一原则，用式（4）可以计算在寻找a的替换单元b时节约的行程成本，并使其最大化来实现总行程距离最小化

式中，SCt表示替换插入节约的总行程成本；tSfa＋tSkb是直接插入的行程成本；tSka＋tSfb是替换插入的行程成本。如果最大SCt为负数或零，则算法将按直接把a插入到Sf的单链表中。否则，a的替换单元b可行，则进行替换插入。整个替换插入算法总过程如图2所示。

图2 避难所分配算法流程图Fig.2 The flow chart of shelter assignment algorithm

4 试验及结果

利用Java程序实现上述算法，并以乌鲁木齐市中心的部分社区人口统计数据来进行试验分析，由于实际统计的街道社区单元空间范围较大，为更好地验证空间单元对避难所的分配效果，利用行程成本网格制定满足网络上和网络外的火车站服务范围的思想［10］。试验中也将所有的街道社区单元进行网格化，网格边长大小为0.5km，试验中总人口数为701 044，被分配到1 263个网格单元中，市区20个避难场所均有各自的容量限制。针对已有的划定服务范围，结合本文提出的算法，利用已有的数据对以下三种不同情况进行试验，不同情况下的避难所划定原则描述如下。

情况1：每个空间单元都分配到一个最近的避难所，而不考虑各避难所容量限制。

情况2：考虑各避难所容量限制，但都用直接插入来分配给未满员的避难所。

情况3：应用本文算法，用替换插入机制来调整已满员的较近避难所，并以式（4）中SCt最大化寻找替换单元，实现避难所合理分配。

通过比较三种情况的运行结果，可以评价替换插入机制和选择替换单元方法的效果。图3分别展示在基于网格模式下，用直线距离作为行程距离，三种情况所划定的服务范围分布图。

图3 三种不同算法划定避难所服务范围Fig.3 The shelter assignment chart of cell for three scenarios

5 分析与比较

根据试验的结果，考虑到避难所分配时的实际问题，从三个方面对不同算法结果进行对比分析，以反映各算法的优越性。

5.1 避难所容量是否超限

从图3（a）中的结果可以得到，情况1的分配结果中有S14、S15、S16三个避难所严重超出其本身容量限制，而避难所S3又存在分配人数不足。其中情况1也为目前大多数服务范围划定算法，如文献［8—9］提到的算法思想，其不考虑容量限制，只寻求最近目标进行分配。图3（b）、（c）分别为情况2和情况3的试验结果，这两种情况均无避难所超限情况。各情况算法结果比较如表1所示。

表1 各算法避难所是否超限比较Tab.1 Comparison of overstep capability of three scenarios

5.2 避难所服务范围是否空间连续

从图3（b）中的结果可以看出，情况2的分析结果中有一些避难所明显具有较多的零散空间单元，如避难所S8所分配的一些空间单元竟然位于S15的下方，这就是说S15下方的一些空间单元要跨越好几个较近的避难所而去S8避难所，这在实际应急疏散中肯定是不合理的。而情况1和情况3的各避难所分配的所有空间单元均具有很好的空间连续性，都在同一空间范围内。各算法分配结果比较如表2所示。

表2 各算法空间连续性比较Tab.2 Comparison of keep the spatial service continuity of three scenarios

5.3 总行程距离比较

这里的总距离就是每种情况下的所有避难所与其所分配的空间单元之间的欧式距离总和，即式（1）中的V。图4中对比说明了三种情况下的总行程距离。从图中可以看出，情况1总是产生最低的总行程距离，情况2最高，而情况3介于两者之间。

图4 不同方法分配避难所行程总和比较Fig.4 Comparison of total travel cost of three scenarios

6 结 论

通过试验及对结果综合性分析，基于替换插值机制的避难所分配算法与目前已有的其他同类算法相比具有优越性，其不仅能有效地避免各避难所容量超限与过度拥挤，并能够很好地保持各避难所服务范围空间连续，同时做到约束条件下的总行程距离最小化。试验结果初步验证了算法的有效性及可行性，并能在城市突发事件人员紧急疏散时起到良好的决策辅助作用。实际情况下，基于街区范围的分配可能更合理，但其空间范围的粒度往往太大，在使用大尺度的人口统计资料时，网格单元更为有效。此外，该算法目前旨在初探避难所宏观分配策略，由于暂时无法获取到乌鲁木齐市区详细的道路网络数据，故本次试验过程中的行程距离采用直线距离而非实际道路网络距离；同时，试验过程中目前也暂未考虑到灾害应急疏散的紧迫性和动态演化性，计划在后续研究中结合其他城市详细的道路网络数据及通达性进行深入探讨分析，同时对算法进行优化和改进，以体现应急疏散的动态演化效果。

［1］ ZHANG Zimin，LI Qi.The Current Situation，Issues and Trends of Evacuation Modeling in Emergency［J］.China Safety Science Journal，2008，18（10）：120－126.（张子民，李琦.应急撤离建模研究的现状、问题与发展趋势［J］.中国安全科学学报，2008，18（10）：120－126.）

［2］ MINCIARDI R，SACILE R，SICCARDI F，et al.Optimal Planning of a Weather Radar Network［J］.Journal of Atmospheric and Oceanic Technology，2003，20（9），1251－1263.

［3］ TOREGAS C，SWAIN R，REVELLE C，et al.The Location of Emergency Service Facilities［J］.Operations Research，1971，19（6），1363－1373.

［4］ PLANE D R，HENDRICK T E.Mathematical Programming and the Location of Fire Companies for the Denver Fire Department［J］.Operations Research，1977，25（4），563－578.

［5］ GLEASON J M.A Set Covering Approach to Bus Stop Location［J］.Omega，1975，3（5），605－608.

［6］ ZHOU Tianying，JIAN Furen.Study on Establishing the Supporting System for Location of the Urgent Refuge［J］.Research of Soil and Water Conservation，2001，18（1）：17－24.（周天颖，简甫任.紧急避灾场所区位决策支持系统建立之研究［J］.水土保持研究，2001，18（1）：17－24.）

［7］ XIE Shunping，FENG Xuezhi，LU Wei.Algorithm for Constructing Voronoi Area Diagram Based on Road Network Analysis［J］.Acta Geodaetica et Cartographica Sinica，2010，39（1）：88－94（谢顺平，冯学智，鲁伟.基于道路网络分析的Voronoi面域图构建算法［J］.测绘学报，2010，39（1）：88－94.）

［8］ HUANG B，LIU N.Bi－level Programming Approach to Optimizing a Logistic Distribution Network with Balancing Requirements［J］.Transportation Research Record：Journal of the Transportation Research Board，2004，18（9），188－197.

［9］ UPCHURCH C，KUBY M，ZOLDAK M，et al.Using GIS to Generate Mutually Exclusive Service Areas Linking Travel on and off a Network［J］.Journal of Transport Geography，2004，12（1），23－33.

［10］ BOYLE P J，DUNN C E.Redefinition of Enumeration District Cancroids：A Test of Their Accuracy Using Thiessen Polygons［J］.Environmental Planning A，1991，23（8）：1111－1119.

［11］ WANG Jian，HU Xiaowei，TONG Jingjing，et al.Route Planning of Regional Emergency Evacuation Based on Lane Modeling［J］.Journal of Traffic and Transportation Engineering，2010，10（2）：82－87.（王健，胡晓伟，佟晶晶，等.基于车道建模的区域应急疏散路径规划［J］.交通运输工程学报，2010，10（2）：82－87.）

［12］ TAN Manchun，TANG Songan，XU Jianmin.Dynamic Discrete Traffic Model of Freeway with Multiple Lanes［J］.China Journal of Highway and Transport，2002，15（2）：91－94.（谭满春，唐松安，徐建闽.多车道高速公路的动态离散交通流模型［J］.中国公路学报，2002，15（2）：91－94.）

［13］ CHEN Jun，ZHAO Renliang.Spatial Relations in GIS：A Survey on Its Key Issues and Research Progress［J］.Acta Geodaetica et Cartographica Sinica，1999，28（2）：97－102.（陈军，赵仁亮.GIS空间关系的基本问题与研究进展［J］.测绘学报，1999，28（2）：97－102.）

［14］ LI Gang，MA Donghui，SU Jingyu，et al.Multiplicatively Weighted Voronoi Diagrams for Responsibility Space Regionalization of Urban Earthquake Emergency Shelters［J］.Building Science，2006，22（3）：55－59.（李刚，马东辉，苏经宇，等.基于加权Voronoi图的城市地震应急避难场所责任区的划分［J］.建筑科学，2006，22（3）：55－59.）

［15］ SU Youpo，LIU Ruixing.Planning Principles and Outlines of Urban Earthquake Shelters［J］.Journal of Catastrophology，2004，19（1）：87－92.（苏幼坡，刘瑞兴.城市地震避难所的规划原则与要点［J］.灾害学，2004，19（l）：87－92.）

［16］ YANG Wenbin，HAN Shiwen，ZHANG Jingjun，et al.Planning Construction of Earthquake Emergency Shelters and Urban Disaster Reduction［J］.Journal of Natural Disasters，2004，13（1）：126－132.（杨文斌，韩世文，张敬军，等.地震应急避灾场所的规划建设与城市防灾［J］.自然灾害学报，2004，13（l）：126－132.）

［17］ YAO Qinglin.On Some Questions of Optimally Selecting Refuges for Large Earthquake［J］.Journal of Seismological Research，1997，19（3）：244－248.（姚清林.关于优选城市地震避灾场地的某些问题［J］.地震研究，1997，19（3）：244－248.）

［18］ AURENHAMMER F.Voronoi Diagrams——a Survey of a Fundamental Geometric Data Structure［J］.ACM Computing Survey，1991，23（3）：345－405.