摘 要：根据模型参数的类型及建模所使用的方法，将覆盖选址问题划分为确定性覆盖和概率覆盖两个大类。在确定性覆盖问题中，重点分析了集合覆盖和最大覆盖两个子类型;在概率覆盖模型中，则回顾了概率集合覆盖、最大可获得性覆盖和最大期望覆盖三种重要的概率覆盖问题。在以上划分的基础上，给出了各种覆盖选址问题典型的数学规划模型，重点分析了上述模型的假设条件及其发展的内在逻辑，并对相关的问题作了评述。
关键词：研究生论文发表,综述,覆盖,选址,分类
Abstract： The covering facility location problem is divided 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)等。在三大经典选址模型中，覆盖类选址是选址问题中的一个重要分支，它已被广泛的应用到应急服务设施以及公共设施点的选址问题中。
目前，国内外关于一般选址研究的文献相对较多，其中综述性的文献就有：Barbaros等[1]，Owen和Daskin[2]，Hale和Moberg[3]，ReVelle和Eiselt[4]，杨丰梅等[5]，王非等[6]，以上文献从总体上对选址问题的研究进展作了介绍与总结。覆盖选址相关的早期重要文献主要有：Hakimi[7]，Toregas等[8]，Toregas和ReVelle[9-10]，Church和ReVelle[11]，Pirkul和Schilling[12-13]，Hogan和ReVelle[14]，这些文献对推动覆盖选址问题的研究有重要作用。
Schilling等[15]对1991年以前的覆盖选址问题作了综述研究。后来，Farahani等[16]对1991年以后至2011年之间与覆盖相关的选址文献作了大量的综述性研究。通过对比这两篇综述所分析的目标文献数量，可以发现：20世纪90年代以后在理论上出现了大量研究覆盖选址问题的文献，其中与应急服务设施相关的有：Current和Kelly[17]，Michael和Feng[18]，Brotcorne等[19-20]，Daskin和Dean[21]，Sorensen和Church[22]等。纵观国内，覆盖选址方面的研究文献主要有：马云峰[23-24]，翁克瑞、杨超[25]，殷代
君[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： 服务半径;
2.1 确定性覆盖模型
2.1.1 集合覆盖(Location Set Covering Problem， LSCP)
其中目标函数(1)式要求建立的服务设施点数量最小;约束(2)式规定，对每一个需求点，至少有一个设施点可以对其提供服务;(3)式是变量取值类型约束。在上述LSCP模型中，如果考虑不同设施点的成本因素，要使建造成本最小，则可以得到加权集合覆盖模型(WSCP)：
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模型为了覆盖所有的需求点，可能导致建立的设施点过多从而超出预算。因此，人们又提出了覆盖选址问题的另一个模型：最大覆盖选址模型。
2.1.2 最大覆盖(Maximal Covering Location Problem， MCLP)
1974年，Church和ReVelle[11]提出了MCLP模型：在给定设施点数量的条件下，如何安排设施点的位置使得覆盖的需求量尽可能的多，其具体形式如下：
其中目标函数(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]综述了覆盖选址模型在其他方面的应用，如数据提取、统计分类和认知过程建模等。
确定性覆盖模型在应用过程中也存在一定的问题，最为主要的便是覆盖半径的确定。早期的文献一般是规定一个事先给定的半径，在此半径内可以完全覆盖，否则不覆盖。因此，这种覆盖方法也被称为0～1覆盖。针对这种两元划分标准，后来的研究文献分别提出了变半径覆盖[50]、逐渐覆盖[51-54]等扩展模型。Berman等[55]对以上两种一般的覆盖模型以及合作覆盖模型做了分类综述。 早期覆盖模型的另一个缺陷是：只要需求点位于设施点的覆盖半径内，任何情况下服务设施点都可以对需求点提供服务。这种假设显然对于那些服务设施点经常处于繁忙状态的系统过于严格。因此，后来提出了备用覆盖和合作覆盖模型来提高服务水平。如Hogan和ReVelle[56]较早地提出了用额外一个设施点作为备用覆盖的研究思路并介绍了其应用;Pirkul和Schilling[12]考虑了有工作能力和备用服务的应急服务设施选址问题;Curtin[57]建立了警察巡逻区域的最大覆盖以及备用覆盖模型，以上等研究只考虑一级备用覆盖。Narisimhan等[58]建立了有容量约束和不同等级的备用覆盖模型，Berman[59]提出了位于平面上、并且服务设施点发出的“信号”能够因叠加而增强的合作覆盖模型。
2.2 概率覆盖模型
如果考虑到所有的不确定性因素，可提供服务的设施点数量、需求点的位置和需求量以及服务单位到达需求点的时间等都有可能是随机变量。备用覆盖模型的提出，考虑了服务设施点可能因处于繁忙状态而不可获得这种情形，因此它提出用额外的服务设施来确保所有需求尽可能得到满足。由于没有具体考虑服务设施点的繁忙状态，这种处理方法属于隐式考虑服务设施点繁忙的模型。就应急服务设施点的选址问题而言，多数研究文献重点关注于服务设施因处于繁忙状态而造成的不可获得性，处理方法上主要有概率模型(不同服务设施点繁忙状态相互独立)和排队论模型。
2.2.1 最大期望覆盖(Maximal Expected Coverage Location Problem， MEXCLP)
在研究服务设施点经常处于繁忙状态的概率覆盖选址问题时，一个重要的问题就是服务设施点繁忙概率的确定。一般有两种情况：系统水平的繁忙概率(system-wide busy fraction)和区域水平的繁忙概率(region-specific busy fraction)，前者假定系统内所有的服务设施点具有相同的繁忙概率，而后者假定不同服务区域的设施点繁忙情况各不相同。如果只考虑概率意义下能够得到服务的需求，就得到了期望类型的覆盖选址模型。
通过假定系统内所有的服务设施具有相等的繁忙概率，Daskin[60]最早介绍了期望覆盖模型在应急医疗服务系统中的应用。后来基于同样的假设，Daskin[61]又建立了最大期望覆盖选址问题的整数规划模型，目标函数最大化覆盖的期望值，并设计了求解的启发式算法，其形式如下：
其他符号如前文所述。目标函数(10)式最大化概率加权意义下的覆盖量;约束(11)式代表能够对每个需求点提供服务的服务设施数量限制;约束(12)式是总的服务设施数量限制，当然也可以取小于等于形式，由于目标函数最大化，两者等价;约束(13)和(14)式是变量取值类型条件。
期望覆盖模型考虑了服务设施的繁忙情形，但是并没有试图提高系统的可靠性。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附近的服务设施点的繁忙概率时，他们使用以下计算公式：
其中目标函数(18)式最小化服务设施的数量;约束(19)式是为达到给定的服务水平所必须的服务设施数量;(20)式是变量类型限制。与LSCP模型不同的是，PLSCP模型中，单个设施点允许安排的服务设施数量可以多于1个，并且由(17)的推导可知，该模型假定各个服务器是否繁忙是相互独立的。
Ball和Lin[71]提出了另一种基于系统水平的PLSCP模型，他们要求需求点不被覆盖的概率不能小于给定的值。Goldberg和Paz[72]建立了另一种非线性的概率覆盖模型，假定服务单位到达需求点的时间是随机的，并且服务时间依赖于需求点的位置，目标函数最大化在给定时间限制时的期望需求量。
上述等人的研究主要考虑了服务设施因繁忙而导致的服务不确定性。对于一般机会约束形式的概率集合覆盖问题，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，其形式如下：
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。
参考文献：
[1] Barbaros C T， Richard L F， Timothy J L. Location on networks： a survey. Part I： The p-Center and p-Median Problems[J]. Management Science， 1983，29(4)：482-497. [2] Owen H S， Daskin M S. Strategic facility location： a review[J]. European Journal of Operational Research， 1988，111：423-447.
[3] Hale T S， Moberg C R. Location science research： a review[J]. Annals of Operations Research， 2003，123：21-35.
[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.
[7] Hakimi S L. Optimum distribution of switching centers in a communication network and some related graph theoretic problems[J]. Operations Research， 1965，13：462-475.
[8] Toregas C， Swain R， ReVelle C， Bergman L. The location of emergency services facilities[J]. Operations Research， 1971，19：1363-1373.
