Lagrangian Heuristic for the Facility Location Problem

In the two-stage capacitated facility location problem a single product is produced at some plants in order to satisfy customer demands. The product is transported from these plants to some depots and then to the customers. The capacities of the plants and depots are limited. The aim is to select cost minimizing locations from a set of potential plants and depots. This cost includes fixed cost associated with opening plants and depots, and variable cost associated with both transportation stages. In this work a Lagrangian relaxation is analyzed and a Lagrangian heuristic producing feasible solutions is presented. The results of a computational study are reported.