12 Location

Location Problems
Basic Concepts of Location

Last IP modeling tricks
Dispel Misconception
Introduce NLP
First Heuristic
15.057 Spring 03 Vande Vate
Where to Locate
Facilities
Rectilinear Location Problems
Euclidean Location Problems
Location - Allocation Problems
Basic Intuition
On the line, if the objective is to min
The maximum distance traveled

The maximum distance left + right
The distance traveled
there and back to each customer
The item-miles traveled
Rectilinear Distance
Travel on the streets and avenues
Distance =
number of blocks East-West +
number of blocks North-South
Manhattan Metric
Rectilinear Distance
Locate a facility...
To minimize the sum of rectilinear
distances
Intuition
Where?
Why?
Minimize the sum of Rectilinear distances to customers
Solver Model
Cust.
1
2
3
4
5
6
7
8
9
10
Facility
9
9
8
3
0
4
4
2
0
5
0
Total
9
3
6
9
6
2
0
0
9
2
0
0
Xdist
Ydist
If Left
If Right If Above If Below
9.00
(9.00)
(9.00)
9.00
9.00
(9.00)
(3.00)
3.00
8.00
(8.00)
(6.00)
6.00
3.00
(3.00)
(9.00)
9.00
(6.00)
6.00
4.00
(4.00)
(2.00)
2.00
4.00
(4.00)
2.00
(2.00)
(9.00)
9.00
5.00
(5.00)
(2.00)
2.00
10
9
8
7
6
5
4
3
2
1
0
0
10
Locate a facility...
To minimize the max of rectilinear

distances
Intuition
Where?
Why?
Models
Set Customers;
Param X{Customer};
Param Y{Customer};
var Xloc >= 0;
var Yloc >= 0;
var Xdist{Customer};
var Ydist{Customer};
Constraints
DefineXdist1{c in Customer}:
Xdist[c] >= X[c]-Xloc;
Xdist[c] >= Xloc-X[c];
DefineYdist1{c in Customer}:
Ydist[c] >= Y[c]-Yloc;
Ydist[c] >= Yloc-Y[c];
10
Objective
Total Distance:
sum{c in Customer}(Xdist[c]+Ydist[c]);
Maximum Distance?
11
Min the Max!
Var Xloc;
var Yloc;
var Xdist{Customer}>= 0;
var Ydist{Customer}>= 0;
var dmax;
min objective: dmax;
s.t. DefineMaxDist{c in Custs}:
dmax >= Xdist[c] + Ydist[c];
12
Min the Max Contd
Xdist[c] >= X[c]-Xloc;
Xdist[c] >= Xloc-X[c];
Ydist[c] >= Y[c]-Yloc;
Ydist[c]
>= Yloc-Y[c];
13
Mimimize the Maximum Rectilinear Distance
Solver Model
Customer
1
2
3
4
5
6
7
8
9
10
Facility
X
9
9
8
3
0
4
4
2
0
5
0
Total
Y Max Total Xdist Ydist If Left If Right If Above If Below

9
0
0
0
0
9
-9
-9
9
3
0
0
0
0
9
-9
-3
3
6
0
0
0
0
8
-8
-6
6
9
0
0
0
0
3
-3
-9
9
6
0
0
0
0
0
0
-6
6
2
0
0
0
0
4
-4
-2
2
0
0
0
0
0
4
-4
0
0
0
0
0
0
0
2
-2
0
0
9
0
0
0
0
0
0
-9
9
2
0
0
0
0
5
-5
-2
2
0
0
10
9
8
7
6
5
4
3
2
1
0
2
10
14
Challenge #3
NIMBY.
Maximize the Minimum Distance
How did you do it?
15
Cust.
1
2
3
4
5
6
7
8
9
10
Facility
X
9
9
8
3
0
4
4
2
0
5
Y Min Total Xdist Ydist Left? Above? If Left If Right If Above If Below
9 0
0
29
-9
11
9
3 0
0
29
-9
17
3
6 0
0
28
-8
14
6
9 0
0
23
-3
11
9
6 0
0
20
0
14
6
2 0
0
24
-4
18
2
0 0
0
24
-4
20
0
0 0
0
22
-2
20
0
9 0
0
20
0
11
9
2 0
0
25
-5
18
2
Total
10
9
8
7
6
Y
NIMBY
Mimimize the Maximum Rectilinear Distance
5
4
3
2
1
0
0
5
X
10
Disjunctive Constraints
One of Two Constraints holds
Ydist = TownY DumpY
Ydist = DumpY TownY
Binary Variable Chooses 1

