考虑多级覆盖衰减的双目标应急设施选址模型及算法

摘要：针对在重大突发事件下应急物资的需求量巨大以及对资源持续需求的特点，考虑设施选址的公平性、效率性及成本等因素，基于备用覆盖和覆盖衰减思想，提出一类应急设施双目标多级覆盖衰减选址模型，并基于MATLAB7.0设计遗传算法对模型进行求解；以一个算例验证了模型和算法的有效性，并比较了传统0-1覆盖与覆盖衰减的优劣，分析了覆盖衰减函数敏感系数、不同覆盖半径对模型目标的影响；结果表明：其模型为决策者进行应急设施选址决策提供了一个有效的途径；最后得出结论并给出了进一步拓展研究的方向。

关键词：应急设施选址；双目标；多级覆盖衰减；遗传算法

中图分类号：F252 文献标识码：A 文章编号：1001-8409（2012）12-0127-05

Bi-objective Emergency Facility Location Model and Algorithm Considering Multi-level Gradual Coverage

XIAO Jun-hua1，2， HOU Yun-xian1

（1.School of Economics and Management，China Agricultural University，Beijing 100083；

2.Beijing Vocational College Labor and Social Security，Beijing 100029）

Abstract：In allusion to the characteristics of tremendous and continued demands for emergency supplies during large-scale emergency occurring， considering the factors of fairness， efficiency and cost for facility location ， a Bi-objective multi-level gradual coverage location model was proposed based on the idea of backup coverage and gradual coverage in this paper. A genetic algorithm procedure based on MATLAB 7.0 was developed to solve the model. A computational experiment was adopted to prove the effectiveness of genetic algorithm， and performance of the traditional binary coverage and gradual coverage was compared， influence of sensitive coefficient of gradual coverage and different covering radius to the objective of model were analyzed. Result shows that the model can provide an effective approach for the decision makers to make the emergency facility location decision. Finally， conclusions and suggestions for the future research were given.

Key words：emergency facility location；bi-objective；multi-level gradual coverage；genetic algorithm

引言

设施选址是选址问题的一个重要研究领域，主要采用运筹学、拓扑学等研究方法，涉及数学建模与算法设计，强调定量，或努力做到定量与定性分析的有机结合[1，2]。传统的设施选址问题可分为：P-中值问题、P-中心问题和覆盖问题[3～5]，其中，覆盖问题是设施选址问题中应用最广的模型，尤其适用于应急设施的选址。Schilling，D.A等[6]对1991年以前的覆盖问题进行了综述，Farahani，R.Z等[7]对1992～2011年的覆盖问题进行了综述。

传统覆盖问题有一个基本假设，即若需求点与设施点之间的距离小于某一距离（时间）则被认为是完全覆盖，反之则认为不会被覆盖，这种假设可以称之为0-1覆盖。学者们认识到这一假设在很多情况下是不合理的，并提出了一些改进思路：Berman，O.等[8]研究了“覆盖逐渐”的最大覆盖选址问题，马云峰[9]提出了基于时间满意度的最大覆盖选址问题，陆相林[10]提出了覆盖半径内需求满意存在差异的最大覆盖选址问题。

覆盖问题的另一个基本假设是需求点只能由一个设施点提供服务。这种假设没有考虑到设施拥塞或失效的情况。为此，Daskin，M.S.等[11]提出了多重覆盖的集覆盖模型；Hogan，K.等[12]提出考虑备用覆盖的最大覆盖模型；Narasimhan，S.等[13]提出了一个考虑容量限制应急设施多水平覆盖选址模型，并用拉格朗日松弛算法进行了求解。

传统的设施选址模型多为单目标决策，而重大突发事件下，应急设施选址应综合考虑多方面的因素，需要使用多目标方法解决选址决策问题。文献[14，15]等考虑应急设施选址的公平性、效率性及成本等因素建立了多目标设施选址模型，并提出了求解方法。

