1

Facility Design-Week13 &14

Facility Location Problem
 2

Logistics Management
Logistics Management can be defined as the
management of the transportation and
distribution of goods. The term goods includes
raw materials or subassemblies obtained from
suppliers as well as finished goods shipped from
plants to warehouses or customers.
 3

Introduction Cont...
Logistics management problems can be
classified as:
(1) location problems;
involve determining the location of one or more new facilities
in one or more of several potential sites. The cost of locating
each new facility at each of the potential sites is assumed to
be known. It is the fixed cost of locating a new facility at a
particular site plus the operating and transportation cost of
serving customers from this facility-site combination.
(2) allocation problems; and
assume that the number and location of facilities are known a
priori and attempt to determine how each customer is to be
served. In other words, given the demand for goods at each
customer center, the production or supply capacities at each
facility, and the cost of serving each customer from each
facility, the allocation problem determines how much each
facility is to supply to each customer center.
(3) Location-allocation problems.
 4

List of Factors Affecting Location Decisions

Proximity to raw materials sources
Cost and availability of energy/utilities
Cost, availability, skill and productivity of labor
Government regulations at the federal, state, country and
local levels
Taxes at the federal, state, county and local levels
Insurance
Construction costs, land price
 5

List of Factors Affecting Location Decisions

(Cont...)
Government and political stability
Exchange rate fluctuation
Export, import regulations, duties, and tariffs
Transportation system
Technical expertise
Environmental regulations at the federal, state, county
and local levels
Support services
 6

List of Factors Affecting Location Decisions

(Cont...)
Community services, i.e. schools, hospitals, recreation,
etc.
Weather
Proximity to customers
Business climate
Competition-related factors
 7

Qualitative Analysis
Step 1: List all the factors that are important, i.e.
have an impact on the location decision.
Step 2: Assign appropriate weights (typically
between 0 and 1) to each factor based on the
relative importance of each.
Step 3: Assign a score (typically between 0 and 100)
for each location with respect to each factor
identified in Step 1.
Step 4: Compute the weighted score for each factor
for each location by multiplying its weight with the
corresponding score (which were assigned Steps 2
and 3, respectively)
Step 5: Compute the sum of the weighted scores for
each location and choose a location based on these
 8

Example 1:
A payroll processing company has recently won
several major contracts in the midwest region of the
U.S. and central Canada and wants to open a new,
large facility to serve these areas. Since customer
service is of utmost importance, the company wants
to be as near its customers as possible.
Preliminary investigation has shown that
Minneapolis, Winnipeg, and Springfield, Ill.,
would be the three most desirable locations and the
payroll company has to select one of these three.
A subsequent thorough investigation of each location
with respect to eight important factors has
generated the raw scores and weights listed in table
 9

Solution:
Steps 1, 2, and 3 have already been completed for
us. We now need to compute the weighted score
for each location-factor pair (Step 4), and these
weighted scores and determine the location based
on these scores (Step 5).
 10

Table 1. Weighted Score for the Three Locations

Score/Weigthed Score
Weight Factor
Minneapolis Winnipeg Springfield
0,25 Proximity to Customer 95 23,75 90 22,50 65 16,25
0,15 Land & Construction Prices 60 9,00 60 9,00 90 13,50

0,15 Wage Rates 70 10,50 45 6,75 60 9,00

0,10 Property Taxes 70 7,00 90 9,00 70 7,00
0,10 Business Taxes 80 8,00 90 9,00 85 8,50
0,10 Commercial Travel 80 8,00 65 6,50 75 7,50
0,08 Insurance Cost 70 5,60 95 7,60 60 4,80
0,07 Office Services 90 6,30 90 6,30 80 5,60
Sum of Weighted Scores 78,15 76,65 72,15
 11

Solution: Cont...
From the analysis in Table 2, it is clear that Minneapolis
would be the best location based on the subjective
information.
Of course, as mentioned before, objective measures must
be brought into consideration especially because the
weighted scores for Minneapolis and Winnipeg are close.
 12

QUANTITATIVE
ANALYSIS
 13

General Transportation Model

 14

General Transportation Model

