comment

a thoughtful web.

Good ideas and conversation. No ads, no tracking. Login or Take a Tour!

comment

wasoxygen · 3588 days ago · link · · parent · post: The Traveling Tesla Salesman

Am I missing something or is he wrong? He says this is "the optimal path that I found," which might be understood to mean that it is not the optimal path, but he also says he was "most interested in finding the exact optimum."

The Concorde tool he used "can find the exact optimal path" but I can't tell from the documentation what it returns if it cannot definitely find the shortest path; perhaps it does the best it can. We don't see how Mr. Mehyar used it because he skips a step in his wonderful report:

  [13] # create input file for Concorde TSP solver
  [14] # after running the Concorde executable, parse the output file

There wasn't a big difference between planar and geodesic At 35°N, over a few hundred miles, I wouldn't expect much projection error. A flight plotter shows very minimal curvature.

Apparently TSPs with a large number of nodes can be definitively solved, and this has been true for some time. I would be surprised if the Concorde program would report a path as the definite solution when there is still some doubt, but I can't believe that what looks like the long way around New Mexico is actually the shortest path.

markup tips · 0