540:462 FACILITIES PLANNING AND

MATERIALS HANDLING
Quantitative Facilities Planning Models

Class Meeting: TF 2 10:20-11:40am (HILL-009)

Prof. Honggang Wang

1

Quantitative Facilities Planning Models

Facility Location Problems (FLP)
Warehouses
New equipments
.

Different objective functions

Minimize average travel time or distance
Minimize worst-case (maximum) travel time or distance

Distance measures
Euclidean distance
Rectilinear distance

Discrete and continuous problems

Select the best location
Identify the optimal coordinates
2

You can use location theory to locate

Warehouses
New manufacturing
plants
Tool racks
Copying machines
McDonalds restaurants
Fire stations
Hospitals
Nuclear reactors
Garbage dumps

Facility Location Factors

Labor, Land, and Utility
Financing, Accounting,
Budgeting

Raw Material
Purchasing/Procurement

Market
Marketing/Sales

Tax, Law, and Regulation

Tax planning/Legal issue

Different Objective Functions

Minisum: Minimize average travel time or
distance
Median problems

Minimax: Minimize worst-case (maximum)

travel time or distance
Center problems

Maxcover: Maximize the fraction of

population less than x minutes from a facility
Covering problems
4

Distance measures
In the plane:
x

Euclidean distance, (c)

Rectilinear distance, (a+b)

On the network:

The shortest path connecting node x and y.

5

2
2

10
4

3
6
5

Single Facility Location

1-median problem
Objective: minimize the total weighted distance.
1-center problem
Objective: minimize the maximum weighted
distance.
Maximum covering problem
Objective: maximize the demand covered within
3 unit.
6

Discrete Location Problems

There is a set of potential sites for the facility to be located.
Single facility problem (an example):
Suppose a new copying machine is to be installed in an office.
The machine can be set up in any one of four possible locations.
Five offices will be using the machine.
Customer

Demand

Location
1

15

20

12

10

7
7

1-Median Problem
Customer

Demand

Location Distance

15

20

12

10

Customer

Location Weighted Distance

45

75

60

45

100

40

80

80

36

72

12

60

90

50

30

40

14

28

56

49

Sum

285

265

238

274

1-Center Problem
Customer

Demand

Location Distance

15

20

12

10

Customer

Location Weighted Distance

45

75

60

45

100

40

80

80

36

72

12

60

90

50

30

40

14

28

56

49

Max

100

75

80

80

Maximum Covering Problem

(cover within 3 distance units)
Customer

Demand

Location Distance
1

15

20

12

10

10

1-Median Problem with Fixed Costs

Customer

Demand

Location Distance
1

15

20

12

10

10

35

10

Customer

Location Weighted Distance

45

75

60

45

100

40

80

80

36

72

12

60

90

50

30

40

14

28

56

49

10

35

10

295

269

273

284
11

Sum Total

Continuous 1-Median Location

Problem
Identify the optimal x and y coordinates of a new
facility such that the summation of total distance is
minimized

Minimize

f ( X ) wi d ( X , Pi )
i

X = (x,y) denotes the location of the new facility

P= (ai,bi) denotes the location of existing facility i, i =
1,,m
wi denotes the weight (or demand/flow) associated
with travel between the new facility and existing
facility i
d(X,Pi) denotes the distance between the new facility
and existing facility i
12

Example1: Continuous 1-Median

Location Problem
Locate a distribution center (DC) that serves 3
retailers in a city. The monthly demands and
locations of the retailers are shown below.

(0,5)
A

12

?
?

C (6,3)
24
(4,1)
6 B

Retailer

ai

bi

Demand

12

24

13

Example (Cont.)
1-Median Problem
Minimize
12*d((0,5),(x,y)) + 6*d((4,1),(x,y)) + 24*d((6,3),(x,y))
A

Rectilinear Distance
Minimize
12(|x|+|5-y|) + 6(|x-4|+|y-1|) + 24(|6-x|+|3-y|)
12|x|+6|x-4|+24|6-x| + 12|5-y|+6|y-1|+24|3-y|
14

Find optimal x
Min f(x) = 12|x|+6|x-4|+24|6-x|

6-x

-x

-1

4-x

x-6

x-4

15

Piecewise linear objective function

12(-x)+6(4-x)+24(6-x) = 168-42x

x0

12(x)+6(4-x)+24(6-x) = 168-18x

0<x4

12(x)+6(x-4)+24(6-x) = 120-6x

4<x6

