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