基于NSGA—Ⅱ的灾害随机环境下应急储备库多目标选址决策模型研究
开篇：润墨网以专业的文秘视角，为您筛选了一篇基于NSGA—Ⅱ的灾害随机环境下应急储备库多目标选址决策模型研究范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要：根据应急物资储备库选址问题的特点建立了多目标选址决策模型。结合模型特点采用了非支配排序多目标遗传算法（Non-dominated Sorting Genetic Algorithm Ⅱ，NSGA-Ⅱ）解决了储备库多目标选址问题，得到了Pareto解并对生成的Pareto图进行了分析，最后验证了模型的有效性。
关键词：选址；多目标决策；成本费用；NSGA-Ⅱ
中图分类号：F251；F224 文献标识码：A 文章编号：1001-8409（2013）11-0048-05
The Decision Model of the Multiobjective Supplies
Reserve Storage Location Problem Under the Environment of Random Risks Based NSGAⅡ
FU Deqiang， ZHANG Wei， WU Xianfeng， LI Changbing
（School of Economics and Management， Chongqing University of Posts and Telecommunications， Chongqing 400065）
Abstract：
This paper establishes a multiobjective location decision model. The model takes the cost of supplies storage under random disaster risk， the efficiency of the coverage and the backup coverage of the key areas into a comprehensive consideration， thus making the selection target and the constraints condition of the good’s storage more in line with the actual situation . Based on the characteristics of the model， it applies the nondominated sorting genetic algorithm Ⅱ（NSGAⅡ） into the solution of the multiobjective supplies reserve storage location problem， and a Pareto solution was produced. By analyzing the Pareto graph， it gives a constructive opinion to the preferential choices of the decision maker and also give prove to the effectiveness of the model.
Key words： location； multiobjective decision； cost； NSGAⅡ
引言
近年来，世界各地自然灾害和突发事件不断产生，例如2001年美国“911”恐怖袭击、2003年SARS疫情、2004年印度洋海啸、2008年中国南方的低温雨雪冰冻以及汶川地震、2011年日本福岛核泄漏危机以及前不久发生在我国北京的“721”超雨袭击等，这些自然灾害及突发事件的产生使受灾害国家和地区人民蒙受了巨大损失，阻碍了世界经济的良好运行。我国是世界上受灾最严重的国家之一，1998年抗洪抢险以来，我国经历的灾害情况总体呈现种类繁多、灾害较为集中、受灾面积广、直接和间接经济损失巨大等特点。
为了减轻这些突发事件和自然灾害带来的巨大损失，国家越来越重视应急基础设施的建立以及应急服务体系的完善。在国家应急体系中，应急物资储备库选址问题是其中的重要一环。储备库的成本费用和选址是否合理直接关系到社会经济效益和国家防灾减灾系统的运行效率，并且与应急物流保障系统的时效性紧密联系。国家于1998年开始建立应急物资储备制度，随后的几年中，国家不断完善应急物资储备库的体系建设，在《国家突发公共事件总体应急预案》[1]和《国家综合防灾减灾规划》[2]中还明确了物资储备库的新、改、扩建办法。虽然我国目前的救灾物资储备网络体系已基本建成，但在大型物资储备库布局方面仍存在不足，如缺少有效的成本约束和储备库运行效率低下等。因此，研究应急物资储备库的选址问题对于当前我国的应急管理工作是非常具有现实意义的。
对于设施选址问题的研究可以追溯到1909年，阿尔弗雷德·韦伯（Alfred Weber）研究的单一仓库设施选址问题。随后的几十年中，设施选址问题得到了专家学者的深入探讨和研究。1964年，Hakimi
[3]发表了他的关于网络多设施选址问题的相关论文，从那以后，设施选址问题引起了全世界相关研究者的兴趣。研究者们做了大量卓有成效的工作，建立了许多模型并得到了颇多成果[4～9]，大多数基本的选址模型是确定型的，这些数学模型广泛应用于赢利企业与非盈利公共服务方面。
在国内，选址问题的研究者们对于公共应急设施选址的研究一般都是基于一定的应用背景下，公共应急设施如医院、消防点等的选址理论研究已经较为成熟。但是国内对于大型应急物资储备库选址问题的研究目前还正处于起步阶段。李静等[10]建立了基于时间满意的应急物资储备库双容量限制选址模型，并给予仿真计算以验证其模型有效性。郭子雪等[11]在构建了约束条件中含有梯形模糊数的应急物资储备库选址模型，给出了一种基于梯形模糊数排序准则的模型算法，最后通过算例分析验证了该方法的有效性。陆相林等[12]探讨了考虑覆盖半径内需求满意差异的最大覆盖设施选址模型，并利用蚁群算法进行求解。刘浪等[13]运用二次分层法的思想应用集合覆盖理论求解无权网络中的应急物资储备点最少点集合的所有组合方案。葛春景等[14]分析了我国目前应急物资储备体系的现状，构建了轴辐式应急物资储备网络体系并提出了相关建议。
上述研究人员对于应急物资储备库的选址问题进行了有效的探讨并给出了一些模型及相应算法，但是，考虑了风险随机下大型储备库节点和边上成本目标的模型并不多，在这些已有的考虑成本目标的模型当中并没有把储备库无法提供满意服务时，在运输路线上产生的缺货惩罚成本考虑进去。本文基于目前的研究现状，针对风险随机环境下的应急物资储备库选址问题进行深入讨论，建立了综合成本费用、覆盖效率以及对重点地区备用覆盖的多目标决策选址模型，并尝试利用nsga-Ⅱ算法结合相应算例讨论其求解策略。
1 模型的建立
11 问题的描述
本文认为，大型应急物资储备库选址问题应具有如下实际特点：
（1）储备库的建立是长期基建项目，由于建设投资、维持及营运成本较高，故具有多项成本约束。
（2）储备库建成后，尽可能覆盖较大范围内需求点的需求。
（3）对灾害多发且人口较为密集的区域可进行超额覆盖。
（4）应急储备库内存放单品种库存物资且库存是处于动态饱和状态的。
（5）储备库起用后，储备系统会产生运输成本费用以及由于无法提供及时满意服务而引起的缺货损失费用。
（6）建成后的储备库可以为需求区域提供高效、及时的应急物资服务。
一般而言，大型应急物资储备库的选址要满足成本最小化、效率最大化和重点地区的备用覆盖。所以，应急物资储备库选址是一个多目标的问题。
12 基本假设及参数定义
假设建成后的储备库提供的是同一类物资的应急服务；每个储备库之间相互独立；当储备库不能提供可靠的满意服务时，需求点损失不断扩大，政府需要承担较高的补货运输费用，由一个惩罚系数C表示，这个系数表示单位经济损失；由于不同灾害风险发生概率不同，为保证在任何情境下，费用都能保持较低，固引入期望值系数α，定义如下：在考虑所有灾害风险发生的前提下，能够得到一个期望估计量，如期望产生的成本Y*s，这时定义可以接受的期望成本是在一个较小的百分比范围内，即在Y*s（1+α）内，本文把这样一个系数α称为期望值系数，α1为期望成本损失值系数。为便于计算且不失一般性，本文假设Pj是物资储备库j能为需求点i提供的服务满意水平且该满意水平随机产生。
定义参数I为需求点集合，由下标i表示；J为储备库候选点集合，由下标j表示；S为风险发生的情境集合，由下标s表示；灾害风险s发生的概率为qs；单位距离运输费率为cij；dij为储备库与需求点的最短距离；i需求点的权重为wi（可以由经济重要性、人口数量以及风险发生的概率进行综合评价）。为了方便计算，每个需求点权重可由该需求区域人口数来确定，即wi=需求区域人口数量，结合以上假设和问题描述，需求点需求量即为人口数量wi。单个储备库年固定投资及运营费用之和为fj；单位持有成本设为hj。本模型中储备库总的持有成本看成是关于需求量的一个函数，由于储备库提供的是同一类物资，因此单位物资的持有成本hj可以看成是一个常量，Qj为储备库j的物资容量。决策变量ui即需求区域i被超额覆盖的次数；设置0-1变量Xj，当j储备库候选点设立储备库时，Xj=1，否则Xj=0；在风险情境s下如果设施j为需求点i提供物资援助，则yijs=1，否则yijs=0。
13 模型的建立
风险随机环境下的大型应急物资储备库多目标选址决策模型可以表述如下：
minY1=C [ijs（1-pj） qs wi yijs]+jfjxj+ jhj Qj+ijscij dij yijs wi （1）
minY2=ijswi dij yijs （2）
maxY3=iwi ui （3）
ST ijwiyijs cij dij+C j （1-pj） iwi y ijs≤（1+α1） Ys s ∈S（4）
yijs-xj≤0 i∈I j∈J s ∈S（5）
jyijs-ui≥1 i∈I s ∈S（6）
Qj= maxiwiyijs s ∈S j∈J（7）
yijs ， xj∈0 ，1， i∈I j∈J s ∈S ，u i≥0，整数（8）
14 模型说明
在以上建立的多目标决策模型中，目标函数式（1）左起第一项表示因储备库无法提供需求点满意物资服务而引起的缺货惩罚成本，第二项则表示储备网络中储备点产生的建设及运营费用之和，第三项表示储备库物资的维持成本之和，由于储备库的建立是要覆盖所有需求点的需求量，所以把它看做是需求点对于储备库的物资需求总和。为了便于理解，把维持成本看做是关于需求量的一个函数。最后一项则表示在风险s下，储备库j向需求点i运输物资的总运输费用。目标函数式（1）的建立表示期望建成的储备库在风险s下的成本费用最小；目标函数式（2）表示使设置的储备库服务需求点的加权距离总和最小，即p-中值模型，用来表示服务效率水平；目标函数式（3）使设置的应急储备库对需求点的超额覆盖最大化，即使在风险s下，权重较大的需求区域也有更多的应急储备库为其服务；约束条件式（4）表示储备网络要达到的期望成本费用水平，即在风险s发生的情况下，系统产生的运输及缺货损失费用与期望最优费用目标之间的差额系数应该是在小于α的范围内；约束条件式（5）表示每个需求点只能由已经设置的储备库提供服务；约束条件式（6）表示至少有一个储备库为需求点i提供服务；约束条件式（7）保证了储备库容量处于一个最大的安全库存范围内；约束条件式（8）限制yijs和xj为0-1决策变量以及ui的整数性质。
2 算法设计
以上所建多目标模型属于NP难题，存在不确定数量的解集即非劣解集，而NSGA-Ⅱ算法可以利用非支配排序使多目标变化为适应度函数的形式，从而解决多目标问题，NSGA-Ⅱ算法已经在解决实际工程问题中得到了广泛应用[15，16]，因此本文首次尝试将该算法运用到应急储备库多目标选址问题中，其步骤如下：
第一步，编码：由于备选的是10个候选点、200个需求点以及4种风险，那么决策变量yijs的个数为10*200*4=8000；决策变量Xj的个数为10， ui的个数为200，那么总的决策变量V的个数为8000+10+200=8210个。约束条件是用来检测每个方案是否正确，每个染色体的位置向量对应一个选址方案。
第二步，虚拟适应度的计算：将染色体进行解码，然后按照多目标选址模型计算与每个个体相适应的目标函数，再依据目标函数的值进行非劣解分层，从而计算每一层个体的虚拟适应度。
第三步，交叉、变异及精英策略：（1） 随机初始化开始种群P0。并对P0进行非支配排序，初始化每个个体的rank值。（2） t=0。（3）通过二进制锦标赛法从Pt中选择个体，并进行交叉和变异操作，产生新一代种群Qt。（4）通过合并Pt和 Qt产生出组合种群Rt=Pt∪Qt。（5）对Rt进行非支配排序，并通过拥挤和精英保留策略选出N个个体，组成新一代种群Pt+1。（6）跳转到步骤（3）并循环，直至满足结束条件。
在本文选取的算法当中二进制变异所使用的基本位变异算子的方法步骤如下：
第一步，对个体的每一个基因座，依变异概率Pm指定其为变异点。
第二步，对每一个指定的变异点，对其基因值做取反运算或用其他等位基因值来代替，从而产生出一个新的个体。变异是针对个体的某一个或某一些基因座上的基因值执行的，因此变异概率Pm也是针对基因而言，即：pm=BM·L。式中B表示每代中变异的基因数目；M表示每代中群体拥有的个体数目；L代表个体中基因串长度。
第三步中，单点交叉算子的具体计算过程如下：
（1）对群体中的个体进行两两随机配对。若群体大小为M，则共有[M/2]对相互配对的个体组。
（2）每一对相互配对的个体，随机设置某一基因座之后的位置为交叉点。若染色体的长度为l，则共有（L-1）个可能的交叉点位置。
（3）每一对相互配对的个体，依设定的交叉概率Pc在其交叉点处相互交换两个个体的部分染色体，从而产生出两个新的个体。
重复以上具体步骤，可得算法流程图如图1。
3 算例分析
某省区计划在10个候选点（A、B、C、D、E、F、G、H、I、J）内选择其中的几个来建立足够容量的大型物资储备库，以满足省内200个需求点的应急物资需求，需求点和物资储备库的位置在600*300的矩形区域内随机产生，需求点和储备库的距离按欧氏距离计算，需求点区域的人口数量wi在U（50，200）内随机产生。
政府部门计划对人口权重位于前三位的区域进行至少超额1次覆盖，建成后的储备库要对这3个区域进行至少2次覆盖（即ui>=1），其余需求点均覆盖1次即可。候选点在灾害风险发生情况下能为需求点提供满意服务的水平pj随机产生于（07，1）内，这里给出四种灾害风险情况，每种发生的概率假设为qs=（1/12，1/10，1/9，1/8）。
表1明确了储备系统产生的各项成本费用，政府在建立这些大型应急物资储备库时，预算的在途正常运输与惩罚成本之和Y*s共计1200万元，期望损失值系数α1设计为10%，为了便于计算，库存物资数量按需求区域人手一件来计。
在仿真计算过程中取初始种群规模为200个，最大遗传代数为145，交叉概率Pc为09，变异概率Pm为002。利用Matlab软件，编程实现NSGA-Ⅱ算法。根据算例所设置的数值精度，当种群规模为200个，迭代次数为145时，运行主程序得到的Pareto前沿（如图2），图2即为选址优化结果。
图2所示的Pareto最优解在空间中的分布情况类似一条不连续的“上升曲线”，该“曲线”实际是由201个非劣解在目标空间均匀分布而组成的。在得到的Pareto最优解集中，三个目标函数之间是此消彼长的关系，由图2可知，总成本、加权距离之和及超额覆盖数是三个相互对立的目标，其中一个目标值发生变化将会导致另外两个目标值的变化，曲线上各点都是三目标值的非劣组合，当选址的目标偏向以成本控制的角度考虑时，可在曲线的左下半支中选择相对满意解；当选址以加权距离总和为出发点考虑时可选取曲线中靠近f2原点的半支，当选址目标为超额覆盖最大时，可在曲线的上半支中选择。
图2中显示了201个点，每个点对应一组非劣解，而一组非劣解又包含了三个目标值。决策者可根据主观意愿或一系列评价方法对f1、f2、f3分别进行赋权，再采用三目标值加权求最小等方式计算并选取图中的某一特定点，该点对应的三目标值即为满意解。
4 结论
在风险随机环境下，应急储备库多目标选址是一个目标与约束复杂度较高的NP难题，从最低成本、加权距离之和最小以及超额覆盖最大这三个角度出发，本文建立了一个应急物资储备库多目标选址决策模型，通过利用NSGA-Ⅱ算法与算例较好地进行结合，得出了可行度较高的非劣解集并为决策者进一步根据主观意愿选取满意解提供了条件，验证了所建多目标选址决策模型的可行性。由于算法本身的特点，采用随机数据得出的数值结果可能与实际存在一定偏差，但总体上NSGA-Ⅱ算法与所建模型具有较高的契合度，说明了模型的实用性，对于应急物资储备库多目标选址决策具有一定意义。
参考文献：
[1]国务院.国家突发公共事件总体应急预案[Z]政府网，200618. http：//wwwgovcn/yjgl/2006-01/08/content_21048htm
[2]国务院.国家综合防灾减灾规划（2011～2015）[Z]政府网，2011128. http：//wwwgovcn/zwgk/2011-12/08/content_2015178htm
[3]S L HakimiOptimal Location of Switching Centers and the Absolute Centers and Medians of a Graph [J]. Operations Research，1964，12：156-164
[4]Ceyhun Araz，Hasan Selim，Irem Ozkarahan A Fuzzy Multi-objective Covering-based Vehicle Location Model for Emergency Services[J]Computers & Operations Research， 2007，34：705-726
[5]Revelle C，Swain R WCentral Facilities Location [J].Geographical Analysis，1970，2：30-42
[6]C Toregas， C ReVelle Optimal Location under Time or Distance Constraints[J]Papers of the Regional Science Association，1972， 28：133-143
[7]R L Church， C S ReVelle Theoretical and Computational Links between the P-median Location Set-covering and the Maximal Covering Location Problem[J] Geographical Analysis， 1976，8：406-415
[8]陈志宗，尤建新重大突发事件应急救援设施选址的多目标决策模型[J].管理科学，2006（4）：10-14
[9]方磊， 何建敏 应急系统优化选址的模型及其算法[J]. 系统工程学报， 2003， 18 （1） ： 49 - 54
[10]李静，赵林度 基于时间满意的应急物资储备库双容量限制选址模型[J].东南大学学报（自然科学版），2007，11
[11]郭子雪，齐美然，张强 基于区间数的应急物资储备库最小费用选址模型[J].运筹与管理，2010，19（1）：15-20
[12]陆相林，侯云先 基于设施选址理论的中国国家级应急物资储备库配置[J].经济地理，2010（7）：1091
[13]刘浪，黄有方 加权网络应急物资储备点选址方法[J].北京理工大学学报，2011（2）：245-252
[14]葛春景，王霞，关贤军 应对重大灾害的轴辐式应急物资储备网络体系[J].自然灾害学报，2011，4
[15]Deb K， Pratap A，Agrawal S， et alA Fast and Elitist Multi-objective Genetic Algorithm： NSGA-II[J]. IEEE Trans Evol Comput， 2002， 6 （2） ： 182 - 197
[16]张志刚，马光文 基于NSGA-Ⅱ算法的多目标水火电站群优化调度模型研究[J].水力发电学报，2010，2
收稿日期：2012-12-23
基金项目：国家自然科学基金项目（60905066）
作者简介：付德强（1976-），男，四川乐至人，博士研究生，研究方向为物流与供应链管理；张 伟（1988-），男，河北廊坊人，硕士研究生，研究方向为物流系统规划与设计；吴先锋（1963-），男，重庆人，教授，研究方向为通信经营管理；李昌兵（1970-），男，重庆人，副教授，研究方向为物流与供应链管理。