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?

  • $\begingroup$ 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. $\endgroup$ – joriki Nov 25 '11 at 5:36
  • 1
    $\begingroup$ This sounds like a variation on the Travelling Salesman Problem. Read about it here: en.wikipedia.org/wiki/Salesman_problem $\endgroup$ – WesT Nov 25 '11 at 6:02
  • $\begingroup$ 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. sauk.wisgop.info/files/2010/08/interstate.gif $\endgroup$ – Vortico Nov 25 '11 at 7:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.