基于二型模糊集理论的应急设施选址方法

杨 广 映，门 金 坤，蒋 鹏*，郑 松，孔 亚 广，沈 刚，赵 烨，苏 楠

( 1.台州学院 电子与信息工程学院(大数据学院)， 浙江 台州 318000；2.杭州电子科技大学 自动化学院， 浙江 杭州 310000；3.浙江中天氟硅材料有限公司， 浙江 衢州 324000；4.衢州市特种设备检验中心， 浙江 衢州 324000；5.杭州市西湖区保障性住房管理服务中心， 浙江 杭州 310000 )

0 引 言

应急设施作为突发事件应急管理系统的基础组成部分，其布局直接影响事故的预防、准备、响应和善后工作.合理的应急设施选址决策一方面可以提高应急管理的效率和有效性，另一方面可以降低建立这些设施和开展应急救援行动的固定成本和可变成本.研究应急设施选址方法，对于提升突发事件应急管理水平意义重大.

应急设施选址问题(emergency facility location problem，EFLP)本质上是一种设施选址问题(facility location problem，FLP)，也称为选址分析[1].最初的FLP被称为韦伯问题(Weber problem，WP)，其目的是为了确定单个仓库的位置，从而最小化仓库与客户之间的总距离.此后，对选址问题的研究产生了许多经典框架来解决各种FLP[2-7].优化目标是区分选址模型的重要依据.根据模型的优化目标，EFLP的相关研究可分为3类[8]：p-中值问题(p-median problem)[9]、p-中心问题(p-center problem)[10]和覆盖问题(covering problem，CP)[11].

Hakimi[12]首次提出了p-中值问题的概念，定义为：规划p个设施的位置，以最小化受灾点和设施点之间的平均(总)距离.Carbone[13]针对医疗中心的选址问题，提出了一个确定性p-中值模型，目的是使多个用户到医疗中心的距离最小化.由于每个需求节点上的用户数量是不确定的，进一步将确定性p-中值模型扩展到机会约束模型，该模型寻求最大化阈值，同时确保总行程距离低于阈值的概率小于指定置信度水平α.Abareshi等[14]研究了一个双层模型来探索最小信息方法下的p-中值问题，在满足客户需求的同时，确定最可能的分配方案，采用了拉格朗日对偶方法将带负载约束的双层p-中值模型简化为单层问题，并引入了混合整数线性规划方法来提升问题求解效率.Herrán等[15]提出了求解汉密尔顿p-中值问题的VNS元启发式方法.Herda[16]为近似求解带负载约束的p-中值问题，提出了一种基于高性能计算集群的遗传算法.与专注于优化应急系统整体性能的p-中值问题相反，p-中心问题试图最小化每个需求点与其最近设施之间的最大距离，因此p-中心问题也被称为Minimax模型.p-中心问题认为需求点总是由其最近的设施提供服务，从而实现了对需求点的全覆盖，因此p-中心问题特别关注最差的服务情况.在过去的几十年里，p-中心问题及其扩展[8，17-18]已经被广泛应用于应急中心、医院、消防站和其他公共设施的选址规划中.Du等[19]针对EFLP构建了两阶段鲁棒优化框架下的可靠性p-中心模型，关注每个客户的可靠性，提出了本构方程的求解方法，包括双切削平面法和约束生成法.Mladenovi等[20]在无三角不等式的情况下提出了基于变邻域搜索和两个禁忌搜索启发式的p-中心问题求解方法，展示了如何更有效地利用邻域结构求解p-中心问题.针对大规模自然灾害事故，Xi等[4]提出了一个改进的p-中值问题，该问题在访问需求点所需最长时间的约束下，使总距离和应急设施的数量都最小化.CP是EFLP最常见的形式之一[21]，其目标是为需求点提供覆盖，此类问题易于理解，模型构造简单，因此在现实生活的适用性很强，如派出所、图书馆、医院和废物处理站等设施的选址问题都可以表述为CP.一般来说，只有在设施可在预定义的距离限制内服务某需求点时，才认为设施可为该需求点提供有效覆盖，此预定义的距离限制被称为覆盖距离或覆盖半径.Li等[22]提出了设施服务能力与服务距离之间的衰减关系函数.针对灾难性连锁化工事故，Men等[23]提出了一种基于多米诺效应风险的应急设施选址多目标优化方法.Zhang等[24]针对不确定性条件下的EFLP，构建了基于不确定理论的LSCP模型，利用逆不确定性分布，将不确定环境下的LSCP模型转化为等价的确定性位置模型进行求解.

