Minimize weighted average distance

shg

MrExcel MVP
Joined
May 7, 2008
Messages
21,836
Office Version
  1. 2010
Platform
  1. Windows
There's a simple weighted center problem at Distribution Center, Fulfillment Center, Warehouse Location Strategy. There are three customers of various sizes:

C​
D​
E​
6​
x​
y​
Wgt​
7​
200​
50​
2500​
8​
300​
100​
1300​
9​
100​
150​
5000​

Assuming the weight is taken to mean the number of trips you need to make each year (out and back, no stops at other customers), where should you locate a distribution center to minimize total distance?

What they did is take the weighted average of x and weighted average of y ({158, 114}), just what I'd have done; it makes the weighted average distance 81.6 miles per trip.

Except it's the wrong answer. Solver would put the facility at {100, 150}, which makes the average trip 70.6 miles.

Can someone explain the disconnect?
 

Excel Facts

How can you turn a range sideways?
Copy the range. Select a blank cell. Right-click, Paste Special, then choose Transpose.
If Solver puts the facility at {100, 150}, coincident with one of the three existing facilities that seems problematic. Hard to believe the facility should be located at the same coordinates as one of the three existing centers. Yes, that center has 57% of the volume, but that's far from all of it. The weighted average seems sensible to me.
 
Upvote 0
shg

The link you've posted uses a centroid/centre of mass approach. Averaging the x and y co-ordinates will minimise the sum of the squares of the distances. It's not the solution it purports to be.

Instead, we need the geometric median. Wikipedia notes:

Despite the geometric median's being an easy-to-understand concept, computing it poses a challenge. The centroid or center of mass, defined similarly to the geometric median as minimizing the sum of the squares of the distances to each point, can be found by a simple formula — its coordinates are the averages of the coordinates of the points — but no such formula is known for the geometric median, and it has been shown that no explicit formula, nor an exact algorithm involving only arithmetic operations and kth roots can exist in general. Therefore only numerical or symbolic approximations to the solution of this problem are possible under this model of computation
Despite the geometric median's being an easy-to-understand concept, computing it poses a challenge.
 
Upvote 0
Again from Wikipedia, which explains the particular solution in this case:

Special Cases:

For 3 (non-collinear) points, if any angle of the triangle formed by those points is 120° or more, then the geometric median is the point making that angle.
 
Upvote 0
Again from Wikipedia, which explains the particular solution in this case:

Special Cases:

For 3 (non-collinear) points, if any angle of the triangle formed by those points is 120° or more, then the geometric median is the point making that angle.

Oops, ignore this, it doesn't apply here!

Instead, it's the weight attached to the vertex of the triangle that makes it the optimal solution.
 
Upvote 0
Just to be clear ...

Given a weighted cloud of n (not just n=3) 2D points, calculate the point having the minimum weighted average distance to all other points. It doesn't seem it should be that complicated.

Also, the weights need not be integers.

I have tried the weighted average, the weighted median, and a few other approaches. None are correct.

Thanks for your interest.
 
Last edited:
Upvote 0
It doesn't seem it should be that complicated.

I agree entirely, it sounds incredibly simple. Just minimise the sum:

ΣWeighti x Distancei

But if I'm reading correctly (I don't pretend to fully understand the maths), there is no algorithm to produce a solution, and approximate or iterative methods need to be used.

I have tried the weighted average, the weighted median, and a few other approaches. None are correct.

I am curious ... is this the original problem you posted, or something else? How do you know the solution is not correct?
 
Upvote 0
The oddity starts in one dimension. What's the point on a line with the nearest average distance to some other points on the same line? Surely the average or the weighted average, right?

Nope -- it's the median point, or the weighted median point if the points are weighted:

A​
B​
C​
D​
E​
F​
G​
H​
I​
J​
K​
1​
x
Wgt
Cum Wgt
Wgt Med
Dist
2​
1​
8.93​
8.93
2
1
F2: =ABS($A2 - E$2)
1
1.292
J2: =SUMPRODUCT($B$2:$B$5, ABS($A$2:$A$5-I2))/SUM($B$2:$B$5)
3​
2​
28.82​
37.75
0
1.1
1.220
4​
3​
23.21​
60.96
1
1.2
1.149
5​
5​
1.29​
62.25
3
1.3
1.078
6​
1.4
1.006
7​
0.578
F7: =SUMPRODUCT($B$2:$B$5, F2:F5)/SUM(B2:B5)
1.5
0.935
8​
1.6
0.864
9​
1.7
0.792
10​
1.8
0.721
11​
1.9
0.650
12​
2
0.578
13​
2.1
0.600
14​
2.2
0.621
15​
2.3
0.642

The partial table shown in column I:J shows the weighted average distance for a bunch of other points, and it is, in fact, a minimum for the weighted median point.

But in 2D, using the weighted median x and y values doesn't work.
 
Upvote 0
But if I'm reading correctly <...> there is no algorithm to produce a solution, and approximate or iterative methods need to be used.
I think you're right. A few days ago, I thought there was a simple closed-form solution.
 
Upvote 0
I completely missed post #3. That nails it, thank you, Stephen.

It's just a question of knowing what to search for.
 
Upvote 0

Forum statistics

Threads
1,213,529
Messages
6,114,155
Members
448,554
Latest member
Gleisner2

We've detected that you are using an adblocker.

We have a great community of people providing Excel help here, but the hosting costs are enormous. You can help keep this site running by allowing ads on MrExcel.com.
Allow Ads at MrExcel

Which adblocker are you using?

Disable AdBlock

Follow these easy steps to disable AdBlock

1)Click on the icon in the browser’s toolbar.
2)Click on the icon in the browser’s toolbar.
2)Click on the "Pause on this site" option.
Go back

Disable AdBlock Plus

Follow these easy steps to disable AdBlock Plus

1)Click on the icon in the browser’s toolbar.
2)Click on the toggle to disable it for "mrexcel.com".
Go back

Disable uBlock Origin

Follow these easy steps to disable uBlock Origin

1)Click on the icon in the browser’s toolbar.
2)Click on the "Power" button.
3)Click on the "Refresh" button.
Go back

Disable uBlock

Follow these easy steps to disable uBlock

1)Click on the icon in the browser’s toolbar.
2)Click on the "Power" button.
3)Click on the "Refresh" button.
Go back
Back
Top