Facilities Design

Basic Models
for the
Location Problem

Lect. delivered by
S P Sarmah

1
 Introduction

Logistics management can be defined as the management of

transportation and distribution of goods. It includes
– facility location
– transportation
– goods handling and storage.

Logistics management problems can be classified as:

(1) location problems;
(2) allocation problems; and
(3) location-allocation problems.
2
 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
• Government and political stability
• Exchange rate fluctuation

3
• Export, import regulations, duties, and tariffs
• Transportation system
• Technical expertise
• Environmental regulations at the federal, state, county and
local levels
• Support services
• Community services, i.e. schools, hospitals, recreation, etc.
• Weather
• Proximity to customers
• Business climate
• Competition-related factors
4
Important Factors in Location Decisions

• International
• National
• State-wide
• Community-wide

5
 Qualitative Analysis
Weighted Factor Scoring Model
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.

6
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 scores.

7
 Example: Factors and Weights for Three
Locations
Wt. Factors Location
A B C
.25 Proximity to customers 95 90 65
.15 Land/construction prices 60 60 90
.15 Wage rates 70 45 60
.10 Property taxes 70 90 70
.10 Business taxes 80 90 85
.10 Commercial travel 80 65 75
.08 Insurance Cost 70 95 60
.07 Office Services 90 90 80
 Table. Weighted Scores for the Three Locations

Weighted Score Location

A B C
• Proximity to customers 23.75 22.5 16.25
• Land/construction prices 9 9 13.5
• Wage rates 10.5 6.75 9
• Property taxes 7 9 8.5
• Business taxes 8 9 8.5
• Commercial Travel 8 6.5 7.5
• Insurance Cost 5.6 7.6 4.8
• Office Services 6.3 6.3 5.6
Sum of weighted Score 78.15 76.65 72.15 9
 Quantitative Analysis

• Several quantitative techniques are available for the discrete

space, single facility location problem.
• Each is appropriate for a specific set of objectives and
constraints.
• For example,
-Minimax location model is appropriate for
determining the location of an emergency service
facility, where the objective is to minimize the max.
distance traveled between Facility and any customer.
Similarly, if objective is to minimize the total distance
travelled, the transportation model is appropriate.
10
 Techniques For
Continuous Space Location Problems

11
 Model for Rectilinear Metric Problem

Consider the following notation:

fi = Traffic flow between new facility and existing facility i

ci = Cost of transportation between new facility and existing

facility i per unit

xi, yi = Coordinate points of existing facility i

12
The median location model is then to minimize:
m
TC = c
i =1
i f i [ | xi − x | + | yi − y | ]

Where TC is the total distribution cost

Since the cifi product is known for each facility, it can be thought
of as a weight wi corresponding to facility i.

m m
Minimize TC = w[ | x
i =1
i i − x | ] +  wi [ | yi − y | ]
i =1

13
 Median Method:

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  wi  
i =1 i =1 2

14
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  wi  
i =1 i =1 2

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.

15
 Notes

1. It can be shown that any other x or y coordinate will not be

that of the optimal location’s coordinates

2. The algorithm determines the x and y coordinates of the

facility’s optimal location separately

3. These coordinates could coincide with the x and y

coordinates of two different existing facilities or possibly
one existing facility

16
 Example:

A high speed copiers are to be located in an office complex

which houses four departments of office 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. Assume that travel originates and ends at the
centroid of each department. Determine the optimal location, i.e.,
x, y coordinates, for the copiers.

17
 Table
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

18
Solution:
Using the median method, we obtain 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.
19
 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).
Solve the above problem using weight 20 to the facility 2 and
interpret your observation 20
 Gravity Method:
• In some location problems, the distance function may not be
linear, but nonlinear.
• If it is quadratic, then the problem of determining the optimal
location of the new facility is rather simple.
• To understand the method of solving such problems, consider
the following objective function for single facility location
problems with a squared Euclidean distance matrix.

21
 Gravity Method: contd.

The cost function is

m
Minimize TC =  i i i
c f (x
i =1
− x ) 2
+ (yi − y )2

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 ( y −
i =1
y ) 2

22
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 = w x
i =1
i i w
i =1
i

23
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

Example # Suppose the distance metric to be used is squared

Euclidean. Determine the optimal location of the new facility
using the gravity method (Consider Example )

24
 Solution - Table
Department i xi yi wi wixi wiyi
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, 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. 25
 Euclidean distance location Problem
Weiszfeld Method
• The objective of this problem is to locate the new (single)
facility in relation to the set of existing facilities such that the
total cost of the material handling is minimized based on
Euclidean distance.
• If we use same mode of transportation for all routes, then it is
equivalent to minimize the total weighted Euclidean distance.
• Example: Location of a transformer from where power cables
are taken to different places is an example in which this type
of distance is used.

26
 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

27
TC 1 m w i 2(x i − x)
= 
x 2 i =1 (x i − x) 2 + (y i − y) 2
m
wixi
=  −
i =1 (x i − x) 2 + (y i − y) 2
m
wix
 =0
i =1 (x i − x) 2 + (y i − y) 2

28
 m
wixi

i =1 (x i − x) 2 + (y i − y) 2
x = m
wi

i =1 (x i − x) 2 + (y i − y) 2

29
TC 1 m w i 2(y i − y)
= 
y 2 i =1 (x i − x) 2 + (y i − y) 2
m
w i yi
=  −
i =1 (x i − x) 2 + (y i − y) 2
m
wiy
 =0
i =1 (x i − x) 2 + (y i − y) 2

30
 m
w i yi

i =1 (x i − x) 2 + (y i − y) 2
y = m
wi

i =1 (x i − x) 2 + (y i − y) 2

Step 0: Set iteration counter k = 1;

m m

w x i i w y i i
x =
k i =1
m
; y =
k i =1
m

w
i =1
i w
i =1
i
31
 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 ) + ( yi − y )
2 2

y k +1 = m
wi

i =1 (xi − x ) + ( yi − y )
2 2

Step 2: If xk+1 = xk and yk+1 = yk, Stop. Otherwise, set k = k + 1

and go to Step 1
32
 Example:
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 the Table .

Departments # xi yi wi
1 10 2 6
2 10 10 20
3 8 6 8
4 12 5 4

33
Solution:
Using the gravity method, the initial seed can be shown to be
(9.8, 7.4). With this as the starting solution, we can apply Step 1
of the Weiszfeld method repeatedly until we find that two
consecutive x, y values are equal. Several Iterations in the
Weiszfeld Method
Iteration No x y TC
1 9.7 7.8 113.4
2 9.7 8.2 111.9
3 9.8 8.4 110.8
- - - -
10 9.9 9.5 106.9
- - - -
20 10 9.9 105.6 34
THANKS

35