Solving the dynamic facility location problem

This paper addresses the multiperiod, or dynamic, uncapacitated facility location problem (DUFLP): The demand varies between time-periods and the solution should answer the questions of where and when to establish facilities. We modelize the problem as a 0–1 quadratic program and, since the DUFLP is NP-hard, we focus on methods for generating heuristic solutions (by simulated annealing) and good lower bounds (by Langrangian relaxation). We prove that our bound is equal to the optimal solution of the continuous relaxation of a linearization of the initial program. Then we show that the method can take into account some additional costs needed to solve some practical problems arising in telecommunication and intelligent networks. Finally, we present experimental results: The small size of the duality gaps explains the good quality of the obtained solutions.