Geoscience Reference
In-Depth Information
changes in demands). The demand of customer j
2
J in period t
2
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
2
J in period t
2
T that
is satisfied from a facility operating at i
2
I that is of type p
2
P
i
,andy
ipt
denoting
a binary variable that is equal to 1 if in period t
2
T a facility of type p
2
P
i
is
installed at i
2
I and 0 otherwise. Assuming that the capacity expansions occur at
the beginning of the time periods, the problem can be formulated as follows:
Minimize
X
t2T
X
X
f
ipt
y
ipt
C
X
t2T
X
X
X
c
ijpt
x
ijpt
(11.54)
i2I
p2P
i
i2I
j2J
p2P
i
subject to
X
i2I
X
x
ijpt
D
1; t
2
T; j
2
J
(11.55)
p2P
i
X
X
t
d
jt
x
ijpt
n
ip
0
Q
p
C
Q
p
y
ip
; t
2
T; i
2
I; p
2
P
i
j2J
D1
(11.56)
x
ijpt
0t
2
T; i
2
I; j
2
J; p
2
P
i
(11.57)
y
ipt
2f
0;1
g
; t
2
T; i
2
I; p
2
P
i
:
(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
j
I
j
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
j
I
j
is small. Nevertheless, for the particular case
in which it is not possible to mix different facility types in the same location (i.e.,
j
P
i
jD
1, i
2
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