覆盖问题的覆盖问题

发布网友发布时间：2022-05-26 16:52

共1个回答

热心网友时间：2023-10-29 13:52

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