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

• 作者: 宁爱兵 张惠珍 胡沁 苟海雯
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 带惩罚的无容量设施选址问题 降阶 上界 下界 回溯算法
• 年，卷（期）: 2020,（24）
• 所属期刊栏目: 理论与研发
• 页码范围: 43-49
• 页数: 7页
• 分类号: TP301.6
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.2002-0352

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	宁爱兵		59	341	11.0	15.0
2	张惠珍		86	662	16.0	23.0
3	苟海雯		3	0	0.0	0.0
4	胡沁		3	0	0.0	0.0