f(x) =

12(x)+6(x-4)+24(x-6) = -168+42x

6<x

168
96
84
-1

7
16

Minimum

Observation: The trick

When the slope changes. x*=6

-1

0
12

slope = -42

4
6

6
24

slope = 42

slope = -18

slope = -6
17

Solution to the 1-Median Problem

(0,5)
A

12
C (6,3)
24
(4,1)
6 B

18

Two very important mathematical

properties
The x-coordinate of the new facility will be the
same as the x-coordinate of some existing
facility
The optimum x-coordinate will be such that
no more than half the total weight is to the
left of x and no more than half of the total
weight is to the right of x.
Both properties also apply in determining the
optimum value of y.
19

Example2: Continuous 1-Median

Location Problem
Find the optimal x and y coordinates of a new location.
Single facility problem (an example):
Suppose a new copying machine is to be installed in an office.
Five offices will be using the machine.
Denote x and y coordinates of office i as (ai,bi)
Office

ai

bi

Demand/Weight

8
20

Contour Lines
Sometimes, the optimal solution may not be
selected because of other reasons.
In such a case, it may be important to know
the set of facilities which are within a certain
threshold value of the optimal objective value.
Plot contour lines (or iso-cost lines)

21

(7,16)

12

1
11

6
(6,10)

-3

-1
(9,10)

3
(5,7)

-3/2

10

1/2

9
8
7

6
5

-2

-1/2

-1 (7,5) 1/2

-1/6

(9,6)
1/6

(15,7)

3
5

2
1

-12

-1

0
0

-6
2

-12

-2

3
6

1
8

10 11 12 13 14 15

12
22

Minmax problem
When you locate a facility, all the points that
you can reach from it within radius r:
r

With Euclidean
distance

With Tchebyshev
distance

With rectilinear
distance

23

1-center problem with rectilinear

distance
Problem:
Min f(x) = max{|x-ai|+|y-bi|, i=1,2m}
Then, the optimal solutions to the minmax location
Let
problem can be shown to be all points on the line
c1= min{ai+bi}
segment connecting point
c2= max{ai+bi}
c3= min{-ai+bi}
(x1*, y1*)= (c1-c3, c1+c3+c5)
c4= max{-ai+bi}
and point
(x2*, y2*)= (c2-c4, c2+c4-c5)
c5= max{c2-c1, c4-c3}

Max distance=c5/2
24

An example
ai

bi

0
4
8
10
4
2
6
8

0
6
2
4
8
4
4
8

ai+bi
0
10
10
14
12
6
10
18

c1=0
c2=16

bi-ai
0
2
-6
-6
4
2
-2
0

(x1*, y1*)= (c1-c3, c1+c3+c5)

(x1*, y1*)=(3, 5)
(x2*, y2*)= (c2-c4, c2+c4-c5)
(x2*, y2*)=(6,2)

c3=-6
c4=4

c5=max{16-0,4-(-6)}=16
25

An example (cont)
9
8
7
6
5
4
3
2
1
0
0

10

11

12

26

Facility Location
Facility Location Models
Rectilinear Facility Location Problem
Single-Facility Minisum Location Problem
Single-Facility Minimax Location Problem
n-Facility Location Problem

Simple Location Analysis Techniques

Location-Allocation Models
Plant Location Model

Waiting Line Models

Poisson Queues
Non-Poisson Queues
27

1-Median with Euclidean Distance

Minimize the squared weighted Euclidean
distance to existing facilities
Also a possible model for placement of emergency
response facilities
A condition worsens in proportion to the square
of the time to respond
Find the location of the new facility ( x, y ) to minimize
m

f ( x, y ) wi [( x ai ) 2 ( y bi ) 2 ]
i 1

28

1-Median with Euclidean Distance

The optimal location that minimizes the weighted Euclidean
distance to existing facilities can be found using calculus
f ( x, y) m
f ( x, y) m
2wi ( x ai ),
2wi ( y bi )
x
y
i 1
i 1

Set each partial derivative equal to zero and solve for x and y
m

x*

wa
i 1
m

i i

w
i 1

y*

wb
i 1
m

i i

w
i 1

i
29

1-Median with Euclidean Distance

The coordinates are weighted averages of the
existing coordinates
This is the centroid or center-of-gravity
Locate facility at center of movement in
geographic area
Based on weight and distance traveled;
establishes grid-map of area
Identify coordinates and weights shipped for each
location
30

Grid-Map Coordinates
y