Parameters
cij: cost of transporting one unit from warehouse i to
customer j
ai: supply capacity at warehouse i
bi: demand at customer j
Decision Variables
xij: number of units transported from warehouse i to
customer j
 15

General Transportation Model

Minimize Total Transporta tion Cost
m n
Z cij xij
i 1 j 1

Subject to
n

x
j 1
ij ai , i 1,2,..., m (supply restrictio n at warehou se i)
m

x
i 1
ij b j , j 1,2,..., n (demand requiremen t at market j)

xij 0, i, j 1,2,..., n (non - negativity restrictio ns)

 16

Transportation Simplex Algorithm

Step 1: Check whether the transportation problem is balanced or unbalanced.
If balanced, go to step 2. Otherwise, transform the unbalanced transportation
problem into a balanced one by adding a dummy plant (if the total demand
exceeds the total supply) or a dummy warehouse (if the total supply exceeds the
total demand) with a capacity or demand equal to the excess demand or excess
supply, respectively. Transform all the > and < constraints to equalities.

Step 2: Set up a transportation tableau by creating a row corresponding to

each plant including the dummy plant and a column corresponding to each
warehouse including the dummy warehouse. Enter the cost of transporting a unit
from each plant to each warehouse (cij) in the corresponding cell (i,j). Enter 0
cost for all the cells in the dummy row or column. Enter the supply capacity of
each plant at the end of the corresponding row and the demand at each
warehouse at the bottom of the corresponding column. Set m and n equal to the
number of rows and columns, respectively and all xij=0, i=1,2,...,m; and j=1,2,...,n.

Step 3: Construct a basic feasible solution using the Northwest corner method.
 17

Transportation Simplex Algorithm

Step 4: Set u1=0 and find vj, j=1,2,...,n and ui, i=1,2,...,n using the formula ui
+ vj = cij for all basic variables.
Step 5: If ui + vj - cij < 0 for all nonbasic variables, then the current basic
feasible solution is optimal; stop. Otherwise, go to step 6.
Step 6: Select the variable xi*j* with the most positive value ui* + vj*- cij*.
Construct a closed loop consisting of horizontal and vertical segments
connecting the corresponding cell in row i* and column j* to other basic
variables. Adjust the values of the basic variables in this closed loop so that
the supply and demand constraints of each row and column are satisfied and
the maximum possible value is added to the cell in row i* and column j*. The
variable xi*j* is now a basic variable and the basic variable in the closed loop
which now takes on a value of 0 is a nonbasic variable. Go to step 4.
 18

Example 2:
Seers Inc. has two manufacturing plants at
Albany and Little Rock supplying Canmore brand
refrigerators to four distribution centers in
Boston, Philadelphia, Galveston and Raleigh.
Due to an increase in demand of this brand of
refrigerators that is expected to last for several
years into the future, Seers Inc., has decided to
build another plant in Atlanta. The expected
demand at the three distribution centers and the
maximum capacity at the Albany and Little Rock
plants are given in Table 3.
 19

Table [Link], Demand and Supply Information

Bost. Phil. Galv. Rale. Supply

Capacity
Albany 10 15 22 20 250
Little Rock 19 15 10 9 300
Atlanta 21 11 13 6 No limit

Demand 200 100 300 280

 20

Example 3: Transportation Model with Plant at

Atlanta

Bost. Phil. Galv. Rale. Supply

Capacity
Albany 10 15 22 20 250
Little Rock 19 15 10 9 300
Atlanta 21 11 13 6 880
Demand 200 100 300 280 880
 21

Example 3
Consider Example 2. In addition to Atlanta, suppose Seers,
Inc., is considering another location Pittsburgh.
Determine which of the two locations, Atlanta or Pittsburgh,
is suitable for the new plant. Seers Inc., wishes to utilize all
of the capacity available at its Albany and Little Rock
Locations
 22

Table 4. Costs, Demand and Supply Information

Bost. Phil. Galv. Rale. Supply

Capacity
Albany 10 15 22 20 250
Little Rock 19 15 10 9 300
Atlanta 21 11 13 6 330
Pittsburgh 17 8 18 12 330
Demand 200 100 300 280
 23

