Geoscience Reference
In-Depth Information
and study some of its properties. The interested reader is addressed to Cornuéjols
et al. (
1990
) for a deeper analysis and further details.
A first observation is that the UFLP basically involves one main decision: finding
the set of facilities to open. Note that an optimal allocation of customers within a
given set of open facilities, say S, is trivial, and consists of serving all the demand of
each customer from a facility in S with minimum allocation cost, with ties broken
arbitrarily. That is, for j
2
J,leti.j/
2
arg min
f
c
ij
j
i
2
S
g
be arbitrarily chosen,
then x
i.j/j
D
1, x
ij
D
0, i
2
I
n
i.j/ is an optimal allocation of customers within
the set of facilities S. Thus, a closed expression for the objective function value for a
set of facilities S
I is
z
.S/
D
P
i2S
f
i
C
P
j2J
min
i2S
c
ij
. The main implication
of this observation is that the UFLP can be stated as the minimization of a known
set function. Before addressing this issue, we study some properties and algorithmic
alternatives, derived from a standard MIP formulation for the UFLP.
Indeed a MIP formulation for the UFLP can be obtained with the y and x
decision variables of the previous sections. Now it is no longer necessary to impose
the binary condition on the allocation variables, even if single allocation is imposed.
The argument is simple: if some customer is allocated to more than one facility in
an optimal solution, the allocation costs of that customer to all its allocated facilities
must be equal (otherwise the solution would not be optimal). Thus the customer can
be fully served from any arbitrarily selected open facility of minimum allocation
cost. On the other hand, even if capacity constraints are no longer needed, it is still
necessary to impose that no customer is assigned to a non-open facility. Thus, by
replacing constraints (
3.3
)by(
3.7
) we obtain the following valid formulation for the
UFLP:
minimize
X
i2I
f
i
y
i
C
X
i2I
X
UFLP
c
ij
x
ij
(3.36)
j2J
subject to
X
i2I
x
ij
D
1j
2
J
(3.37)
x
ij
y
i
i
2
I;j
2
J
(3.38)
0
x
ij
i
2
I; j
2
J
(3.39)
y
i
2f
0;1
g
i
2
I:
(3.40)
A broad literature exists on the UFLP. From seminal papers (Kuehn and
Hamburger
1963
; Stollsteimer
1963
; Manne
1964
; Balinski
1966
; Efroymson
1966
;
Spielberg
1969a
,
b
; Khumawala
1972
; Bilde and Krarup
1977
; Cornuéjols et al.
1977
; Guignard and Spielberg
1977
; Nemhauser et al.
1978
) and other early
contributions (Guignard
1980
; Cornuéjols and Thizy
1982
; Guignard
1988
; Beasley
1988
;Körkel
1989
; Beasley
1993
;Aardal
1998
), to more recent works (Goldengorin
et al.
2004
;KloseandDrexl
2005
; Mladenovi
´
cetal.
2006
; Janacek and Buzna
2008
;
Beltran-Royo et al.
2012
; Letchford and Miller
2012
,
2014
), virtually any type of
solution algorithm has been proposed for it. As with the general facility location
problem, an extensive literature review is outside the scope of this chapter. The
