Keywords

1 Introduction

Facility location decisions are usually made taking into account the values of some parameters, such as the setup costs for the facilities and the demand levels. If variations are predictable for such values, it may be desirable to plan in advance for future adjustments in the location of facilities and in other related decisions (e.g., shipment decisions). In this case, locating a set of facilities becomes a question not only of “where” but also of “when”. A new dimension is introduced in the decision space: the time. This is the topic of the current chapter.

In order to capture predictable variations in the parameters of a facility location problem, we often have to consider a dynamic or time-dependent model. From a practical point of view, this type of model can be quite relevant because it allows for embedding other decisions, such as those related with (1) inventory management, (2) opening new facilities and removing existing ones, and (3) adjustment of the operating capacities (which, from a cost point of view is often better than opening new facilities). Even when the underlying parameters do not induce a dynamic model, some other conditions may do so. For instance, if a budget constraint exists say, per year, for installing new facilities, then locating the facilities over time may be unavoidable.

When facility location decisions are to be made over time, it is important to define the planning horizon beforehand. This is the time frame for which the decision maker wishes to plan. Only a few papers have investigated facility location problems over an infinite planning horizon. In this case, a static or a finite-horizon decision is usually sought that is “the best” for an infinitely long planning horizon. Some works in this direction include Chand (1988) and Daskin et al. (1992). Nevertheless, in most cases, decision makers assume a finite planning horizon (see the recent review paper by Arabani and Zanjirani Farahani 2012). This is the case we consider in this chapter.

When working with dynamic models, we can make a distinction between continuous and discrete-time models. In the first case, there are no specific moments for implementing the decisions; the best timing for performing changes in the system is itself a decision to make. Some works exploring this feature include Drezner and Wesolowsky (1991), Orda and Rom (1991), Puerto and Rodríguez-Chía (1999), and Zanjirani Farahani et al. (2009). In our opinion, continuous-time facility location problems are better addressed in the context of optimal control. Therefore, in this chapter we do not focus on this type of problems. Instead, we consider a discrete-time setting in which we have several moments in time for implementing the decisions. These moments induce a partition of the planning horizon into several time periods.

Facility location problems are often classified, according to the location space, as being continuous, on a network, or discrete (Hamacher and Nickel 1998). In recent years, due to successful applications of location theory to many areas, discrete models have increasingly played a major role. For this reason, in this chapter, special emphasis is given to this type of problems.

The remainder of the chapter is organized as follows: in Sects. 11.2 and 11.3 we present a brief overview of continuous and network multi-period facility location problems, respectively. In Sects. 11.4 and 11.5 we focus on discrete problems. Section 11.6 is used for introducing the value of the multi-period solution. Finally, in Sect. 11.7, we discuss some challenges and future trends on the topic.

2 Continuous Problems

One of the best-known facility location problems is the Weber problem: given a set of weighted nodes in the Euclidean plane, where to locate a single facility minimizing the weighted sum of the distances to the points? A multi-period extension of this problem was first proposed by Wesolowsky (1973). A finite planning horizon T, divided into several time periods, is assumed. In each period t ∈ T, a set of weighted nodes J t is considered. The goal is to find the optimal location for the single facility in each period. When the facility changes from one location to another (in consecutive periods), a relocation cost is paid. The conceptual model proposed by Wesolowsky (1973) is the following:

$$\displaystyle{ \mbox{ Minimize}\quad \sum _{t\in T}\sum _{j\in J_{t}}c_{\mathit{tj}}(x_{t},y_{t}) +\sum _{ t=2}^{\vert T\vert }f_{ t}z_{t} }$$
(11.1)
$$\displaystyle{ \mbox{ subject to}\quad z_{t} = 0\mbox{ if }d_{t-1,t} = 0,\quad t \in T\setminus \{1\} }$$
(11.2)
$$\displaystyle{ \quad z_{t} \in \{ 0,1\},\quad t \in T. }$$
(11.3)

In this model, c tj (x t , y t ) represents the present value of the cost for shipping from a facility located at (x t , y t ) to demand point j ∈ J t in period t ∈ T; f t denotes the cost for relocating the facility at the beginning of period t ∈ T; d t−1, t is the distance by which the facility is moved at the beginning of period \(t \in T\setminus \{1\}\). All the costs are assumed to be forecasted in advance and therefore known to the model. For tackling this problem, Wesolowsky (1973) proposed an incomplete dynamic programming algorithm. The stages are associated with the time periods, the states correspond to a set of possible locations for the facility and the decisions correspond to the possible changes in the location of the facility. The relevance of this work arises from the fact that it represents the first attempt to extend the Weber problem to a multi-period setting. Nevertheless, the first work addressing the location and relocation of a single facility in the plane over a multi-period finite planning horizon is due to Ballou (1968). The goal is to maximize the total profit generated by a distribution system involving factories, markets and the single warehouse to be located and relocated. In that paper, a restricted set of potential locations for the warehouse was defined considering the optimal location for the facility in the different periods. This set then defined the states for all periods, and (incomplete) dynamic programming was then applied. The method was later converted into an exact one by Sweeney and Tatham (1976) who extended the restricted set just mentioned. In fact, a set of potential locations for the warehouse can be found in each time period, thus ensuring that the optimal solution of the problem is not lost when dynamic programming is applied. It is worth noting that the methodologies proposed by Ballou (1968) and Sweeney and Tatham (1976) can be applied to problems defined in a discrete setting.

Drezner and Wesolowsky (1991), investigated a different type of problem. Like in all of the above works, a single facility is considered, which can be relocated over time as a reaction to predictable changes in the demand. The set J of demand nodes is the same throughout the planning horizon. The demand of each node j ∈ J, is represented by a continuous function of time w j (. ). A planning horizon T divided into several time periods is assumed. The following optimization model can be considered for each period t ∈ T:

$$\displaystyle{ C_{t} =\min _{x_{t},y_{t}}\left \{\sum _{j\in J}W_{\mathit{jt}}d_{j}(x_{t},y_{t})\right \}. }$$
(11.4)

In this expression, (x t , y t ) denotes the coordinates of the facility in period t ∈ T; \(W_{\mathit{jt}} =\int _{ a_{t-1}}^{a_{t}}w_{j}(\tau )d\tau\); a t−1 and a t are the lower and upper time limits for period t, respectively; d j (x t , y t ) denotes the distance between demand point j ∈ J and point (x t , y t ). The cost for the entire planning horizon is given by ∑ t ∈ T C t . Drezner and Wesolowsky (1991) made use of the above model to solve a more general problem which consists of making a decision about the division of the planning horizon into time periods. In this case, the number of time periods and the “break points” are decisions to make. This work was later extended by Zanjirani Farahani et al. (2009) that included a cost for relocating the facility.

