有容量集合覆盖选址问题的降阶回溯算法  

Backtracking Algorithm with Reduction for Capacitated Set Covering Location Problem

作　　者：尚春剑 宁爱兵[1] 彭大江 张惠珍[1] SHANG Chun-jian;NING Ai-bing;PENG Da-jiang;ZHANG Hui-zhen(Business School,University of Shanghai for Science and Technology,Shanghai 200093,China)

机构地区：[1]上海理工大学管理学院,上海200093

出　　处：《小型微型计算机系统》2020年第4期692-698,共7页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(71401106)资助;上海市一流学科建设项目(S1201YLXK)资助;上海市教委“管理科学与工程”高原学科建设项目(2018-2021)资助;高等学校博士学科点专项科研基金联合课题项目(20123120120005)资助。

摘　　要：有容量集合覆盖选址问题是组合优化中的一个经典的NP-Hard问题,在许多工程领域和科学领域中的应用十分广泛.本文将集合覆盖问题的模型应用到有容量设施选址问题中,首先研究了该问题的数学性质并给予相应的证明,利用这些数学性质能够对问题进行降阶,降低问题求解难度;然后设计了上界子算法、下界子算法和分配子算法,基于这些子算法提出了一种能够快速缩小问题规模同时能得到精确解的降阶回溯算法;最后文章通过分析和求解一个示例来进一步阐述本文算法的原理和执行过程.Capacity set covering location problem is a classical NP-Hard problem in combinatorial optimization,which is widely used in engineering and scientific fields.In this paper,we apply the set covering model to the capacitated facility problem.Firstly we study some mathematical properties of the problem and give corresponding proofs;then the upper bound sub-algorithm,the lower bound subalgorithm and the allocation sub-algorithm are designed,which can reduce the scale of the problem quickly.Based on these sub-algorithms,a backtracking algorithm with reduction that can rapidly reduce the problem size and obtain a global best solution is proposed.Finally,an instance is given to illustrate the principle and implementation of the proposed algorithm.

关 键 词：集合覆盖 有容量选址问题 降阶算法 上界 下界 回溯算法 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]