A Tabu Search Approach With Dynamical Neighborhood Size for Solving the Maximum Min-Sum Dispersion Problem

Abstract

The maximum min-sum dispersion problem (Max-Minsum DP for short) is a representative binary optimization problem that is proved to be NP-hard and has a number of real-world or potential applications. In this paper, to solve efficiently this computationally challenging problem, we propose a tabu search algorithm with a dynamical neighborhood size (TSDNS) by integrating a solution-based tabu strategy, three new hash functions, and a mechanism of adjusting adaptively the size of neighborhood exploited by the algorithm. The performance of the proposed TSDNS algorithm is assessed through extensive experiments on 160 benchmark instances widely used in the literature, and the experimental results show that the proposed algorithm is very competitive compared with the state-of-the-art algorithms in the literature especially for the large scale instances, and that the best known results are improved for a number of benchmark instances. Analysis experiments show that the new hash functions used in the tabu strategy are more efficient than those from the literature for the large scale instances, and that the mechanism of controlling adaptively neighborhood size plays a key role for the high performance of proposed algorithm.

Keywords

• Tabu search
• dynamical neighborhood size
• dispersion problems
• binary optimization
• heuristic search