Scott (1971) studied a multi-facility, multi-period continuous location problem, assuming a finite planning horizon T divided into several time periods, and a set of demand nodes, J. In each time period, a single facility is to be located and must remain operating until the end of the planning horizon. A sequence of | T | problems can be considered. In particular, the following mathematical model holds for period t ∈ T (the coordinates (x τ , y τ ), \(\tau = 1,\ldots,t - 1\), were already determined):

$$\displaystyle{ \mbox{ Minimize}\quad \sum _{j\in J}\sum _{\tau =1}^{t-1}u_{ j\tau }d_{j}(x_{\tau },y_{\tau }) +\sum _{j\in J}u_{\mathit{jt}}d_{j}(x_{t},y_{t}) }$$
(11.5)
$$\displaystyle{ \mbox{ subject to}\quad \sum _{\tau =1}^{t}u_{ j\tau } = 1,\quad j \in J }$$
(11.6)
$$\displaystyle{ \quad u_{j\tau } \in \{ 0,1\},\quad \tau = 1,\ldots,t,\:j \in J. }$$
(11.7)

In this model, (x t , y t ) are the coordinates (to be determined) of the facility to install at the beginning of period t ∈ T; u jt is a binary variable equal to 1 if demand point j ∈ J is allocated to the facility installed in period t ∈ T (such allocation can only occur in periods t, …, | T | ), and 0 otherwise; d j (x t , y t ) is the Euclidean distance between demand node j ∈ J and the facility to be installed in period t ∈ T. By solving the full sequence of problems (one for each t ∈ T), a solution is obtained for the multi-period problem. Nevertheless, using such a myopic procedure, optimality cannot be guaranteed for the whole planning horizon.

A multi-period extension of the planar p-median problem was proposed by Drezner (1995) who considered a finite planning horizon divided into | T |  = p time periods. The set of demand nodes is denoted by J and demand changes over time. The demand of node j ∈ J is represented by a continuous function of time w j (. ). At the beginning of each time period t ∈ T, exactly one facility is to be installed. The decision variables are the coordinates of the p locations for the facilities, (x t , y t ), t ∈ T. The problem can be formulated as follows:

$$\displaystyle{ \mbox{ Minimize}\quad \sum _{t\in T}\sum _{j\in J}W_{\mathit{jt}}\min _{\tau =1,\ldots,t}\left \{d_{j}(x_{\tau },y_{\tau })\right \}, }$$
(11.8)

where d j (x t , y t ), t ∈ T, represents the distance between demand node j ∈ J and the facility established at the beginning of period t ∈ T; \(W_{\mathit{jt}} =\int _{ a_{t-1}}^{a_{t}}w_{j}(\tau )d\tau\); a t−1 and a t are, respectively, the lower and upper time limits for period t. The function to be minimized in (11.8) results from adding the costs for all periods. Drezner (1995) proposed a specially tailored algorithm for the 2-facility problem and suggested the use of a standard non-linear solver for the general case.

3 Network Problems

One of the earliest works on multi-period facility location problems on networks is due to Cavalier and Sherali (1985). The problems under consideration consist of progressively installing a set of facilities on a chain or on a tree considering a multi-period finite planning horizon. In each period, at most one facility can be installed. Demand occurs continuously on the edges, according to a uniform distribution. Different strategies were analyzed for obtaining solutions to the problems.

Considering general networks, Mesa (1991) addressed several multi-period facility location problems. Different concepts were introduced in that paper, such as the vertex | T | -period p-median, the vertex multi-period (α 1, …, α  | T | )-median and the absolute multi-period (α 1, …, α  | T | )-median. Among the different problems studied, the absolute multi-period (α 1, …, α  | T | )-median problem was, at the time, the one which was closer to what could be referred to as an extension of the p-median problem to a multi-period setting. In that problem, α t points must be located in each period t ∈ T, satisfying ∑ t ∈ T α t  = p. The author proved that the initial infinite set of possible choices for facilities can be reduced to a discrete set of nodes. This is due to the vertex-optimality property (Hakimi 1964, 1965), which holds for this multi-period problem.

The extension of the network p-median problem to a multi-period setting was proposed by Hakimi et al. (1999). Considering a time varying network, N = (V, E, T), with T representing the planning horizon, it is assumed that the weight of each vertex v j  ∈ V and the length of each edge e ∈ E are functions of time and are invariant in each period. Assuming moving costs for the facilities, the multi-period, 1-median problem on network N can be formulated as follows:

$$\displaystyle{ \mbox{ Minimize}\quad \sum _{t\in T}\left (\sum _{j\in V }w_{\mathit{jt}}d_{t}(v_{j},x_{t}) + g(t)d_{t}(x_{t},x_{t+1})\right ). }$$
(11.9)

In this model, w jt denotes the weight of vertex v j  ∈ V in period t ∈ T; x t represents the location of the median in period t ∈ T (the exact location x t , is defined with respect to the edge to which the median belongs and is given by its distance to the closest end node of the edge); d t (v j , x t ) is the shortest path between v j and x t in period t ∈ T; g(t) is a function representing the unitary cost for relocating the facility in the end of period t moving it from location x t in period t to location x t+1 in period t + 1 (t ∈ T, \(x_{\vert T\vert +1} = x_{\vert T\vert }\)). Hakimi et al. (1999) proved that the vertex-optimality property holds for this problem. The above model and this result can be easily extended to the p-facility case. The formulation is the following:

$$\displaystyle{ \mbox{ Minimize}\quad \sum _{t\in T}\left (\sum _{j\in V }w_{\mathit{jt}}d_{t}(v_{j},X_{t}) + g(t)d_{t}(X_{t},X_{t+1})\right ). }$$
(11.10)

In this case, X 1, …, X  | T |  are the sets of locations for the p facilities during the planning horizon with \(X_{\vert T\vert +1} = X_{\vert T\vert }\); \(d_{t}(v_{j},X_{t}) =\min \{ d_{t}(v_{j},x_{k})\,\mid \,x_{k} \in X_{t}\}\); d t (X t , X , t+1) is defined by the total weight of a minimum weight perfect matching in the complete bipartite graph G t (X t , X t+1) defined as follows: X t and X t+1 define the partition; for every point x ′ in X t and for every point x ′ ′ in X t+1 the weight of the edge (x ′, x ′ ′) is given by d t (x ′, x ′ ′). In (11.10), g(t) denotes the unitary cost for relocating a facility in (the end of) time period t ∈ T. This problem is NP-hard since it includes the static network p-median problem as a particular case. For this reason, the authors developed a heuristic procedure.

One important class of facility location problems on networks are center problems. The multi-period extension of the 1-center problem on a network was proposed also by Hakimi et al. (1999). The model is the following (the notation is the same presented above):

$$\displaystyle{ \begin{subarray}{1}\mbox{ Minimize}\\ x_{1 },x_{2 },\ldots,x_{ \vert T\vert +1}\end{subarray}\quad \sum _{t\in T}\max _{j\in V }\left \{w_{\mathit{jt}}d_{t}(v_{j},x_{t}) + g(t)d_{t}(x_{t},x_{t+1})\right \}. }$$
(11.11)