基于以上分析，本文针对在重大突发事件下，需求点对应急物资的需求量巨大以及对资源的持续需求特点，基于多级覆盖和覆盖衰减思想，考虑覆盖需求量最大和选址总成本最小等因素，提出一类应急设施双目标多级覆盖衰减选址模型（Bi-objective Multi-Level Gradual Covering Location Problem，BOMLGCLP），并利用遗传算法对模型进行求解，比较了传统0-1覆盖与多级覆盖选址模型的优劣，并对几种覆盖衰减函数应用效果进行了对比分析；最后得出结论和研究展望。

1 BOMLGCLP模型建立

1.1 问题描述

选址问题涉及两类站点，一类为需求站点，统称为需求点；另一类为服务站点，即应急物资储备库，统称为设施点。设施点为需求点提供服务，以距离表示设施点与需求点之间的联系紧密程度。ML-GMCLP模型假设如下：

假设1：设施点和需求点均为离散的；

假设2：任意设施点和需求点的距离为欧氏距离；

假设3：设施点可以建立在需求点上，也可以独立于需求点之外，单独建立；

假设4：设施点可以为多个需求点提供服务，且设施点服务能力无限制；

假设5：待建设施点的数量有限，为p个；

假设6：需求点有k级需求覆盖水平，且在其每一个需求覆盖水平上最多由一个设施点为其提供服务如图1所示；

假设7：设施点的覆盖对到需求点距离的增加是逐渐衰减的。

1.2 覆盖衰减函数

传统最大覆盖选址模型中的覆盖是0-1型的。但是，在现实生活中，比如地震救援中，理论上区域内所有的应急设施都可以为受灾点提供救援服务，当设施点与受灾点距离小于或等于距离D时，则覆盖满意度为1，否则，覆盖满意度随距离的增加而衰减，借鉴王文峰[16]提出的方法构建覆盖衰减函数：

fkidij=1dij≤Dkα1-dij-Dkmaxdij-Dkβdij>Dk（1）

式（1）中，α和β为设施点对需求点提供服务的敏感系数，其中α∈[0，1]，β∈（0，+∞）；

max（dij）为任意设施点到需求点的最大距离；Dk为第k级覆盖水平的最大距离。

1.3 模型构建

设I表示应急需求点的集合，i∈I；J表示备选设施点的集合，j∈J；从集合J中选择p个设施为每一个需求点提供K级覆盖。定义如下决策变量：

xkij=1，如果设施点j为需求点i提供k级覆盖；0，否则；

yj=1，如果设施点j被选中； 0，否则； 

模型参数定义：

p为选择的设施点的数量；K为需求点的需求覆盖水平；Mi为需求点i的需求量；wk为第k级覆盖水平的权重，且权重之和为1；Dk为第k级覆盖水平的最大距离；dij为需求点i到设施点j的距离；Cj为设施点j的建设成本；υ为物资单位距离的运输成本。

双目标多级覆盖选址模型（BOMLGCLP）：

问题P：

Z1=max∑i∈I∑j∈J∑k∈KwkfkidijMixkij（2）

Z2=min∑j∈Jcjyj+υ∑i∈I∑j∈J∑k∈KwkfkidijMidijxkij（3）

Subject to：

∑j∈Jyj=p（4）

∑j∈Jxkij=1i∈I，k∈K（5）

xkij≤yji∈I，j∈J（6）

xkij，yj∈0，1 i∈I，j∈J，k∈K（7）

目标函数（2）是使需求点在各需求覆盖水平上被覆盖的总需求量最大；式（3）使总的成本最小化；式（4）规定需要建立的设施点的数量；式（5）表示需求点在各需求覆盖水平上最多只能由1个设施点提供服务；式（6）则表示只有当设施点被选定时，才能为需求点提供服务；式（7）表示yj和xkij均为二元整数决策变量。

2 模型求解分析及算法设计

2.1 模型求解分析

多目标规划可同时处理两个或两个以上具有冲突关系的目标，因此多目标规划所求得的解是一个Pareto最优向量[17]。常见的多目标规划的解法主要有：约束法、分层序列法、功效系数法、评价函数法、乘除法、层次分析法等[18]。分层序列法的思想是把目标按其重要性给出一个序列，分为最重要目标、次重要目标等。设给出的重要性序列为f1（x），f2（x），…，fm（x）。首先对第一个目标求最优，并找出所有最优解的集合记为R0，然后在R0内求第二个目标的最优解，记为R1，如此一直求出第m个目标的最优解，即得到多目标规划的满意解[19]。本文应用分层序列法对模型进行如下分解：

