基于粒子群算法的多目标消防站选址规划模型

姚佳淇

（中国矿业大学信息与控制工程学院 江苏省徐州市 221116）

1 引言

火情发生的突然性和对生命财产危害的严重性很大程度上要求消防站的布局选址必须合理，这样才能做到将灾害损失减少，让人们的安全得到保障。设施选址优化问题是空间组合优化在具体实践上的体现，选址问题在许多不同的学科上都有存在或联系，综合不同的学科的论述可以总结出选址问题最实质的定义是：给定一个可以度量的空间，并且安排了需求点的位置，接下来进行新设施的放置，使得在需求点和新设施的约束条件成立的情况下，某种由供需关系所确定的目标达到最优。选址问题可以分为连续选址和离散选址[1]，连续选址的待选区域是一个平面，不考虑其他结构，并且可能的选址位置数量是无限的，同时选址模型也是连续的。本文讨论的消防站选址问题属于典型的连续选址问题。

对于消防站的选址问题，传统方法只考虑了最具有时效性的目标，如距离或时间目标[2][3]，当考虑到其他因素时，一些研究方法也应运而生，基于多目标模糊优选理论[4]的选址方法可以对一些无法量化的模糊因素做出评价，基于熵权TOPSIS 法[5]的选址模型是对多指标选址评价的理想解法，把AHP 结合覆盖模型[6]应用到消防站选址中也可以较明显地比较出各个选址策略的优劣。但是这些决策选址方法只适用于备选数量较少的消防站选址问题，而当消防站备选数量增加，逐个分析评价就会非常繁琐，不具有实践意义。本文对消防站选址进行深入分析，根据不同的影响因素确定多目标选址规划模型，并且运用改进的粒子群算法来得出最佳选址方法，对解决数量庞大的消防站选址问题具有一定的合理性。

2 多目标选址规划模型

多设施选址所考虑的影响因素和求解难度相比于单设施选址会更加有难度，主要体现在：

（1）设施的服务对象；

（2）设施的容量约束；

（3）设施间的互动；

（4）设施数的确定等[1]。

消防站选址相对于加油站，运输站，快递站等其他设施的选址在策略目标上会更加注重需求影响，效益最大化，成本最小化和社会环境[7]的影响。综合考虑消防站选址的影响因素和策略方法，结合经典的覆盖模型和P-类问题[8]模型，进行如下模型的构建：

模型说明如下：

n 是所给空间的站点数量；

D 表示消防站到需求点的最大距离；hi表示需求点的人数；mi表示需求点；dij表示消防站j 到需求点i 的距离；kj表示消防站建在j 处的成本费用；δij表示在灾害发生过程中，消防站j 遭到破坏，服务应急能力下降后的能效系数[9]；w 表示维修消防站的单位成本；

目标函数（1）和约束条件（7）表示使消防站到达需求点的最大距离取到最小，是P-中心问题的合理运用；约束条件（8）则表示一个需求点只需要一个消防站来服务；约束（6）表示消防站没有被选定时，不能为需求点提供服务；目标函数（5）考虑到经济效益，分别表示所建设的消防站数量应达到最小以及建设成本和维修成本也应为最少；目标函数（3）运用到了最大覆盖模型，表示使消防站在有限资源约束下所能覆盖的最大需求量；目标函数（4）体现了p-中值问题的运用，使得消防站到需求点的总距离和为最小；约束条件（9）考虑到火灾对消防站的损坏，必须保证对需求点具有足够服务能力的消防站。

3 粒子群算法的设计

本文所构建的消防站选址模型为典型的多目标优化问题，传统的多目标优化算法包括加权法、约束法和线性规划法等，实际上就是将多目标函数转化为单目标问题进行求解，这容易造成部分最优解的流失。随着智能优化算法的快速发展，对于多目标优化类模型就有了更合理高效的解法。粒子群算法[10]作为一种智能优化算法，已在组合优化和数值优化等方面发挥巨大作用。粒子群算法来源于鸟类的群体活动的规律性，利用群体智能建立简化模型。该算法模拟鸟类的觅食行为，把鸟类的飞行空间比作模型变量的搜索范围，每只鸟个体表征一个可能解，把算法运行过程当做鸟类觅食的过程。

基本粒子群算法流程图如图1所示。

图1：粒子群算法流程图

步骤1：首先对所给空间进行数据预处理。对路网数据进行求最短路问题的处理，用Floyd 算法[11]进行求解：构造邻接矩阵，矩阵中每个元素意义如下：

4 模型分析

如图2，这是一个地区的消防站候选区的赋权图，可以写出其邻接矩阵，并使用Floyd 算法得到15 个区域的最短距离矩阵D。

图2：候选区域赋权图

在选址过程中，粒子群算法不能直接适用于求解空间型数据，为了将二维平面空间中的候选位置与粒子种群产生联系，需要将问题的可行解从解空间转换到粒子群算法所能处理的搜索空间[14]，因此对初始粒子种群的位置进行编码，采用二进制编码，形如[x1x2x3x4x5x6x7x8x9x10]为一个初始粒子，[1010100010]表示在x1,x3,x5,x9处设置消防站。

在接下来的过程中，基于初始粒子种群的二进制编码，采取离散粒子群算法，即粒子的位置更新的取值变化仅限于0 和1 两个值，粒子群的速度更新公式不发生改变，而位置更新则表示为：

其中r 是从U(0,1)分布中产生的随机数。

对于约束条件可以采用罚函数进行处理：

将不等约束条件写为gj(x)的形式，其中|gj(x)|表示当gj(x)≥0时取|gj(x)|的值，满足约束条件取0；fmax是粒子群体中最差可行粒子的适应度，没有可行粒子时为0。

5 结论

本文研究了对消防站设施的选址，构建了多目标规划的选址模型，考虑到各方面的影响因素，结合覆盖模型和P-问题模型，并用改进的粒子群算法进行算法设计。粒子群算法会根据自己的速度来决定搜索，没有遗传算法中重要的交叉与变异步骤，并且每个粒子在算法运行或结束时都还保有各自的个体极值，所以算法不仅可以给出全局极值，也可以对一系列次优解进行分析，如本文所讨论的Pareto 解集以及非支配排序，这为多目标规划模型的求解提供了一种新的思路。