Hybrid Analysis
Critical
Objective
Subjective

CFij = 1 if location i satisfies critical factor j,

0 otherwise
OFij = cost of objective factor j at location i
SFij = numerical value assigned
(on scale of 0-100)
to subjective factor j for location i
wj = weight assigned to subjective factor
(0< w < 1)
 24

Hybrid Analysis Cont...

p
CFM i CFi1CFi 2 CFip CFij ,
j 1

i 1,2,..., m

q q
max i OFij OFij
j 1 j 1
OFMi ,i 1,2,...,m
q
q

max i OFij min i OFij
j 1 j 1
r
SFMi w j SFij ,i 1,2,...,m
j 1
 25

Hybrid Analysis Cont...

The location measure LMi for each location is then
calculated as:

LMi = CFMi [ OFMi + (1- ) SFMi ]

Where is the weight assigned to the objective factor.

We then choose the location with the highest location

measure LMi
 26

Example 4:
Mole-Sun Brewing company is evaluating six
candidate locations-Montreal, Plattsburgh, Ottawa,
Albany, Rochester and Kingston, for constructing a
new brewery. There are two critical, three objective
and four subjective factors that management
wishes to incorporate in its decision-making. These
factors are summarized in Table 2-4. The weights of
the subjective factors are also provided in the table.

Determine the best location if the subjective factors

are to be weighted 50 percent more than the
objective factors.
 27

Table 2. Critical Factors

Location Factors
Critical
Water Tax
Supply Incentives
Albany 0 1
Kingston 1 1
Montreal 1 1
Ottawa 1 0
Plattsburgh1 1
Rochester 1 1
 28

Table 3. Objective Factors

Objective Factors OFMi

Labor Energy
Revenue Sum of
Cost Cost
Location OFi
Albany 185 80 10 -95 1
Kingston 150 100 15 -35 0
Montreal 170 90 13 -67 0.533333
Ottawa 200 100 15 -85 0.833333
Plattsburgh 140 75 8 -57 0.366667
Rochester 150 75 11 -64 0.483333
Max -35
Min -95
Max-min 60
 29

Table 4. Subjective Factors

Subjective Factors

Location Comm Ease of Labor SFMi

Supp Service
Att Transport Unionization

0.3 0.4 0.25 0.05

Albany 0.5 0.9 0.6 0.7 0.695
Kingston 0.6 0.7 0.7 0.75 0.6725
Montreal 0.4 0.8 0.2 0.8 0.53
Ottawa 0.5 0.4 0.4 0.8 0.45
Plattsburgh 0.9 0.9 0.9 0.55 0.8825
Rochester 0.7 0.65 0.4 0.8 0.61
 30

Table 5. LMi Calculation

OFM SFM
Location
w=0.333 w=0.667 CF LMi
Albany 1 0.695 0.796667 0 0
Kingston 0 0.6725 0.448333 1 0.448333
Montreal 0.533333 0.53 0.531111 1 0.531111
Ottawa 0.833333 0.45 0.577778 0 0
Plattsburgh 0.366667 0.8825 0.710556 1 0.710556
Rochester 0.483333 0.61 0.567778 1 0.567778
 31

TECHNIQUES FOR
CONTINUOUS SPACE LOCATION
PROBLEMS
 32

Distance Measures
Pi = (ai, bi)

Rectilinear distance (L1 norm)

d(X, Pi) = |x - ai| + |y - bi| X = (x, y)

Pi = (ai, bi)
Straight line or Euclidean distance
(L2 norm)
(x - a i) 2 + (y - b i) 2
X = (x, y)
d(X, Pi) =
Pi = (ai, bi)

Tchebyshev distance (L norm)

X = (x, y)
d(X, Pi) = max{|x - ai|, |y - bi|}
 33

Classification of Planar Facility Location Problems

# of facilities Objectives Distance measures

Rectilinear

Minisum Euclidean

Tchebyshev
Single-
Facility
Rectilinear

Minimax Euclidean

Tchebyshev

Facility
Location
Rectilinear

Minisum Euclidean

Tchebyshev
Multi-
Facility
Rectilinear

