覆盖模型

覆盖模型覆盖模型•覆盖模型是一类离散点选址模型。所谓覆盖模型，是对于需求已知的一些需求点，如何确定一组服务设施来满足这些需求点的需求。•常用的有两类主要模型：集合覆盖模型，即用最小数量的设施去覆盖所有的需求点；最大覆盖模型，即在给定数量的设施去覆盖所有需求点。•区别：集合覆盖模型要满足所有需求点的需求，而最大覆盖模型则只覆盖有限的需求点，两种模型的应用情况取决于服务设施的资源充足与否。集合覆盖模型的构建第一步，找到每一个候选地址可以提供服务的所有需求点的集合A(j),它们距离该候选地址的距离小于或者等于指定距离。第二步，找到可以给每一个需求点提供服务的所有候选地址的集合B(i)，一般说来，它与A(j)是一样的，但是考虑他条件的限制，也有不一样的情况，这要视具体的情况而定。第三步，设变量xij＝1表示位于i点的物流中心向位于j点的需求点供货，否则xij＝0。yi＝1表示在i点建立物流中心，否则yi=0。由于每个需求点都可以从一个或者多个物流中心进货，由此决定了物流服务分配的约束条件为,1，根据B(i)可以写出各个约束条件。但是为了减少物流中心建设的成本，应该选取能够覆盖所有需求点的最小数量的候选地址的组合。第四步，检验。根据集合A(j)，验证求得的物流中心选址是否覆盖了所有需求点。实例在Ad-hoc传感器网络中，信号覆盖范围或覆盖率是衡量网络服务质量的主要度量指标。因此，如何在保证信号覆盖质量的前提下，尽可能地节省网络建设成本就显得格外重要[1]。如图1所示，四个平面上的圆形区域是同种型号的传感器S1~S4的信号覆盖范围，e1~e9是九个服务客户，问：设置传感器的最佳方案是什么?•不妨将九个服务客户视为“元素”，而各传感器的信号覆盖范围内的元素（客户）分别构成集合：S1={e1，e2，e3，e4，e5}S2={e3，e4，e5，e6，e7，e8}S3={e2，e4，e5，e7，e8，e9}S4={e1，e2，e3，e4，e8，e9}则传感器的最佳设置方案应为集合S={e1~e9}的一个基数最小的集合覆盖。最大覆盖模型