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

摘要：

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

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

所属期刊栏目：38

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金;上海市一流学科建设项目

在线出版日期：2021-12-14（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：3678-3682