Geoscience Reference
In-Depth Information
Van Roy and Erlenkotter (
1982
) proposed a heuristic for the condensed dual
just presented. Starting from the trivial dual feasible solution defined by v
jt
D
min
i2I
f
c
ijt
g
(t
2
T , j
2
J) an ascent procedure is performed for increasing the
values of the dual variables v
jt
, thus increasing the value of the dual objective
function. When this procedure does not lead to further improvements, a primal
solution is constructed using the slackness conditions. Finally, a primal-dual
adjustment phase is performed in order to reduce the gap between the values of
the primal and dual objective functions. When no further gap reduction is achieved,
a branch-and-bound procedure is applied to complete the search for an optimal
solution for the problem. The reader should refer to Van Roy and Erlenkotter (
1982
)
for further details.
The procedure developed by Van Roy and Erlenkotter (
1982
) is quite efficient to
solve instances of moderate size. Nevertheless, this multi-period facility location
problem includes the UFLP as a special case and thus, it is NP-hard. For this
reason, Saldanha-da-Gama and Captivo (
1998
) proposed a two-phase heuristic
procedure for the problem. The first phase is a drop procedure which starts with
all facilities operating in all periods, and progressively removes operating periods
to the facilities. This is done while a reduction in the total cost is observed. Losing
feasibility is never allowed during the process. The second phase consists of a local
search procedure.
Although representing an important basis for describing real problems, the
above models still miss one important feature found in many applications: capacity
constraints. Denote by Q
i
the capacity of a facility located at i
2
I, and by d
jt
the demand of customer j
2
J in period t
2
T . A capacitated multi-period facility
location problem consists of minimizing (
11.41
) subject to (
11.42
), (
11.44
), (
11.45
),
and
X
d
jt
x
ijt
Q
i
X
2T
it
z
i
; t
2
T; i
2
I:
(11.51)
j2J
This model was addressed by Saldanha da Gama (
2002
) who developed a dual-
based procedure for obtaining lower and upper bounds. The model was previously
enhanced with (
11.43
)and
X
X
R
kit
z
it
r
k
; k
2
K:
(11.52)
t2T
i2I
By choosing appropriate values for R
kit
and r
k
, these generic constraints can
accommodate every inequality involving the binary variables. This is important
because the linear relaxation of capacitated facility location problems can often
be strengthened through the inclusion of valid inequalities involving the location
variables. For instance, a set of constraints often used in (static) capacitated facility
location problems, state that the operational capacity must be at least equal to the