Again, \(X_{\vert T\vert +1} = X_{\vert T\vert }\). If the choice for x t is restricted to a finite number of points in the network, the problem can be handled using a technique similar to the one presented in the same paper for the multi-period p-median problem.

The existing literature reveals that for most of the multi-period extensions proposed so far for well-known minsum facility location problems, the vertex-optimality property holds. This reduces the location space to a discrete set. Accordingly, models and techniques from integer programming and combinatorial optimization emerge as a possibility for tackling these problems. Multi-period minmax facility location problems on networks have been scarcely investigated.

4 Discrete Problems

We start with one of the best-known discrete facility location problems, the p-median problem (see Chap.2), which can be easily extended to a multi-period setting. Consider a set J, of nodes, whose demand must be supplied during a finite multi-period planning horizon, T. Let I ⊆ J be the set of nodes where the facilities can be located and assume that p facilities have to be operating in each period. The problem of deciding the best location for the facilities throughout the planning horizon, minimizing the total cost for satisfying the demand can be formulated as follows:

$$\displaystyle{ \mbox{ Minimize}\quad \sum _{t\in T}\sum _{i\in I}\sum _{j\in J}c_{\mathit{ijt}}x_{\mathit{ijt}} }$$
(11.12)
$$\displaystyle{ \mbox{ subject to}\quad \sum _{i\in I}x_{\mathit{ijt}} = 1,\quad t \in T,\:j \in J }$$
(11.13)
$$\displaystyle{ \quad \sum _{j\in J}x_{\mathit{ijt}} \leq \vert J\vert x_{\mathit{iit}},\quad t \in T,\:i \in I }$$
(11.14)
$$\displaystyle{ \quad \sum _{i\in I}x_{\mathit{iit}} = p,\quad t \in T }$$
(11.15)
$$\displaystyle{ \quad x_{\mathit{ijt}} \in \{ 0,1\},\quad t \in T,\:i \in I,\:j \in J. }$$
(11.16)

In this formulation, c ijt represents the cost for allocating demand node j ∈ J to facility i ∈ I in period t ∈ T; x ijt is a binary variable equal to 1 if demand node j ∈ J is allocated to facility i ∈ I in period t ∈ T and 0 otherwise; x iit  = 1 indicates that a facility is operating at i ∈ I in period t ∈ T (i is allocated to itself). When I = J we have a multi-period p-median problem.

In order to progressively build models that are more relevant from a practical point of view, we first note that the above problem still has little “multi-period flavor” because it can be decoupled, leading to | T | single-period problems. Nevertheless, this model is an excellent basis for what we present next. In fact, a more interesting multi-period problem emerges if we include opening and closing costs for the facilities. This was first done by Wesolowsky and Truscott (1975). The extended problem can be formulated as follows:

$$\displaystyle{ \mbox{ Minimize}\quad \sum _{t\in T}\sum _{i\in I}\sum _{j\in J}c_{\mathit{ijt}}x_{\mathit{ijt}} +\sum _{t\in T}\sum _{i\in I}g_{\mathit{it}}z_{\mathit{it}}^{{\prime}} +\sum _{ t\in T}\sum _{i\in I}h_{\mathit{it}}z_{\mathit{it}}^{{\prime\prime}} }$$
(11.17)
$$\displaystyle\begin{array}{rcl} & & \mbox{ subject to}\quad \mbox{ (11.13)\textendash (11.16)} \\ & & \qquad \qquad \qquad \sum _{i\in I}z_{\mathit{it}}^{{\prime}}\leq m_{ t},\qquad t \in T {}\end{array}$$
(11.18)
$$\displaystyle{ \quad x_{\mathit{iit}} - x_{\mathit{ii},t-1} + z_{i,t-1}^{{\prime\prime}}- z_{\mathit{ it}}^{{\prime}} = 0,\qquad t \in T\setminus \{1\},\:i \in I }$$
(11.19)
$$\displaystyle{ \quad z_{\mathit{it}}^{{\prime}},z_{\mathit{ it}}^{{\prime\prime}}\in \{ 0,1\},\qquad t \in T,\:i \in I. }$$
(11.20)

In this model, facilities are assumed to be opened (closed) at the beginning (end) of time periods; m t is the maximum number of facilities that can be opened in each period t ∈ T, whereas the binary variable z it ′ (\(z_{\mathit{it}}^{{\prime\prime}}\)) is equal to 1 if a facility is opened (closed) at i ∈ I in period t ∈ T and 0 otherwise; g it and h it (i ∈ I, t ∈ T) denote the opening and closing costs, respectively. Wesolowsky and Truscott (1975) solve the above problem using dynamic programming. However, the method can only be used for instances with a small number of potential locations for the facilities because the dimension of the state space is exponential in this number.

Galvão and Santibañez-Gonzalez (1992) do not consider closing decisions and assume that the number of operating facilities does not have to be the same in all periods. Their formulation can be obtained from the above model by ignoring the variables and costs associated with closing the facilities and by replacing p with p t in (11.15). For each period t ∈ T, p t denotes the number of facilities to be operating in that period. Furthermore, in their model constraints (11.18) are redundant (m t  =  | I | , t ∈ T) and constraints (11.14) are disaggregated, yielding

$$\displaystyle{ x_{\mathit{ijt}} \leq x_{\mathit{iit}},\quad t \in T,\:i \in I,\:j \in J. }$$
(11.21)

Without closing decisions, constraints (11.19) can be written as

$$\displaystyle{ z_{\mathit{it}}^{{\prime}}\geq x_{\mathit{ iit}} - x_{ii,t-1},\quad t \in T\setminus \{1\},\:i \in I. }$$
(11.22)

For this problem, Galvão and Santibañez-Gonzalez (1992) proposed two Lagrangean relaxation based procedures for computing lower and upper bounds: in the first one, constraints (11.13) and (11.22) are dualized; in the second, the choice involves constraints (11.21) and (11.22).

In all of the problems presented so far in this section, facilities can be opened and closed more than once during the planning horizon. However, in many applications this is not realistic. In order to illustrate how this aspect can be captured, we consider another well-known problem: the uncapacitated facility location problem (UFLP) described in Chap.3. Like for the p-median problem, the extension of the UFLP to a multi-period setting is straightforward. Again we consider a finite multi-period planning horizon, T. The set of potential locations for the facilities is denoted by I = { 1, …, m} and the set of demand nodes by J = { 1, …, n}. Additionally, let f it be the cost for operating facility i ∈ I in period t ∈ T, and c ijt the cost for satisfying all the demand of customer j ∈ J in period t ∈ T from facility i ∈ I. A multi-period uncapacitated facility location problem is the following:

