覆盖问题

　　覆盖问题分为最大覆盖问题和集覆盖问题两类。

　　集覆盖问题研究满足覆盖所有需求点顾客的前提下，服务站总的建站个数或建设费用最小的问题。集覆盖问题最早是由Roth和Toregas等提出的，用于解决消防中心和救护车等的应急服务设施的选址问题，他们分别建立了服务站建站成本不同和相同情况下集覆盖问题的整数规划模型。随后Minieka、Moore和ReVelle等都继续研究集覆盖问题。Plane和Hendrick、Daskin和Stern建立了服务站个数最小和备用覆盖的顾客最大的双目标集覆盖问题。Heung-SukHuang研究了产品会随时间变坏或变好时的动态集覆盖问题。最近十几年来许多基于启发式的算法被用于解决集覆盖问题，M.L.Fisher和P.Kedia提出了基于对偶的启发算法并用来解决最多有200个候选点、2000个需求点的集覆盖问题；BeasleyJ.E.和Jornsten.K将次梯度优化法和拉格朗日松弛算法结合起来求解这类问题；MarcosAlminana和JesusT.Pastor应用代理启发式算法求解集覆盖问题。J.E.Beasley和P.C.Chu给出了求解服务站建站成本不同时集覆盖问题的遗传算法。Grossman和Wool[56]用大量的实验对比了九种用于求解SCLP的启发式算法，其中随机贪婪算法(R-Gr)、简单贪婪算法(S-Gr)和转换贪婪算法(Alt-Gr)在几乎所有问题中都是最好的前四种算法之一，其中随机贪婪算法表现最好，在60个随机问题中有56次获得最好的解。Karp证明了集覆盖问题是NP-完全问题。

　　最大覆盖问题或P-覆盖问题是研究在服务站的数目和服务半径已知的条件下，如何设立P个服务站使得可接受服务的需求量最大的问题。同其它基本问题一样，最大网络覆盖问题也是NP-困难问(Marks.Daskin)。最初的最大覆盖问题是由ChurchRL和ReVelleC提出的，他们将服务站最优选址点限制在网络节点上；ChurchRL和MeadowsME在确定的关键候选节点集合中给出了一般情况下的最优算法，他们通过线性规划的方法求解，如果最优解不是整数就用分枝定界法求解；Church和Meadows提出了最大覆盖问题的伪Hakimi特性，即在任何一个网络中，存在一个有限节点的扩展集，在这个集合中至少包含一个最大覆盖问题的最优解。Benedict，Hogan和ReVelle，Daskin考虑服务系统拥挤情况下的最大覆盖问题，他们把任意一个服务站繁忙的概率当作外生变量，目标函数是服务站可以覆盖的期望需求量最大。HaldunAytug和CemSaydam用遗传算法来求解大规模最大期望覆盖问题，并进行了比较。FernandoY等对最大期望覆盖问题中排队与非排队的情况进行了对比。Berman研究了最大覆盖问题和部分覆盖问题之间的关系。OdedBerman和DmitryKrass、OdedBerman,DmitryKrass和ZviDrezner讨论比传统最大覆盖问题更一般的最大覆盖问题，并给出了拉格朗日松弛算法。OrhanKarasakal和EsraK.Karasakal讨论了部分覆盖问题，对覆盖程度进行了定义。JorgeH.Jaramillo、JoyBhadury和RajanBatta在选址问题的遗传算法应用研究时介绍了最大覆盖问题遗传算法的操作策略。