Research On Iterative Local Search Algorithm For Dispersion Problems

Dispersion problems come from the practical application of urban public facilities location and homogeneous group selection.It is a NP-hard combinatorial optimization problem.According to the objectives,it can be divided into two categories: efficiency-based dispersion problems and balance-based dispersion problems.Equilibrium-based dispersion problems guarantee the equilibrium among selected elements,including the minimum differential dispersion problem,the maximum mean dispersion problem,the maximum min-sum dispersion problem.Efficiency-based dispersion problems take the overall dispersion of all selected elements,including maximum diversity problem and the max-min diversity problem.In view of the high complexity of dispersion problems,the accuracy algorithm can only solve small-scale examples.The iterative local search algorithm is used to solve large-scale dispersion problem.A representative problem is selected from the two categories,and a general algorithm is designed to the minimum differential dispersion problem and the maximum min-sum problem.The main research work is as follows:An iterative local search algorithm framework is used to search for high-quality solutions by descent process,and the perturbation processes with different intensity are adaptively selected for pit jumping.In the process of searching,the neighborhood operator of point-to-point exchange is used,and the solution-based tabu scheme is added to avoid searching the same solution space repeatedly,which improves the efficiency of searching in the same downtime.The same neighborhood operation,descent process and perturbation process are designed for different problem solving objectives to achieve the generality of the search algorithm framework.The proposed algorithm is tested experimentally by test examples of the minimum differential dispersion problem and the maximum min-sum problem,and compared with the best algorithm in literature.The experimental results show that the proposed iterative local search algorithm can solve a class of dispersion problems with good generality and high performance.