关于存在部分覆盖的最大覆盖选址模型研究

摘要

最大覆盖选址问题(MCLP)以覆盖需求点的数量最大为目标来解决指定设施数量选址的问题.传统上,如果一个需求点位于一个设施的极限服务距离之内就被假定为完全覆盖,位于这一距离之外则认为根本不会覆盖.由于最大覆盖选址问题的最优解对于临界距离的选择可能很敏感,当覆盖范围没有以一种清晰的方式从"完全覆盖"到"不覆盖"改变时,确定临界距离值可能导致错误的结果.为解决该问题,本文引入了部分覆盖的概念,允许覆盖范围在一个距离范围内从"覆盖"逐渐变为"不覆盖",而不是单一的临界距离;然后构建了存在部分覆盖的最大覆盖选址问题的数学模型;制定了一种基于拉格朗日松弛法的求解方案,最后通过计算机实验验证了该算法的求解效果良好.