x=

i=1

1 (x1, y1), W1

x1

x2

x3

y=
Wi

Wi

i=1

where,
x, y = coordinates of new facility at
center of gravity
xi, yi = coordinates of existing facility i
Wi = annual weight shipped from
facility i

3 (x3, y3), W3

y3

yiWi

i=1

y1

xiWi

i=1

2 (x2, y2), W2

y2

x
31

Center-of-Gravity Technique: Example

y
700
600

Miles

500

C
(135)

200

B
100
500
105

C
250
600
135

D
500
300
60

(105)

400
300

x
y
Wt

A
200
200
75

D
(60)

A
(75)

100
0

100 200 300 400 500 600 700 x

Miles
32

Center-of-Gravity Technique: Example

(cont.)
n

xW
i i

x=

i=1

W
i

(200)(75) + (100)(105) + (250)(135) + (500)(60)

75 + 105 + 135 + 60

= 238

i=1
n

yW
i i

y=

i=1

W
i

(200)(75) + (500)(105) + (600)(135) + (300)(60)

75 + 105 + 135 + 60

= 444

i=1

33

Center-of-Gravity Technique: Example

(cont.)
y
700
600

Miles

500

C
(135)

B
(105)

400
300
200

x
y
Wt

A
200
200
75

B
100
500
105

C
250
600
135

D
500
300
60

Center of gravity (238, 444)

D
(60)

(75)

100
0

100 200 300 400 500 600 700 x

Miles
34

Load-Distance Technique
Compute (Load x Distance) for each site
Choose site with lowest (Load x Distance)
Distance can be actual or straight-line

35

Load-Distance Calculations
n

LD =

li di

i=1
where,
LD =
li =

di =
di =

load-distance value
load expressed as a weight, number of trips or units
being shipped from proposed site and location i
distance between proposed site and location i
(xi - x)2 + (yi - y)2

where,
(x,y) = coordinates of proposed site
(xi , yi) = coordinates of existing facility
36

Load-Distance: Example
Potential Sites
Site
X
1
360
2
420
3
250

Y
180
450
400

X
Y
Wt

A
200
200
75

Suppliers
B
C
100
250
500
600
105
135

D
500
300
60

Compute distance from each site to each supplier

Site 1 dA = (xA - x1)2 + (yA - y1)2

= (200-360)2 + (200-180)2

= 161.2

dB = (xB - x1)2 + (yB - y1)2

= (100-360)2 + (500-180)2

= 412.3

dC = 434.2

dD = 184.4
37

Load-Distance: Example (cont.)

Site 2

dA = 333

dB = 323.9 dC = 226.7 dD = 170

Site 3

dA = 206.2 dB = 180.3 dC = 200

dD = 269.3

Compute load-distance

LD =

ld

i=1
i

Site 1 = (75)(161.2) + (105)(412.3) + (135)(434.2) + (60)(434.4) = 125,063

Site 2 = (75)(333) + (105)(323.9) + (135)(226.7) + (60)(170) = 99,789

Site 3 = (75)(206.2) + (105)(180.3) + (135)(200) + (60)(269.3) = 77,555*

* Choose site 3
38

Locating Multiple Facilities

Assumptions
The facilities are identical. Therefore, the
customers have no preference. They would go
to the nearest facility.
The facilities have no capacities.

39

Multiple Facilities
Problem: We would like to locate 2 identical service
stations.
We identified six areas from which demand will occur.
There are four possible buildings where we can locate the
service stations. The table below shows the customer
demand and their distance to the potential sites.
Customer

Demand

Distance to Potential Sites

1

100

50

200

100

20

50

40

Brute Force Approach

Customer

Demand

100

50

200

100

20

50

Distance to Potential Sites

1&2

1&3

1&4

2&3

2&4

3&4

41

A heuristic
The idea:
Locate one facility at a time
where the maximum benefit is derived from

A facility should be located where the cost of

assigning all customers to that location is the
minimum

42

One Site at a Time

Customer

Demand

Distance to Potential Sites

1

100

50

200

100

20

50

7
Customer

Weighted Distance to Potential Sites

1

500

100

300

150

200

100

100

800

600

1400

400

300

600

400

40

80

60

20

100

300

200

350

1590

1580

2660

1270
43

Calculate Potential Savings with an

Additional Site
Customer

Potential Savings
1

500

100

300

150

200

100

100

800

600

1400

400

300

600

400

40

80

60

20

100

300

200

350
1270

44