鉴于EFLP的地理性质，大多数研究将时间和距离视为应急设施选址决策的关键因素.目标函数通常侧重于满足预定义的受灾地点(需求点).传统的空间优化模型[5，25-29]通常并不会对这些预定义的需求点加以区分.然而，不同需求点对应急资源的需求程度往往与区域内人口密度密切相关[30].选址准则不仅应考虑应急设施的空间特征，还应考虑选址区域内的人口分布.此外，由于人口的流动性，实际应用中通常难以获得精确的人口密度数据.在确定性环境下所得的应急设施选址决策可能难以满足突发事件风险管理的实际需求.

综上，本文分析选址决策的人口因素和地理因素，建立一个选址集最大覆盖模型，以区域人口密度量化每个需求点对应急资源的需求程度，期望在资源有限的情况下寻求给定数量应急设施的最大覆盖程度，并且尽可能侧重于满足人口密度较高区域的应急需求.由于人口的流动性，将人口密度定义为一个梯形区间二型模糊变量.根据梯形区间二型模糊变量的上/下边界隶属度函数，结合置信度理论与机会约束规划方法将原模糊模型转化为其等价确定性模型.为了处理模型中大规模复杂高维的空间地理数据，采用一种基于网格空间表示法的矩阵编码策略与遗传算法耦合进行模型求解，以避免维数灾难，提升EFLP的求解效率，并通过仿真对比试验验证方法的有效性.

1 模糊集理论

模糊集理论建立了自然语言与定量描述之间的桥梁和纽带，是分析定性和定量之间相互转化的认知模型，模糊集理论作为非概率性不确定性信息描述工具被广泛应用于解决不确定性决策的相关问题[31].

1.1 模糊集定义

实际生活中的许多事件本身是无法采用精确定义来描述的.为了弥补确定性理论在描述事件复杂性和可能性上的不足，Zadeh[32]提出了模糊集(fuzzy set，FS)的概念.论域U上的FS可由其隶属度函数定义，式(1)～(3)给出了A的3种常见表达形式[33]：

A={(x，μA(x))：∀x∈U}

(1)

(2)

A={μA(x)：∀x∈U}

(3)

1.2 模糊变量定义

假设Θ为一个非空集合，θ是Θ的幂集，Pos是可能性度量，R为一个表示模糊事件的实数集，(Θ，θ，Pos)为概率空间，则模糊变量(fuzzy variable，FV)可被定义为一个由概率空间到实数集的函数[34]：ξ：(Θ，θ，Pos)→R.如图1(a)所示，ξ为一个由(a，b，c，d，w)，a

(4)

(a) 梯形模糊隶属度函数

(b) 三角模糊隶属度函数

1.3 置信度理论

对于任意模糊事件{ξ∈B}，B⊂R，其可能性度量Pos{ξ∈B}的计算方法如式(5)所示，其必要性度量Nec{ξ∈B}的计算方法如式(6)所示[35].

(5)

(6)

对于任意模糊事件{ξ∈B}，B⊂R，其置信度度量Cr{ξ∈B}的计算方法如下：

(7)

与可能性度量Pos{ξ∈B}和必要性度量Nec{ξ∈B}相比，置信度度量Cr{ξ∈B}具有自偶性.若Cr{ξ∈B}=1，则表示模糊事件{ξ∈B}，B⊂R必定会发生；若Cr{ξ∈B}=0，则表示模糊事件{ξ∈B}，B⊂R必定不会发生.

