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

Backtracking algorithm with reduction for constrained competitive location problem

作　　者：傅汤毅 宁爱兵[1] 孙智勇 林道晗 张惠珍[1] Fu Tangyi;Ning Aibing;Sun Zhiyong;Lin Daohan;Zhang Huizhen(Business School,University of Shanghai for Science&Technology,Shanghai 200093,China)

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

出　　处：《计算机应用研究》2021年第12期3678-3682,共5页Application Research of Computers

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

摘　　要：有约束竞争选址问题是组合优化中一个经典的NP-hard问题,现有算法研究该问题时或是无法求得最优解或是求解速度慢。针对现有算法的缺点,首先在这个经典问题的基础上进行修改,构建了一个新的数学模型;接着对该模型的数学性质进行研究,并在数学性质的基础上提出了上下界算法和降阶子算法对问题进行降阶,达到了缩减问题搜索解空间的目的,降阶的过程中既有单个的降阶,也有成批的降阶;然后在前面的基础上设计了一个回溯子算法来求解问题的最优解;最后通过两个示例分析更清楚地阐述该算法的原理,结果证明该算法可以较快求得最优解。The constrained competitive location problem is a classic NP-hard problem in combinatorial optimization.When the existing algorithms study this problem,the optimal solution cannot be obtained or the solution speed is slow.Aiming at the shortcomings of the existing algorithms,this paper modified this classic problem and constructed a new mathematical model.Then it studied the mathematical properties of the model,and proposed upper and lower bound algorithms and lower bound algorithms on the basis of mathematical properties.The order sub-algorithm reduced the order of the problem and achieved the purpose of reducing the search solution space of the problem.There were both single order reduction and batch reduction in the order reduction process.Then it designed a backtracking sub-algorithm on the basis of the previous one to solve the optimal solution of the problem.Finally,the principle of the algorithm was explained more clearly through the analysis of two examples,and the result proves that the algorithm can find the optimal solution faster.

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

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