Premium
Heuristics for the capacitated dispersion problem
Author(s) -
Peiró Juanjo,
Jiménez Iris,
Laguardia José,
Martí Rafael
Publication year - 2021
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/itor.12799
Subject(s) - grasp , heuristics , computer science , heuristic , mathematical optimization , set (abstract data type) , greedy randomized adaptive search procedure , key (lock) , greedy algorithm , variable (mathematics) , algorithm , mathematics , artificial intelligence , mathematical analysis , computer security , programming language
In this paper, we investigate the adaptation of the greedy randomized adaptive search procedure (GRASP) and variable neighborhood descent (VND) methodologies to the capacitated dispersion problem. Dispersion and diversity problems arise in the placement of undesirable facilities, workforce management, and social media, among others. Maximizing diversity deals with selecting a subset of elements from a given set in such a way that the distance among the selected elements is maximized. We target here a realistic variant with capacity constraints for which a heuristic with a performance guarantee was previously introduced. In particular, we propose a hybridization of GRASP and VND implementing within the strategic oscillation framework. To evaluate the performance of our heuristic, we perform extensive experimentation to first set key search parameters, and then compare the final method with the previous heuristic. Additionally, we propose a mathematical model to obtain optimal solutions for small‐sized instances, and compare our solutions with the well‐known LocalSolver software.