问题P1：

Z1=max∑i∈I∑j∈J∑k∈Kakifkjdijxkij（8）

Subject to：（4）-（7）

问题P2：

Z3=min∑j∈Jcjyj+∑i∈I∑j∈R∑k∈Kakicijdijxkij（9）

Subject to：（4）-（7）

其中：R为P1中所有Pareto解的集合。

2.2 遗传算法设计

最大覆盖选址模型已经被证明为NP-Hard问题[20]，而本文所建多级覆盖衰减选址模型是最大覆盖模型的扩展，所以也是NP-Hard问题。由于该类问题计算复杂度较大，难以利用精确算法进行求解，只能借助于启发式或近似算法来求得其近似解。本文运用遗传算法对模型进行求解。作为一种有效的全局搜索方法，遗传算法的应用领域已渗透到多个学科[21]。越来越多的研究者将遗传算法应用在设施选址领域，研究文献包括求解集覆盖问题、p-中值问题和最大覆盖问题等[22]。遗传算法主要技术如下：

（1）编码方案

对所有的备选设施点按1至n进行赋值，每个代码表示一个基因。每个染色体代表模型的一个可行解，染色体的每一个基因代表选择的备选设施点，设定染色体长度为p。

（2）初始种群的产生

为了确保每个设施点都有机会被选择，初始种群中的每个染色体通过随机的方法生成。借鉴文献[22]的方法，将种群的规模定义为N=max{100，1.2[J/P]}，其中“[]”表示向下取整数。

（3）适应值赋值

种群中每个染色体的适应度评估由目标函数式（8）和式（9）来计算。适应度计算过程如下：

步骤1：选择第一个需求点，计算其到染色体中每一个基因的距离，对距离进行升序排序，选择前k个距离dk；

步骤2：判断距离dk与各覆盖等级最大距离Dk的关系，并由覆盖衰减函数判断每一个基因所代表的设施点为需求点提供的最大物资量，求出需求点得到的总物资量，并计算物资运输的最小成本；

步骤3：重复步骤1～2，遍历全部需求点，得到全部需求点获得的总物资量和物资运输的总成本。

（4）选择、交叉和变异操作

父代的选择采用从群体中随机选择的方式。交叉采用非标准的交叉方式产生子个体，首先将两个父代个体合并为一个长度为2p的个体，并去掉个体中的重复点，然后采用贪婪取走算法去掉个体中对目标值贡献最小的基因，直到剩余p个基因即为子个体。

在变异过程中，随机选择一个染色体，从选择的染色体中随机选择一个基因然后替换为一个与原染色体中基因不重复的新的基因。将变异率设为0.1。

（5）终止条件

在每次迭代中，记下适应值最大的染色体，直到已经达到了算法规定的最大迭代次数时算法终止。当算法终止时，最好的染色体即是该选址问题的最优解。

（6）遗传算法具体操作流程

步骤1：对数据进行实数编码，构造备选设施点与需求点之间的距离矩阵Cm×n；定义遗传算法参数（群体规模N、最大遗传代数Maxgen、交叉概率pc、变异概率pm）。

步骤2：用随机的方法生成初始化种群P（0），令t=1，P（t）=P（0）。

步骤3：计算种群P（t）的适应值。

步骤4：用随机选择策略选择两个父个体P1和P2，进行交叉、变异、重插入等操作得到子种群Q（t）。

步骤5：将P（t）和Q（t）合并，得到新的种群R（t）。

步骤6：对新种群R（t）进行优劣排序，得到P（t+1）。

步骤7：t=t+1，判断是否满足结束条件，如果否，转步骤3；否则结束，输出结果。

3 算例分析

