Biology Reference
In-Depth Information
The
Weiszfeld Method
[17] for solving this problem is an iterative method with
updates
N
c
+
:=
λ
i
(
c
)
x
i
,
(2.40)
i
=1
giving the next iterate
c
+
as a convex combination, with weights
λ
i
(
c
) computed
by (2.39) for the current iterate
c
. Note that
λ
i
(
c
) is undefined if
c
=
x
i
.Ifthe
Weiszfeld iterates converge to a point
c
∗
,then
c
∗
is optimal by (2.38).
The Weiszfeld method is the best-known method for solving the Fermat-
Weber location problem, see the history in [13, Sec. 1.3].
2.6.2.
Multiple Facility Location Problem
The
multiple facility location problem
(abbreviated
MFLP
) is to locate several
facilities so as to serve optimally the given customers. We assume no interactions
between facilities. If the number of facilities
K
is given, the problem is to:
(a) determine the locations
c
k
of the facilities (
location
decision), and
(b) assign customers to facilities (
allocation
or
assignment
),
so as to minimize the sum of weighted distances from facilities to assigned points.
K
min
w
i
x
i
−
c
k
(2.41)
k
=1
i
∈C
k
C
k
is the index set of the customers assigned to the
k
th
facility. If the
number of facilities is not given in advance, and must be determined, the problem
is written as,
where
K
min
K
=1
,...,N
w
i
x
i
−
c
k
(2.42)
k
=1
i∈C
k
When
K
=1, the Weiszfeld method, (2.40), expresses the facility location as
a convex combination of the customers' coordinates.
For
K>
1 the PDQ center formulas (2.30) represent each facility as a convex
combination of the customers' coordinates, and these reduce to Weiszfeld's for-
mula if
K
=1, in which case all the probabilities in (2.30) equal 1. When applied
to MFLP, the PDQ Algorithm is thus an extension of Weiszfeld's Method [9].
Examples 2.7 and 2.8 illustrate the PDQ Algorithm for solving MFLP's.
Example 2.7.
(Cooper [3, p. 47]) It is required to locate 3 facilities to serve the
15 customers described in Table 2.5.
Search WWH ::
Custom Search