结合上述置信度度量方法与FV的定义，可将式(7)推广至模糊变量的置信度度量方法.令ξ为一个由(a，b，c，d，w)，a

(8)

(9)

针对梯形模糊变量ξ=(a，b，c，d，w)，a

Cr{ξ≤x}≥α⟹

(10)

Cr{ξ>x}≥α⟹

(11)

1.4 二型模糊集理论

∀φ∈Jx⊂[0，1]}

(12)

(13)

(14)

(15)

(16)

2 模型构建

2.1 区域网格化

为了减少计算负载和协调选址模型，采用相同大小的网格将整个区域划分为如图2所示笛卡儿坐标系(n×m)中的二维空间.示例点1和2可以分别用坐标(2，5)和(5，9)表示.如果每个网格的长度为100 m，则图2中任意两个网格之间的距离可以用它们的坐标表示如下：

(17)

其中dij为网格i到网格j之间的距离；x*和y*为网格*的坐标.

图2 网格化的选址区域

2.2 选址集最大覆盖模型

基于上述网格化的选址区域，综合分析选址决策的人口因素和地理因素，建立一个选址集最大覆盖模型.模型假设如下：

(1)选址区域内的所有网格都视为选址模型中的需求点.

(2)不可放置应急设施的网格是已知的.

(3)应急设施的覆盖半径无限制，但其应急能力会随着应急距离的增加而降低[22].令i为设施放置点，j为需求点，dij为设施点i到需求点j的距离，k为衰减系数，则设施应急能力和应急距离之间的衰减关系可表示为e-kdij.

(4)每个被选中的应急设施放置点会被分配同样数量和类型的应急设施.

(5)可建立的应急设施放置点个数为p.

模型的决策变量如下：

∀i≤n×m

(18)

模型的优化目标如下：

(19)

优化目标最大化应急设施需求加权覆盖程度，以区域人口密度量化每个需求点对应急资源的需求，在资源有限的情况下尽可能侧重于满足人口密度较高区域的应急需求，ρj为网格j处的人口密度.由于人口的流动性，将人口密度定义为一个梯形区间二型模糊变量，任意网格处的人口密度ρi由式(20)定义.

(20)

图3 ρi的隶属度函数示例

根据ρi的边界隶属度函数，采用置信度理论和机会约束规划方法处理带模糊参数的目标函数Z.

对于上层隶属度函数，其机会约束规划如下：

(21)

对于下层隶属度函数，其机会约束规划如下：

(22)

式(21)、(22)中，αu和αl为预定义的置信度水平，根据式(10)、(11)，模型等价约束如下：

(23)

综上所述，原带模糊参数的目标函数Z被转化为其等价确定性目标函数(24)、(25).

(24)

(25)

最终，采用线性加权技术将目标函数Z重定义为

maxZr=(Zu+Zl)/2

(26)

选址集最大覆盖模型的等价确定性模型如下：

(27)

3 模型求解

选址问题是一类典型的NP-hard问题，分支定界法、割平面法以及PILP等精确算法往往难以在可接受时间范围内得到最优解.进化算法是一类基于种群智能的全局优化启发式算法，此类算法鲁棒性较高，适用性强，不要求目标函数可微或可导，在机器智能领域得到了广泛的关注.

以进化算法为基础的遗传算法(genetic algorithm，GA)已经被广泛应用于求解NP-hard问题.GA自初始种群Pset开始，然后对当前种群Pset执行进化操作，进化操作一般按照选择、交叉以及变异3种算子顺序执行[37].选择算子从Pset中选择适应度高的个体放入交配集；交叉算子每次从交配集随机选取个体执行交叉操作产生新个体；在交叉操作的基础上，引入变异操作可以有效避免算法早熟.重复上述进化操作直至产生预定规模的子代种群Rset.为避免丢失优质个体，以子代种群Rset和当前种群Pset的并集为联合解集Uset.最终，判断算法是否满足停止迭代条件，若满足，则输出当前最优解；若不满足，则根据精英策略更新下一代种群，并重复上述迭代过程.GA的迭代过程是最优解不断逼近真实最优解的过程.

