3
$\begingroup$

Say I'm building n highway system for $N$ cities on a Euclidean plane. I want to minimize the ratio of the average highway distance between each pair of cities, i.e. $\sum_{i \in P, j \in P} \| i - j \| / N^2$, divided by the total length of the roads. Is there a method for creating these paths which gives the least of this ratio?

  • 0
    I don't see how the randomness enters into the question. Would the answer be any different if you left out "randomly distributed"? Also, you haven't said anything about the sorts of highways that are allowed. Can we only connect pairs of cities directly, or could we also join more than two of them with additional vertices in between? In either case, I wouldn't expect there to be a simple answer.2011-11-25
  • 1
    This sounds like a variation on the Travelling Salesman Problem. Read about it here: http://en.wikipedia.org/wiki/Salesman_problem2011-11-25
  • 0
    Yes, additional vertices are allowed, and I have removed "randomly distributed." If the points were large cities in the United States, the result would look something like this. http://sauk.wisgop.info/files/2010/08/interstate.gif2011-11-25

0 Answers 0