Multi-Neighborhood Simulated Annealing for the Capacitated Dispersion Problem

We propose a novel Multi-Neighborhood Simulated Annealing approach to address the Capacitated Dispersion Problem. It makes use of three neighborhoods, adapted from similar proposals from the literature. Our search method, properly engineered and tuned, is able to consistently improve the state-of-the-art methods on almost all instances from public benchmarks. In addition, we highlight the limitations of the current datasets and we propose a new, more challenging one, obtained by sampling data from real maps and population density. Finally, we propose two compact mathematical models that obtain good bounds on small/medium size instances as well as, with long runs, on large ones.