$$\displaystyle{ \mbox{ Minimize}\quad \sum _{t\in T}\sum _{i\in I}f_{\mathit{it}}y_{\mathit{it}} +\sum _{t\in T}\sum _{i\in I}\sum _{j\in J}c_{\mathit{ijt}}x_{\mathit{ijt}} }$$
(11.23)
$$\displaystyle{ \mbox{ subject to}\quad \sum _{i\in I}x_{\mathit{ijt}} = 1,\quad t \in T,\:j \in J }$$
(11.24)
$$\displaystyle{ \quad \sum _{j\in J}x_{\mathit{ijt}} \leq ny_{\mathit{it}},\quad t \in T,\:i \in I }$$
(11.25)
$$\displaystyle{ \quad x_{\mathit{ijt}} \geq 0,\quad t \in T,\:i \in I,\:j \in J }$$
(11.26)
$$\displaystyle{ \quad y_{\mathit{it}} \in \{ 0,1\},\quad t \in T,\:i \in I. }$$
(11.27)

In this formulation, x ijt represents the fraction of the demand of customer j ∈ J in period t ∈ T that is supplied by facility i ∈ I; y it is a binary variable equal to 1 if a facility is operating at i ∈ I in period t ∈ T and 0 otherwise. Again, this problem can be decomposed into | T | single-period problems. Nevertheless, it contains the basic ingredients for building more interesting models. In fact, one extension of this problem was proposed by Warszawski (1973), who included opening costs for the facilities. These costs are incurred whenever a facility is opened (even if the same facility has operated in some past period). Denoting by g it the cost for opening a facility at i ∈ I in the beginning of period t ∈ T, the model proposed by Warszawski (1973) differs from (11.23)–(11.27) by considering the following quadratic objective function:

$$\displaystyle{ \qquad \sum _{t\in T}\sum _{i\in I}g_{\mathit{it}}y_{\mathit{it}}\left (1 - y_{i,t-1}\right ) +\sum _{t\in T}\sum _{i\in I}f_{\mathit{it}}y_{\mathit{it}} +\sum _{t\in T}\sum _{i\in I}\sum _{j\in J}c_{\mathit{ijt}}x_{\mathit{ijt}}, }$$
(11.28)

with y i0 = 0, i ∈ I. Warszawski (1973) considered dynamic programming for solving instances with a small number of potential locations for the facilities, | I | , and a local search heuristic for larger instances. Chardaire et al. (1996) studied the same problem starting by disaggregating constraints (11.25). They developed a Langragean relaxation based algorithm for computing lower and upper bounds. A linearized model was also proposed and compared with the quadratic one in terms of the quality of the lower bounds produced.

Another extension of model (11.23)–(11.27) was proposed by Canel and Khumawala (1997) for locating facilities across different countries. They explicitly considered binary decision variables z it indicating whether or not a new facility is opened at i ∈ I in period t ∈ T. They proposed a profit maximization problem as follows:

$$\displaystyle{ \mbox{ Maximize}\quad \sum _{t\in T}\sum _{i\in I}\sum _{j\in J}r_{\mathit{ijt}}x_{\mathit{ijt}} -\sum _{t\in T}\sum _{i\in I}f_{\mathit{it}}y_{\mathit{it}} -\sum _{t\in T}\sum _{i\in I}g_{\mathit{it}}z_{\mathit{it}} }$$
(11.29)
$$\displaystyle\begin{array}{rcl} & & \mbox{ subject to}\quad \mbox{ (11.24)},\mbox{ (11.26)},\mbox{ (11.27)} \\ & & \qquad \qquad \qquad \sum _{j\in P_{\mathit{it}}}x_{\mathit{ijt}} \leq n_{\mathit{it}}y_{\mathit{it}},\quad t \in T,\:i \in I {}\end{array}$$
(11.30)
$$\displaystyle{ \quad z_{\mathit{it}} \geq y_{\mathit{it}} - y_{i,t-1},\quad t \in T,\:i \in I }$$
(11.31)
$$\displaystyle{ \quad z_{\mathit{it}} \in \{ 0,1\},\quad t \in T,\:i \in I, }$$
(11.32)

with y i0 = 0, i ∈ I. In this model, r ijt represents the revenue obtained when supplying all the demand of customer j ∈ J in period t ∈ T from facility i ∈ I. For each facility i ∈ I there is a maximum number of customers, n it , it can supply in period t ∈ T. Furthermore, not all the facilities can supply all customers. In particular, P it represents the set of customers that can be served from facility i ∈ I in period t ∈ T. As we will see below, constraints (11.30) had been proposed before for another problem. Canel and Khumawala (1997) developed a branch-and-bound procedure for this problem adapting the algorithm proposed by Khumawala (1972), and Canel and Khumawala (2001) proposed a heuristic approach for the same problem.

In all of the above problems, facilities can be opened and closed more than once during the planning horizon. Dias et al. (2007) point out that these models ignore the fact that re-opening a facility has in general a smaller cost than opening it for the first time (for instance, land acquisition costs are incurred only once). They propose a model taking this aspect into account. Additional decision variables are required to distinguish whether a facility is being opened for the first time or is being re-opened. A primal-dual heuristic is proposed for obtaining lower and upper bounds for the problem. The gap is closed using a branch-and-bound procedure.

5 Modular Construction of Intrinsic Multi-Period Facility Location Models

In many practical situations it is not acceptable to install and remove a facility, say, in consecutive periods. This may make sense for seasonal facilities, such as warehouses if, for instance, they can be rented for short time intervals. Nevertheless, this cannot be assumed in general. Accordingly, the models presented in the previous section may be short for capturing some real-world problems. Early, researchers have noticed this fact and have considered models involving constraints that impose a limit on the number of changes performed in each location during the planning horizon. Often, such constraints state that once a facility is installed (removed), it must remain opened (closed) until the end of the planning horizon.

We consider again the multi-period p-median problem, i.e., we assume that a plan is to be made for locating exactly p facilities in a finite multi-period planning horizon T. Let us assume that removing facilities is not allowed. One additional feature that may be worth considering for this type of problem is the speed at which p changes. The adequate model is the following (the notation was introduced in Sect. 11.4):

$$\displaystyle{ \mbox{ Minimize}\quad \sum _{t\in T}\sum _{i\in I}\sum _{j\in J}c_{\mathit{ijt}}x_{\mathit{ijt}} }$$
(11.33)
$$\displaystyle{ \mbox{ subject to}\quad \sum _{i\in J}x_{\mathit{ijt}} = 1,\quad t \in T,j \in J }$$
(11.34)
$$\displaystyle{ \quad \sum _{j\in J}x_{\mathit{ijt}} \leq nx_{\mathit{iit}},\quad t \in T,\:i \in J }$$
(11.35)
$$\displaystyle{ \quad \sum _{i\in J}x_{\mathit{iit}} = p_{t},\quad t \in T }$$
(11.36)
$$\displaystyle{ \quad x_{\mathit{iit}} \geq x_{\mathit{ii},t-1},\quad t = 2,\ldots,\vert T\vert,\:i \in J }$$
(11.37)
$$\displaystyle{ \quad x_{\mathit{ijt}} \geq 0,\quad t \in T,\:i \in J,\:j \in J, }$$
(11.38)

