0 概述

大规模紧急事件, 如地震、洪水、恐怖袭击等, 通常毫无预兆, 但其对社会经济带来的影响是巨大的, 这也使针对各类应急服务的需求急剧增加。将有限的应急资源有效分发并满足大众需求可以大幅减少紧急事件带来的损失。一旦发生紧急事件, 地方政府部门需要建立物资分发点或救援设施派遣站点, 例如物资仓库、物资分发中心、应急医疗中心、救护车站点等, 若设施站点未开设在合适的位置, 则会大幅增加资金投入和库存成本并影响服务质量, 更为严重的是, 应急医疗设施选址不当还会导致疾病发病率和事故死亡率升高。因此, 应急设施选址问题一直是学术界的研究热点。

1909年, WEBER率先提出一个仓库选址问题, 其目标是将仓库与一组客户之间的总距离最小化^[1]。此后, 选址理论及其应用在不同的研究领域得到发展, 诸多高校、研究机构及政府部门相关人员考虑各类紧急事件的特点, 有针对性地提出或改进了一系列的选址模型及其优化求解方法。

本文重点研究关于应急设施选址问题的61篇文献, 从应急设施分类、选址模型构建和优化求解方法3个方面进行对比分析, 提出当前研究存在的不足, 并对未来的主要研究方向进行展望, 以期准确把握该领域的最新研究进展, 为突破研究瓶颈提供有益参考。

1 应急设施分类

应急设施需要考虑在应对大规模紧急事件时可能遇到的情况, 例如基础设施网络遭到破坏、服务能力受损、需求不确定等。因此, 对应急设施进行具体的界定并对其选址特点进行分析是非常必要的。本文主要从设施时效性和设施应用领域2个方面对应急设施进行分类。

1.1 设施时效性

应急设施按照时效性可以分为永久应急设施和临时应急设施2类。

1.1.1 永久应急设施

永久应急设施长期存在于固定站点, 在紧急情况下迅速开设或启用并提供应急服务, 属于大规模紧急事件发生前的规划范畴。永久性应急设施的选址决策建立在对所发生事件进行形势预测分析的基础之上, 以便及时提供基础的应急服务, 尽可能减少损失。

1.1.2 临时应急设施

临时应急设施并不长期存在, 而是在发生大规模紧急事件时迅速分析当前情况, 在合适的地点部署展开。因此, 临时应急设施具有设施开设简易、选址决策效率要求高的特点。

1.2 设施应用领域

应急设施按照应用领域可以分为应急医疗设施、应急物流设施和防灾减灾设施3种类型。

1.2.1 应急医疗设施

应急医疗设施包括救护车站点、供血站等。救护车站点主要负责提供必要的急救服务, 并将患者迅速送到就近或指定的医院以获得全面治疗。国外文献中有较多针对救护车站点选址问题的研究, 其研究目标主要有适应急救需求和服务范围的时变性^[2-3]、最小化派遣时间或晚到时间^[4-6]、最大化服务范围^[7]、最大化救治生存率^[8]等。文献[9-10]将救护车分为不同级别, 分别服务不同范围和严重性的紧急事故。文献[11]针对血液本身的时效性及其存储不当会造成浪费的情况, 构建一种旨在对血液供应设施站点数量和选址进行决策的优化模型。

1.2.2 应急物流设施

应急物流设施主要有应急仓库、配送中心等。预先建立应急仓库等储备设施可有效应对陡增的物资需求, 而临时建设的仓库或应急配送中心则负责暂存收到的补给物资并及时分发至需求区域。文献[12]考虑大规模紧急事件可能使设施失效的情况, 构建国家煤炭应急储备中心的选址模型。文献[13]对灾后开设临时仓库所涉及的选址、需求分配、物资和车辆分配进行建模。文献[14-15]在研究应急仓库选址时考虑了仓库受损毁坏、运输受阻的可能性和物资需求的不确定性。文献[16]分析了各临时设施之间的过量资源调配, 力求减少损失。文献[17-18]以汶川大地震应急物资保障过程为算例, 构建应急配送中心的双层规划模型。文献[19]同时考虑应急配送中心和上级中心仓库的选址, 进行两层级人道主义物流网络设计。

