Metaheuristic techniques for the capacitated facility location problem with customer incompatibilities

We study a novel version of the capacitated facility location problem, which includes incompatibilities among customers. For this problem, we propose and compare on a fair common ground a portfolio of metaheuristic techniques developed independently from each other. We tested our techniques on a new dataset composed of instances of increasing size, varying from medium to very large ones. The outcome is that the technique based on data mining has been able to outperform the others in most instances, except for a few large cases, for which it is overcome by the simpler greedy one. In order to encourage future comparisons on this problem, we make the instances, solution validator and implementations of the metaheuristic techniques available to the community.