The use of state space relaxation for the dynamic facility location problem

Dynamic facility location is concerned with developing a location decision plan over a given planning horizon during which changes in the market and in costs are expected to occur. The objective is to select from a list of predetermined possible facility sites the locations of the facilities to use in each period of the planning horizon to minimise the total costs of operating the system. The costs considered here include not only transport and operation/maintenance charges but also relocation costs arising from the opening and closing of facilities as required by the plan. The problem is formulated in terms of dynamic programming but for simplicity with restrictions on the numbers of facilities that can be opened in a given period. The problem was solved using both dynamic programming and a branch and bound approach using state space relaxation. These two approaches are contrasted with different data and with different assumptions to compare the influence of alternative factors on the computational efficiency of both solution methods.