The authors present a Lagrangean heuristic for the pk-median dynamic location problem (DLP-pk). In this problem clients must be supplied from pk facilities in period k,k=1,2,...,K, with the objective of minimizing installation/relocation and transportation costs. DLP-pk may be formulated as a 0-1 integer programming problem. In this paper the authors develop two Lagrangean relaxations for the problem and a Lagrangean heuristic algorithm based on these two relaxations and on two alternate procedures to find primal feasible solutions. The computational performance of the method is analysed for problems of up to the size 50 clients×50 potential facility location sites×7 time periods. The authors also investigate the effect of using in the subgradient optimization procedure step size rules that are an alternative to the classical approach suggested by Held, Wolfe and Crowder.