where 1 ≤ p 1 ≤ p 2 ≤ … ≤ p  | T |  = p.

Constraints of type (11.37) were first proposed for a multi-period facility location problem by Roodman and Schwarz (1975, 1977). The latter paper was pioneering in the assumption that a set of facilities may be operating before the beginning of the planning horizon. These are the facilities that can be removed. Therefore, the possibility of adapting an existing system to predictable changes in some parameters, becomes explicitly considered in the models. The set of locations I can now be partitioned into two subsets: I c and I o. The former represents the facilities that are operating before the beginning of the planning horizon; the latter represents the set of locations for new facilities. A more comprehensive model for the multi-period facility location problem emerges:

$$\displaystyle\begin{array}{rcl} & & \mbox{ Minimize}\quad \mbox{ (11.23)} \\ & & \mbox{ subject to}\quad \mbox{ (11.24)\textendash (11.27)} \\ & & \qquad \qquad \quad y_{\mathit{it}} \leq y_{i,t-1},\quad t = 2,\ldots,\vert T\vert,\:i \in I^{c}{}\end{array}$$
(11.39)
$$\displaystyle{ \quad y_{\mathit{it}} \geq y_{i,t-1},\quad t = 2,\ldots,\vert T\vert,\:i \in I^{o}. }$$
(11.40)

Roodman and Schwarz (1977) were also pioneering by considering a maximum number of customers that can be served by each facility in each period and assumed that not all facilities can serve all customers. These aspects are easily accommodated in the above model if we replace (11.25) by (11.30). As mentioned before, the latter constraints would be later considered by Canel and Khumawala (1997). The research done by Roodman and Schwarz (1977) extends the work by the same authors published 2 years before (Roodman and Schwarz 1975) in which a pure phase-out problem had been considered.

The above models allow the removal of an existing facility before the beginning of period 1 with no costs imputed to the planning horizon. Imposing that the existing facilities must operate in at least one period, can be easily done by setting y i1 = 1, i ∈ I c.

Van Roy and Erlenkotter (1982) proposed a reformulation of model (11.23)–(11.27), (11.39), and (11.40). Their idea, which can be extended to every multi-period facility location problem, consists of considering binary decision variables representing a change in a location instead of considering the traditional location variables. In particular, for an existing facility i ∈ I c, a new binary variable z it , can be defined that is equal to 1 if the facility is removed at the end of period t (i.e., it operates in periods 1, …, t) and 0 otherwise. For facility i ∈ I c, z i | T |  = 1, indicates that the facility is operating during the entire planning horizon. For a potential new facility i ∈ I o, the binary variable, z it , is equal to 1 if it is installed at the beginning of period t (i.e., it operates in periods t, …, | T | ) and 0 otherwise. Using the new set of variables, we obtain the following model:

$$\displaystyle{ \mbox{ Minimize}\quad \sum _{t\in T}\sum _{i\in I}F_{\mathit{it}}z_{\mathit{it}} +\sum _{t\in T}\sum _{i\in I}\sum _{j\in J}c_{\mathit{ijt}}x_{\mathit{ijt}} }$$
(11.41)
$$\displaystyle{ \mbox{ subject to}\quad \sum _{i\in I}x_{\mathit{ijt}} = 1,\quad t \in T,\:j \in J }$$
(11.42)
$$\displaystyle{ \quad x_{\mathit{ijt}} \leq \sum _{\tau \in \overline{T}_{\mathit{ it}}}z_{i\tau },\quad t \in T,\:i \in I,\:j \in J }$$
(11.43)
$$\displaystyle{ \quad x_{\mathit{ijt}} \geq 0,\quad t \in T,\:i \in I,\:j \in J }$$
(11.44)
$$\displaystyle{ \quad z_{\mathit{it}} \in \{ 0,1\},\quad t \in T,\:i \in I. }$$
(11.45)

In this model, F it (i ∈ I, t ∈ T) represents the total operation cost for facility i if z it  = 1, i.e., \(F_{\mathit{it}} = f_{i1} +\ldots +f_{\mathit{it}}\) for i ∈ I c, t ∈ T and \(F_{\mathit{it}} = f_{\mathit{it}} +\ldots +f_{i\vert T\vert }\) for i ∈ I o, t ∈ T. The set \(\overline{T}_{\mathit{it}}\) contains the periods in which it is possible to remove (install) a facility at i ∈ I c (i ∈ I o) if we want to have it operating in period t ∈ T. More formally, \(\overline{T}_{\mathit{it}} =\{ t,\ldots,\vert T\vert \}\) if i ∈ I c and \(\overline{T}_{\mathit{it}} =\{ 1,\ldots,t\}\) if i ∈ I o. It is important to note that the aggregated costs F it can be easily extended to more general situations, such as the one in which we have fixed setup and removal costs for the facilities. In fact, suppose that a fixed cost g it is incurred when removing (installing) a facility i ∈ I c (i ∈ I o) in period t. We can simply set \(F_{\mathit{it}} = g_{\mathit{it}} + f_{i1} +\ldots +f_{\mathit{it}}\) for i ∈ I c, t ∈ T and \(F_{\mathit{it}} = g_{\mathit{it}} + f_{\mathit{it}} +\ldots +f_{i\vert T\vert }\) for i ∈ I o, t ∈ T.

The relation between the previous y-variables and the new z-variables is straightforward:

$$\displaystyle\begin{array}{rcl} \begin{array}{llll} &z_{i\vert T\vert } = y_{i\vert T\vert }, &&\quad i \in I^{c} \\ &z_{\mathit{it}} = y_{\mathit{it}} - y_{i,t+1},&&\quad t \in \{ 1,\ldots,\vert T\vert - 1\},\:i \in I^{c} \\ &z_{i1} = y_{i1}, &&\quad i \in I^{o} \\ &z_{\mathit{it}} = y_{\mathit{it}} - y_{i,t-1},&&\quad t \in \{ 2,\ldots,\vert T\vert \},\:i \in I^{o}\end{array} & & {}\\ \end{array}$$

Using these relations, it is straightforward to prove that model (11.23)–(11.27), (11.39), and (11.40) is equivalent to model (11.41)–(11.45). The relevance of the latter arises from the fact that it is particularly suited for the application of a dual-based heuristic, which is a popular method for obtaining sharp lower and upper bounds for discrete facility location problems. This fact was explored by Van Roy and Erlenkotter (1982). Multiplying constraints (11.43) by − 1 the dual of the linear relaxation of model (11.41)–(11.45) becomes:

