Heuristics for Large-scale Capacitated Facility Location Problems

In this article, we present the heuristic methods, named as median cost heuristic and penalty heuristic, for solving large instances of the capacitated facility location problem. In these methods, only a single transportation problem of reduced size needs to be solved succeeding some calculations. Quality of the solutions given by such methods and solution time have been investigated with benchmark and random instances of the problem. Problem size has been (100 (locations) x 1000 (demand points)) for benchmark instances, and (100 x 100), (100 x 200) for random instances. The methods show very good performance for instances, in which capacity ratio is less than 4. Average efficiency, with respect to a lower bound, of the solutions given by the methods for random instances satisfying this is above 90%. Time requirement by the methods is within practical limits.