1.2.3 防灾减灾设施

在灾害发生时需要将大批受灾民众转移到避难所, 而疏散效率取决于避难所的开设位置及其附近的交通状况。对应急避难所进行合理选址可以使民众在短时间内迅速疏散至就近设施, 这对于灾害控制及救援具有重要意义。文献[20]通过混合整数线性规划建模对避难所选址进行决策, 以更好地应对可能发生的地震灾害, 文献[21]则在考虑避难所选址时考虑了民众撤离疏散是否方便的因素。

1.3 相关文献分析

表 1给出部分文献按应急设施时效性和应用领域的分类情况。国外文献中有较多关于应急医疗设施选址的研究, 尤其是对于救护车站点的研究频次较高, 相比之下, 国内对应急医疗服务的理解大多还停留在单纯靠医院派遣救护车的情况, 对专门的救护车站点缺乏相关的认识。同时, 国内文献中对应急物流设施的研究频次较高, 这是因为近年来发生多起大规模自然灾害, 如2008年汶川大地震^{[14, 17-18]}和2013年雅安芦山大地震^[22]等, 而在救灾过程中暴露出应急物流体系物资存储和分发效率低下的问题, 因此, 国内文献中出现了较多关于应急仓库、临时配送中心选址问题的研究。

此外, 通过对比中外应急设施选址的文献可以发现, 国外文献大多会明确指出具体的应急设施类型, 而国内研究在此方面则较为笼统, 很多文献仅指出是对包括出警中心、医疗中心在内的应急服务设施进行选址, 或只说明是对应急物流设施进行选址而不明确其时效性。但实际上, 不同种类的应急设施对应不同的问题背景, 其选址特点也不尽相同, 设施类型的不明确势必会对研究结果的实用性造成影响, 这是以后研究中需要注意的一个问题。

2 应急设施选址模型

选址问题从地理位置的角度可分为连续设施选址问题和离散设施选址问题^[41]两类, 前者使设施位于计划区域内的任意位置, 后者则从候选站点中选取部分进行建立, 本文所考察的文献都属于离散选址的范畴。设施选址模型通常基于混合整数线性规划构建, 本节根据影响模型目标的因素将其分为基本选址问题、动态选址问题、随机选址问题、鲁棒选址问题和其他选址问题。

2.1 基本选址问题

基本选址问题主要包括基于覆盖的问题和基于中值的问题两类。

2.1.1 基于覆盖的问题

基于覆盖的问题主要包括:

1) 最大覆盖问题。此类问题通常预先定义设施提供服务的最大覆盖范围, 然后对设施位置进行选址, 在预定范围内最大限度地扩展所覆盖的需求。最大覆盖问题通过需求水平的高低对需求点进行重要程度区分。文献[42]在进行医疗应急设施选址研究时, 构建最大覆盖问题的模型以最大化地满足需求。文献[23]与文献[36]将最大覆盖纳入多目标选址问题模型中, 前者用于救护车选址, 后者则是针对救灾物资分发中心的选址。文献[7]在救护车选址常用的遵从表策略基础上, 以最大化期望覆盖为目标, 制定可用救护车数量不同时的救护车选址方案。文献[32]则在选址模型中考虑了多级覆盖和覆盖衰减的情况。

2) 集合覆盖问题。此问题致力于将覆盖所有需求点所需的设施数量最小化, 在集合覆盖问题中, 选址目标是在达到特定需求覆盖水平的情况下, 将设施的数量或总的选址成本最小化。这一问题主要包括两个要点, 一个是特定范围的需求点都能在服务设施的指定服务距离(或派遣时间)内, 另一个是降低选址设施的数量或成本。文献[43]研究了应急抢修点选址的集合覆盖问题, 其约束条件为派遣抢修小组迟到机率小于一定概率。文献[30]对“最后一公里”的应急医疗设施进行选址, 考虑设施容量和服务人数的限制, 尽可能减小设施的数量。文献[35]在研究“平战”两种状态下社会应急资源的布局问题时, 使用集合覆盖的模型对平时状态的供应商位置进行选址。