$$\displaystyle\begin{array}{rcl} \mbox{ Maximize}\quad \sum _{t\in T}\sum _{j\in J}v_{\mathit{jt}}& &{}\end{array}$$
(11.46)
$$\displaystyle\begin{array}{rcl} \mbox{ subject to}\quad v_{\mathit{jt}} - w_{\mathit{ijt}} \leq c_{\mathit{ijt}},\quad t \in T,\:i \in I,\:j \in J& &{}\end{array}$$
(11.47)
$$\displaystyle\begin{array}{rcl} \quad \sum _{j\in J}\sum _{\tau \in T_{\mathit{it}}}w_{\mathit{ij}\tau } \leq F_{\mathit{it}},\quad t \in T,\:i \in I& &{}\end{array}$$
(11.48)
$$\displaystyle\begin{array}{rcl} \quad w_{\mathit{ijt}} \geq 0,\quad t \in T,\:i \in I,\:j \in J.& &{}\end{array}$$
(11.49)

In this model, v jt and w ijt (t ∈ T, i ∈ I, j ∈ J) are the dual variables associated with constraints (11.42) and (11.43), respectively (with the latter previously multiplied by − 1). The set T it (i ∈ I, t ∈ T) contains the operating periods for facility i if a change (installation or removal) occurs in this location in period t. In particular, T it  = { 1, …, t} if i ∈ I c and T it  = { t, …, | T | } if i ∈ I o.

From (11.47) and (11.49) we may set

$$\displaystyle{w_{\mathit{ijt}} =\max \{ 0,v_{\mathit{jt}} - c_{\mathit{ijt}}\},\quad t \in T,\:i \in I,\:j \in J,}$$

which yields the following condensed dual:

$$\displaystyle\begin{array}{rcl} & & \mbox{ Maximize}\quad \mbox{ (11.46)} \\ & & \mbox{ subject to}\quad \sum _{j\in J}\sum _{\tau \in T_{\mathit{it}}}\max \{0,v_{\mathit{jt}} - c_{\mathit{ijt}}\} \leq F_{\mathit{it}},\quad t \in T,\:i \in I.{}\end{array}$$
(11.50)

The complementary slackness conditions for the linear relaxation of model (11.41)–(11.45) are the following:

$$\displaystyle\begin{array}{rcl} \begin{array}{llll} &v_{\mathit{jt}}\left (\sum _{i\in I}x_{\mathit{ijt}} - 1\right ) = 0 &&\quad t \in T,\:j \in J \\ &w_{\mathit{ijt}}\left (\sum _{\tau \in \overline{T}_{\mathit{ it}}}z_{i\tau } - x_{\mathit{ijt}}\right ) = 0, &&\quad t \in T,\:i \in I,\:j \in J \\ &x_{\mathit{ijt}}\left (v_{\mathit{jt}} - c_{\mathit{ijt}} - w_{\mathit{ijt}}\right ) = 0,&&\quad t \in T,\:i \in I,\:j \in J \\ &z_{\mathit{it}}S_{\mathit{it}} = 0, &&\quad t \in T,\:i \in I,\end{array} & & {}\\ \end{array}$$

where S it represent the slack variables for constraints (11.50).

Van Roy and Erlenkotter (1982) proposed a heuristic for the condensed dual just presented. Starting from the trivial dual feasible solution defined by \(v_{\mathit{jt}} =\min _{i\in I}\{c_{\mathit{ijt}}\}\) (t ∈ T, j ∈ J) an ascent procedure is performed for increasing the values of the dual variables v jt , thus increasing the value of the dual objective function. When this procedure does not lead to further improvements, a primal solution is constructed using the slackness conditions. Finally, a primal-dual adjustment phase is performed in order to reduce the gap between the values of the primal and dual objective functions. When no further gap reduction is achieved, a branch-and-bound procedure is applied to complete the search for an optimal solution for the problem. The reader should refer to Van Roy and Erlenkotter (1982) for further details.

The procedure developed by Van Roy and Erlenkotter (1982) is quite efficient to solve instances of moderate size. Nevertheless, this multi-period facility location problem includes the UFLP as a special case and thus, it is NP-hard. For this reason, Saldanha-da-Gama and Captivo (1998) proposed a two-phase heuristic procedure for the problem. The first phase is a drop procedure which starts with all facilities operating in all periods, and progressively removes operating periods to the facilities. This is done while a reduction in the total cost is observed. Losing feasibility is never allowed during the process. The second phase consists of a local search procedure.

Although representing an important basis for describing real problems, the above models still miss one important feature found in many applications: capacity constraints. Denote by Q i the capacity of a facility located at i ∈ I, and by d jt the demand of customer j ∈ J in period t ∈ T. A capacitated multi-period facility location problem consists of minimizing (11.41) subject to (11.42), (11.44), (11.45), and

$$\displaystyle{ \sum _{j\in J}d_{\mathit{jt}}x_{\mathit{ijt}} \leq Q_{i}\sum _{\tau \in \overline{T}_{\mathit{ it}}}z_{i\tau },\quad t \in T,\:i \in I. }$$
(11.51)

This model was addressed by Saldanha da Gama (2002) who developed a dual-based procedure for obtaining lower and upper bounds. The model was previously enhanced with (11.43) and

$$\displaystyle{ \sum _{t\in T}\sum _{i\in I}R_{\mathit{kit}}z_{\mathit{it}} \leq r_{k},\quad k \in K. }$$
(11.52)

By choosing appropriate values for R kit and r k , these generic constraints can accommodate every inequality involving the binary variables. This is important because the linear relaxation of capacitated facility location problems can often be strengthened through the inclusion of valid inequalities involving the location variables. For instance, a set of constraints often used in (static) capacitated facility location problems, state that the operational capacity must be at least equal to the total demand. In the multi-period case, these constraints are written as

$$\displaystyle{ \sum _{i\in I}\left (Q_{i}\sum _{\tau \in \overline{T}_{\mathit{ it}}}z_{i\tau }\right ) \geq \sum _{j\in J}d_{\mathit{jt}},\quad t \in T, }$$
(11.53)

which can be easily accommodated in (11.52).

For the linear relaxation of model (11.41)–(11.45), (11.51), and (11.52), Saldanha da Gama (2002) extended the dual-based procedure proposed by Van Roy and Erlenkotter (1982), thus obtaining sharp lower and upper bounds for the problem.

The inclusion of capacity constraints is an important step towards building more comprehensive multi-period facility location models. Nevertheless, the capacity constraints (11.51) are rather restrictive when it comes to real applications, namely those arising in logistics (see Chap. 16). By considering a fixed capacity in each location, these constraints neglect the possibility of making future adjustments in the capacity of the facilities, which is a feature quite relevant in practice. In fact, it is often the case that adjusting the capacity of an existing facility is more advantageous from a cost point of view than installing a new facility in some other location. One attempt to overcome such restrictive representation for the capacities was made by Van Roy and Erlenkotter (1982) who considered exogenous time-dependent capacities Q it (i ∈ I, t ∈ T). Nevertheless, this is still unsatisfactory from a practical point of view because no connection is established between the capacities in different periods.

The problem of planning for the capacity expansion of existing facilities was very much in focus in the 1970s and in the 1980s (see, for instance, Erlenkotter 1981, and Lee and Luss 1987). However, at that time, the focus was put mainly on the expansion of existing facilities. In many cases, the location of facilities was not even a decision to make. Furthermore, many of these works considered continuous adjustments in the capacities, which is often not adequate from a practical point of view. In fact, if we think of production or sorting lines, we immediately realize that changes in the capacities should be modular, or at least discrete.

