摘要
有约束竞争选址问题是组合优化中一个经典的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.
作者
傅汤毅
宁爱兵
孙智勇
林道晗
张惠珍
Fu Tangyi;Ning Aibing;Sun Zhiyong;Lin Daohan;Zhang Huizhen(Business School,University of Shanghai for Science&Technology,Shanghai 200093,China)
出处
《计算机应用研究》
CSCD
北大核心
2021年第12期3678-3682,共5页
Application Research of Computers
基金
国家自然科学基金项目(71401106)
上海市一流学科建设项目(S1201YLXK)。
关键词
竞争选址
上下界算法
降阶算法
回溯算法
competitive location
upper and lower bound algorithm
reduced order algorithm
backtracking algorithm
