Iterated tabu search for the maximum diversity problem

In this paper, we deal with the maximum diversity problem (MDP), which asks to select a specified number of elements from a given set so that the sum of distances between the selected elements is as large as possible. We develop an iterated tabu search (ITS) algorithm for solving this problem. We also present a steepest ascent algorithm, which is well suited in application settings where solutions of satisfactory quality are required to be provided very quickly. Computational results for problem instances involving up to 5000 elements show that the ITS algorithm is a very attractive alternative to the existing approaches. In particular, we demonstrate the outstanding performance of ITS on the MDP instances taken from the literature. For 69 such instances, new best solutions were found.