Multi-neighborhood simulated annealing for the capacitated facility location problem with customer incompatibilities

We consider the Capacitated Facility Location Problem with Customer Incompatibilities, which is a recently -proposed variant of the classic facility location problem whose distinctive feature is to take into account incompatibilities between customers. We tackle this problem using local search and we propose a combination of neighborhoods and ad hoc techniques to reduce the size of the search space, in order to effectively deal with large instances. The resulting multi-neighborhood approach is guided by a simulated annealing procedure. Our method, suitably tuned in a statistically-principled way, has been able to outperform all previous techniques on the publicly available dataset, on both short and long running times.