3) P-中点问题。此类问题是第3类基于覆盖的选址问题, 其目标是在覆盖特定范围需求点的情况下, 将所有需求点与其对应的设施之间的最大距离(或派遣时间)最小化。如果其中的某一设施无法满足对应需求点的需求, 这些需求点会被分配给其他可用的开放设施。此类选址问题的要点是需求点对应的设施分配(或者反过来说, 将设施进行适当选址并分配特定的需求点), 其可称为一种“最小化最大值”问题。文献[5]以时间为衡量标准, 将最小化总派遣时间和最久派遣时间作为模型目标对救护车进行选址。文献[14]对经典的P-中点模型进行拓展, 考虑人口分布、经济状况、交通及部分关键部位的多重覆盖, 尝试对中国国家应急仓库选址进行改善。

2.1.2 基于中值的问题

基于中值的问题是在候选位置中对设施进行选址, 从而使需求点与所分配的设备之间的加权平均距离(时间)成本最小化, 满足此目标的设施选址位置即为整个设施系统网络的中值。因为此类问题对设施选址和分配进行了决策, 所以也可称为位置分配问题, 具体包括如下两个方面:

1) P-中值问题。此问题致力于使设施覆盖的各需求点到设施的加权平均距离最小化, 其在一个设施网络中对一定数量的设施进行选址, 是设施选址中最受欢迎的问题之一。文献[33]研究了应急物资储备库的选址问题, 在不超过储备库最大容量且每库容量各不相同的条件下, 将设施到需求点的总加权距离最小化。

2) 固定费用设施选址问题。此类问题和P-中值问题密切相关, 将设施建立和服务的总成本最小化。文献[40]提出关于应急保护设施选址的双层模型, 在守护者层面使用固定费用设施选址模型, 力求最小化建造设施和迁移设施的开销。

2.2 动态选址问题

基本选址是只考虑一个时间周期的确定性问题, 因其参数固定, 可以只根据给定状况进行一次选址决策, 所以也可称为单一时段选址。然而在现实情况中, 由于环境、需求、服务成本和效率会随时间变化, 设施选址并不能一劳永逸, 反而可能会是一个长期性、持续性的决策过程。因此, 有必要考虑动态选址决策, 即将整体决策周期划分为多个时间段, 并在每个时间段根据当前形势对选址决策做出调整, 从而达到及时跟进的决策效果。在这种情况下, 影响设施开设的因素不仅是地理上的, 还是时间上的。此类问题可建模为动态确定性模型, 假设将选址过程分为T个时段, 每一时段t有m_t个候选站点或候选目标点, 则模型的数学表达如下:

1) 集合:T时段的集合, J候选点的集合。

2) 输入参数:时段t内的候选站点数量m_t, 设施在时段t进行迁移所花费的成本r_t, 时段t内设施迁移至候选点j所花费的运输成本f_tj(x_t, y_t), 在时段t的设施迁移距离d_{t－1, t}。

3) 目标函数:

$ \min \sum\limits_{t=1}^{T} \sum\limits_{j=1}^{m_{t}} f_{t j}\left(x_{t}, y_{t}\right)+\sum\limits_{t=2}^{T} r_{t} z_{t} $

(1)

约束条件:

$ z_{t}=\left\{\begin{array}{l}{0, d_{t-1, t}=0} \\ {1, d_{t-1, t}>0}\end{array}\right. $

(2)

目标函数将位于(x_t, y_t)的设施到目标点j的运输成本、各时段设施迁移成本的总和最小化。约束条件为设施是否随时段改变而迁移的0-1约束, 其中, 2≤t≤T。

在本文研究的文献中, 文献[2-3]根据救护车选址动态性的特点建立救护车的时变选址迁移模型。文献[16]针对应急响应规划构建一种临时分发设施动态选址和资源分配的网络流模型。文献[39]则研究了震后应急物资供应点的多目标动态选址-分配问题。

2.3 随机选址问题

对于带有不确定性因素的选址问题, 随机优化是一种广受欢迎的建模方法, 其在多种专业领域应用广泛且能对现实问题进行良好的表达。随机选址问题可由确定性问题扩展而来, 在模型中包含服从一定概率分布的不确定参数, 这些参数可能既存在于目标函数中也可能在约束条件中。随机选址问题的数学表达如下:

1) 集合:S时段的集合。

