Will We Ever Solve The Traveling Salesman Problem!?

https://www.wired.com/2013/01/traveling-salesman-problem/

Before we had the computing technology, the traveling salesman problem to get around all the cities of the United States was worked on for hours on end as people could never truly find the shortest route. Now, with the use of machines and computer algorithms people are surely disappointed to find out that there is possibly no true solution, but instead produces routes guaranteed to be at most 50 percent longer than the shortest route. This method was Christofides’ algorithm. It wasn’t until a Stanford-McGill team was finally able to beat out Christofides’ algorithm by 10 percent, making thee current record 40 percent longer than the shortest route.  Mathematicians are confident that in order to come up with a route any shorter we must come up with new ideas, as we haven’t quite “hit the switch” yet.

 

The shortest traveling salesman route going through all 13,509 cities in the United States with a population of at least 500 (as of 1998).

 

One Reply to “Will We Ever Solve The Traveling Salesman Problem!?”

  1. I find it interesting that, even with the copious amounts of technology we’ve created, nobody is able to figure out a real solution to this problem. I think one of the more interesting factors in this problem is that it is done by population.

    As most people know, the population, in general, continues to increase around the world. If the traveling salesman is going to every city with a population of more than 500, there will always be new cities popping up that the salesman would have to visit, which will change the results every time.

Leave a Reply