A Heuristic Algorithm for Solving Capacitated Facility Location Problems Using a Greedy-Based Iterative LP Relaxation Procedure

Abstract

A new methodology to solve the capacitated facility location problem (CFLP) is presented. This optimization problem can be explicitly formulated and solved as a mixed integer program (MIP); however, because binary variables are used, obtaining exact solutions can be computationally intensive. This issue is apparent for solving large-scale problems, where the problem complexity is known to increase exponentially in the number of location variables. The proposed approach will instead solve the problem in a heuristic manner, returning an approximate solution rather than an exact one. A linear program (LP) relaxation to the problem is solved, while iteratively fixing select binary location variables to 0 or 1 until a feasible solution is obtained. Experimental results show that the proposed methodology can be effective in obtaining solutions in a fraction of CPU (central processing unit) time compared to exact methods. The quality of the solution is also shown to be extremely close to optimal for problems with relatively high fixed cost parameters. An application to a real-life problem is also explored to validate the practicality of the proposed methodology. Not only does the algorithm offer a new approach to solving the CFLP, but it also presents a fast approximation method which can be applied to solve MIP models in general. Additional ideas for improving the algorithm are also presented.