Minimize weighted average distance

[shg]

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?

 

[JoeMo]

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.

 

[StephenCrump]

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.

 

[StephenCrump]

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.

 

[StephenCrump]

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.

 

[shg]

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.

 

[StephenCrump]

It doesn't seem it should be that complicated.

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

ΣWeight_i x Distance_i

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?

 

[shg]

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.

 

[shg]

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.

 

[shg]

I completely missed post #3. That nails it, thank you, Stephen.

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