An LP-based heuristic for two-stage capacitated facility location problems

In this paper, a linear programming based heuristic is considered for a two -stage capacitated facility location problem with single source constraints . The problem is to find the optimal locations of depots from a set of poss ible depot sites in order to serve customers with a given demand, the optim al assignments of customers to depots and the optimal product flow from pla nts to depots. Good lower and upper bounds can be obtained for this problem in short computation times by adopting a linear programming approach. To t his end the LP formulation is iteratively refined using valid inequalities and facets which have been described in the literature for various relaxati ons of the problem. After each reoptimisation step, that is the recalculati on of the LP solution after the addition of valid inequalities, feasible so lutions are obtained from the current LP solution by applying simple heuris tics. The results of extensive computational experiments are given.