考虑容量和成本的最大最小分散度选址问题的降阶回溯算法  

Backtracking Algorithm with Reduction for the Max-min Dispersion Location Problem with Capacity and Cost

作　　者：储旭 宁爱兵[1] 胡开元 刘睿石 张惠珍[1] CHU Xu;NING Aibing;HU Kaiyuan;LIU Ruishi;ZHANG Huizhen(Business School,University of Shanghai for Science and Technology,Shanghai 200093,China)

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

出　　处：《小型微型计算机系统》2024年第10期2384-2393,共10页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(71401106)资助.

摘　　要：最大最小分散度问题可简单描述为:在给定的集合中选择包含固定元素个数的子集,使得该子集中的元素在给定距离度量下的最小距离最大;该问题在生产生活中有广泛的应用.近些年来,该问题的一种考虑容量下限和成本上限的变体开始引起学者们的关注,并已被证明为NP-Complete问题.基于考虑容量和成本的最大最小分散度选址问题进行研究,首先提出该问题的数学性质并证明,利用这些性质可以减小问题规模或缩减搜索空间,以加快问题的求解速度,然后设计了上下界子算法及降阶子算法;基于这些子算法提出一种可大幅缩减搜索空间并能得到最优解的降阶回溯算法.通过分析和求解一个示例来阐述该算法的原理和执行过程,并通过随机算例测试、算法对比分析和案例分析进一步验证了该算法的可行性和有效性.结果表明该算法可有效通过大幅缩减搜索空间加快问题的求解速度.The max-min dispersion problem can be simply described as selecting a fixed number of elements from a given set so that the minimum distance of the chosen elements is maximal under a given metric.This problem is widely used in many industries.In recent years,a variant of this problem with a lower limit of capacity and an upper limit of cost has attracted the attention of scholars and has been proven to be NP-Complete.This paper studies the Max-min dispersion location problem with capacity and cost.Firstly,some mathematical properties of the problem are proposes and proves that using these properties can reduce the problem size or the search space thereby accelerating the speed of solving the problem.Then the paper designes upper and lower bound sub-algorithms and the reduced order sub-algorithm.Based on these sub-algorithms,the paper proposes a backtracking algorithm with reduction which can greatly reduce the search space and obtain the optimal solution.Finally,the paper analyzes and solves an example to illustrate the principle and execution process of the proposed algorithm,and verifies the feasibility and effectiveness by random example tests,algorithm comparative analysis and case analysis.The results show that the algorithm can effectively accelerate the solving speed of the problem by greatly reducing the search space.

关 键 词：考虑容量和成本的最大最小分散度选址问题 精确算法 数学性质 上下界算法 

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