2) 决策变量:如果在场景s∈S中需求点i∈I被位于j∈J的设施覆盖, 则决策变量O_ij^s为1, 否则为0;如果需求点i∈I在场景s∈S中被覆盖, 则E_i^s为1, 否则为0。

3) 输入参数:场景s∈S的发生概率P(s)。

4) 目标函数:

$ \max \sum\limits_{i \in I} \sum\limits_{s \in S} P(s) w_{i} E_{i}^{s} $

(3)

约束条件:

$ \sum\limits_{j \in J} x_{j} \leqslant P $

(4)

$ E_{i}^{s} \leqslant \sum\limits_{j \in J} O_{i j}^{s}, \forall i \in I, \forall s \in S $

(5)

$ O_{i j}^{s} \leqslant X_{j}, \forall i \in I, \forall j \in J, \forall s \in S $

(6)

$ O_{i j}^{s}, X_{j}, E_{i}^{s} \in\{0, 1\}, \forall i \in I, \forall j \in J, \forall s \in S $

(7)

式(3)使得在所有网络情况下在一预定距离内的期望总需求最大化。在约束条件中, 式(4)规定开设设施数最多为P, 式(5)强调需求点被覆盖的条件是i∈I在场景s∈S下被至少一个开放设施覆盖, 式(6)确保需求点i∈I在场景s∈S下只能被开放设施覆盖, 式(7)为0-1约束。

文献[16]提出的应急物流配送中心选址-配送模型考虑了需求的不确定性, 将运送车辆物资超载、仓库容量不足的概率纳入约束条件中, 文献[44]提出两阶段随机容错设施选址问题, 将接受服务的顾客假设为随机分布, 并在第2阶段结合可能的场景及相应概率进行考虑, 文献[34]针对自然灾害发生时提供备份库存和保证服务持续性的问题, 对应急储备系统的选址进行研究, 并考虑设施被破坏的发生概率以加强应急储备系统的可靠性。国外文献中的随机选址问题主要与救护车选址迁移模型有关, 考虑的要素包括需求随机性^{[3, 24, 28]}和救护车繁忙(不可用)的随机性^{[3, 25]}。文献[31]在研究救灾物资存储设施的选址时, 考虑了整个设施网络中各链路遭受破坏的可能性。

2.4 鲁棒选址问题

与随机选址问题对应, 还有一种针对不确定性选址问题的方法是鲁棒优化法。在此类问题中, 不确定性因素的概率未知, 因此, 不确定性通过引入不同的离散场景或连续范围来体现。鲁棒优化与随机优化的不同还体现在鲁棒优化的解含有松弛性^[45]。鲁棒选址问题的数学表达如下:

1) 集合:不确定性因素(干扰参数)的集合I, 不确定性因素i∈I所对应的所有可能性的集合U_i。

2) 输入参数:决策变量的向量x, 在向量x下进行选址的成本f₀(x)。

3) 目标函数:

$ \min f_{0}(\boldsymbol{x}) $

(8)

约束条件:

$ f_{i}\left(\boldsymbol{x}, u_{i}\right) \leqslant 0, \forall u_{i} \in U_{i}, 1 \leqslant i \leqslant m $

(9)

式(8)表示从u_i∈U_i所对应的所有可行解中找出成本最小的解x^*。式(9)是针对各不确定性因素所定义的约束, 即对于具体问题中的各个不确定性因素可能都会制定相应约束, 其中, x为各决策变量组成的向量, u_i则是从不确定性因素U_i的所有可能值中任意选取的值。如果集合U_i只有一个元素, 则对应的约束就不存在确定性或不确定性。

此类选址问题对于包含不确定参数的优化问题提供了一些具有可行性的保护措施, 例如, 文献[11]构建了一种用于灾后血液供应设施的鲁棒选址模型。

2.5 其他选址问题

除上述4种选址问题外, 还有部分文献的选址模型属于其他类别。文献[46]构建最小化P-嫉妒模型以体现客户对设施服务的满意度水平差距, 将区域i内客户的不满意度定义为从i区域到所有p服务设施点的函数。而后, 文献[8]构建了有最低存活率要求的最小P-嫉妒选址模型, 将“嫉妒”定义为地区之间客户满意度的差别, 并将目标函数从原来的距离函数转变为生还率函数。此外, 文献[47]研究了不受欢迎设施选址, 即对特定区域内的有害但必需设施(如反应堆、废水处理厂等)进行选址, 使所选设施远离社会公众并尽量集中。因此, 不受欢迎选址模型的目标与上述其他模型相反, 具体体现在以下3个方面:

