关于存在部分覆盖的最大覆盖选址模型研究
最大覆盖选址问题(MCLP)以覆盖需求点的数量最大为目标来解决指定设施数量选址的问题.传统上,如果一个需求点位于一个设施的极限服务距离之内就被假定为完全覆盖,位于这一距离之外则认为根本不会覆盖.由于最大覆盖选址问题的最优解对于临界距离的选择可能很敏感,当覆盖范围没有以一种清晰的方式从”完全覆盖”到”不覆盖”改变时,确定临界距离值可能导致错误的结果.为解决该问题,本文引入了部分覆盖的概念,允许覆盖范围在一个距离范围内从”覆盖”逐渐变为”不覆盖”,而不是单一的临界距离;然后构建了存在部分覆盖的最大覆盖选址问题的数学模型;制定了一种基于拉格朗日松弛法的求解方案,最后通过计算机实验验证了该算法的求解效果良好.
服务设施 最大覆盖选址 部分覆盖 拉格朗日松弛法
刘蓓琳 肖璐彬
北京工商大学计算机与信息工程学院,北京100048
国内会议
管理科学与工程学会2014年年会暨第十二届中国管理科学与工程论坛
哈尔滨
中文
646-651
2014-09-19（万方平台首次上网日期，不代表论文的发表时间）