A. Martínez Gavara, R. Martí, J. Sánchez-Oro
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 variant in which the selected elements have to satisfy a realistic constraint, a minimum capacity limit, which in spite of its practical significance in facility location, has received little attention. In this talk we review the different mathematical models and discuss the metaheuristics proposed to deal with them. Specifically, we present a heuristic based on the Scatter Search methodology to maximize the diversity while satisfying the capacity constraint. We perform extensive experimentation to compare our heuristic proposal with the optimal solutions obtained with the models applied to the Gurobi optimizer, as well as with a previous heuristic.
Palabras clave: metaheuristics, dispersion problem, combinatorial optimization
Programado
GT09 Heurísticas II. Heurísticas y metaheurísticas
8 de junio de 2022 17:20
A04
