An Algorithm for Solving Dynamic Capacitated Plant Location Problems with Discrete Expansion Sizes (Q3978841)

Suppose the demands at different points are known during several time periods. These demands have to be satisfied in each period by either priorily existing or new facilities of possibly different capacities. The new facilities have to be located among given sites, for each of which it is known which types of facility and in what number it may accomodate. For each time period the setup costs for any facility type at each site, a variable cost per unit of demand served by each type of facility (independent of its location), and the transportation costs per unit of demand between any site and any demand point (independent of facility type) are given. The problem studied consists of determining the schedule of new facility placements and the way to meet all demands during each period, minimizing the total costs over the complete planning horizon. A mixed 0-1 linear formulation is derived. A Lagrangian relaxation is obtained by relaxing the demand constraints. The obtained subproblems are solved by dynamic programming, which is exponential in the general case. For the case where mixing of facilities of different types at the same location is not allowed, the subproblems turn out to be polynomially solvable. In this case two heuristics are also described for deriving feasible solutions from infeasible ones obtained in the subproblems. Some computational experience is given.