A two-phase intensification tabu search algorithm for the maximum min-sum dispersion problem

Abstract In this paper, we study the maximum min-sum dispersion problem (Max-Minsum DP for short) which is a classical binary optimization problem proven to be NP-hard and with numerous real-world applications. For solving this computationally challenging problem, we propose a two-phase intensification tabu search algorithm (TPITS), which integrates several distinguishing features, such as an intensification tabu search to avoid visiting the previous encountered solutions and an attribute-based tabu search to refine the search in the second phase. Tested on seven sets of totally 160 public instances in the literature, the study demonstrates the efficacy of the proposed TPITS algorithm in terms of both solution quality and computational efficiency. Specifically, our proposed TPITS algorithm is able to improve the previous best known results for 69 instances, while matching the previous best known results for 74 ones. We also provide experimental evidences to highlight the beneficial effect of the important components in the TPITS algorithm.