The Single Period Coverage Facility Location Problem: Lagrangean heuristic and column generation approaches

Abstract

In this paper we introduce the Single Period Coverage Facility Location Problem. It is a multi-period discrete location problem in which each customer is serviced in exactly one period of the planning horizon. The locational decisions are made independently for each period, so that the facilities that are open need not be the same in different time periods. It is also assumed that at each period there is a minimum number of customers that can be assigned to the facilities that are open. The decisions to be made include not only the facilities to open at each time period and the time period in which each customer will be served, but also the allocation of customers to open facilities in their service period.

We propose two alternative formulations that use different sets of decision variables. We prove that in the first formulation the coefficient matrix of the allocation subproblem that results when fixing the facilities to open at each time period is totally unimodular. On the other hand, we also show that the pricing problem of the second model can be solved by inspection. We prove that a Lagrangean relaxation of the first one yields the same lower bound as the LP relaxation of the second one. While the Lagrangean dual can be solved with a classical subgradient optimization algorithm, the LP relaxation requires the use of column generation, given the large number of variables of the second model. We compare the computational burden for obtaining this lower bound through both models.