| 无容量限制设施选址问题的降阶回溯算法 |
| |
| 引用本文： | 何永梅,宁爱兵,彭大江,尚春剑,张惠珍.无容量限制设施选址问题的降阶回溯算法[J].运筹与管理,2018,27(9):17-21. |
| |
| 作者姓名： | 何永梅 宁爱兵 彭大江 尚春剑 张惠珍 |
| |
| 作者单位： | 上海理工大学管理学院,上海 200093 |
| |
| 基金项目： | 国家自然科学基金(71401106);上海市一流学科建设项目资助(S1201YLXK);高等学校博士学科点专项科研基金联合资助课题 (20123120120005) |
| |
| 摘 要： | 无容量限制设施选址问题(uncapacitated facility location problem, UFLP)是经典组合优化中NP-Hard问题之一,在诸多领域具有广泛的应用价值。本文首先研究UFLP的数学性质,并进行了数学证明。运用这些数学性质不仅可以确定某些设施必定开设或者关闭,还可以确定某些连接边是否在服务集中,从而缩小问题的规模,加快求解速度;在此基础上设计出一个新的基于上下界的回溯算法来求解UFLP。最后,通过一个示例进一步阐述该算法的原理,结果表明该算法具有明显的可行性和有效性。
|
| 关 键 词： | 无容量限制设施选址问题 降阶 上界 下界 回溯算法 |
| 收稿时间： | 2017-06-11 |
Reduction Backtracking Algorithm for Uncapacitated Facility Location Problem |
| |
| HE Yong-mei,NING Ai-bing,PENG Da-jiang,SHANG Chun-jian,ZHANG Hui-zhen.Reduction Backtracking Algorithm for Uncapacitated Facility Location Problem[J].Operations Research and Management Science,2018,27(9):17-21. |
| |
| Authors: | HE Yong-mei NING Ai-bing PENG Da-jiang SHANG Chun-jian ZHANG Hui-zhen |
| |
| Affiliation: | School of Management, University of Shanghai for Science and Technology, Shanghai 200093, China |
| |
| Abstract: | The uncapacitated facility location problem(UFLP)is a well-known NP-Hard problem in the area of combinatorial optimization, which has wide application value in various fields. The present paper firstly provides new observations of the UFLP model and gives the proof of the new observation. These mathematical properties not only can be used to decide whether some facilities should be open or closed, but also can be used to determine whether some of the connection edges are in service set. Therefore, the size of the original problem can be reduced, and the solution speed can be accelerated by utilizing the new observation in the paper. Given the fact, a new reduction backtracking algorithm based on upper and lower bounds is designed to solve the UFLP. In the end, an example is given to illustrate the principle of the algorithm, and the optimal solution of the example is obtained by utilizing the reduction backtracking algorithm in the paper .Therefore, the results show that the algorithm is feasible and effective. |
| |
| Keywords: | uncapacitated facility location problem reduction upper bound lower bound backtracking algorithm |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《运筹与管理》浏览原始摘要信息 |
|
点击此处可从《运筹与管理》下载全文 |
|
