Solution-based tabu search for the maximum min-sum dispersion problem

The maximum min-sum dispersion problem (Max-Minsum DP) is an important representative of a large class of dispersion problems. Having numerous applications in practice, the NP-hard Max-Minsum DP is however computationally challenging. This paper introduces an effective solution-based tabu search (SBTS) algorithm for solving the Max-Minsum DP approximately. SBTS is characterized by the joint use of hash functions to determine the tabu status of candidate solutions and a parametric constrained swap neighborhood to enhance computational efficiency. Experimental results on 140 benchmark instances commonly used in the literature demonstrate that the proposed algorithm competes favorably with the state-of-the-art algorithms both in terms of solution quality and computational efficiency. In particular, SBTS improves the best-known results for 80 out of the 140 instances, while matching 51 other best-known solutions. We conduct a computational analysis to identify the respective roles of the hash functions and the parametric constrained swap neighborhood.