基于服务可靠性的应急救援设施选址问题研究

吴 进，胡 刚，傅 惠

(广东工业大学机电工程学院)

基于服务可靠性的应急救援设施选址问题研究

吴 进，胡 刚，傅 惠

(广东工业大学机电工程学院)

设置应急救援设施的目的是为需求点提供快速、可靠的救援服务。针对城市事故灾害应急救援行动，提出救援设施的服务可靠性是由车辆从救援设施到救援需求点的时间决定的。在分析了应急救援设施选址问题的基础上，根据系统可靠性的理论，建立了基于服务可靠性的救援设施选址模型，并分别采用分枝定界法和混沌搜索算法进行模型求解。实验表明，这两种算法都能有效的求解该模型。

应急救援;设施选址;可靠性;混沌

1 引言

应急救援设施(以下简称:应急设施)的选址问题，是指如何运用科学的方法决定应急设施的地理位置，在实际中也可以是从若干个候选地点中，选取数个建设点，以达到预期的选址目标。随着我国城市规模的不断扩大以及城市化进程日益加快，城市事故灾害发生所造成的不良影响也相应增加。在此背景下，如何提高救援设施选址的科学性以及应急救援服务的可靠性，对于提升政府应急管理水平有着十分重大的现实意义。

针对设施的选址问题，国内外的专家和学者建立了经典的问题模型:P-中心问题、P-中值问题、覆盖问题、动态选址问题等，并将这些模型应用到应急设施，取得了良好的效果。已有的研究成果中，对于救援设施服务中的不确定性或可靠性研究较少。应急救援讲究时效性，救援资源的能否快速到达救援需求点，直接救援的成功与否，一定程度上反映了救援的可靠性。随着近些年对应急救援设施选址问题研究的逐步深入，文献从稳健可靠性角度研究了设施选址的问题，稳健性体现在最小化期望成本和最坏成本，目标是为了找到在任何随机参数的情况下，使整个供应链运行良好的解。文献从设施失效成本的角度研究了设施选址的可靠性问题。

可靠性这一概念最早来源于产品设计，产品可靠性反映的是产品在规定的条件下、在规定的时间内完成规定功能的能力。根据应急救援的特点，本文借鉴可靠性的基本理念，将救援设施的服务可靠性定义为:在发生城市事故灾害后，从救援设施点派出的救援资源(包括人员、物资等)，在一定的交通、气象环境条件下，在规定时间范围内到达事发地，并能够实时救援的可能性。影响救援设施的服务可靠性的因素主要有2个:(1)救援资源能否及时到达;(2)救援工作能否展开，前者由救援路径和车流速度决定，后者由是否指派准确的救援资源决定。本文在分析这两个问题的基础上，提出旨在提高救援设施服务可靠性的设施选址问题。

2 基于服务可靠性的应急救援设施选址问题分析

2.1 基于服务可靠性的应急救援设施选址的特征

应急救援是在城市事故灾害发生后，应急救援部门接警出发，从应急设施所在地赶往救援需求点的全过程。应急救援具有高度的时间紧迫性。因此，救援设施的选址直接影响到应急救援服务水平和效率。应急救援设施的选址有以下特征:

(1)时间效率重于经济效益

救援的可靠性，很大程度上依赖救援到达时间的长短。事故灾害发生后，如得不到及时救援，灾害规模及其带来的损失会迅速扩大，因此应急救援具有时间紧迫性。灾害带来的损失会随着应急救援时间的延长而扩大。提高应急救援的时间效率，也就间接提高了其经济效益。

(2)事前防范结合事后应急

建设应急设施的最终目的是为将来的救援需求点提供快速、可靠的救援服务。由于灾害的发生具有随机性，要充分考虑到所选的点能够覆盖潜在的救援需求点，靠近救援需求频发点。

(3)供需分级，有的放矢

由于一般小规模事故灾害发生频率相对重大事故要高，本文把各个需求区域的需求视为确定的值，大小由需求区域的价值(如人口、经济重要性等)和突发事件发生概率来评估，并适当的分类。此外，不同救援设施的救援能力也有差异性，一些重大灾害需要的救援资源只有少数的救援设施才能提供，因此救援设施也要分类。

在考虑救援供需双方的需求和供给的情况下，充分考虑和利用事故灾害的分布规律和特征，合理配置应急设施的等级和地理位置，形成高低合理搭配的多级救援格局，有助于最大化利用有限的救援资源，提高应急救援效率。

2.2 选址目标和影响因素

(1)救援设施选址的目标。

而已有的研究成果中，决策目标往往是以下4大类:成本最小化、需求导向、利益最大化和环境因素，而这些决策目标并不能很好的体现救援设施的服务可靠性。救援设施选址的目标是，选择的救援点有利于提供快速可靠的救援服务，选址点的服务可靠性的体现在是:需求的救援资源能否快速到达或在规定的时间内到达。

