Geoscience Reference
In-Depth Information
multi-period uncapacitated facility location problem is the following:
Minimize
X
t2T
X
f
it
y
it
C
X
t2T
X
X
c
ijt
x
ijt
(11.23)
i2I
i2I
j2J
subject to
X
i2I
x
ijt
D
1; t
2
T; j
2
J
(11.24)
X
x
ijt
ny
it
; t
2
T; i
2
I
(11.25)
j2J
x
ijt
0; t
2
T; i
2
I; j
2
J
(11.26)
y
it
2f
0;1
g
; t
2
T; i
2
I:
(11.27)
In this formulation, x
ijt
represents the fraction of the demand of customer j
2
J in
period t
2
T that is supplied by facility i
2
I; y
it
is a binary variable equal to 1 if a
facility is operating at i
2
I in period t
2
T and 0 otherwise. Again, this problem
can be decomposed into
j
T
j
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
2
I in the beginning of period t
2
T , the model proposed
by Warszawski (
1973
) differs from (
11.23
)-(
11.27
) by considering the following
quadratic objective function:
X
X
g
it
y
it
.1
y
i;t1
/
C
X
t2T
X
f
it
y
it
C
X
t2T
X
X
c
ijt
x
ijt
;
(11.28)
t2T
i2I
i2I
i2I
j2J
with y
i0
D
0, i
2
I. Warszawski (
1973
) considered dynamic programming for
solving instances with a small number of potential locations for the facilities,
j
I
j
,
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 Khu-
mawala (
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
2
I in period t
2
T . They proposed a profit maximization problem as
follows:
Maximize
X
t2T
X
X
r
ijt
x
ijt
X
t2T
X
f
it
y
it
X
t2T
X
g
it
z
it
(11.29)
i2I
j2J
i2I
i2I
subject to
(
11.24
); (
11.26
); (
11.27
)
