Quickest lower 48 US states tour

[Ron Lee]

KentB is off again, over MS. Is there a way to easily determine the shortest routing that would cover all 48 states? I don't mean manually.

Starting point is not relevant.

[erich weaver]

I remember from many years ago that the problem of finding the shortest route given multiple destinations had defied mathematicians for ages. There were various approaches that yielded "good" routes, but no guarantee that it was the absolute shortest. Now that we are in the computer age, it may be that the brute-force method of trying them all is feasible in many cases. Gonna have to google this and see what the latest is.

erich

[erich weaver]

http://en.wikipedia.org/wiki/Travell...lesman_problem


Much of this is way over my head, but I get the general idea that the problem is non-trivial, and the time required to find an exact solution increases exponentially with the number of desired destinations. Once you get more than about 20 destinations, you would have a very long wait to come up with the best route, even using modern computers.

erich

[David Paule]

Assuming that the specific question can even be answered, there are a few other constraints to add in, like winds aloft and other potential weather difficulties, fuel availability, and perhaps even TFRs. These can all delay or even make a particular destination impossible in the optimal sequence.

All this suggests that finding a useable, robust route might be a better real-world solution.

In other words, treat the problem like an engineering problem ("Get it good enough and press on," as Mark Drela put it) rather than as a scientific problem, where a theoretical state of perfection is the goal.

[Kyle Boatright]

Originally Posted by erich weaver

http://en.wikipedia.org/wiki/Travell...lesman_problem


Much of this is way over my head, but I get the general idea that the problem is non-trivial, and the time required to find an exact solution increases exponentially with the number of desired destinations. Once you get more than about 20 destinations, you would have a very long wait to come up with the best route, even using modern computers.

erich

We studied this problem back in my days as an Industrial Engineering student. This problem fascinated the Operations Research folks (who were the hardcore academic types in the IE realm) and they loved talking about it. All because there was no easy technique to optimize the route. As Eric points out, with enough computing power, enough time, and a small enough set of destinations, it could be brute forced, but it isn't easy.

The first rule for this kind of thing is that the optimum path never crosses itself. That's a starting point for creating a good route. For more information, you'll need to call a grad student or a professer who deals in Operations Research. I'm sure that'll be enlightenng. ;-)