Tabu search for the Max–Mean Dispersion Problem

摘要

In this paper, we address a variant of a classical optimization model in the context of maximizing the diversity of a set of elements. In particular, we propose heuristics to maximize the mean dispersion of the selected elements in a given set. This NP-hard problem was recently introduced as the maximum mean dispersion problem (MaxMeanDP), and it models several real problems, from pollution control to ranking of web pages. In this paper, we first review the previous methods for the MaxMeanDP, and then explore different tabu search approaches, and their influence on the quality of the solutions obtained. As a result, we propose a dynamic tabu search algorithm, based on three different neighborhoods. Experiments on previously reported instances show that the proposed procedure outperforms existing methods in terms of solution quality. It must be noted that our findings on the use of different memory structures invite to further consideration of the interplay between short and long term memory to enhance simple forms of tabu search.