有约束竞争选址问题的降阶回溯算法

来源：计算机应用研究杂志2021年第12期北京时间：

作者：傅汤毅,宁爱兵,孙智勇,林道晗,张惠珍,

单位：上海理工大学管理学院,上海200093；

摘要：有约束竞争选址问题是组合优化中一个经典的NP-hard问题，现有算法研究该问题时或是无法求得最优解或是求解速度慢。针对现有算法的缺点，首先在这个经典问题的基础上进行修改，构建了一个新的数学模型；接着对该模型的数学性质进行研究，并在数学性质的基础上提出了上下界算法和降阶子算法对问题进行降阶，达到了缩减问题搜索解空间的目的，降阶的过程中既有单个的降阶，也有成批的降阶；然后在前面的基础上设计了一个回溯子算法来求解问题的最优解；最后通过两个示例分析更清楚地阐述该算法的原理，结果证明该算法可以较快求得最优解。

关键词：竞争选址,上下界算法,降阶算法,回溯算法,

基金资助：国家自然科学基金项目(71401106)；上海市一流学科建设项目(S1201YLXK)；；