GRASP and tabu search for the generalized dispersion problem

摘要

The problem of maximizing dispersion requires the selection of a specific number of elements from a given set, in such a way that the minimum distance between the pairs of selected elements is maximized. In recent years, this problem has received a lot of attention and has been solved with many complex heuristics. However, there is a recent variant in which the selected elements have to satisfy two realistic constraints, a minimum capacity limit and a maximum budget, which in spite of its practical significance in facility location, has received little attention. In this paper, we first propose mathematical models to obtain the optimal solution of small- and medium-size instances, and then present new metaheuristic procedures for finding approximate solutions to target large-size instances. Specifically, we develop a GRASP and a tabu search to obtain high quality solutions in short computational times. We perform extensive experimentation to compare our heuristic proposals with the optimal solutions obtained with the models applied to the Gurobi optimizer, as well as with a previous heuristic. Statistical tests confirm the superiority of our methods.