计算机技术在应急设施选址问题上的应用

刘建友，蒋春霞

(广东理工学院，广东 肇庆 526020)

人们对各种应急服务的需求变得越来越强烈，如果能迅速地把有效的应急资源分配到事故现场，可以大大减少损失，这就需要有合适的应急救援仓库和救援设施派遣站点。研究了计算机技术在应急设施选址问题中的应用，展望了未来需要关注的方向，以提供一些参考。

1 应急设施分类

应急设施按照不同方法可以分为不同种类。按照时效性可分为永久应急设施和临时应急设施。永久应急设施长期存在于固定站点，在紧急情况下迅速开设或启用并提供应急服务，属于大规模紧急事件发生前的规划范畴。临时应急设施一般是暂时占用，只有当发生非常紧急情况时，有关部门根据紧急形势分析出在某一地点临时建立救援点。按照应用领域可以分为应急医疗设施、应急物流设施和防灾减灾设施三种类型。应急医疗设施主要包括救护车站点、供血站等。应急物流设施主要包括应急仓库、配送中心等。防灾减灾设施是指发生灾害时，把大批受灾群众转移到避难所的一些必要设施。

2 应急设施选址模型

选址问题主要有连续型和离散型。连续型是指在事前指定区域内进行任意位置的选择(即指定的任选)。离散型则是在候选站点选取部分进行选择(即选再选)。研究针对离散型，利用计算机技术和混合整数线性规划构建模型，将其分为5个控制因素，即基本选址问题、动态选址问题、随机选址问题、鲁棒选址问题和其他选址问题。

2.1 基本选址问题

基本选址问题有基于覆盖和基于中值两种类型。

基于覆盖的问题有：第一，最大覆盖问题。它通常是配备设施于一个最大的覆盖区域，在给定区域内进行选址，方法是根据需求水平的高低对需求点进行重要程度区分。很多文献中关于救护车选址、救灾物资分发中心选址中都选用了这种方法。第二，集合覆盖问题。它的核心是想尽办法把覆盖区域内所有需求点的设施数量最小化，即在满足需求覆盖水平的情况下，尽可能让设施数量或总的选址成本最小。第三，P-中点问题。它是在第二类问题基础上发展起来的，目的是在满足覆盖区域内需求点数量的情况下，让需求点和与其对应的设施间的最大距离或到达时间最小，把人口分布、经济状况、交通及部分关键部位等都作为关键要素考虑进去。

基于中值的问题是在被选的位置中进行选址，把所需点和设备间用距离或时间进行加权，使其成本最小化，以达到设施选址位置为整个设施系统网络的中值目标。它包括P-中值问题，即使设施覆盖的每一个需求点的加权平均距离最小化。固定费用设施选址问题，即使设施建立和服务的总成本最小化。

2.2 动态选址问题

在生活中，任何东西都是随时间而变化的，如环境、需求、服务成本和效率，因此在选址时要考虑动态问题，必须划分不同的时间段，每个时间段根据当前的情况来选址，不断进行调整。可以利用计算机技术建立一个动态确定性模型，总时间为T，每一个时间段为t，候选点的集合M里包含nt个候选站点或候选目标点，进行迁移所花费的成本用ct表示，则时段t内设施迁移到候选点m所花费的运输成本用ftm(xt，yt)表示，在时段t的设施迁移距离用dt-1，t。建立函数：

制约条件是：

2.3 随机选址问题

制约条件：

在一些地方应急物流配送中心选址-配送模型充分利用了这种方法，他们把运输车的超载问题和应急仓库容积问题也一并纳入了不确定因素中。

2.4 鲁棒选址问题

它与随机选址问题相似，它的不确定因素是事前并不知道，同时把不确定性因素通过一定的方法加入不同的离散区域或连续区域来体现其具有松弛性。表达方法如下：I={不确定性因素}，不确定性因素i∈I，Ui={可能的不确定性因素}，在决策变量的向量x下进行的选址成本是fo(x)；建立函数：

minfo(x)

制约条件是：

fi(x,ui)≤0,∀ui∈Ui,1≤i≤m

这个函数对于包含不确定参数具有优化作用，在一些国家常用于灾后血液供应设施选址上。

2.5 其他选址问题

除了以上几种常见的选址之外，还有其他几种常见的类型，如构建最小化 P-嫉妒模型，它的原理是根据用户对设施服务的满意水平不同，把区域j内的客户不满意度的范围建立一个从j到p服务设施点的函数。在此基础上，又出现了最低存活率要求的最小P-嫉妒选址模型，跟原来的最大区别是把“嫉妒”定义由原来的不满意变为了满意，所以计算函数也由原来的距离函数变为生还率函数。

3 应急设施选址优化求解

应急设施选址一般有精确算法和非精确算法两种，精确算法适用于相对简单的优化问题，一般能找到准确的最优解，但是随着现场各种复杂情况的出现，精确算法已不能满足需求，因而产生了非精确算法。

3.1 精确算法

对于一些简单的选址，应用精确算法快速准确，如分支界限法经常运用于供血设施的鲁棒选址模型。拟合动态规划算法常常用于救护车选址问题。对无容量限制的设施选址问题求解时，运用分支界限法和分支割平面法。隐枚举-下降算法常用在预防紧急事件上，如应急物流设施选址问题等。

3.2 非精确算法

非精确算法中，最普遍的是经典启发式算法和新型启发式算法，而经典启发式算法又分为紧急搜索法、遗传算法、模拟退火法、蚁群算法和拉格朗日松弛算法 5 种类型。使用紧急搜索算法可以用样本的平均近似值去推测各个待选址的目标函数值，实现了快速搜索大规模场景样本。遗传算法是利用自然进化过程搜索最优解，在发展中又引入了惩罚种群用来表达已经存在的设施点，在算法运行过程中还加入了变异强度。在大城市药物分发设施选址中，一般使用模拟退火算法。

运行时如果加入了变邻域搜索算法等就变成了新型启发式算法。为了增加算法的寻优性能，在应急仓库的选址或救护车位置选址中，在给定期限条件的选址问题求解中利用了量子竞争决策算法，同时把进化博弈论中学习和调整的动态演化思想引入到算法中。结果表明，运用这种方法求解公共卫生应急服务设施点选址问题，算法性能有了显著提高。

两种求解方法都运用了通用优化软件，使用了编程语言编制、算法等。将以上算法总结如表1：

表1 优化算法归类

4 未来研究方向

应急选址方面，因为问题出现的随机和不确定性，所以选址时要关注动态需求，资源连续性消耗问题。如可以把变量由二元变为多元和连续，方向由水平变为多维度等。

求解过程方面，由于现实中的问题规模越来越大，这就要求优化求解的性能要越来越好，可以利用计算机对现有算法进行并行计算的改进，以达到高速度、高效率的目的。

体系研究方面，可以利用多阶段多分辨率迭代计算的方法代替目前的离散选址。选址只是应急体系中的一个问题，选址时要配合其他它问题一起考虑。

应急设施选址问题在满足应急需要的同时，除了要考虑其本身的动态性和不确定性因素外，还要考虑其与其他配套问题的协调，以开展整体应用场景及标准测试用例的研究。