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?

 

[shg]

Stephen,

I implemented a weighted version of Weiszfeld's algorithm (shown in the Wikipedia article you linked to), and it works perfectly. Happy to post the code if you're interested.

Thanks again.

 

[StephenCrump]

Stephen,

I implemented a weighted version of Weiszfeld's algorithm (shown in the Wikipedia article you linked to), and it works perfectly. Happy to post the code if you're interested.

Thanks again.

You're welcome, and you're one step ahead of me, as I was tempted to do the same.

So yes, please post your code, I'd love to take a look.

On a slight tangent, I found this website which lets you play with real geographical co-ordinates:

Geographic Midpoint Calculator, Find Your Personal Center of Gravity

 

[shg]

The workbook is posted at https://app.box.com/s/9cy8ocy71nhfrtoqvls3

I looked at the calculator (pretty cool) but didn't enter any values. At a glance, the geographic center of distance algorithm does kind of a 2D binary search.

Having implemented Weiszfeld's algorithm, who worked with Paul Erdos, I have now reduced my Erdos number to about 1E6.

 

[StephenCrump]

Wow, you've been busy! It looks great, but I may not have a chance to play with it for a couple of days.

The Erdos bunch are pretty snooty. Perhaps the likes of us should stick to Six Degrees of Kevin Bacon?

 

[shg]

The Erdos bunch are pretty snooty.

I envy the Erpos 1's. What an honor to have him appear at your door, single suitcase in hand containing all of his worldy belongings, ready to move in and do math. It is impossible for me to imagine the intellects of the chosen ones, but I can well imagine their rapture on his arrival.

 

[shg]

Did some cleanup and consolidation of the code, added some error checking, added a nod to Stephen for getting me pointed in the right direction. Same link.

 

[StephenCrump]

shg

Finally, I have had time to take a proper look. Nice work!

Just one very minor correction to the format:

I was curious why in the Complex-2D sheet, your algorithm exactly matched Solver's optimum latitude, but was always slightly off on the optimum longitude. Nothing to do with tolerance or number of iterations, just zeroing in very quickly on a slightly wrong solution. Also strange given that the algorithm adjusts x and y co-ordinates in exactly the same way ...

Then I realised you're passing adjusted longitudes, and the algorithm is correctly calculating the optimum adjusted longitude. But your format treats this value as if it were a longitude, and therefore calculates the weighted average distance based on an adjusted adjusted longitude.

 

[shg]

Wow, a year later I see your response. Thanks for the critical eye, Stephen.

I had wondered why the calculated answer was slightly off the Solver result, and now understand. "Unadjusting" the calculated (adjusted) longitude brings the two answers closer, but they still don't agree. Pondering.

But thank you again.

 

[StephenCrump]

Wow, a year later I see your response.

Not a problem!

... I'm not sure how close you want the results to get?

I can milk out improvements (i.e. lower weighted average distance) by reducing your tolerance variable dTol from its current .001 down to 1E-7.

Solver's results are within a tiny fraction of 1% of these, and from my testing (limited) it looks like Weiszfeld delivers the better result, i.e. Solver gives up iterating earlier.