Minimax Euclidean

Tchebyshev
 34

Rectilinear Distance Facility Location Problem

Determine a new location of a warehouse in Montreal
area which provides materials to 5 different companies
(1-5)
Location of these companies (a, b) and the material
movement between the new warehouse and the existing
facilities (w) are provided:
Where should the new warehouse be located?
 35

Rectilinear Distance Facility Location Problem

Various objectives can be used

Minisum location problem
Minimizing the sum of weighted distance between
the new facility and the other existing facilities

Minimax location problem

Minimizing the maximum distance between the
new facility and any existing facility
 36

Equivalent Linear Model for the Rectilinear Distance

(Single-Facility Location-Minisum Problem)
Parameters
fi = Traffic flow between new facility and existing facility i
ci = Unit transportation cost between new facility and
existing facility i
xi, yi = Coordinate points of existing facility I

Decision Variables
x, y = Optimal coordinates of the new facility
TC = Total distribution cost
 37

Equivalent Linear Model for the Rectilinear Distance

(Single-Facility Location-Minisum Problem)

The median location model is then to

m m
Minimize TC w [ | x x |] w [| y
i 1
i i
i 1
i i y |]
 38

Equivalent Linear Model for the Rectilinear Distance

(Single-Facility Location-Minisum Problem)

Since the cifi product is known for each facility, it can be

thought of as a weight wi corresponding to facility i. The
previous equation can now be rewritten as follows

m m
Minimize TC w [ | x x |] w [| y
i 1
i i
i 1
i i y |]
 39

Procedure using Median Method Approach

Step 1: List the existing facilities in non-decreasing order of
the x coordinates.
Step 2: Find the jth x coordinate in the list at which the
cumulative weight equals or exceeds half the total weight
for the first time, i.e.,

j 1 m j m
wi wi

i 1
wi
i 1 2
and
i 1
wi
i 1 2
 40

Equivalent Linear Model for the Rectilinear Distance

(Single-Facility Location-Minisum Problem)
Step 3: List the existing facilities in non-decreasing order of
the y coordinates.
Step 4: Find the kth y coordinate in the list (created in Step
3) at which the cumulative weight equals or exceeds half
the total weight for the first time, i.e.,
k 1 m k m
wi wi

i 1
wi
i 1 2
and
i 1
wi
i 1 2

Step 4: Cont... The optimal location of the new facility is

given by the jth x coordinate and the kth y coordinate
identified in Steps 2 and 4, respectively.
 41

Notes
1. It can be shown that any other x or y coordinate will not
be that of the optimal locations coordinates
2. The algorithm determines the x and y coordinates of the
facilitys optimal location separately
3. These coordinates could coincide with the x and y
coordinates of two different existing facilities or possibly
one existing facility
 42

Example 5:
Two high speed copiers are to be located in the fifth floor of
an office complex which houses four departments of the
Social Security Administration. Coordinates of the centroid
of each department as well as the average number of trips
made per day between each department and the copiers
yet-to-be-determined location are known and given in Table
9 below. Assume that travel originates and ends at the
centroid of each department. Determine the optimal
location, i.e., x, y coordinates, for the copiers.
 43

Table 5. Centroid Coordinates and Average Number of

Trips to Copiers
Dept. Coordinates Average number of
# x y daily trips to copiers
1 10 2 6
2 10 10 10
3 8 6 8
4 12 5 4
 44

Solution:
Using the median method, it is obtained the following
solution:
Step 1:
Dept. x coordinates in Weights Cumulative
# non-decreasing order Weights
3 8 8 8
1 10 6 14
2 10 10 24
4 12 4 28
Step 2: Since the second x coordinate, namely 10, in
the above list is where the cumulative weight equals
half the total weight of 28/2 = 14, the optimal x
coordinate is 10.
 45

Solution:
Step 3:

Dept. y coordinates in Weights Cumulative

# non-decreasing order Weights
1 2 6 6
4 5 4 10
3 6 8 18
2 10 10 28

Step 4: Since the third y coordinates in the above

list is where the cumulative weight exceeds half
the total weight of 28/2 = 14, the optimal y
coordinate is 6. Thus, the optimal coordinates
of the new facility are (10, 6).
 46

