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

Authors: Pritibhushan Sinha

Addresses: Quantitative Methods and Operations Management Area, Indian Institute of Management Kozhikode, Kozhikode – 673570, Kerala, India

Abstract: 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.

Keywords: capacitated facility location problem; CFLP; heuristics; facilities location.

DOI: 10.1504/IJAMS.2009.026199

International Journal of Applied Management Science, 2009 Vol.1 No.4, pp.388 - 400

Published online: 28 May 2009 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article