1) 所选设施到各目标点总距离最大化^[47]。

2) 所选设施在特定范围内能覆盖的目标点最小化^[48]。

3) 所选设施到各目标点的最短距离最大化^[49]。

2.6 模型构建的相关文献分析

表 2给出相关文献按所属选址问题的归类结果。由于部分文献属于多目标或多层模型, 因此一篇文献可能会同时涉及多类选址问题。

确定性的基本选址问题占了现有文献研究内容的大部分, 且与非确定性问题有较多交叉, 这主要是因为非确定性问题大多可由确定性的基本选址问题发展而来, 因此都可以找到对应的基本选址模型。除P-中点问题外, 其他基本选址问题都较受欢迎。同时, 基于覆盖的问题研究频次大于基于中值的问题, 其原因在于前者强调服务范围覆盖的需求量, 后者更强调效率性、最小化平均或总的派送时间/距离, 而紧急情况下很可能没有足够的服务设施可以提供服务, 应急设施的目标应在紧急情况发生时, 尽快对尽可能多的需求点提供服务, 即需求覆盖为先, 其总的派送时间或距离并非是最重要的考虑因素。当然, 在一些双层规划或多目标模型中, 也可以在优化服务覆盖范围的同时考虑最小化派送时间/距离, 例如, 文献[56]在研究突发事件应急设施选址模型时列出了3个目标函数, 即最小化应急设施服务点建设总成本、各候选站点到各需求点的最大距离最小化(体现覆盖的公平性)以及各候选点到达各需求点的总加权距离最小化(体现服务的效率性)。

对于非确定性的选址问题, 国内外都有文献在考虑不确定性因素的基础上对随机选址问题进行研究, 包括需求的不确定性和设施工作状态的不确定性, 前者主要针对紧急情况下未知或不便于预测的需求, 后者则更关注具有破坏性的紧急事件对设施造成损坏, 从而导致无法提供服务的情况。需要注意的是, 对设施工作状态不确定性的考察, 基本都只关注设施完全无法工作或者各设施之间受损概率互相独立的情况^[34]。在现实情况下, 设施可能只是部分受损而导致服务效率下降, 并且各设施间因道路网络相连造成各设施失效概率互相关联, 因此, 随机选址问题的研究还不能很好地满足实际需求。同时, 从表 2可以看出, 相关文献对动态选址问题、鲁棒选址问题和其他选址问题的研究还不够充分。动态选址问题主要进行多时段建模以体现参数的时变性, 文献[2-3]在考察救护车派遣和迁移问题时, 考虑了派遣时间会因路况等因素实时变化的情况, 从而构建了动态模型。此外, 不受欢迎设施的选址问题和其他类型的选址问题具有同样的重要性, 但现有文献对垃圾收集站等必需却受排斥的设施选址问题研究不多, 这说明此类问题还未得到广泛关注。

就各类选址问题的适用场景而言, 在基本选址问题中, P-中点问题只在永久医疗设施和永久物流设施领域有应用, 集合覆盖问题只在临时医疗设施和永久医疗设施中有应用, 而最大覆盖问题作为较常见的基于覆盖的问题, 则在医疗和物流设施中都有应用。P-中值问题和固定费用设施选址问题涉及的设施种类较为类似, 范围也较广, 但是, 固定费用设施选址问题的分布较均衡, 而P-中值问题分布差异较大, 其在临时物流设施选址中的使用明显多于其他类型设施。在非确定性选址问题中, 动态选址模型和鲁棒选址模型应用的设施类型较少且使用这2种模型的文献也较少, 相比之下, 随机选址模型在永久医疗设施、临时物流设施和永久物流设施的选址问题研究中均有应用, 但与基本选址问题所涉及的应用范围相比仍然不够全面。总体而言, 随机、动态和鲁棒选址模型较贴近实际, 有很好的实用性, 但这些非确定性选址模型的应用领域仍有待拓展。需要注意的是, 几乎每一类型的选址问题都有部分文献未指定具体设施种类, 这种情况在集合覆盖问题中尤其突出, 这也再次说明现有文献不太注重具体设施的研究, 对设施选址特点的分析较为笼统。