Ydist TownY DumpY + 20*Left
Ydist DumpY TownY + 20*(1-Left)
Only 1 matters (20 is big)

Objective drives the right choice
These are hard for the solver
17
Outline
Rectilinear Location Problems
Euclidean Location Problems
Location - Allocation Problems
18
Locating a single facility

Distance is not linear
Distance is a convex function
Local Minimum is a global Minimum
19
S1
S21
S19
S17
S15
S13
S11
S9
S7
S5
S3
What kind of function?
20
Where to Put the Facility

Total Cost = ckdk(x,y)
= ck(xk- x)2 + (yk- y)2
Total Cost/x = ck (xk - x)/dk(x,y)
Total Cost/x = 0 when
x = [ckxk/dk(x,y)]/[ck/dk(x,y)]
y = [ckyk/dk(x,y)]/[ck/dk(x,y)]
But dk(x,y) changes with location...
21
Iterative Strategy
Start somewhere, e.g.,
x = [ckxk]/[ck]
y = [ckyk]/[ck]
as though dk= 1.
Step 1: Calculate values of dk

Step 2: Refine values of x and y
x = [ckxk/dk]/[ck/dk]
y = [ckyk/dk]/[ck/dk]
Repeat Steps 1 and 2. ...
22
Solver Model: Not Linear
Facility
4.5
4.283971
4.241999
4.239085
4.239961
4.238616
4.235342
4.23113
4.226679
4.222382
4.21843
4.214899
4.211803
4.209121
4.206817
4.6
4.0907
3.73981
3.486694
3.298874
3.15693
3.048107
2.963646
2.897385
2.844914
2.80302
2.769336
2.742087
2.719928
2.701827
50.88679
50.35772
50.11444
49.9801
49.90163
49.85438
49.82525
49.80693
49.79522
49.78763
49.78265
49.77935
49.77714
49.77565
49.77464
Center of Gravity
Better Answer
23
Euclidean Location
5
45.8
4.5
45.6
4
45.4
3.5
Distance
Location
45.2
2.5
45
2
1.5
44.8
1
44.6
0.5
44.4
1
8
Iteration
10
11
12
13
14
15
Distance
Euclidean Location
9
9
8
3
0
4
4
3
0
5
4.5
4.283971
4.241999
4.239085
4.239961
4.238616
4.235342
4.23113
4.226679
4.222382
4.21843
4.214899
4.211803
4.209121
4.206817
9
1
10
9
6
2
0
0
9
0
4.6
4.0907
3.73981
3.486694
3.298874
3.15693
3.048107
2.963646
2.897385
2.844914
2.80302
2.769336
2.742087
2.719928
2.701827
4.217658 2.805268
d(x,y)
6.293648
5.762812
6.43506
4.648656
4.712749
2.64764
4.627094
4.838388
6.293648
4.627094
50.88679
50.35772
50.11444
49.9801
49.90163
49.85438
49.82525
49.80693
49.79522
49.78763
49.78265
49.77935
49.77714
49.77565
49.77464
1/d(x,y)
0.15889
0.173526
0.155399
0.215116
0.21219
0.377695
0.216118
0.20668
0.15889
0.216118
2.090624
d(x,y)
6.807507
5.638559
6.980594
5.074427
4.690185
2.109897
4.100544
4.287471
6.515646
4.152893
1/d(x,y)
0.146897
0.17735
0.143254
0.197067
0.213211
0.473957
0.24387
0.233238
0.153477
0.240796
2.223116
d(x,y)
7.092825
5.490459
7.301544
5.404827
4.806559
1.75656
3.747632
3.940653
6.757525
3.815855
1/d(x,y)
0.140988
0.182134
0.136957
0.18502
0.208049
0.569294
0.266835
0.253765
0.147983
0.262064
2.35309
d(x,y)
7.284426
5.371216
7.521146
5.65083
4.928139
1.505796
3.494881
3.70032
6.954595
3.568757
1/d(x,y)
0.137279
0.186178
0.132958
0.176965
0.202916
0.664101
0.286133
0.270247
0.14379
0.28021
2.480777
d(x,y)
7.427032
5.286094
7.683943
5.83441
5.027261
1.320854
3.30759
3.524213
7.104936
3.385296
1/d(x,y)
0.134643
0.189176
0.130142
0.171397
0.198915
0.757086
0.302335
0.283751
0.140747
0.295395
2.603587
10
9
8
7
6
Y
Customer
1
2
3
4
5
6
7
8
9
10
Facility
5
4
3
2
1
0
0
10
25
Moving On
Example of Convex Minimization (Nonlinear)
Example of a Heuristic: Not guaranteed to
give us the best answer, but works well.
26
Locating Several Facilities