而在事故救援过程中，救援响应时间不仅和救援设施与救援需求点之间的方位、距离相关，还和救援当时交通状况、天气等相关，这就造成了即便是同一路段，每次的救援响应时间都不一样。因此将时间作为选址的决策目标最大的难点在于其本身的不确定性。根据相关文献可知，现有路段行程时间的概率分布常用的统计分布主要有以下四种:正态分布(Normal)、对数正态分布(Lognormal)、韦伯分布(Weibull)和伽玛分布(Gamma)。

根据救援车辆运行时间的分布规律，体现救援服务到达时间的可靠性要综合2个方面考虑:一是，从一般情况下救援车辆的到达现场的运行时间来考虑，要求救援设施到达需求点的平均运行时间最小;二是，从救援车辆运行时间的不确定性考虑，要求救援车辆到达需求点的平均运行时间的方差最小。

(2)救援设施选址的影响因素

影响救援设施选址问题可分为:成本因素和非成本因。成本因素主要体现在:建设成本、运营成本、救援点数量、救援时间限制等，这些因素都会对救援设施的经济投入和经济效益有直接的影响。非成本因素包含了:路网特征、需求点的布局、事件等级和自然环境条件等。由于设置救援点要求尽可能大的覆盖灾害、事故黑点，甚至多重覆盖，救援资源的运输也依靠路网等等，因此，这些因素也会对救援设施的选址、规划有着直接的影响。

3 基于服务可靠性的应急救援设施选址问题建模

从提高应急救援服务可靠性的角度出发，结合应急救援设施选址问题的以上特点，这里假设:(1)候选救援设施、救援需求点的位置和数量确定;(2)从候选设施中，选择的救援设施的数量确定;(3)从各个救援点按时赶到需求点的平均时间和平均运行时间方差已知;4)救援设施建设和需求点的需求可分为若干等级，高等级的救援设施可以为同级或低等级的需求点提供救援服务;5)每个需求点的权重由该地区人口和人口灾害发生率决定。

考虑到需求区域集合I，和候选设施集合J，决策变量wi为需求点i的权重;0-1变量yj为:如果设施j被设置，yj=1，否则 yj=0，j=1，2，……，J;0-1 变量 zij为:设施 j服务需求点 i，zij=1，否则 zij=0，i=1，2，……，I，j=1，2，……，J。cjk为在候选j设施点建设k等级设施的成本，C表示全部的选址成本上限;0-1变量ljk表示，设施j属于k级救援设施，变量ri表示，需求点i是ri级救援需求点，其至少需要ri级的救援设施提供救援;救援点j到需求点i的平均运行时间为xij，救援点j到需求点 i的平均运行时间的方差为 Δij，u1，u2为目标函数中时间目标和方差目标的权重。

据此，本文建立基于救援设施服务可靠性的设施选址模型如下:

约束条件1:使得选址的数量最多为n个;约束条件2:每个救援设施点只能建设一种等级的救援等级的设施;约束条件3:救援设施的总建设成本上限为C;约束条件4:每个需求点都会被指派相应的救援设施;约束条件5:约定只有被选中的救援设施，才有被指派任务的权利，如果某个设施j没有被选中，则其不会被指派给任何一个需求点。每个需求点由于其人口数量、重要程度等不同，造成其需求权重也有所不同。为简便起见，本文中每个救援需求点的权重由该区域的人口决定。

该模型的求解实际上是一个0-1整数规划问题，求解这类问题一般采用分枝定界法、完全枚举法、动态规划法和遗传算法等。前3种是精确算法，研究的比较多，针对问题模型不是很大的算例，能够很准确快速的得到结果。当算例的规模比较大(需求点和候选设施数目增多)时，这些算法的计算量非常大，求解过程复杂，甚至无法求解。对于问题规模较大的情况，宜采用高效率的算法。例如，混沌搜索算法、遗传算法优化算法。

4 模型的应用算例和求解

假定某城市有10个社区，当地政府计划在这10个社区中选择4个分别建设一个救援设施。这里假设每个社区的需求点都在该社区的中心。各个设施候选点能够在规定的时间内到达各需求点的平均运行时间和平均运行时间方差如下表所示。表格最后一列为每个社区的人口数，这里将其转化为作为各社区的应急服务需求点的权重。救援设施的建设分为2级，其中需求点1和需求点8为2级资源需求点。总体的选址建设成本上限:200万元。

表1 候选设施准时到达需求区域的平均运行时间及其方差及各区域的人口数量

表2 候选设施点建设相应等级救援设施的建设成本

针对这个算例，使用线性整数规划的程序得到该问题的解为 42，选址结果为:y1=1，y5=1，y9=1，y10=1。其中 y1，y10为1级救援点，y5，y9为2级救援点。

除了传统的求解0-1的精确算法，混沌搜索算法也可以用来解决这类0-1规划问题。混沌搜索算法，是模仿粒子的混沌运动而设计的一种搜索算法。该算法的搜索过程具有伪随机性、遍历性等特点，能在一定的范围内按其自身的规律不重复地遍历所有状态。

混沌搜索的目的是，每次经过混沌迭代后，会产生不同的数据结果。由于Logistic映射的迭代公式为g:z(k+1)i=uzki(1-zki)，式中u为控制参数，当u=4时，Logistic映射为混沌映射，迭代将处于混沌状态。因此可以采用该公式作为混沌搜索算法的迭代公式。