CONTOUR LINE
METHOD
 47

Algorithm for Drawing Contour Lines:

Step 1: Draw a vertical line through the x coordinate
and a horizontal line through the y coordinate of each
facility
Step 2: Label each vertical line Vi, i=1, 2, ..., p and
horizontal line Hj, j=1, 2, ..., q where Vi= the sum of
weights of facilities whose x coordinates fall on
vertical line i and where Hj= sum of weights of
facilities whose y coordinates fall on horizontal line j
Step 3: Set i = j = 1; N0 = D0 =
Step 4: Set Ni = Ni-1 + 2Vi and Dj = Dj-1 + 2Hj.
Increment i = i + 1 and j = j + 1
 48

Algorithm for Drawing Contour Lines:

Step 5: If i < p or j < q, go to Step 4. Otherwise, set i
= j = 0 and determine Sij, the slope of contour lines
through the region bounded by vertical lines i and i
+ 1 and horizontal line j and j + 1 using the equation
Sij = -Ni/Dj. Increment i = i + 1 and j = j + 1
Step 6: If i < p or j < q, go to Step 5. Otherwise
select any point (x, y) and draw a contour line with
slope Sij in the region [i, j] in which (x, y) appears so
that the line touches the boundary of this line. From
one of the end points of this line, draw another
contour line through the adjacent region with the
corresponding slope
Step 7: Repeat this until you get a contour line
ending at point (x, y). We now have a region
 49

Notes on Algorithm for Drawing Contour

Lines
1. The number of vertical and horizontal lines need not be
equal the Ni and Dj as computed in Steps 3 and 4
correspond to the numerator and denominator,
respectively of the slope equation of any contour line
through the region bounded by the vertical lines i and i +
1 and horizontal lines j and j + 1

Consider t he objective function w hen the new facility

is located at some point (x, y), i.e., x x, y y
m m
TC wi xi x wi yi y
i 1 i 1
 50

Notes on Algorithm for Drawing

Contour Lines (Cont)

By noting that the Vis and Hjs calculated in Step 2 of the

algorithm correspond to the sum of the weights of facilities
whose x, y coordinates are equal to the x, y coordinates,
respectively of the ith, jth distinct lines and that we have p, q
such coordinates or lines (p < m, q < m), the previous
equation can be written as follows
p q
TC Vi xi x H i yi y
i 1 i 1
 51

Notes on Algorithm for Drawing

Contour Lines (Cont)
2. Suppose that x is between the sth and s+1th (distinct) x
coordinates or vertical lines (since we have drawn
vertical lines through these coordinates in Step 1).
Similarly, let y be between the tth and t+1th vertical lines.
Then
s p

TC V (x x ) V ( x
i i i i x)
i1 i s1
t q

H i (y y i ) H (y i i y)
i 1 i t 1
 52

Notes on Algorithm for Drawing Contour Lines

(Cont)
Rearranging the variable and constant terms in the above
equation, we get

s p
t q

TC V V
i i x H H i i y
i 1 i s 1 i 1 i t 1
s p t q
Vi xi V x H y H y
i i i i i i
i 1 i s 1 i 1 i t 1
 53

Notes on Algorithm for Drawing Contour Lines

(Cont)
The last four terms in the previous equation
can be substituted by another constant term c
and the coefficients of x can be rewritten as
follows
s p s s
TC Vi V V V
i i i
i 1 i s 1 i 1 i 1

Notice that we have only added and

subtracted the term s

Vi i 1
 54

Notes on Algorithm for Drawing Contour Lines

(Cont)
s m
Since it is clear from Step 2 that V w ,
i 1
i
i 1
i

the coefficient of x can be rewritten as

s
s p
s p
2 Vi V V
i i 2 Vi Vi
i 1 i 1 i s 1 i 1 i 1
s m
2 Vi wi
i 1 i 1

Similarly, the coefficient of y is t m

2 H i wi
i 1 i 1
 55

Notes on Algorithm for Drawing Contour Lines

(Cont)
s m
t m

