How Good Is Local Search for Capacitated Facility Location Problem: An Experimental Study

Abstract

Facility location problems have been widely studied since 1960’s. These problems are known to be strongly NP-hard. In capacitated variant of the problem, a capacity constraint is associated with each facility. Capacitated facility location problem (CFLP) instances can be solved exactly using existing MILP solvers but only for small instance sizes. As the size of the problem instance increases beyond few hundred facilities and few hundred clients, it becomes prohibitive to solve these instances exactly. For large problem instances, therefore, other solution methods are used. One approach is to use heuristic methods. These methods usually give good solutions in reasonable time but they do not provide any guarantee about the quality of the solution. Somewhere between these two extremes exist another class of algorithms called approximation algorithms. They also provide only suboptimal solutions to the problem, like heuristic algorithms, in polynomial time. How ever they guarantee worst case upper bounds on the cost of the solution. So, a solution obtained using an approximation algorithm is guaranteed to have its cost between the optimal cost and the upper bound. We present experimental studies done with a local search based approximation algorithm for CFLP given by Bansal et al. [1] to show that this algorithm performs well in practice.