Geoscience Reference
In-Depth Information
where the demand of each customer represents a physical object that cannot be
split. This case is known as the
single allocation
FLP (SFLP). Equations (
3.1
)-(
3.5
)
is a valid formulation for the SFLP. Many FLP models, however, allow splitting the
demand at users among several open facilities. Such models, which are referred to
as
multiple allocation
FLPs (MFLPs), arise, for instance, when customers represent
population areas and not all the individuals in a given area need to be served from
the same service center. In MFLPs allocating customer j to facility i means that
some positive fraction of d
j
is served from facility i. Hence, for i
2
I, j
2
J
the allocation decision variables x
ij
are defined as the fraction of demand of user
j served by facility i; and the domain for the x variables is thus substituted by its
continuous relaxation
0
x
ij
1;
i
2
I;j
2
J:
(3.8)
With the above definition of the allocation decision variables, constraints (
3.2
)
have a slightly more general interpretation than in the single allocation case. Since
they impose that the sum of all the fractions served from the different facilities be
one, they also guarantee that the total demand at each user is satisfied. Therefore,
in order to obtain a valid formulation for the MFLP, in formulation (
3.1
)-(
3.5
)we
“only” have to change the domain of the allocation variables x. It then follows
that (
3.1
)-(
3.4
) together with (
3.8
) is a valid formulation for the MFLP.
The FLP is
-hard since a polynomial transformation can be used to reduce
the node cover problem, which is known to be
NP
-hard (Garey and Johnson
1979
), into the FLP (see, for instance, Cornuéjols et al.
1990
).
The reader may note that the “difficult” decision in FLPs is the selection of the
facilities to open. This is readily seen in the multiple allocation case where, if the
set of facilities to open is given, S
I, the best allocation of customers within S
can easily be obtained by solving the following transportation problem:
TP
.S/ minimize
z
D
X
i2S
NP
X
.c
ij
=d
j
/s
ij
(3.9)
j2J
subject to
X
i2S
s
ij
d
j
j
2
J
(3.10)
X
s
ij
q
i
i
2
S
(3.11)
j2J
s
ij
0
i
2
S; j
2
J:
(3.12)
In formulation (
3.9
)-(
3.12
) above the continuous decision variable s
ij
denotes
the amount of demand of customer j which is served from facility i. Hence we
have the relation, x
ij
D
s
ij
=d
j
.
In the single allocation case, finding an optimal allocation of customers to
a given set of open facilities S
I is still a difficult problem, namely a
Generalized Assignment Problem, which is also
NP
-hard (Fisher et al.
1986
).