One paper that clearly interconnects multi-period facility location decisions with discrete capacity expansion is due to Shulman (1991). A set of facility types P is considered, and in each location, facilities of different types can be progressively established during the planning horizon, as a way of adjusting the operating capacity of the system. In each period, at most one facility of each type can be installed in each location but several facilities can be installed if they are of different types. For each location i ∈ I, a set P i  ⊆ P is assumed, corresponding to the set of facility types that can be located at i. Denote by c ijpt the cost for supplying all the demand of customer j ∈ J in period t ∈ T from a facility operating at i ∈ I that is of type p ∈ P i . Let f ipt be the cost for installing a facility of type p ∈ P i at i ∈ I in period t ∈ T. Additionally, let Q p be the capacity of a facility of type p ∈ P. Finally, let n ip0 denote the number of facilities of type p ∈ P i operating at location i ∈ I before the beginning of the planning horizon (i.e., the problem captures the situation in which the system is not built from scratch but is to be adapted to future changes in demands). The demand of customer j ∈ J in period t ∈ T is again denoted by d jt . Two sets of decision variables were proposed by Shulman (1991): x ijpt , representing the fraction of the demand of customer j ∈ J in period t ∈ T that is satisfied from a facility operating at i ∈ I that is of type p ∈ P i , and y ipt denoting a binary variable that is equal to 1 if in period t ∈ T a facility of type p ∈ P i is installed at i ∈ I and 0 otherwise. Assuming that the capacity expansions occur at the beginning of the time periods, the problem can be formulated as follows:

$$\displaystyle{ \mbox{ Minimize}\quad \sum _{t\in T}\sum _{i\in I}\sum _{p\in P_{i}}f_{\mathit{ipt}}y_{\mathit{ipt}} +\sum _{t\in T}\sum _{i\in I}\sum _{j\in J}\sum _{p\in P_{i}}c_{\mathit{ijpt}}x_{\mathit{ijpt}} }$$
(11.54)
$$\displaystyle{ \mbox{ subject to}\quad \sum _{i\in I}\sum _{p\in P_{i}}x_{\mathit{ijpt}} = 1,\quad t \in T,\:j \in J }$$
(11.55)
$$\displaystyle\begin{array}{rcl} \quad \sum _{j\in J}d_{\mathit{jt}}x_{\mathit{ijpt}} \leq n_{\mathit{ip}0}Q_{p} +\sum _{ \tau =1}^{t}Q_{ p}y_{\mathit{ip}\tau },\quad t \in T,\:i \in I,\:p \in P_{i}& &{}\end{array}$$
(11.56)
$$\displaystyle\begin{array}{rcl} \quad x_{\mathit{ijpt}} \geq 0\quad t \in T,\:i \in I,\:j \in J,\:p \in P_{i}& &{}\end{array}$$
(11.57)
$$\displaystyle\begin{array}{rcl} \quad y_{\mathit{ipt}} \in \{ 0,1\},\quad t \in T,\:i \in I,\:p \in P_{i}.& &{}\end{array}$$
(11.58)

The values c ijpt may include the transportation costs between facilities and customers as well as handling costs at the facilities. Shulman (1991) proposed a Lagrangean relaxation based procedure for obtaining lower and upper bounds for the problem. Constraints (11.55) are dualized. The relaxed problem can be decomposed into | I | problems, each of which to be solved exactly by dynamic programming. However, the complexity of this algorithm is exponential in the number of facilities. Therefore, it can only be used when | I | is small. Nevertheless, for the particular case in which it is not possible to mix different facility types in the same location (i.e., | P i  |  = 1, i ∈ I), a polynomial algorithm for the relaxed problem was proposed in the same paper.

The need for more comprehensive multi-period facility location models suited for being applied to real-world problems has led to further important developments. Hinojosa et al. (2000) proposed the first multi-period, multi-echelon, multi-product capacitated discrete facility location problem, setting one important foundation for the strong link that we observe nowadays between multi-period facility location and logistics network design (see Chap. 16). Two facility echelons are considered in that work: plants and warehouses. Location decisions are to be made for both. This paper extends the models proposed by Roodman and Schwarz (1977) by considering more than one facility echelon and multiple commodities. Existing facilities are assumed to be operating before period 1 and can be removed during the planning horizon. Additionally, a set of potential locations for establishing new facilities during the planning horizon is considered. Once removed, a facility cannot be opened again, and once installed, a facility must remain opened until the end of the planning horizon. Hinojosa et al. (2000) proposed a Lagrangean relaxation based procedure in order to compute lower and upper bounds. The problem would be later extended by Hinojosa et al. (2008) to include inventory decisions. The new model proposed extends the reformulation proposed by Van Roy and Erlenkotter (1982) (i.e., the decision variables represent the changes in the locations—installation of new facilities and removal of existing ones—in the different periods of the planning horizon). A Lagrangean relaxation based procedure was also proposed.

Canel et al. (2001) also investigated a system with two echelons: factories and facilities (e.g., distribution centers). Unlike the problems investigated by Hinojosa et al. (2000, 2008), location decisions are to be made only for the lower echelon. Furthermore, facilities can be opened and closed more than once during the planning horizon. Multiple commodities are considered as well as an important feature much relevant is real logistic systems: the possibility of making direct shipments from the upper echelon to the customers. The authors proposed an exact approach for the problem based on branch-and-bound and dynamic programming.

Jena et al. (2012) investigated a multi-period capacitated facility location problem that in addition to the decisions about where to locate new facilities, consider the possibility of relocating existing facilities or expanding the capacity of existing ones. The authors also consider the possibility of temporarily closing facility parts. The problem arises within the context of logging companies that wish to plan for locating accommodation camps for their workers over some finite planning horizon. The authors proposed several mixed integer linear programming formulations for the problem that they compared in terms of the bounds provided by linear relaxation and tested in instances that use data provided by a real company. They also observed that the problem calls for a very specific cost structure associated with capacity changes. This motivated a more recent work (Jena et al. 2014) in which a general cost structure is associated with capacity changes. A mixed integer linear programming modeling framework was then proposed and shown to generalize two important special cases: facility closing and reopening and capacity expansion and reduction. Alternative formulations were also proposed for these special cases which were compared with the above general modeling framework in terms of the linear relaxation bounds. A combination of the above mentioned cases can also be accommodated in the general modeling framework proposed. In that work, the general model was solved using an off-the-shelf solver. Computational tests were performed using a large set of generated instances.

