Geoscience Reference
In-Depth Information
A multi-period extension of the planar p-median problem was proposed by
Drezner (
1995
) who considered a finite planning horizon divided into
j
T
jD
p time
periods. The set of demand nodes is denoted by J and demand changes over time.
The demand of node j
2
J is represented by a continuous function of time
w
j
.:/.At
the beginning of each time period t
2
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
2
T . The problem can be formulated as follows:
Minimize
X
t2T
X
D1;:::;t
˚
d
j
.x
;y
/
;
W
jt
min
(11.8)
j2J
where d
j
.x
t
;y
t
/, t
2
T , represents the distance between demand node j
2
J and
the facility established at the beginning of period t
2
T ; W
jt
D
R
a
t
a
t1
w
j
./d; a
t1
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.
11.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
j
T
j
-period p-median, the vertex multi-period .Ǜ
1
;:::;Ǜ
jT j
/-median
and the absolute multi-period .Ǜ
1
;:::;Ǜ
jT j
/-median. Among the different problems
studied, the absolute multi-period .Ǜ
1
;:::;Ǜ
jT j
/-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
2
T , satisfying
P
t2T
Ǜ
t
D
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
D
.V;E;T/, with T representing the planning horizon, it is assumed that the weight of
each vertex v
j
2
V and the length of each edge e
2
E are functions of time and are
invariant in each period. Assuming moving costs for the facilities, the multi-period,