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

doi:10.3778/j.issn.1002-8331.2002-0352

计算机工程与应用 ›› 2020, Vol. 56 ›› Issue (24): 43-49.DOI: 10.3778/j.issn.1002-8331.2002-0352

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

苟海雯，宁爱兵，胡沁，张惠珍

上海理工大学管理学院，上海 200093

出版日期:2020-12-15 发布日期:2020-12-15

Reduction Backtracking Algorithm for Uncapacitated Facility Location Problem With Penalties

GOU Haiwen, NING Aibing, HU Qin, ZHANG Huizhen

Business School, University of Shanghai for Science and Technology, Shanghai 200093, China

Online:2020-12-15 Published:2020-12-15

摘要/Abstract

摘要：

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

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

Abstract:

The Uncapacitated Facility Location Problem（UFLP） is a classical NP-Hard problem in the area of combinatorial optimization. Aiming at the Uncapacitated Facility Location Problem With Penalties（UFLPWP）, this paper researches the new observations of UFLWP and proves the new observations, which including the properties that can determine batches of facilities that must engage. A backtracking algorithm with upper and lower bounds based on these mathematical properties is designed to decrease the scale and the degree of complexity of the original problem and solve the UFLPWP. An example is illustrated to illuminate the principle further.

Key words: Uncapacitated Facility Location Problem With Penalties（UFLPWP）, reduction, upper bound, lower bound, backtracking algorithm

苟海雯，宁爱兵，胡沁，张惠珍. 带惩罚的无容量设施选址问题的降阶回溯算法[J]. 计算机工程与应用, 2020, 56(24): 43-49.

GOU Haiwen, NING Aibing, HU Qin, ZHANG Huizhen. Reduction Backtracking Algorithm for Uncapacitated Facility Location Problem With Penalties[J]. Computer Engineering and Applications, 2020, 56(24): 43-49.

[1]	程帅，吴华锋，梅骁峻. 交替非负约束框架的海洋传感网协同定位[J]. 计算机工程与应用, 2021, 57(23): 129-136.
[2]	乔勋双，毕文杰. 考虑时变奖励的多摇臂算法在动态定价中的应用[J]. 计算机工程与应用, 2021, 57(12): 237-242.
[3]	徐娟，姚如贵，高岩，朱礼亚. 信道估计误差有界时速率损失上界统计特性[J]. 计算机工程与应用, 2020, 56(20): 82-86.
[4]	刘志民，宁爱兵，黄飞，何咏梅，张惠珍. 加权分治与皇冠技术求解最大加权独立集[J]. 计算机工程与应用, 2017, 53(9): 26-30.
[5]	霍倩倩1，田翔2，姜琳3，蔡翠莹3. 基于无线通信TOA值对终端定位问题的研究[J]. 计算机工程与应用, 2017, 53(13): 252-258.
[6]	支志兵，宁爱兵，陈吉珍，王永斐，杨晓芳. 最大团问题的加权分治算法[J]. 计算机工程与应用, 2016, 52(2): 50-53.
[7]	徐康丽1，杨志霞1，蒋耀林2. 基于Krylov-Schur重启技术的Arnoldi模型降阶方法[J]. 计算机工程与应用, 2016, 52(12): 251-255.
[8]	陈吉珍，宁爱兵，支志兵，胡琳琳，张惠珍. 图论中最大独立集问题的精确算法[J]. 计算机工程与应用, 2016, 52(1): 20-22.
[9]	刘艳芳，宁爱兵，王英磊. 图的Steiner最小树问题的降阶回溯算法[J]. 计算机工程与应用, 2014, 50(7): 67-70.
[10]	张振娟. 基于降阶观测器的双线性系统H_∞补偿器设计[J]. 计算机工程与应用, 2013, 49(9): 65-67.
[11]	秦新强，王伟伟，胡钢. 基于遗传算法的C-Bézier曲线降阶[J]. 计算机工程与应用, 2013, 49(5): 174-178.
[12]	白夏红，李辉，邢钢. 消除噪声的ICA盲多用户检测[J]. 计算机工程与应用, 2013, 49(24): 210-213.
[13]	赵永鹏1，周厚春2. 构造一类cartesian认证码的新方法[J]. 计算机工程与应用, 2013, 49(18): 86-88.
[14]	熊小华1，宁爱兵2. 最小比率生成树的竞争决策算法[J]. 计算机工程与应用, 2012, 48(28): 47-51.
[15]	杨珂1，2，万明康1，李鸥1. 多天线协同接收PSK载波参数估计的CRLB[J]. 计算机工程与应用, 2012, 48(22): 142-146.

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

Reduction Backtracking Algorithm for Uncapacitated Facility Location Problem With Penalties

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics