Comparison of Heuristics and Relaxations for the Capacitated Plant Location Problem

摘要

This paper compare approaches proposed in the literature for the Capacitated Plant Location Problem. The comparison is based on new theoretical and computational results. The main emphasis of the paper is on relaxations. In particular we identify dominance relations among the various relaxations found in the literature. We also perform a probabilistic study of these relaxations using a Euclidean model. In the computational study, we compare the relaxations as a function of various characteristics of the test problems. Several of these relaxations can be used to generate heuristic feasible solutions that are better than the classical greedy or interchange-type heuristics, both in computing time and in the quality of the solutions found.