When I read this neat little puzzle I was reminded of one of my more memorable experiences studying industrial engineering in college. We were supposed to be learning about location optimizing. Imagine you are a service technician and your work is done in the different facilities of your only three customers. The following table indicates where each facility is (X and Y) and how many times a year you have to visit it (N).

#

X

Y

N

1

150

50

47

2

250

250

12

3

50

150

36

The question is what would the optimal location be to establish your own headquarters in order to minimize driving?

In my class the following was proposed as the solution to this problem.

X= (n1x1 + n2x2 + n3x3) / (n1+n2+n3)
Y= (n1y1 + n2y2 + n3y3) / (n1+n2+n3)

Not only did I recognize that this was actually a center of mass calculation, but I had a nagging intuition that it was also incorrect when applied to this problem.

Here is the calculation for the center of mass of this system.

Xcom= (47*150 + 12*250 + 36*50) / (47+12+36) = 124.7368
Ycom= (47*50 + 12*250 + 36*150) / (47+12+36) = 113.1579
Center of mass = 124.7368,113.1579

The red point shows what that looks like.

(0,300) (300,0) (0,0) (50,150) n3=36 (250,250) n2=12 (150,50) n1=47

That looks reasonable. But is it right? In the class I was told that was the optimal position which implies a falsifiable hypothesis: you can not find another point that is better. For some reason, I thought I could.

To figure this out we must know what the total annual driving distance would be for the proposed center of mass location. First calculate the distance from the proposed point to each customer location.

d1= 68.0232
d2= 185.517
d3= 83.3242

You can check this kind of thing with a term such as distance {124.7368,113.1579} {50,150} in WolframAlpha.

Now multiply each distance by the number of trips to that location (e.g. T1= 68.0232 * 47).

T1= 3197
T2= 2226
T3= 3000

Add these together and the total distance traveled to service all of the customers for the year is 8423. Is it possible to choose a location that can yield a lower amount of annual driving?

What about (137,75)? Let’s do the same analysis for that point. First the distances from this point to all of the customers.

d1= 28.178
d2= 208.312
d3= 114.865

Now multiply that by the number of trips.

T1= 1324.366
T2= 2498.544
T3= 4135.14

The total distance for all of those trips from this point is 7958, more than a 5% improvement. This point is shown in green.

(0,300) (300,0) (0,0) (50,150) n3=36 (250,250) n2=12 (150,50) n1=47

Notice I’m not saying that (137,75) is optimal. I actually guessed to find this point. When I was in college I was able to write an AutoLisp program that iterated over the plausible area and just brute force checked for the best location. I did the same just now with my own geometry inspired Lisp-like programming language. I don’t actually know the best approach to solving this problem but it’s encouraging that I was able to notice that the official technique which I was taught was not it.