Performance of an add-drop-interchange heuristic for the capacitated facility location problem

In this article, we present a heuristic method for solving instances of the capacitated facility location problem. In the method, first, a linear programming relaxation, a transportation problem, is solved to obtain an initial solution. This also gives a lower bound of an optimal solution of the capacitated facility location problem instance. The initial solution is improved in subsequent iterations. In each iteration all possible single-exchange add, drop or interchange of the facilities are considered. Without solving the resultant transportation problems exactly, an approximate method is used for the purpose. Some asymptotic conditions when the method would give an optimal solution are given. Average performance of the method, with respect to the quality of the solutions, has been investigated with benchmark and random instances of the problem. An optimal solution is obtained for most of the benchmark instances. For random instances also, performance of the method is satisfactory.