Fixed Number of Facilities to Consider
Single Sourcing
Two Questions:
Location: Where
Allocation: Whom to serve
Each is simple
Together they are harder
27
Iterative Approach
Put the facilities somewhere
Step 1: Assign the Customers to the
Facilities
Step 2: Find the best location for each
facility given the assignments (see
previous method)
Repeat Step 1 and Step 2 .
28
Assign Customers to Facilities

Uncapacitated (facilities can be any size)
Greedy: Assign each customer to closest
facility
Capacitated
Use Optimization: Single-sourcing
29

12 Location

Uploaded by

Copyright:

Available Formats

12 Location

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

12 Location

Uploaded by

Copyright:

Available Formats

Location Problems

Basic Concepts of Location

15.057 Spring 03 Vande Vate

15.057 Spring 03 Vande Vate

The maximum distance traveled

The item-miles traveled

15.057 Spring 03 Vande Vate

Travel on the streets and avenues

15.057 Spring 03 Vande Vate

15.057 Spring 03 Vande Vate

15.057 Spring 03 Vande Vate

Minimize the sum of Rectilinear distances to customers

15.057 Spring 03 Vande Vate

To minimize the max of rectilinear

15.057 Spring 03 Vande Vate

15.057 Spring 03 Vande Vate

Min the Max!

Min the Max Contd

Mimimize the Maximum Rectilinear Distance

Y Max Total Xdist Ydist If Left If Right If Above If Below

15.057 Spring 03 Vande Vate

Maximize the Minimum Distance

How did you do it?

15.057 Spring 03 Vande Vate

Mimimize the Maximum Rectilinear Distance

15.057 Spring 03 Vande Vate

Binary Variable Chooses 1

Only 1 matters (20 is big)

15.057 Spring 03 Vande Vate

Locating a single facility

Local Minimum is a global Minimum

15.057 Spring 03 Vande Vate

15.057 Spring 03 Vande Vate

What kind of function?

Where to Put the Facility

Step 1: Calculate values of dk

Repeat Steps 1 and 2. ...

15.057 Spring 03 Vande Vate

Solver Model: Not Linear

15.057 Spring 03 Vande Vate

15.057 Spring 03 Vande Vate

15.057 Spring 03 Vande Vate

Locating Several Facilities

15.057 Spring 03 Vande Vate

Assign Customers to Facilities

15.057 Spring 03 Vande Vate

You might also like