3 应急设施选址优化求解

应急设施选址模型的优化求解方法大致分为精确算法及非精确算法两大类, 其中, 精确算法能够找到准确的最优解, 适合解决相对简单的优化问题。随着选址问题规模的增大, 精确算法出现难以求得最优解的情况, 从而促进了以启发式算法为代表的非精确算法的应用。

3.1 精确算法

对于计算规模较小的应急设施选址问题, 可使用精确算法求得准确的最优解。在本文所考察的文献中, 文献[11]使用分支界限法对供血设施的鲁棒选址模型进行求解。文献[3]在求解救护车选址问题时使用了拟合动态规划算法, 这是一种较新的能有效解决随机动态问题的方法。文献[58]分别使用分支界限法和分支割平面法求解无容量限制的设施选址问题, 并对两种算法的求解效率进行比较。文献[38]在研究预防紧急事件的应急物流设施选址问题时, 构建了隐枚举-下降算法求解模型。

3.2 非精确算法

非精确算法主要分为经典启发式算法和新型启发式算法。

3.2.1 经典启发式算法

经典启发式算法主要包括紧急搜索法、遗传算法、模拟退火法、蚁群算法和拉格朗日松弛算法5种类型。

在本文所考察的文献中有4篇文献使用了禁忌搜索算法。文献[40]研究双层固定费用选址问题, 在求解时使用CPLEX 11.2优化软件, 选择禁忌搜索算法进行求解。文献[52]使用禁忌搜索算法求解灾后废物清理站点的选址问题。文献[8]为禁忌搜索算法添加了交换记录列表, 并在此基础上求解弗吉尼亚州汉诺威县应急医疗系统选址的公平性问题。文献[29]使用禁忌搜索算法求解随机网络被破坏时的应急设施选址问题, 且在求解过程中利用样本平均近似值估算各候选解的目标函数值, 从而在短时间内实现对一个大规模场景样本的搜索。

遗传算法通过模拟自然进化过程搜索最优解。文献[51]在研究应急设施多重覆盖选址问题时, 利用贪婪技术对标准遗传算法进行改进, 以产生优良解并加快算法的收敛速度。文献[43]在经典遗传算法的基础上构建混合遗传算法, 采用Lambda修复算法对迭代产生的不可行解进行修复, 以满足随机约束, 为了增强种群搜索新的解空间的能力, 在主循环中引入惩罚种群用来代表已开设的设施站点, 并在算法中逐步增大变异强度。文献[7, 52]针对应急设施选址-联运双层规划的特点, 对遗传算法进行两阶段解码的改进。此外, 遗传算法作为一种广泛使用的启发式算法, 出现了很多变种。其中, 非受控排序遗传算法(NSGA-Ⅱ)常用于求解多目标模型, 例如, 文献[33]使用NSGA-Ⅱ算法求解应急物资储备库的多目标优化选址模型, 文献[39]则通过基于矩阵编码与小生境技术的NSGA-Ⅱ算法求解震后应急物资供应点的多目标动态选址-分配模型。

相比之下, 模拟退火算法在所考察文献中的应用缺乏变化与改进。文献[29]在研究生物恐怖袭击下的大城市药物分发设施选址时使用了模拟退火算法, 并与新提出的启发式算法进行比较。

此外, 在应急设施选址问题求解中的经典算法还有蚁群算法和拉格朗日松弛算法。文献[6]在比较遗传算法和蚁群算法的基础上, 选择对后者进行改进以求解上海应急医疗系统选址的效费比问题。文献[54]则使用拉格朗日松弛法, 将目标函数转化为不受任何约束且易于求解的问题, 从而求解选址模型并得到了较好的次优解。

3.2.2 新型启发式算法