基于混沌搜索原理，设计算法如下:

步骤1:给Zki赋初值(即k=0时)，本算例中初值个数为 4 个，记为:Z01、Z02、Z03、Z04，初值为介于 0 ～1 的实数，且不能为:0.25、0.5、0.75，初值互不相等，两两之和不能为 1;

步骤2:将(0，1)区间划成10等份，即10个相等的小区间(0，0.1)，［0.1，0.2) ，［0.2，0.3)……［0.9，1)，并将这些区间按顺序编好组1、2、……、10;

步骤3:判断生成的混沌变量值 Zk1、Zk2、Zk3、Zk4所在的区间范围。由此，得到一组选址的结果;

步骤4:判断选址结果是否满足相应的约束条件，若满足则计算相应的目标函数，否则转入下一步;

步骤5:判断是否满足搜索结束条件，如果不满足，则按混沌映射公式zk+1=uzk(1-zk)进行迭代，并跳往步骤3。如果满足，则结束搜索，输出最优的结果。

虽然，本文给的算例的运算规模不是很大，但还是可以体现出混沌搜索算法求解这类问题的优越性。混沌搜索算法计算该算例的结果见表3。

表3 基于混沌搜索的计算结果

表2展示了4组数据混沌搜索算法的计算结果，表中第2组数据计算的结果收敛速度最快，只需要23次迭代就可以得到最优解，第4组最慢。这反映了混沌搜索算法求解问题存在的局限性，即初值选择对搜索效率的影响很大。另外，该算法在有限的迭代次数内无法保证能得到实际算例的最优解。对此，可从2个方面加以解决:

(1)多组数据并行搜索。如果对表2中4组数据进行并行搜索，那么只需搜索23次即可得到最优解。并行搜索的优势在于，能够将初值选择不当的可能性降至很低。并行的搜索的个数控制在5～10个为宜，并行搜索的个数少了，达不到将初值选择不当的概率降至很低的目的;并行搜索的个数多了，会增加每次混沌迭代后求解最优值的计算量。

(2)在第N次迭代后，目标函数得到一个新的最优值，之后继续迭代M次(这里M、N的值，可以根据不同的计算实例来确定)，如果目标函数始终得不到优化，则停止迭代，把第N次的最优值作为最终的结果。

5 结论

救援服务的可靠性是救援设施的选址需要考虑的重要因素，本文建立了基于服务可靠性的救援设施选址模型。并通过传统的分支定界法法和混沌搜索算法分别求解该模型，分析了对于不同问题规模情形下，两种不同优化算法的适应性和特点。

由于本文的救援服务可靠性是基于救援平均运行时间和运行时间方差的，研究下一步可以将文中提到的多个影响救援可达性的因素，加入OD对间救援的交通可靠度计算中，得到的结果和实际会更加吻合。另外，本文假设了所有救援活动之间相互独立，而在实际的救援时间中，有时救援活动(针对发生时间、发生区域重合的城市灾害的救援活动)会相互影响，这也是研究救援设施服务可靠性的一部分。

［1］S.L.Hakimi.Optimum locations of switch centers and the absolute centers and medians of a graph［J］.Operations Research，1964，12(3):450-459.

［2］王菲，徐渝，李毅学.离散设施选址问题研究综述［J］.运筹与管理，2006，15(5):64-69.

［3］Susan Hesse Owen，Mark S.Daskin.Strategic facility location:A review［J］.European Journal of Operational Research ，1998，111(3):423-447.

［4］陈志宗，尤建新.重大突发事件应急救援设施选址的多目标决策模型［J］.管理科学，2006，19(4):10-14.

［5］朱长虹.具有稳健可靠性的供应链选址模型与算法研究［D］.南京:南京理工大学，2007:1-117

［6］Lawrence V.Snyder，Mark S.Daskin.Reliability models for facility:The expected failure cost case［J］.TRANSPORTATION SCIENCE.2005.39(3):400-416.

［7］李保维.系统可靠性设计与分析［M］.西安:西北工业大学出版社，2008.

［8］熊志华，邵春福.随机需求条件下道路网行程质量评估—行程时间可靠性［J］.交通运输工程与信息学报，2006，4(2):40-44.

［9］祁荣宾，冯汝鹏.求解一类0-1整数规划问题的新方法——混沌搜索算法［J］.控制与决策，2003，18(6):712-715.

［10］刘树安，郑秉霖，王梦光.基于GAs求解整数规划问题的算法设计［J］.东北大学学报(自然科学版)，1998，19(2):198-200.

［11］何大阔，王福利.一种提高遗传算法全局收敛性的方法［J］.东北大学学报(自然科学版)，2003.24(6):511-514.

U492

C

1008-3383(2013)04-0126-03

2013-02-25

吴进(1987-)，男，江西九江人，硕士研究生，研究方向:智能交通。

国家自然科学基金项目(60974143)，广东省科技计划项目(2009B010800052)