假设某地区有30个需求点，当地政府计划从15个备选地点选择建设一定数量的应急设施点以应对突发事件，目标是以最小的总成本来最大化满足突发事件发生时的应急需求。需求点和备选设施点的位置在一个[0，100]的平面上均匀分布，需求点和备选设施点的坐标如表1和表2所示；假设各需求点应急物资为单一种类，且需求量在区间[3，5]间随机产生，单位为万件；设施点的固定建设费用均为100万元；单位产品的运输费用Cij=0.1×dij，dij为需求点i与设施点j间的距离。各覆盖等级的覆盖半径由式Dk=Dmin+Mk（Dmax-Dmin）确定，其中Mk为各等级覆盖半径的乘数，Dmin和Dmax为需求点到备选设施点的最小和最大距离；为了比较不同覆盖距离下，设施点覆盖满意度和服务成本之间的关系，本文分别设Mk为（0.05、0.1、0.15）、（0.1、0.2、0.3）和（0.2、0.4、0.6）；假设多级覆盖为3级覆盖，需求点对各覆盖等级的需求量分别为需求点总需求量的60%、30%和10%。应用Matlab7.0设计遗传算法程序，并在DELL N4040笔记本电脑上进行计算。

3.1 传统0-1多级覆盖模型和多级覆盖衰减模型的比较

由式（1），当α=0 时，覆盖衰减函数转化为0-1结构，此时问题P为传统0-1多级覆盖问题。选择5个设施点，对传统0-1多级覆盖模型和多级覆盖衰减模型的性能进行比较，其中覆盖半径乘数Mk为（0.1，0.2，0.3），覆盖衰减函数的敏感系数当α=0，β=2。表1比较了两种模型的性能，图2为两种覆盖模型的选址结果。

3.2 覆盖衰减函数的敏感度分析

多级覆盖衰减选址模型中的覆盖衰减函数敏感系数α，β的不同取值将对模型的覆盖满意度产生不同的影响，此处假设α=1，β分别取0.5、1、2，覆盖半径乘数Mk为（0.1，0.2，0.3），分别比较当选择设施点数分别为4、5、6、7、8、9时的覆盖满意度。如图3所示，当α=1，β=0.5时，多级覆盖衰减选址模型在选择不同个数的设施点时均取得了最大的覆盖满意度。因此在接下来的选址过程中，覆盖衰减函数的敏感系数可选择α=1，β=0.5。

3.3 不同覆盖半径下的设施成本、覆盖满意度的敏感度分析

多级覆盖衰减选址模型在不同的覆盖半径下，在选择不同数目的设施时，设施选址的成本、覆盖满意度均有所不同。此处假设模型覆盖半径乘数Mk分别取（0.05，0.1，0.15）、（0.1，0.2，0.3）和（0.2，0.4，0.6），比较当选择设施数分别为4、5、6、7、8、9时，分析不同覆盖半径下多级覆盖衰减选址模型的性能，如表2所示。

由表2，在不同覆盖半径下，模型覆盖满意度均随选择设施点数量的增加而增加；在选择相同数目的设施点的情况下，覆盖满意度随着覆盖半径的增加而增加，当覆盖半径乘数Mk取（0.2，0.4，0.6），选择设施点数目为8时，覆盖满意度达到100%；在选择设施点个数确定时，运输成本和总成本均随覆盖半径的增加而增加；当模型覆盖半径确定时，运输成本随选择设施点个数的增加而降低，总成本随设施点个数的增加而增加。决策者在进行选址决策时，可根据本地的实际情况，综合考虑覆盖满意度和选址成本进行决策。

3.4 覆盖满意度为100%时的选址决策

如表2所示，当要求设施覆盖满意度达100%时，决策者可选择覆盖半径乘数为（0.2，0.4，0.6），选择建立8个设施点，选址方案为（2，3，5，7，8，10，13，14），每个设施点在不同覆盖等级服务的需求点如表3所示。

4 结论及研究展望

