摘 要：根据模型参数的类型及建模所使用的方法，将覆盖选址问题划分为确定性覆盖和概率覆盖两个大类。在确定性覆盖问题中，重点分析了集合覆盖和最大覆盖两个子类型;在概率覆盖模型中，则回顾了概率集合覆盖、最大可获得性覆盖和最大期望覆盖三种重要的概率覆盖问题。在以上划分的基础上，给出了各种覆盖选址问题典型的数学规划模型，重点分析了上述模型的假设条件及其发展的内在逻辑，并对相关的问题作了评述。
关键词：综述;覆盖;选址;分类
中图分类号：F250 文献标识码：A
Abstract： The covering facility location problem is spanided into deterministic and probabilistic type covering model according to the parameter and methods used. The set covering and maximal covering location problem in the deterministic model and the probabilistic set covering， the maximal available covering and maximal expected coverage location problem in the probabilistic model are reviewed in the time order， respectively. Based on the above classification， detailed information about classic location mathematical programming models， assumptions and their development logic of each type are given and analyzed as well as review on some important issues.
Key words： review; covering; location; classification
0 引 言
选址问题作为一项战略决策，其影响是深远和持久的。根据决策者的目标和所面临的约束条件的不同，选址问题可以分为不同的种类，较常见的有：单一设施点选址（Single Facility Location），多设施点选址（Multi-facility Location），层次性选址（Hierarchical Location），p中值问题（p-Median），p中心问题（p-Center），覆盖问题（Coverage）等。在三大经典选址模型中，覆盖类选址是选址问题中的一个重要分支，它已被广泛的应用到应急服务设施以及公共设施点的选址问题中。
君[26]，葛春景等[27]，他们主要研究了最大覆盖选址模型的一些应用及其求解算法。应用排队论来处理覆盖选址问题的相关研究主要有胡丹丹[28-29]，鹏等[30]。可以发现，同国外的研究相比，国内关于覆盖选址问题的研究相对不足，相关的综述研究也较少。
从时间上来看，Schilling和Farahani等人的综述研究几乎覆盖了从覆盖选址模型最初提出到2011年间的所有相关文献。但是，由于分类标准的不同和研究文献的零散性，要全面了解覆盖选址问题的发展以及不同覆盖模型之间的内在关系就比较困难，尤其是概率选址问题的提出及应用。
鉴于此，以下从各个模型出现的时间顺序以及所使用的方法将覆盖选址问题其划分类别，重点分析模型假设条件的不断改进和不同模型之间的内在联系，使读者能够从整体上把握覆盖选址模型的发展逻辑和各种重要的类别细分。同时，对覆盖选址相关的重要文献做相关的评述，为今后研究覆盖选址问题提供便利。
1 覆盖选址问题的分类
选址问题按照不同的标准可以划分为不同的类型，较为常见的分类标准有以下几种：①设施点的数目;②潜在设施点的空间布局;③目标函数的数量;④设施点是否有容量限制;⑤设施点受顾客偏爱的性质;⑥设施点之间是否存在等级关系;⑦模型参数是确定还是随机的，等等。众多的划分标准，使得如何对选址问题进行阐述本身就是一个困难的问题，不同的标准体现了研究重点差异。王非等[6]人按照时间节点将选址研究划分为三个阶段：零散研究阶段（1909～1960s）;系统研究阶段（1960s ～1980s）;不确定性研究阶段（1980s～至今）。按照时间维度将选址研究分为不同的阶段是很自然的选择，但是以下将采用另一种更为细致的标准来介绍覆盖选址模型的分类和研究进展。
按照模型参数（或者约束条件的形式）是否确定，覆盖选址问题可以分为确定性选址模型和概率选址模型两大类。对于概率模型，按照所应用的方法，进一步将划分为一般概率模型和应用排队论的概率模型。对于其他的子类别，则主要通过目标函数或者模型之间的相互关系进一步进行细分，具体结果如图1。
覆盖选址问题■
图1 覆盖选址问题分类
鉴于篇幅限制，本文主要分析确定性覆盖模型和概率模型中的一般概率覆盖问题，并且重点回顾国外关于覆盖选址问题的相关研究状况。对于选址问题其他的分类方法和相关介绍，可以进一步参考文献[31-33]。
2 分类评述
对于大多数的覆盖类选址问题，可以叙述如下：已知需求点集合和潜在的设施点集合，对于给定的服务半径，①当设施点的数量无限制时，要求寻找一种设施点的配置方式使得使用最少的服务设施以覆盖所有的需求点;②当给定设施点数量时，要求找到一种设施点配置方式使得其覆盖的需求点尽可能的多。其中情形一为集合覆盖问题，而情形二为最大覆盖问题。当然，对于如何确定设施点能够覆盖需求点，不同的方法又会得到其他的形式，比如，变半径覆盖，概率覆盖以及多重覆盖等。同时，目标函数和约束条件的稍微变化又可以得到不同扩展类型的覆盖问题。下文主要按照图1的划分对重要的覆盖选址问题进行分类评述，对于每一类问题，同时给出基本的数学规划模型。
由于基本覆盖模型的应用较为广泛，其符号记法一般也稍有差异，在介绍各个模型之前，先对部分符号做如下规定：
i： 需求点标号;
j： 设施点标号;
V： 需求点集合;
W： 设施点集合;
r： 服务半径;
p： 允许建立的设施点数量;
h■： 需求点i的需求量;
c■： 设施点j的固定建造成本;
d■： 需求点i到设施点j的距离;
N■=j：d■≤r： 能够对需求点i提供服务的设施点集合;
M■=i：d■≤r： 设施点j可以服务的需求点集合;
X■： 设施点j安排的服务设施数量，X■∈N;
x■=■;
y■=■。
2.1 确定性覆盖模型
2.1.1 集合覆盖（Location Set Covering Problem， LSCP）
LSCP最早由Toregas[8]等人提出，主要用于解决应急服务设施点的选址问题，它要求建立最少的服务设施点以覆盖所有的需求点，其模型如下（LSCP）：
min■x■ （1）
x■∈0，1， ？坌j∈W （3）
min■c■x■ （4）
s.t.（2）～（3）
对于此模型，Roth[35]最早设计了计算机求解算法。注意到，LSCP是WSCP所有设施点成本相同时的特殊情况。就LSCP的起源，一般认为Hakimi是该问题的最早提出者[7，16]，在1965年的一篇论文中，Hakimi[34]研究了网络图上的顶点覆盖问题，并考虑了在给定距离约束的条件下，如何安排最少数量的警察以覆盖所有高速公路网络上的顶点，只是当时所建立的模型并不是标准的覆盖选址模型。
1969年，Roth[35]提出了求解覆盖问题局部最优解的计算机算法，由于其目标函数是加权和最小形式，因此并不严格属于集合覆盖问题（Set Covering Problem， SCP），而是一般意义上的加权集合覆盖问题（Weighted Set Covering Problem， WSCP）。另外，由于该文献最初并不是基于选址问题而提出，这就造成后来人们在回顾LSCP的研究文献时常常将Roth的研究工作忽略。 1971年，Toregas等[8]正式建立了应急服务设施的LSCP数学规划模型，当服务设施点具有相同的成本时，目标函数转化为建立最少的服务设施点以覆盖所有的需求点。事实上，这是Roth模型中目标函数权系数相同的特殊情况，但是在选址理论中，一般认为Toregas等人是LSCP数学模型的最早提出者。
LSCP模型建立以后，人们面临着如何有效求解的问题。受Roth提出的求解算法的启发，在接下来的两年时间里，Toregas和ReVelle[9-10]又分别提出了精确求解LSCP的行和列简化算法（Row and Column Reduction）。Vasko和Wilson[36]提出了求解LSCP①的启发式算法，其结果表明：在同等条件下，LSCP比WSCP更难于求解。
Alminana和Pastor[37]提出了一种改进形式的代理启发式算法（Surrogate Heuristic）用以求解LSCP。Brotcorne等[19]提出了求解需求点离散、潜在设施点连续的大规模覆盖选址问题的快速启发式算法。
以上等人的研究大多属于标准的SCP，要覆盖的目标对象为网络或者平面上的点集。对于其他形式的集合覆盖问题，Boffey和Narula[38]，Gendreau等[39]分别提出了路径覆盖和回路覆盖问题，Current和Storbeck[40]研究了有容量约束的LSCP，Murray
等[41]提出了另外两种隐式和显式的LSCP模型。
在现实生活中，决策者往往面临着有限的预算约束，而LSCP模型为了覆盖所有的需求点，可能导致建立的设施点过多从而超出预算。因此，人们又提出了覆盖选址问题的另一个模型：最大覆盖选址模型。
1974年，Church和ReVelle[11]提出了MCLP模型：在给定设施点数量的条件下，如何安排设施点的位置使得覆盖的需求量尽可能的多，其具体形式如下：
max■h■y■ （5）
s.t. ■x■≥y■， ？坌i∈V （6）
■x■≤p （7）
x■=0，1， ？坌j∈W （8）
y■=0，1， ？坌i∈V （9）
其中目标函数（5）式最大化覆盖的需求量;约束（6）式是需求点被覆盖时应满足的条件;约束（7）式规定了建立设施点的最大数量;约束（8）和（9）式为变量取值类型。
同年，White和Case[42]以部分覆盖模型的方式提出了一种特殊的最大覆盖问题，即所有需求点具有相等的需求量，因此，目标函数转化为覆盖尽可能多的需求点（而非需求点的需求量），并分析了该模型和SCP模型的关系。Klastorin[43]证明了MCLP可以转化为一般指派问题进行求解。
在实践应用方面，MCLP模型主要用于解决应急服务设施的选址问题。Bennett等[44]应用MCLP模型，研究了边远地区的医疗资源的选址问题;Eaton等[45-46]将MCLP模型应用到现实中的应急医疗车辆的选址问题中。Richard等[47]应用MCLP模型研究了保护区的选择问题，最大化能够覆盖的物种数量。Li等[48]综述了覆盖模型在应急服务设施选址和规划方面的应用，Chung[49]综述了覆盖选址模型在其他方面的应用，如数据提取、统计分类和认知过程建模等。
2.2 概率覆盖模型
如果考虑到所有的不确定性因素，可提供服务的设施点数量、需求点的位置和需求量以及服务单位到达需求点的时间等都有可能是随机变量。备用覆盖模型的提出，考虑了服务设施点可能因处于繁忙状态而不可获得这种情形，因此它提出用额外的服务设施来确保所有需求尽可能得到满足。由于没有具体考虑服务设施点的繁忙状态，这种处理方法属于隐式考虑服务设施点繁忙的模型。就应急服务设施点的选址问题而言，多数研究文献重点关注于服务设施因处于繁忙状态而造成的不可获得性，处理方法上主要有概率模型（不同服务设施点繁忙状态相互独立）和排队论模型。
2.2.1 最大期望覆盖（Maximal Expected Coverage Location Problem， MEXCLP）
在研究服务设施点经常处于繁忙状态的概率覆盖选址问题时，一个重要的问题就是服务设施点繁忙概率的确定。一般有两种情况：系统水平的繁忙概率（system-wide busy fraction）和区域水平的繁忙概率（region-specific busy fraction），前者假定系统内所有的服务设施点具有相同的繁忙概率，而后者假定不同服务区域的设施点繁忙情况各不相同。如果只考虑概率意义下能够得到服务的需求，就得到了期望类型的覆盖选址模型。
通过假定系统内所有的服务设施具有相等的繁忙概率，Daskin[60]最早介绍了期望覆盖模型在应急医疗服务系统中的应用。后来基于同样的假设，Daskin[61]又建立了最大期望覆盖选址问题的整数规划模型，目标函数最大化覆盖的期望值，并设计了求解的启发式算法，其形式如下：
max■■1-qq■h■y■ （10）
s.t. ■y■≤■X■， ？坌i∈V （11）
■X■=p （12）
y■∈0，1， ？坌i∈V， k=1，…，p （13）
X■=0，1，…，p， ？坌j∈W （14）
其中：
q： 服务设施繁忙的概率;
y■=■。
期望覆盖模型考虑了服务设施的繁忙情形，但是并没有试图提高系统的可靠性。Fujiwara[62]将MEXCLP模型应用到城市的救护车辆布局上，设计了求解问题的近似算法并通过模拟对近似解进行了分析。Daskin等[63]将多重备用覆盖模型和MEXCLP结合起来，建立了概率形式的备用覆盖模型，从备用覆盖的角度考虑了服务的可靠性。Sorensen和Church[64]考虑了服务的可获得性，建立了有区域可靠性的MEXCLP模型，目标函数最大化在保证服务质量的情况下所能够覆盖的需求量。Chuang和Lin[65]建立了有双重覆盖标准的应急医疗救护车辆MEXCLP模型。
Repede和Bernardo[66]考虑了需求随时间变化的MEXCLP，并将其同决策支持系统相结合应用到实例城市的应急医疗服务系统中，其结果表明应急反应时间可以减少36%。McLay[67]考虑了有两种不同服务设施、不同顾客类型的MEXCLP模型。Rajagopalan等[68]设计了求解MEXCLP的三种启发式算法：遗传算法，禁忌搜索和模拟退火，并使用方差分析技术对以上三种算法的性能进行了分析。根据模型是否考虑服务的可获得性和反应时间这两种因素的随机性，Erkut等[69]分析了MCLP和MEXCLP等五类覆盖模型在救护车选址问题中的差异。 2.2.2 概率集合覆盖（Probabilistic Location Set Covering Problem， PLSCP）
通过对基于区域的服务繁忙概率进行估计，ReVelle和Hogan[70]提出了概率形式的集合覆盖选址模型。在计算需求点i附近的服务设施点的繁忙概率时，他们使用以下计算公式：
q■=■ （15）
其中：
■： 单个服务的平均持续时间（小时）;
f■： 需求点k的服务请求率（个/天）。
如果记F■=■・■f■/24，则（15）式可以改写为：q■=F■■X■。要使需求点i能够得到服务的概率不小于给定的值α，则应有：
1-F■■X■■≥α （16）
记b■是使得（17）成立的最小整数，
1-F■b■■≥α （17）
由此可以得到基于区域水平估计的概率集合选址模型：
min■X■ （18）
s.t. ■X■≥b■， ？坌i∈V （19）
X■∈N， ？坌j∈W （20）
上述等人的研究主要考虑了服务设施因繁忙而导致的服务不确定性。对于一般机会约束形式的概率集合覆盖问题，Beraldi和Ruszczynski[73]提出了约束右端项为0～1随机变量的概率集合覆盖模型，其中约束成立的联合概率不小于给定的值p，在p有效点的基础上提出了求解所有p有效点的枚举算法和分支定界算法。在Beraldi和Ruszczynski 提出的模型基础上，Saxena等[74]又建立了在约束左端项为0～1矩阵时的非线性整数规划模型，进一步给出了两种等价形式的线性规划化模型，并设计了基于线性规划的分离算法。Hwang[75]将上述概率集合覆盖模型应用到物流系统的设计中，在系统设计的第一阶段用于解决仓库或分销中心对客户的覆盖问题。
考虑到服务设施的繁忙情形，概率集合覆盖要求被覆盖的需求点必须在给定的服务水平下能够得到服务。显然，这比LSCP模型假定所有被覆盖的需求任何时候都可以得到服务更符合实际，尤其是对于经常处于繁忙状态的系统而言。
2.2.3 最大可获的性覆盖（Maximal Availability Location Problem， MALP）
同集合覆盖模型一样，概率集合覆盖模型为了在给定的服务水平下覆盖所有的需求，它同样会安排较多的服务设施点。如果给定了可以使用的服务设施数量，要在保证服务水平的条件下覆盖尽可能多的需求，就得到了对应于MCLP的概率模型。根据服务繁忙概率的不同假设，ReVelle和Hogan[76]分别使用系统和区域水平的服务繁忙率，建立了有可靠性水平保证的最大可获得性选址问题模型MALP I和MALP II。其中前者假定系统内所有的服务设施具有相等的繁忙概率，而后者假定不同的需求区域具有不同的繁忙概率。由于前者是后者的特殊情形，因此只考虑MALP II，其形式如下： max■h■y■ （21）
s.t. ■y■≤■X■， ？坌i∈V （22）
y■≤y■， ？坌i∈V， k=2，…，b■ （23）
■X■=p （24）
X■∈N， ？坌j∈W （25）
ReVelle和Marianov[77-78]将MALP模型扩展到两种不同类型的服务设施，考虑了消防系统中引擎和卡车这两种服务设施的共同选址问题，只有当每种服务设施可获得的概率或者其联合概率大于事先给定的值时，需求才能够被覆盖。
Chiyoshi和Morabito[79]设计了求解扩展的MALP模型的禁忌搜索算法，并同模拟退火算法的结果进行了比较：对于小规模的问题，模拟退火算法的效果较好;而大规模的问题，禁忌搜索算法所得到的解较好。
Erkut等[80]从批判的角度指出了有概率水平保证的可获得性覆盖或者可靠性覆盖模型在救护站和应急车辆选址中所存在的问题。首先概率模型比确定性模型对数据的要求更高，即使是将机会约束线性化处理以后，这种问题依然存在;其次是可靠性水平的确定比较主观，没有一个合理的方式来选择这一概率值。因此，他们认为应当使用期望类型的覆盖模型来解决应急服务设施的选址问题。
3 结 论
覆盖模型的提出，为解决以应急服务为主的设施点选址提供了科学的方法。最先提出的覆盖选址模型是LSCP和MCLP，早期的覆盖问题其模型参数都是确定性的，并且只要需求点位于事先规定的服务半径内，那么所有的需求点都可以得到服务。但是，对于一些经常处于繁忙状态的服务系统而言，服务设施点并不总是能够对其服务半径内的需求点提供服务。考虑到这种情况，研究领域又提出了概率覆盖模型。在概率选址问题中，根据假设条件和所使用的方法，可以进一步划分为一般概率覆盖和排队覆盖模型。一般概率覆盖模型假定各个服务设施点是否繁忙是相互独立的，从而能够从一般概率意义上来分析所研究的问题。服务设施相互独立假设使得模型的构建不至于太复杂、求解不过于困难，这对早期的理论应用有重要的价值。在研究方法上，也为后来运用排队论模型提供了框架和自然的过渡。
然而在现实生活中，服务设施在提供服务时面临排队是一种十分普遍的现象，如医院就诊、120救护车辆提供救援等。多数情况下，服务设施点在一个系统内工作，其运行并不是相互独立的，由此来看，一般概率覆盖模型的假设需要进一步改进。基于排队论的覆盖选址模型，可以更精确地反映此类服务设施在现实中的运行情况。所以，进一步研究工作可以分析排队覆盖选址问题在理论和现实两个方面的发展及应用。
注：①在其文献中称之为Minimum Cardinality Set Covering Problem（MCSCP），也有文献称为Unicost Set Covering Problem。
参考文献：
[4] ReVelle C S， Eiselt H A. Location analysis： a synthesis and survey[J]. European Journal of Operational Research， 2005，165：1-19.
[5] 杨丰梅，华国伟，邓猛，等. 选址问题研究的若干进展[J]. 运筹与管理，2005，14（6）：1-7.
[6] 王非，徐渝，李毅学. 离散设施选址问题研究综述[J]. 运筹与管理，2006，15（5）：64-69.
[8] Toregas C， Swain R， ReVelle C， Bergman L. The location of emergency services facilities[J]. Operations Research， 1971，19：1363-1373.
[10] Torgas C， ReVelle C. Binary logic solutions to a class of location problems[J]. Geographical Analysis， 1973，5：145-155.
-111.
[12] Pirkul H， Schilling D. The capacitated maximal covering location problem with backup service[J]. Annals of Operations Research， 1989，18：141-154.
-55.
[18] Michael O B， Feng L L. A Reliability Model Applied to Emergency Service Vehicle Location[J]. Operations Research， 1993，41（1）：18-36.
[22] Sorensen P， Church R. Integrating expected coverage and local reliability for emergency medical services location problems[J]. Socio-Economic Planning Sciences， 2010，44：8-18.
[24] 马云峰. 网络选址中基于时间满意的覆盖问题研究[D]. 武汉：华中科技大学（博士学位论文），2005.
[25] 翁克瑞，杨超. 多分配枢纽站最大覆盖选址问题[J]. 工业工程与管理，2007（1）：40-44.
[26] 殷带君. 广义最大覆盖模型在应急服务设施选址中的应用研究[D]. 济南：山东大学（硕士学位论文），2007.
[29] 胡丹丹. 拥塞型设施的选址问题研究[D]. 武汉：华中科技大学（博士学位论文），2011.
[32] Daskin M S. Network and discrete location： models， algorithms and applications[M]. New York： Wiley Interscience， 1995.
[33] Farahani R Z， Hekmatfar M. Facility location： concepts， models， algorithms and case studies[M]. Berlin： Springer-Verlag， 2009.
[35] Roth R. Computer solutions to minimum cover problems[J]. Operations Research， 1969，3：455-464.
[37] Alminana M， Pastor J T. An adaptation of SH heuristic to the location set covering[J]. European Journal of Operational Research， 1997，100：586-593.
-342.
[39] Gendreau M， Laporte G， Semet F. The covering tour problem[J]. Operations Research， 1997，45（4）：568-576.
[45] Eaton D， Daskin M， Simmons D， et al. Determining emergency medical service vehicle deployment in austin， texas[J]. Interfaces， 1985，15：96-108.
[49] Chung C H. Recent applications of the maximal covering location planning （M.C.L.P.） model[J]. The Journal of the Operational Research Society， 1986，37（8）：735-746.
[52] Drezner Z， Wesolowsky G O， Drezner T. The Gradual Covering Problem[J]. Naval Research Logistics， 2004，51：841-855.
[53] Berman O， Kalcsics J， Krass D， et al. The Ordered Gradual Covering Location Problem on a Network[J]. Discrete Applied Mathematics， 2009，157：3689-3707.
[54] Eiselt H A， Marianov V. Gradual location set covering with service quality[J]. Socio-Economic Planning Sciences， 2009，43：121-130.
[55] Berman O， Drezner Z， Krass D. Generalized coverage： New developments in covering location models[J]. Computers Operations Research， 2010，37：1675-1687.
[61] Daskin M S. A maximum expected covering location model： Formulation， properties and heuristic solution[J]. Transportation Science， 1983，17：47-70.
[62] Fujiwara O， Makjamroen T， Gupta K. Ambulance deployment analysis： a case study of Bangkok[J]. European Journal of Operational Research， 1987，31（1）：9-18.
[63] Daskin M S， Hogan K， ReVelle C. Integration of multiple excess backup and expected covering models[J]. Environment and Planning B： Planning and Design， 1988，15：15-35.
[64] Sorensen P， Church R. Integrating expected coverage and local reliability for emergency medical services location problems[J]. Socio-Economic Planning Sciences， 2010，44：8-18.
[65] Chuang C， Lin R. A maximum expected covering model for an ambulance location problem[J]. Journal of the Chinese Institute of Industrial Engineers， 2007，24（6）：468-474.
[66] Repede J F， Bernardo J J. Developing and validating a decision support system for locating emergenct medical vehicles in louisville Kentucky[J]. European Journal of Operational Research， 1994，75（5）：567-581.
[67] McLay L A. A maximum expected covering location model with two types of servers[J]. IIE Transactions， 2009，41：730-741.
[68] Rajagopalan H K， Vergara F E， Saydam C， et al. Developing effective meta-heuristics for a probabilistic location model via experimental design[J]. European Journal of Operational Research， 2007，177：83-101.
[69] Erkut E， Ingolfsson A， Sim T. Computational comparison of five maximal covering models for locating ambulances[J]. Geographical Analysis， 2009，41：43-65.
[73] Beraldi P， Ruszczynski A. The probabilistic set-covering problem[J]. Operations Research， 2002，50（6）：956-967.
[75] Hwang H. Design of supply-chain logistics system considering service level[J]. Computers and Industrial Engineering， 2002，43：283-297.
[77] ReVelle C， Marianov V. A probabilistic FLEET model with inspanidual vehicle reliability requirements[J]. European Journal of Operational Research， 1991，53：93-105.
[79] Chiyoshi F Y， Morabito R. A Tabu search algorithm for solving the extended maximal availability location problem[J]. International Transactions in Operational Research， 2011，18：663-678.
[80] Erkut E， Ingolfsson A， Budge S. Maximum availability/reliability models for selecting ambulance station and vehicle locations： a critique[Z]. 2008.
