Heuristics for the Capacitated Dispersion Problem

A hybridization of GRASP and VNS implementing within the Strategic Oscillation to solve he Capacitated Dispersion Problem

We investigate the adaptation of the Greedy Randomized Adaptive Search Procedure (GRASP) and Variable Neighborhood Search (VNS) methodologies to the Capacitated Dispersion Problem (CDP). 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 withcapacity constraints for which a heuristic with a performance guarantee was previously introduced. In particular, we propose a hybridization of GRASP and VNS 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 one. Additionally, we propose a mathematical model to obtain optimal solutions for small size instances and compare our solutions with the well-known Local-Solver software.