除较为经典的启发式算法外, 应急设施选址优化中还使用了一些新型的算法。例如, 变邻域搜索(Variable Neighborhood Search, VNS)算法被用于求解救护车位置选址^[2]和应急仓库的选址研究^[14]。文献[53]利用一种量子竞争决策算法求解给定期限条件的应急设施选址问题, 将进化博弈论中学习和调整的动态演化思想引入到算法中, 使博弈者具备自学习和自进化的能力, 增强了算法的寻优性能。文献[56]利用模拟植物生长的算法求解突发事件应急设施选址问题。文献[30]提出以细菌觅食算法为主体, 将量子进化算法及粒子群优化算法嵌入其中, 形成一种群体智能融合算法, 并用于求解公共卫生应急服务设施点选址问题, 结果表明算法性能有了大幅提高。

3.3 优化求解的相关文献分析

本文主要从优化求解方式、优化算法和测试用例3个维度对相关文献的优化求解方法进行分析。

3.3.1 求解方式

表 3给出相关文献按求解方式的分类情况, 可以看出, 通用优化软件主要包括各版本的GAMS、CPLEX和LINGO, 其直接求解的方法是比较受欢迎的, 此外, 也有文献使用编程语言自行编制算法程序。上述两种方式各有优点, 通用优化软件中的方法较标准, 省去了手动编写程序的过程, 能让使用者把精力集中到建模上, 而使用编程语言自行编制算法则较为灵活, 适用于对现有算法进行一定改进的情况。就编程语言的选择而言, Matlab较为受欢迎, 这主要是因为Matlab具有高效的数值计算功能、完备的计算结果和编程可视化的功能。在计算结果展示方面, 应急设施选址问题主要涉及地形条件、需求分布及设施分布等内容, 对问题可视化描述、选址结果的多样化展示有较高要求, Matlab凭借其本身的绘图功能而占有优势。

3.3.2 优化算法

表 4给出根据选址模型所用的优化算法对文献进行归类的结果。由表 4可知, 在非精确求解中, 启发式方法为常用的求解方法, 主要包括禁忌搜索法、遗传算法、模拟退火法、蚁群算法和拉格朗日松弛法。此外, 也有文献使用精确求解方法, 主要包括分支界限法、动态规划法、分支割平面法和隐枚举算法等。相较而言, 非精确算法可提高求解效率, 适用于处理较大规模的问题, 并且有利于对问题进行灵敏度分析。总体来讲, 非精确算法更受欢迎, 并逐渐成为设施选址问题优化求解的主流方法。就各优化算法的适用选址模型而言, 几种精确算法均只有一篇相关文献, 表明精确算法由于性能限制导致其受欢迎程度下降。值得注意的是, 使用分支界限法和动态规划法的2篇文献分别研究了鲁棒选址问题、随机选址问题和动态选址问题, 这说明精确算法对于不确定性选址问题仍然适用。在非精确算法方面, 蚁群算法、拉格朗日松弛法都只用于求解集合覆盖问题的选址模型, 而另外3种经典算法, 即禁忌搜索法、遗传算法和模拟退火法所对应的文献数量较多, 表明上述方法较受欢迎, 但其多用于研究确定性选址模型, 仅有4篇文献(文献[15, 31, 34, 43])涉及随机选址问题, 这表明经典算法在不确定性选址问题中的应用研究仍不够充分。至于新型启发式算法, 因其本身发展时间较短, 在选址问题中的应用不多, 都只是探索性地用于求解确定性选址问题, 其中, 模拟植物生长算法求解的选址模型具有3个目标^[56], 体现出该算法在求解多目标选址问题时的有效性。

3.3.3 测试用例

测试用例按数据的真实性可分为2种, 一种使用随机生成数据或标准的测试数据, 其相对方便, 许多现成的测试用例可从互联网上直接下载, 另一种则使用真实案例或历史记录的真实数据, 这需要做大量持续性的数据收集工作, 但该数据更贴近实际情况, 也更具可靠性。根据两种类型的测试用例对相关文献进行归类, 结果如表 5所示。

出于应用真实性的考虑, 同时也得益于求解算法性能的提升(尤其是启发式算法应用的增多), 使用真实案例数据构造测试用例的文献达到25篇, 其中完全使用假设数据的文献为17篇, 算例规模也越来越大。需要注意的是, 现有文献在使用真实数据构造算例的过程中仍然存在一定程度的假设, 主要体现在以下两个方面:

