Geoscience Reference
In-Depth Information
X
z it m t ;
t 2 T
(11.18)
i2I
x iit x ii ;t1 C z 0 i;t1 z it D 0;
t 2 T nf 1 g ;i 2 I
(11.19)
z it ; z 00
it 2f 0;1 g ;
t 2 T; i 2 I:
(11.20)
In this model, facilities are assumed to be opened (closed) at the beginning (end) of
time periods; m t is the maximum number of facilities that can be opened in each
period t 2 T , whereas the binary variable z it
( z 00
it ) is equal to 1 if a facility is opened
(closed) at i 2 I in period t 2 T and 0 otherwise; g it and h it (i 2 I, t 2 T ) denote
the opening and closing costs, respectively. Wesolowsky and Truscott ( 1975 )solve
the above problem using dynamic programming. However, the method can only
be used for instances with a small number of potential locations for the facilities
because the dimension of the state space is exponential in this number.
Galvão and Santibañez-Gonzalez ( 1992 ) do not consider closing decisions and
assume that the number of operating facilities does not have to be the same in all
periods. Their formulation can be obtained from the above model by ignoring the
variables and costs associated with closing the facilities and by replacing p with p t
in ( 11.15 ). For each period t 2 T , p t denotes the number of facilities to be operating
in that period. Furthermore, in their model constraints ( 11.18 ) are redundant (m t D
j I j , t 2 T ) and constraints ( 11.14 ) are disaggregated, yielding
x ijt x iit ; t 2 T; i 2 I; j 2 J:
(11.21)
Without closing decisions, constraints ( 11.19 ) can be written as
z it x iit x ii;t1 ; t 2 T nf 1 g ;i 2 I:
(11.22)
For this problem, Galvão and Santibañez-Gonzalez ( 1992 ) proposed two
Lagrangean relaxation based procedures for computing lower and upper bounds: in
the first one, constraints ( 11.13 )and( 11.22 ) are dualized; in the second, the choice
involves constraints ( 11.21 )and( 11.22 ).
In all of the problems presented so far in this section, facilities can be opened and
closed more than once during the planning horizon. However, in many applications
this is not realistic. In order to illustrate how this aspect can be captured, we consider
another well-known problem: the uncapacitated facility location problem (UFLP)
described in Chap. 3 . Like for the p-median problem, the extension of the UFLP
to a multi-period setting is straightforward. Again we consider a finite multi-period
planning horizon, T . The set of potential locations for the facilities is denoted by
I Df 1;:::;m g and the set of demand nodes by J Df 1;:::;n g . Additionally, let
f it be the cost for operating facility i 2 I in period t 2 T ,andc ijt the cost for
satisfying all the demand of customer j 2 J in period t 2 T from facility i 2 I.A
Search WWH ::




Custom Search