Thus, TC 2 Vi wi x 2 H i wi y c
i 1 i 1 i 1 i 1
The Ni computation in Step 4 is in fact calculation
of the coefficient of x as shown above. Note that
Ni=Ni-1+2Vi. Making the substitution for Ni-1, we get
Ni=Ni-2+2Vi-1+2Vi
Repeating the same procedure of making
substitutions for Ni-2, Ni-3, ..., we get
m i

Ni=N0+2V1+2V2+...+2Vi-1+2V1= wi 2 Vk
i 1 k 1
 56

Notes on Algorithm for Drawing Contour Lines

(Cont) m i

Similarly, it can be verified that Di wi 2 H k

i 1 k 1

s m
t m

Thus, TC 2 Vi wi x 2 H i wi y c
i 1 i 1 i 1 i 1
N s x Dt y c
which can be rewritten as
Ns
y x (TC c)
Dt
The above expression for the total cost function at x, y or in fact,
any other point in the region [s, t] has the form y= mx + c,
where the slope m = -Ns/Dt. This is exactly how the slopes
are computed in Step 5 of the algorithm
 57

Notes on Algorithm for Drawing Contour Lines (Cont)

3. The lines V0, Vp+1 and H0, Hq+1 are required for defining
the exterior regions [0, j], [p, j], j = 1, 2, ..., p,
respectively)
4. Once we have determined the slopes of all regions, the
user may choose any point (x, y) other than a point which
minimizes the objective function and draw a series of
contour lines in order to get a region which contains
points, i.e. facility locations, yielding as good or better
objective function values than (x, y)
 58

Example 6:
Consider Example 5. Suppose that the weight of facility 2
is not 10, but 20. Applying the median method, it can be
verified that the optimal location is (10, 10) - the centroid
of department 2, where immovable structures exist. It is
now desired to find a feasible and near-optimal location
using the contour line method.
 59

Solution:
The contour line method is illustrated using the figure below
 60

Solution:
Step 1: The vertical and horizontal lines V1, V2, V2 and H1,
H2, H2, H4 are drawn as shown. In addition to these lines,
we also draw line V0, V4 and H0, H5 so that the exterior
regions can be identified
Step 2: The weights V1, V2, V2, H1, H2, H2, H4 are
calculated by adding the weights of the points that fall on
the respective lines. Note that for this example, p=3, and
q=4
 61

Solution:
4

Step 3: Since w
i 1
i 38

set N00 = D00 = -38

Step 4: Set
N11 = -38 + 2(8) = -22; D11 = -38 + 2(6) = -26;
N22 = -22 + 2(26) = 30; D22 = -26 + 2(4) = -18;
N33 = 30 + 2(4) = 38; D33 = -18 + 2(8) = -2;
D44 = -2 + 2(20) = 38;
(These values are entered at the bottom of each
column and left of each row in figure 1)
 62

Solution:
Step 5: Compute the slope of each region.
S00 = -(-38/-38) = -1; S14 = -(-22/38) = 0.58;
S01 = -(-38/-26) = -1.46; S20 = -(30/-38) = 0.79;
S02 = -(-38/-18) = -2.11; S21 = -(30/-26) = 1.15;
S03 = -(-38/-2) = -19; S22 = -(30/-18) = 1.67;
S04 = -(-38/38) = 1; S23 = -(30/-2) = 15;
S10 = -(-22/-38) = -0.58; S24 = -(30/38) = -0.79;
S11 = -(-22/-26) = -0.85; S30 = -(38/-38) = 1;
S12 = -(-22/-18) = -1.22; S31 = -(38/-26) = 1.46;
S13 = -(-22/-2) = -11; S32 = -(38/-18) = 2.11;
 63

Solution:
Step 5: Compute the slope of each region.

S33 = -(38/-2) = 19;

S34 = -(38/38) = -1;
(The above slope values are shown inside each region.)

Step 6: When we draw contour lines through point (9, 10), we

get the region shown in the previous figure.
Since the copiers cannot be placed at the (10, 10) location, we
drew contour lines through another nearby point (9, 10).
Locating anywhere possible within this region give us a
feasible, near-optimal solution.
 64

