Multi-Period Facility Location - Location Science - page 277

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,