N cities on a straight highway, where to put the airport

[markprince77]

Here is the question, that I am struggling with:
If n cities are located at various points along a straight highway, at what point along the road should an airport be located in order to minimize the sum of the distances from the n cities to the airport.

I am pretty sure that the answer is the median, due to the minimization of the mean absolute error rule, but I am unsure how to demonstrate this answer.

I started by sketching n points along a line of d distance. I think that the p.f. of the function will be something like 1/d|A -xi|, where A is the location of the airport, and xi is the location of each city i=1,..., n

I also know that the formula for finding a median is 1/2>=Pr(X<=m) and 1/2>=Pr(X>=m), but that is where I am stuck. Any help would be greatly appreciated.

 

[Denis]

Played around with it a bit; made up simple example:
A(0)..........5............B(5).....2.....C(7)...............7................D(14).............6............E(20)
That's 5 towns (A,B,C,D,E) on straight road, A and E at ends and 20 miles apart;
B is 5 from A, C is 2 from B, D is 7 from C, E is 6 from D; cumulative in brackets.

A(0)..........5............B(5).....2.....C(7).....2.....X(9).........5......D(14).............6............E(20)
Let's guess and place airport X at the 9 mile point:
travelling: from A = 9, from B = 4, from C = 2; total 15
travelling: from D = 5, from E = 11; total 16; purty close.

If we let x = X's distance from A, then:
(x-0) + (x-5) + (x-7) = (14-x) + (20-x) : notice that the cumulatives are used
3x - 12 = 34 - 2x
5x = 46
x = 46/5 = 9.2

So placing airport at 9.2 miles from A would be "perfection".

Edit: thanks wjm; I missed the simplicity!

 

[wjm11]

If n cities are located at various points along a straight highway, at what point along the road should an airport be located in order to minimize the sum of the distances from the n cities to the airport.

Just add the distances from one end and divide by the number of towns. Using Denis' example:

(0 + 5 + 7 + 14 + 20)/5 = 9.2

 

[Denis]

Thanks again, wmj :wink:

So with n towns, we have n-1 "distances"; in my example, n=5 and distances = 5,2,7,6.
Letting distances be a=5, b=2, c=7, d=6: sum of cumulatives = s = 4a + 3b + 2c + d;
so airport position from "left" town = s / n.

Similarly, s = 4d + 3c + 2b + a; results in position from "right" town: 10.8 miles in my example.

So quite simple; using a Basic program:
Data 5,2,7,6
n = 5
For t = n-1 to 1 step -1
Read d
s = s + t*d
Print s
Next t
p = s/n
Print p
End
OUTPUT:
20
26
40
46
9.2

A possible "formula" could be (k distances; k=n-1):
[d1(n-1) + d2(n-2) + ... + dk] / n : d1, d2, ... , dk are individual distances

[5(4) + 2(3) +... + 6] / 5 = 9.2

I'm sure anybody can come up with something better !