当采用GA解决特定问题时，从问题空间到编码空间的映射称为编码.进化算法中，常见的编码策略为二进制字符串、实数、序列编码、随机序列和树编码[8，38-39].然而，由于应急设施选址问题涉及的空间数据量和解空间庞大，上述编码策略往往难以保证产生可行的子代种群，这对算法收敛性造成了极大的影响.为了提升算法性能，采用了一种基于网格空间表示法的矩阵编码策略.如图4所示，采用矩阵表示笛卡儿坐标系中的二维空间，结合二进制编码的特点，将应急设施放置点对应的矩阵元素设置为1.矩阵编码策略在保持了二进制编码便于操作特点的同时，减少了问题维度的规模.

图4 基于网格空间表示法的矩阵编码策略示例

4 仿真算例

以30×30网格化选址区域为例进行方法验证.可建立的应急设施放置点p=10.假设每个网格都可以放置应急设施，即不可放置应急设施的网格集B=∅.通过一定次数的测试运行，将最大迭代次数设为200，种群规模设为100，交叉概率设为0.8，变异概率设为0.08.

4.1 算法性能分析

为了测试编码策略的性能，将采用矩阵编码得到的最优解与采用整数向量编码[8]以及采用二进制编码[1]得到的最优解进行比较.

所有算法都运行在一台配置为Intel (R) Core (TM) i7-7700 CPU @ 3.60 GHz，32.0 GB RAM的计算机上，算例实现的软件环境均为Matlab 2016a.由于进化算法的随机性，在评估算法性能时，需要执行多次独立运行.在不失一般性的前提下，进行10次独立运行，从最优解的平均质量与最优质量两个方面比较算法性能.

3种编码策略最优收敛曲线如图5所示，GA-A为采用整数向量编码策略所得最优收敛曲线，GA-B为采用二进制编码策略所得最优收敛曲线，GA-M为采用矩阵编码策略所得最优收敛曲线.仿真结果表明，采用矩阵编码与遗传算法耦合进行模型求解时的收敛性最好，采用二进制编码和整数向量编码与遗传算法耦合进行模型求解时陷入了局部最优解.表1比较3种编码策略10次独立运行后所得最优解目标函数值以及算法运行时间.矩阵编码所得最优解的平均质量与最优质量是最好的，整数向量编码次之，二进制编码最差.由于高维复杂的空间地理数据以及庞大的解空间，二进制编码会严重影响算法性能[40].通过进一步分析可以发现，二进制编码与整数向量编码的平均运行时间要远比矩阵编码的运行时间长.这表明所提出的矩阵编码策略在保持了二进制编码便于操作特点的同时，减少了问题维度的规模，可有效避免维数灾难.

图5 3种编码策略最优收敛曲线(p=10)

表1 算法性能比较

4.2 敏感性分析

等价确定性模型中，目标函数会随着预定义的置信度水平αu和αl而改变，同一个解在不同置信度水平α下的目标函数值是不同的.因此，以置信度水平为敏感参数进行敏感性分析.通过敏感性分析，验证所得最优选址决策的可靠性.

(28)

(29)

图6 不同置信度水平下最优决策目标函数值

在实际应用中，为了应急设施选址决策可靠性，预定义的置信度水平应该设置为0.5～1.0，即αu，αl∈[0.5，1.0].

5 结 语

本文研究了突发事件应急管理中的应急设施选址问题.在传统选址集最大覆盖模型的基础上，充分考虑了选址决策的人口因素和地理因素，以区域人口密度量化应急资源需求程度.在模型求解时，设计了一种新颖的基于网格空间表示法的矩阵编码策略.与其他常见编码策略相比，所提出的矩阵编码策略可以成功地与遗传算法耦合，实现在全局范围内快速地搜索最优解，有效避免维数灾难，显著提升了算法性能.最后，以置信度水平为敏感参数进行了敏感性分析.通过敏感性分析，验证了所得最优选址决策的可靠性.所提算法不限于求解不确定条件下的EFLP，对于许多具有不确定属性的决策问题也有一定的适用性.