Geoscience Reference
In-Depth Information
1-median problem on network N can be formulated as follows:
0
@
X
j2V
1
A
:
Minimize
X
t2T
w
jt
d
t
.v
j
;x
t
/
C
g.t/d
t
.x
t
;x
tC1
/
(11.9)
In this model,
w
jt
denotes the weight of vertex v
j
2
V in period t
2
T ; x
t
represents
the location of the median in period t
2
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
2
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
tC1
in period t
C
1 (t
2
T , x
jT jC1
D
x
jT j
). 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:
0
@
X
j2V
1
Minimize
X
t2T
A
:
w
jt
d
t
.v
j
;X
t
/
C
g.t/d
t
.X
t
;X
tC1
/
(11.10)
In this case, X
1
;:::;X
jT j
are the sets of locations for the p facilities during the
planning horizon with X
jT jC1
D
X
jT j
; d
t
.v
j
;X
t
/
D
min
f
d
t
.v
j
;x
k
/
j
x
k
2
X
t
g
;
d
t
.X
t
;X
;tC1
/ is defined by the total weight of a minimum weight perfect matching
in the complete bipartite graph G
t
.X
t
;X
tC1
/ defined as follows: X
t
and X
tC1
define
the partition; for every point x
0
in X
t
and for every point x
00
in X
tC1
the weight of
the edge .x
0
;x
00
/ is given by d
t
.x
0
;x
00
/.In(
11.10
), g.t/ denotes the unitary cost
for relocating a facility in (the end of) time period t
2
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):
X
j2V
˚
w
jt
d
t
.v
j
;x
t
/
C
g.t/d
t
.x
t
;x
tC1
/
:
Minimize
x
1
;x
2
;:::;x
jT jC1
max
(11.11)
t2T
Again, X
jT jC1
D
X
jT j
. 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
