1、1基于 NSGA算法的电力企业应急物资储备中心选址研究【摘 要】首先阐述了电力企业应急物流的基本现状，结合省级电网企业应急物资储备中心选址的目标和原则，进行了应急物资储备中心选址问题研究，并建立了省级电网企业应急物资储备中心选址模型。采用 NSGA-算法来进行模型求解，最后以 NX 省电网应急物资储备中心选址为实例进行了分析。 【关键词】电力企业应急物资；设施选址；NSGA-算法 引言 由于对电网企业应急物资储备中心规划与设计的研究较少，目前各省级电网企业应急物资储备体系大多还处于较为原始的状态，普遍存在应急物资储备中心选址不合理的问题。为最大程度减少突发事件对电网安全运行造成的影响，保障供电
2、安全，迫切需要对省级电网企业应急物资储备中心的选址问题进行研究。 为节约省级应急物资储备中心的选址成本，本文从现有地市级仓库中选择合适的地点作为省级应急物资储备中心。即假设现有地市级物资仓库的所在地既是应急物资的需求地，又是省级应急物资储备中心的候选地。选址的目标是在应急物资储备中心的数目最少、成本最低且不能超过投资预算的前提下，实现应急物资储备中心到各需求点的总时间最小。 21.国内外研究现状 由于电力企业应急物资储备库选址题问研究的起步较晚，研究成果相对较少。但对于一般设施的选址问题，国内外学者已经做了大量的研究，取得了比较成熟的研究成果。从总体上看，研究成果可分成静态确定性选址问题和多阶
3、段动态选址问题。 静态确定性选址问题主要包括：（1）P中心问题，是选择 p 个设施的区位，使所有需求点得到服务，并且每个需求点到其最近设施的最大距离最小1。 （2）P 一中值问题，是考虑 P 个设施点到需求点之间的加权距离最小化。通常是假定目标成本最小，使得费用最低，时间最少，距离最短，所以，又可称之为最小和问题2。 （3）覆盖问题，在满足所有需求点的前提下，设施点的建设费用最小的问题，主要用于应急服务设施的选址3。 多阶段动态选址问题主要包括：（1）动态选址模型。最早由 Ballou提出，它研究如何确定一个仓库的位置，使其在规划期内实现利润最大化，该模型的思想是求解出较优位置的集合，再用动态
4、规划求解在决策期内的最优位置4。Gebennini 和 Rodriguez5等人对模型进行了拓展。国内，朱鸿等人研究了非确定性需求环境下的配送中心选址问题，运用随机机会约束规划为基本建模工具，建立了配送中心动态选址模型6。（2）随机模型。Berman 等人详细总结和评述了需求为随机变量的设施选址问题7。Xu Jiuping 等人研究了在运行时间、服务时间、供应与需求等都随机变化的条件下的 P-中值问题8。Pasandideh 等人提出了随机性集合覆盖模型9。国内，毕娅等人构建了供应链总成本最低和配送中3心覆盖率最大的多目标离散随机选址模型10。 2.模型构建 本文的选址问题可描述为：给定需求点
5、集合和候选点集合，且候选点集合等于需求点集合，已知需求点的数目、需求点之间的运行时间，各个候选点建立应急物资储备中心的投资成本及各需求点要求服务时间的限制，求解一个能实现应急物资储备库数目最少，投资成本最低，所需时间最少的选址结果。 在个需求点中选（一般）个应急物资储备库，优化的目标就是如何以最低的成本建立一些应急物资储备中心，使得自然灾害和生产事故发生时，实现应急物资储备中心到需求点的时间最短。设表示应急物资储备库中心候选点组成的集合，表示需求点组成的集合，表示设施点到需求点的运行时间，为建立应急物资储备中心的投资成本，是候选应急物资储备中心到达需求点的最短时间， ，是需求点所需的服务时间限
6、制，如果则表示应急物资储备中心到需求点的最短时间满足需求点所要求的服务时间限制，否则应从可行解中剔除。 则多目标应急物资储备中心选址问题的数学模型为： （2-1） （2-2） （2-3） 式中：N应急物资储备中心数量；T应急物资储备中心到达需求点的最短时间之和；C按照选址方案进行建设的总成本；TC预算总投资。 43.模型求解 3.1 NSGA-算法概述 1995 年，Srinivas 和 Deb 提出了非支配排序遗传算法（Non-dominated Sorting Genetic Algorithms，NSGA） 。这是一种基于帕累托最优概念的遗传算法，它与简单的遗传算法的主要区别在于：该算法
7、在选择算子执行之前根据个体之间的支配关系进行了分层。2000 年，Deb又提出 NSGA 的改进算法带精英策略的非支配排序遗传算法（NSGA-） 。主要体现在三个方面： （1）提出了快速非支配排序法，降低了算法的复杂度。时间由原来的 O（mN3）降到 O（mN2） ，其中 m 为目标函数个数，N 为种群大小。 （2）提出了拥挤度和拥挤度比较算子代替适应度共享策略，保持了种群的多样性。 （3）引入精英策略，扩大采样空间。在产生下一代种群时，让父代种群与子代种群共同参与竞争。 3.2 求解过程 由于应急物资储备中心的数量和地点均未定，难以采用精确算法求出最优解。鉴于 NSGA-算法对于复杂问题求解
8、的优势。本文采用 NSGA-算法进行模型求解，过程如下： （1）快速非支配排序。设种群大小为，通过快速非支配排序可以计算种群中每个个体的参数和，其中为种群中支配个体的解个体的数量，为种群中被个体所支配的解个体的集合。 1）对种群中的个体，令其参数， 。 52）将种群中的所有个体与种群中其他个体进行比较：1 若支配， ；若支配， ；2 若，种群中没有其他个体支配个体，则；3 若， ，为非支配解集。3）令。 4）当时：1 令；2 对集合中的所有个体，考察它所支配的个体集，对集合中的每所有个体，令。若， ；若， ；3；4 形成下一非支配集合。 5）返回非支配集。 整个算法的计算复杂度是，为目标函数个
9、数，为种群大小。 （2）拥挤度计算。在 NSGA -算法中，拥挤度计算是保证种群多样性的一个重要环节。计算方法如下。 1）对集合中的每一个个体，令。 2）对于每个目标函数：1 基于该目标函数对集合中的个体进行排序，；2 令集合中每个个体边界的拥挤度为无穷，即， 。 3）对于到 （3-1） 式中，中第个个体的第个函数值。 （3）拥挤度比较。经过排序和拥挤度计算，群体中每个个体都得到两个属性：非支配序和拥挤度。当满足条件，或满足条件且时，定义。 （4）模拟二进制交叉原理。使用模拟二进制交叉算法模拟自然界中的二进制交配，计算方法如下。 （3-2） （3-3） 6式中， 组分的第个子代；选择的父代；由
10、下面的密度分布函数产生的随机数。 （3-4） （3-5） （3-6） （3-7） 其中，（ 0，1） 范围内均匀取随机数；交叉的分布指数。 （5）多项式突变。 （3-8） 式中，为子代，为父代，和为父代的上下限，为小的偏差，该偏差由一个多项式分布计算得到，公式如下： （3-9） （3-10） 式中，（ 0，1） 范围内均匀抽取的随机数；突变分布指数。 （6）重组再选择。子代种群与父代种群组合，进行非支配排序。新种群由存储非支配排序结果的集合进行填充，直到超出种群大小。如果将集合中所有个体加入新种群会超出种群大小，则将集合中个体按拥挤度降序排列后再依次选入新种群，直至种群大小为。 4.算例分析
11、假设 NX 省对应急物资响应能力的要求是当事故发生后，应急物资必须在 5 小时内送达救援现场。NX 省现有 5 个地市和 1 个经济开发区，为了节约建设成本，拟从现有的 6 个地市级仓库中选取一定数量的仓库进7行改扩建，形成省级物资储备中心。由于资金预算的限制，应急物资储备中心的数量应尽可能小，所有应急物资中心的改扩建费用不能超过2500 万元。各地区之间抢险车辆行驶时间见表 4-1，各地区建设应急物资储备库的成本见表 4-2。 表 4-1 各地区之间运行距离 单位：小时 地区 地区 1 地区 2 地区 3 地区 4 地区 5 地区 6 地区 1 0 1.5 2.25 3.9 4.05 2.7
12、 地区 2 1.5 0 3 3.75 1.8 1.5 地区 3 2.25 3 0 2.25 4.2 3.15 地区 4 3.9 3.75 2.25 0 2.4 3.45 地区 5 4.05 1.8 4.2 2.4 0 1.5 地区 6 2.7 1.5 3.15 3.45 1.5 0 表 4-2 各地区建设应急物资储备库的成本 单位：万元 地区 地区 1 地区 2 地区 3 地区 4 地区 5 地区 6 成本 1025 1000 950 1200 1175 1080 （1）构造数学模型。三个目标函数分别代表三个优化目标，分别是应急物资储备中心数量最小，应急物资储备中心到各地区的总时间最少和建设应
13、急物资储备中心的总成本最小。 （2）求解。设定初始种群为 100，迭代次数为 50，交叉率为 0.9，变异率为 0.02。在 Matlab 环境下运用 NSGA -解决多目标优化问题，经计算得出一系列 Pareto 最优解，计算结果如表 4-3 所示。 表 4-3 应急物资储备中心选址方案比较 8序号 方案 成本（万元） 总时间（小时） 1 （1，0，0，1，0，0） 2225 8.85 2 （0，1，0，1，0，0） 2200 7.05 3 （0，1，0，0，1，0） 2175 8.4 4 （1，0，0，0，1，0） 2200 7.65 5 （0，0，1，0，1，0） 2125 7.8 6
14、（0，0，1，0，0，1） 2060 7.5 由表 4-3 可知，6 个方案的总成本都没有超过资金预算，按照优先考虑应急响应时间的评价标准，应选择方案 2 作为最终的实施方案，在地区 2 和地区 4 建设应急物资储备中心。 参考文献： 1Davoodi M.，Mohades A.，Rezaei J.Solving the constrained p-center problem using heuristic algorithmsJ.Applied Soft Computing，2011，11（4）：3321-3328. 2Manzour，Torabi S.，Eshghi K.Single-S
15、ource Capacitated Multi-Facility Weber Problem-An iterative two phase heuristic algorithm J.Computers and Operations Research， 2012，39（7）：1465-1476. 3HarPeled，Sariel and Lee，Mira.Weighted geometric set cover problems revisited J. Journal of Computational Geometry，2012，3（1）：65-85. 4Ballou，R.H.Dynamic
16、 Warehouse Location AnalysisJ.9Journal of Marketing Research， 1968（5）：271-276. 5RM Rodrguez，H Takagi.Application of renewal theory to call handover counting and dynamic location management in cellular mobile networksJ.European Journal of Operational Research，2010，204（1）：1-13. 6朱鸿，徐克林，朱伟等.动态需求下的多目标配送
17、中心选址研究J.物流技术，2012，31（4）：68-70. 7Oded Bermana，Dmitry Krassa，Jiamin Wang.The probabilistic gradual covering location problem on a network with discrete random demand weightsJ.Computers and Operations Research，2011，38（11）：1493-1500. 8Xu Jiuping，Yao Liming，Zhao，Xiaodan.A multi-objective chance-constrain
18、ed network optimal model with random fuzzy coefficients and its application to logistics distribution center location problem J. Fuzzy Optimization And Decision Making，2010，10（3）：255-285. 9Pasandideh，Seyed H.，Niaki，Seyed T. Genetic application in a facility location problem with random demand within queuing framework J. Journal Of Intelligent Manufacturing，2012，23（3）：651-659. 10毕娅，李文锋.基于协同库存和模糊需求的离散选址模型研究J.统计与决策，2011， （6）：66-69. 10作者简介： 王丽国（1986-） ，内蒙古赤峰人，华北电力大学经济与管理学院物流工程专业在读研究生。 曹原（1987-） ，河南三门峡人，毕业于华北电力大学物流工程专业，现供职于国网河南省电力公司物资公司。
