Geoscience Reference
In-Depth Information
optimization emerge as a possibility for tackling these problems. Multi-period
minmax facility location problems on networks have been scarcely investigated.
11.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 .LetI
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:
Minimize
X
t2T
X
X
c
ijt
x
ijt
(11.12)
i2I
j2J
subject to
X
i2I
x
ijt
D
1; t
2
T; j
2
J
(11.13)
X
x
ijt
j
J
j
x
iit
; t
2
T; i
2
I
(11.14)
j2J
X
x
iit
D
p; t
2
T
(11.15)
i2I
x
ijt
2f
0;1
g
; t
2
T; i
2
I; j
2
J:
(11.16)
In this formulation, c
ijt
represents the cost for allocating demand node j
2
J to
facility i
2
I in period t
2
T ; x
ijt
is a binary variable equal to 1 if demand node
j
2
J is allocated to facility i
2
I in period t
2
T and 0 otherwise; x
iit
D
1
indicates that a facility is operating at i
2
I in period t
2
T (i is allocated to itself).
When I
D
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
j
T
j
single-period problems. Nev-
ertheless, 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:
Minimize
X
t2T
X
X
c
ijt
x
ijt
C
X
t2T
X
g
it
z
it
C
X
t2T
X
h
it
z
00
it
(11.17)
i2I
j2J
i2I
i2I
subject to
(
11.13
)-(
11.16
)
