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?
Connecting points while minimizing path distance between them and the total distance of the paths
3
$\begingroup$
graph-theory
optimization
-
0Yes, 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.gif – 2011-11-25