An algorithm for solving Dynamic Capacitated Plant Location Problems with discrete expansion sizes

In the Dynamic Capacitated Plant Location Problem (DCPLP) the task is to find a time schedule and sizes for installing facilities at plant locations to minimize the discounted cost of capital expenditures over the planning horizon. The costs include setup costs for establishing facilities, volume dependent operational costs, and transportation costs for distributing demand from facilities to customers. The paper considers a class of the DCPLP in which the available facilities have finite capacities and the number of facility types is relatively small so that the expansion sizes cannot be modeled by continuous variables. The DCPLP is formulated as a combinatorial optimization problem that allows consideration of more than one facility type and finds the optimum mix of facilities in each location. The paper describes an optimization algorithm for solving the DCPLP based on the Lagrangian relaxation technique. Algorithms for converting infeasible optimal solutions of the Lagrangian to a feasible solution of the DCPLP are presented. The procedure has been tested on both randomly generated and real-life based problems. Computational results indicate that the algorithm produces solutions within 3% of the lower bounds for a wide range of input data.