SINGLE-FACILITY
LOCATION-MINISUM
PROBLEM WITH SQUARED
EUCLIDEAN DISTANCES
 65

Gravity Method:
The cost function is
m
MinimizeTC c i f i(x i x) (yi y)
2 2

i 1

As before, we substitute wi = fi ci, i = 1, 2, ..., m and

rewrite the objective function as
m m
Minimize TC i i
w (
i 1
x x ) 2
i i
w (
i 1
y y ) 2
 66

Gravity Method (Cont)

Since the objective function can be shown to be convex,
partially differentiating TC with respect to x and y, setting
the resulting two equations to 0 and solving for x, y
provides the optimal location of the new facility

TC m m
2 wi x 2 wi xi 0
x i 1 i 1
m m
x wi xi w i
i 1 i 1
 67

Gravity Method (Cont)

Similarly,
TC m m
2 wi y 2 wi yi 0
y i 1 i 1
m m
y wi yi w i
i 1 i 1

Thus, the optimal locations x and y are simply the

weighted averages of the x and y coordinates of the
existing facilities
 68

Example 7:
Consider Example 5. Suppose the distance metric
to be used is squared Euclidean. Determine the
optimal location of the new facility using the gravity
method.
 69

Solution
Department i xii yii wii wiixii wiiyii
1 10 2 6 60 12
2 10 10 10 100 100
3 8 6 8 64 48
4 12 5 4 48 20
Total 28 272 180

From table 10, we conclude that

x 272 28 9.7 and y 180 28 6.4
If this location is not feasible, we only need to find another
point which has the nearest Euclidean distance to (9.7, 6.4) and
is a feasible location for the new facility and locate the copiers
there
 70

SINGLE-FACILITY LOCATION-
MINISUM PROBLEM WITH
EUCLIDEAN DISTANCES

WEISZFELD
METHOD
 71

Weiszfeld Method:
The objective function for the single facility location
problem with Euclidean distance can be written as:

m
Minimize TC c i f i (x i x) 2 (y i y) 2
i 1

As before, substituting wi=cifi and taking the

derivative of TC with respect to x and y yields
 72

Weiszfeld Method:

TC 1 m w i 2(x i x) m
wixi

x 2 i 1 (x i x) 2 (yi y) 2
i 1 (x i x) 2 (y i y) 2
m
wixi x m


wi
i 1 (x i x) 2 (yi y) 2
i 1 (x i x) 2 (y i y) 2
m
wix
0
i 1 (x i x) 2 (yi y) 2
 73

Weiszfeld Method:

TC 1 m w i 2(y i y)

y 2 i1 (x i x) 2 (y i y) 2 m
w i yi
m
(x i x) 2 (y i y) 2
w i yi i 1
y m
wi
i 1 (x i x) 2 (y i y) 2
i 1 (x i x) 2 (y i y) 2
m
wiy
0
i 1 (x i x) 2 (y i y) 2
 74

Weiszfeld Method:
Step 0: Set iteration counter k = 1;
m m

w x i i w y i i
xk i 1
m
; yk i 1
m

w
i 1
i w
i 1
i
 75

Weiszfeld Method:
m
wi xi
Step 1: Set

i 1 xi x 2 yi y 2
x k 1 m
wi

i 1 xi x 2
yi y
2

m
wi yi

i 1 xi x 2 yi y 2
y k 1 m
wi

i 1 xi x 2 yi y 2
Step 2: If xk+1
k+1 = xkk and yk+1
k+1 = ykk, Stop. Otherwise,

set k = k + 1 and go to Step 1

 76

Example 8:
Consider Example 6. Assuming the distance metric to be
used is Euclidean, determine the optimal location of the
new facility using the Weiszfeld method. Data for this
problem is shown in Table below.
Table :Coordinates and weights for 4 departments

Departments # xii yii wii

1 10 2 6
2 10 10 20
3 8 6 8
4 12 5 4
 77

Summary: Methods for Single-Facility,

Continuous Space Location Problems (MINISUM
PROBLEM)
Problem
Rectilinear
Squared Euclidean
Euclidean Method
Median
Gravity
Weiszfeld