Heuristics for the capacitated dispersion problem

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.

Automated summary

This paper investigates the adaptation of GRASP and VND methodologies to the capacitated dispersion problem, proposing a hybrid algorithm within the strategic oscillation framework. Extensive experimentation and mathematical modeling are used to evaluate the algorithm's performance. Comparisons with existing software solutions are also made.