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

作     者：尚春剑 宁爱兵 彭大江 张惠珍 SHANG Chun-jian;NING Ai-bing;PENG Da-jiang;ZHANG Hui-zhen

作者机构：上海理工大学管理学院上海200093 

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

出 版 物：《小型微型计算机系统》 (Journal of Chinese Computer Systems)

年 卷 期：2020年第41卷第4期

页      码：692-698页

摘      要：有容量集合覆盖选址问题是组合优化中的一个经典的NP-Hard问题,在许多工程领域和科学领域中的应用十分广泛.本文将集合覆盖问题的模型应用到有容量设施选址问题中,首先研究了该问题的数学性质并给予相应的证明,利用这些数学性质能够对问题进行降阶,降低问题求解难度;然后设计了上界子算法、下界子算法和分配子算法,基于这些子算法提出了一种能够快速缩小问题规模同时能得到精确解的降阶回溯算法;最后文章通过分析和求解一个示例来进一步阐述本文算法的原理和执行过程.

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

学科分类：08[工学] 081202[081202] 0812[工学-测绘类] 

D　O　I：10.3969/j.issn.1000-1220.2020.04.004

馆 藏 号：203898110...