本文主要研究了多级覆盖衰减的应急设施选址问题，提出了一个双目标的整数规划模型。然后运用遗传算法对模型进行了求解并进行了算例分析。算例结果显示，多级覆盖衰减选址模型较之传统0-1多级覆盖选址模型有更高的覆盖满意度。当敏感系数α和β分别取1和0.5时，模型可以取得更高的覆盖满意度。模型覆盖满意度随设施点个数的增加而增加；在设施点个数确定时，覆盖满意度随着覆盖半径的增加而增加；总成本随设施点个数和覆盖半径的增加而增加；在规定覆盖半径下，运输成本随设施点个数的增加递减，总成本随设施点个数的增加递增。最后本文还给出了当要求设施完全覆盖需求点的情况下，设施选址方案以及各设施在不同覆盖等级服务的需求点集合。

本文提出运用分层序列法对双目标模型进行求解。仅当前面的重要目标有多个Pareto解时，后面的次要目标才有意义，当重要目标仅有一个最优解时，则次要目标就失去了求解的意义。因此，在实用中，可为重要目标设定一定的宽容量，以保证双目标规划模型的有效性。

参考文献：

[1]杨丰梅，华国伟，邓 猛，黎建强.选址问题研究的若干进展[J].运筹与管理，2005，14（6）：1-7.

[2]王非，徐渝，李毅学.离散设施选址问题研究综述[J].运筹与管理，2006，15（5）：64-69.

[3]Roth puter Solutions to Minimum Cover Problems[J].Operation Research，1969（17）：455-465.

[4]Toregas C，Swaim R，ReVelle C and Bergman L.The Location of Emergency Service Facilities[J].Operation Research，1971（19）：1363-1373.

[5]Church R and ReVelle C.Maximal Covering Location Problem[J].Papers of the Regional Science Association，1974（32）：101-118.

[6]Schilling D A，Jayaraman V and Barkhi R.A Review of Covering Problem in Facility Location[J].Location Science，1993，1（1）：25-55.

[7]Farahani R Z.Covering Problems in Facility Location：A Review[J].Computers and Industrial Engineering.2012，62（1）：368-407.

[8]Berman O，Dreznerb Z and Krass D.Generalized Coverage：New Developments in Covering Location Models[J].Computers and Operations Research，2010，（37）：1675-1687.

[9]马云峰，杨超，张敏等.基于时间满意的最大覆盖选址问题[J].中国管理科学，2006，14（2）：45-51.

[10]陆相林，侯云先，林文，申强.基于选址理论的小城镇应急物资储备库优化配置—以北京房山区为例[J].地理研究，2011，30（6）：1000-1008.

[11]Daskin M S and Stern E H.A Hierarchical Objective Set Covering Model for Emergency Medical Service Vehicle Deployment[J].Transportation Science，1981（15）：137-152.

[12]Hogan K and ReVelle C.Concepts and Applications of Backup Coverage[J].Management Science，1986（32）：1434–1444.

[13]Narasimhan S，Pirkul H and Schilling D A.Capacitated Emergency Facility Siting with Multiple Levels of Backup[J].Annals of Operations Research，1992，40（1）：323-337.

[14]陈志宗，尤建新.重大突发事件应急救援设施选址的多目标决策模型[J].管理科学，2006，19（40）：10-14.

[15]李国旗，张锦，刘思婧.城市应急物流设施选址的多目标规划模型[J].计算机工程与应用，2011，47（19）：238-241.

[16]王文峰， 刘新亮， 郭波.综合多准则决策的保障设施选址-分派方法[J].系统工程理论与实践，2008，5（5）：148-155.

[17]韩庆兰.物流设施规划的多目标优化模型[J].控制与决策，2006，21（8）：957-960.

[18]万凤娇.基于多目标规划的危险废弃物物流选址一选线模型研究[D].武汉：武汉理工大学，2010.

[19]运筹学[M].第3版.北京：清华大学出版社，2007.

[20]Kariv O and Hakimi S.An Algorithm Approach to Network Location Problem[J].SIAM Journal of Applied Mathematics，1979（37）：513-560.

[21]马永杰，云文霞.遗传算法研究进展[J].计算机应用研究，2012，29（4）：1201-1210.

[22]Jia H Z，Ordónez F，Dessouky M M.Solution Approaches for Facility Location of Medical Supplies for Large-scale Emergencies[J].Computers and Industrial Engineering，2007（52）：257-276.