带惩罚的无容量设施选址问题的降阶回溯算法

摘要：

无容量设施选址问题(Uncapacitated Facility Location Problem,UFLP)是组合优化中经典的NP-Hard问题之一.针对UFLP的变形问题之一,即带惩罚的无容量设施选址问题(Uncapacitated Facility Location Problem With Penalties,UFLPWP),研究了UFLPWP的数学性质,其中包括可以批量确定某些设施一定关闭的性质,并进行了数学证明,利用这些数学性质可以对问题进行降阶,进而缩小问题的规模.在此基础上设计了基于上、下界的回溯算法来求解UFLPWP.通过一个示例分析,进一步阐述该算法的原理.

关键词：带惩罚的无容量设施选址问题、降阶、上界、下界、回溯算法

所属期刊栏目：56

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金;上海市一流学科建设项目

在线出版日期：2020-12-21（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：43-49