1) 需求点的聚集, 即在需求点过多时, 将一定范围内的需求点聚合为一个需求点, 并计算出此聚合点总的需求量。

2) 使用行政区划、人口等地理环境数据, 据此对需求进行估计。

同时还应指出, 使用“真实”数据并不一定就是最可靠的。如前所述, 真实数据的采集是一项繁重的工作, 虽然一般具有较高的可信度, 但在灾害等大规模紧急情况下, 数据采集会因为潜在的危险变得十分困难, 再加上通信不畅等因素, 数据的有效性、准确性会受到一定影响, 甚至完全无法采集。

4 未来研究方向

经过几十年的发展, 大批学者针对各类应急设施在实际选址中不同的侧重点提出了多种选址模型, 也将诸多精确、非精确算法应用于选址模型的求解过程中。本文针对应急设施选址问题未来的研究方向提出几点建议:

1) 选址模型方面, 首先应更关注不确定性。未来研究应当更关注多时间阶段下出现动态需求、资源连续性消耗的情况, 以及服务因遭破坏而中断、各设施服务能力相互关联的选址问题。同时, 也可对现有的基本选址模型进行改进, 加入随机条件使选址问题更好地体现出大规模紧急事件的不确定性。其次要考虑更多的选址影响因素, 应急设施选址会受空间、环境效益、经济效益及服务满意度等诸多因素的影响, 将这些因素体现在目标函数中可使模型更贴近实际, 模型的表示也应更加准确。例如, 可将约束中的二元变量替换为连续变量, 包括将覆盖问题中二元覆盖变为水平/质量连续变化的覆盖, 以及将设施中断/失效变为部分失效以体现服务质量因遭破坏而受到的不同程度的影响。

2) 优化求解方面, 面对越来越大的数据量和日益复杂的模型, 优化求解的性能要求越来越高, 应急设施选址的实时决策面临计算时间长、效率低下的问题。近年来出现的新型启发式算法, 如生物地理学优化算法、布谷鸟搜索、水稻田算法、仿生算法、烟花算法等都体现出较好的全局搜索能力, 在各类工程优化问题中具有良好的应用前景。然而, 在应急设施选址模型求解中对此类算法的使用较少, 也缺乏针对具体问题的改进, 因此, 在未来的研究中可以考虑尝试使用较新颖的启发式算法来求解模型。同时, 还应当注意对现有算法的改进与混合创新, 例如可以尝试对现有算法进行并行计算的改进以提高计算效率, 或者在多目标优化中对重要目标设定一定的宽容量, 以保证多目标优化的有效性。

3) 体系研究方面, 当前考虑的设施选址多为离散选址问题, 区域栅格化的过程存在分辨率设置的问题。合适的分辨率是平衡求解精度和计算速度的关键, 可以通过使用多阶段多分辨率迭代计算的方法解决该问题, 但如何避免因初始分辨率过低而陷入局部最优仍是亟待解决的问题。此外, 设施选址并非一个孤立的问题, 而是应急反应体系中的一个环节, 因此, 在研究中可以考虑将应急设施选址和物资预储、设施分配、资源分配和路径规划等优化行为结合起来, 从而构建符合应急物流反应过程的多阶段规划模型。另外, 还应有针对性地建设面向整个应急反应体系的测试用例标准库, 为全领域的研究工作提供统一、规范的数据共享环境, 以便于研究工作的开展以及研究成果的分析和比较。

5 结束语

本文对应急设施选址问题的相关文献进行研究, 分别从应急设施分类、选址模型构建、优化求解方法3个方面展开分析评述。应急设施选址问题在现实中有着广泛应用, 近年来相关模型和算法研究取得了诸多进展, 但还不能完全满足现实需求。为此, 本文指出当前研究中存在的问题, 并在此基础上对未来的研究方向进行展望。整体而言, 应急设施选址方法在满足不同现实需求方面还有很大的改进空间, 主要表现为选址模型需要考虑更多的动态性、不确定性因素, 模型求解时应尝试更多的新型优化算法或改进的混合算法, 选址问题可以与应急物流相关的其他问题进行综合考虑, 开展整体应用场景以及标准测试用例的研究等。