Albareda-Sambola et al. (2009) extended the model proposed by Roodman and Schwarz (1977) for handling the so-called multi-period incremental service facility location problem. In each time period, a minimum number of facilities is to be established that should be kept operating until the end of the planning horizon. All the customers must start being served in some period and remain served until the end of the planning horizon. The problem is motivated by some practical problems requiring a multi-period plan for progressively extending some service to the population in some region. Accordingly, the service level is progressively increased over time until all customers are being served. A Lagrangean relaxation based procedure was proposed in that paper for obtaining lower and upper bounds. A particular case of this problem was addressed by Albareda-Sambola et al. (2010), assuming that each customer requires service only in a subset of periods. Additionally, it is possible not to fulfil the request in one or several of those periods but in this case, a penalty cost is paid. Several mathematical programming formulations were proposed for the problem, which were compared computationally.

A multi-period discrete facility location problem was also investigated by Gourdin and Klopfenstein (2008). The problem is motivated within the context of telecommunications network design and consists of planning for the location of modular equipment over a finite planning horizon. Operating capacity constraints are considered for the nodes and for the links. The goal is to progressively expand the capacity of the equipment as well as the capacity of its links to the demand nodes. In that paper, the mathematical programming model initially proposed for the problem was enhanced via polyhedral analysis.

6 The Value of the Multi-Period Solution

Multi-period modeling frameworks like those proposed in the previous sections, involve one extra dimension in the decision space: the time. Models tend to be large and thus more difficult to tackle, even for instances of moderate size. Accordingly, one may ask whether it is worth considering this extra dimension. In other words, let us consider a situation in which it is possible to make a static decision even with costs, demands (and possibly other parameters) varying over time. Is it still worth considering a multi-period modeling framework? An answer to this question can be given by the value of the multi-period solution, which is a concept first introduced by Alumur et al. (2012) in the context of a multi-period reverse logistics network design problem.

The value of the multi-period solution compares the optimal value of the multi-period problem and the value of a solution found by solving a static counterpart. A static counterpart is a problem that takes into account the information available for the planning horizon and looks for a static (time invariant) solution. Given the optimal solution to a static counterpart, one can consider again the original multi-period problem and set such solution for all periods of the planning horizon. If, by doing so, we obtain a feasible solution to the multi-period problem, the difference between its value and the optimal value of the multi-period problem gives the value of the multi-period solution. In general, several static counterparts can be associated with a multi-period problem. Depending on the one that is considered, a different static solution may be obtained. Accordingly, the value of the multi-period solution may not be unique.

In a multi-period facility location problem, costs, demands, and possibly other parameters are assumed to change over the planning horizon. A static counterpart is a problem that looks for a static location for the facilities, i.e., that can be implemented at the beginning of period 1 and remain unchanged until the end of the planning horizon. One possibility for building a static counterpart is to somehow aggregate the information available for all periods. For instance, consider time varying demands. If facilities are uncapacitated, then several possibilities emerge for aggregating this information: (1) the demands can be averaged over the planning horizon, or (2) a reference value can be determined (e.g., the maximum value observed throughout the planning horizon). If additional constraints exist (e.g., capacity constraints) then, choosing a reference value may render the resulting static solution infeasible in some periods. In this case, one possibility for building a static counterpart is to define the (time invariant) demand of each customer according to the maximum value observed across all periods. In any case, the adequate aggregation of multi-period data is very much problem-dependent.

In order to clarify the above explanation, we consider problem (11.23)–(11.27), (11.39), and (11.40). A static counterpart can be obtained simply by considering the UFLP with operation costs f i , i ∈ I, equal to the average of the values f it , t ∈ T and distribution costs c ij , i ∈ I, j ∈ J, given by the average of the values c ijt , t ∈ T.

When the value of the multi-period solution is obtained by aggregating the data for all periods we refer to it as a weak value of the multi-period solution. On the other hand, we obtain a strong value of the multi-period solution when no aggregation is performed in the data. This is a possibility in some cases, namely when we can add a set of constraints to the problem stating that some or all decisions are to be the same in all periods of the planning horizon. In the case of a multi-period facility location problem, a static counterpart must define a static location, i.e., a solution in which the location of the facilities is the same for all periods of the planning horizon. Consider, for instance, problem (11.41), (11.42), (11.44), (11.45), and (11.51). A static counterpart yielding a strong value of the multi-period solution is obtained by setting

$$\displaystyle\begin{array}{rcl} \begin{array}{llll} &z_{\mathit{it}} = 0&&\quad t = 1,\ldots,\vert T\vert - 1,\:i \in I^{c}, \\ &z_{\mathit{it}} = 0&&\quad t = 2,\ldots,\vert T\vert,\:i \in I^{o}.\end{array} & & {}\\ \end{array}$$

These conditions simply impose that the status of each location does not change during the planning horizon. Therefore, the set of operating facilities will be the same across all periods.

To the best of our knowledge, the only paper within the context of facility location, in which the relevance of using a multi-period modeling framework is measured is the one by Alumur et al. (2012).

7 Conclusions

In this chapter, we have presented and discussed several essential aspects related with multi-period facility location problems. The existing literature reveals that the topic has achieved a significant level of maturity. From a modeling point of view, it is now clear how to capture several features of practical relevance and how to tackle the resulting models. We discussed the weak and strong values of the multi-period solution as measures for the relevance of using a multi-period modeling framework.

In recent years, much work has been developed on facility location problems arising in the context of logistics systems (see, e.g., Melo et al. 2009). As it will be discussed in Chap. 16, an adequate modeling framework can hardly neglect the multi-period nature of such problems. Some papers within this context that somehow extend some multi-period models discussed in the previous sections are those by Melo et al. (2006) and Manzini and Gebennini (2008).

Another aspect of relevance in many applications regards the uncertain nature of the data underlying the problems. Aghezzaf (2005) addressed a multi-period facility location problem under uncertainty. A robust optimization modeling framework was proposed. Recently, multi-period stochastic facility location problems were addressed by Nickel et al. (2012) and Albareda-Sambola et al. (2013). These works show that capturing uncertainty in multi-period facility location problems is still a challenge.

Another challenging area in multi-period facility location concerns the location of public facilities. One first work in this direction is due to Antunes and Peeters (2001). Although static models for public facilities location have attracted much attention in the past, the same does not happen with multi-period problems.

One class of problems which is still much unexplored, regards multi-criteria, multi-period facility location problems. To the best of our knowledge only a few papers exist within this context. Dias et al. (2008) proposed a memetic algorithm for multi-period problems when it is possible to install and remove a facility more than once during the planning horizon. Hugo and Pistikopoulos (2005) and Melachrinoudis and Min (2007) study multi-criteria, multi-period facility location problems in the context of logistics network design.

Most of the contents in this chapter are a basis for addressing more complex real-world problems. In fact, several models presented in the previous sections have already been extended to problems arising in other areas (see, for instance, Chaps.12,15 and 16). Nevertheless, some challenges still exist. The research done so far is scarce when it comes to some classes of multi-period facility location problems, such as those just mentioned above. These are existing research directions worth exploring in order to broaden the scope and knowledge on multi-period facility location, making the topic an even stronger basis for being applied to real-world systems.