覆盖问题简介

分类

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

集覆盖问题

集覆盖问题研究满足覆盖所有需求点顾客的前提下，服务站总的建站个数或建设费用最小的问题。集覆盖问题最早是由 Roth和 Toregas等提出的，用于解决消防中心和救护车等的应急服务设施的选址问题，他们分别建立了服务站建站成本不同和相同情况下集覆盖问题的整数规划模型。随后 Minieka、Moore 和 ReVelle等都继续研究集覆盖问题。Plane 和Hendrick、Daskin 和 Stern建立了服务站个数最小和备用覆盖的顾客最大的双目标集覆盖问题。Heung-Suk Huang研究了产品会随时间变坏或变好时的动态集覆盖问题。最近十几年来许多基于启发式的算法被用于解决集覆盖问题，M.L. Fisher 和 P.Kedia提出了基于对偶的启发算法并用来解决最多有 200 个候选点、2000 个需求点的集覆盖问题；Beasley J.E. 和 Jornsten. K将次梯度优化法和拉格朗日松弛算法结合起来求解这类问题；Marcos Alminana 和 Jesus T. 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)。最初的最大覆盖问题是由 Church RL 和 ReVelle C提出的，他们将服务站最优选址点限制在网络节点上；Church RL和 Meadows ME在确定的关键候选节点集合中给出了一般情况下的最优算法，他们通过线性规划的方法求解，如果最优解不是整数就用分枝定界法求解；Church 和Meadows提出了最大覆盖问题的伪 Hakimi 特性，即在任何一个网络中，存在一个有限节点的扩展集，在这个集合中至少包含一个最大覆盖问题的最优解。Benedict，Hogan 和 ReVelle，Daskin考虑服务系统拥挤情况下的最大覆盖问题，他们把任意一个服务站繁忙的概率当作外生变量，目标函数是服务站可以覆盖的期望需求量最大。Haldun Aytug 和 Cem Saydam用遗传算法来求解大规模最大期望覆盖问题，并进行了比较。Fernando Y等对最大期望覆盖问题中排队与非排队的情况进行了对比。Berman研究了最大覆盖问题和部分覆盖问题之间的关系。Oded Berman 和 DmitryKrass 、Oded Berman, Dmitry Krass 和 Zvi Drezner讨论比传统最大覆盖问题更一般的最大覆盖问题，并给出了拉格朗日松弛算法。Orhan Karasakal 和 Esra K.Karasakal讨论了部分覆盖问题，对覆盖程度进行了定义。Jorge H. Jaramillo、Joy Bhadury 和 Rajan Batta在选址问题的遗传算法应用研究时介绍了最大覆盖问题遗传算法的操作策略。