# Traveling Salesman Problem

First off some context. The Traveling Salesman Problem(TSP) is to find the most efficient route passing through a series of points only once. However, there is no perfect function to solve for this in a reasonable amount of time. Because with each additional point, the number of possible routes is greatly increased. This is in terms of a factorial function:

n!


Where 'n' is the number of points.

I am doing a project that is attempting to examine the mathematical properties of different algorithms that provide an answer for the TSP. I am trying to examine the relationship of the time it takes to produce an answer, and how close that answer is to the correct answer. This means that I am checking every possible route using a brute force algorithm, and then will be comparing the other algorithms, and their shortest length to that of the correct answer.

Currently I am comparing the Greedy salesman method, and the brute force method, but I would like some other fairly simple algorithms that can be used for the problem. If there are any common methods that I should do more research into, or any methods that work well, please tell me along with the basic concept behind that process. For example the Greedy salesman method is always going to the closest point, and the brute force method is checking all of the possible routes.

I appreciate any of the algorithms or methods that are suggested.

• There's an excellent ipython notebook which discusses various TSP strategies that you might find useful: nbviewer.ipython.org/url/norvig.com/ipython/TSPv3.ipynb – Hemmer Oct 19 '15 at 8:15
• you might also consider the problem itself. Are you doing this on a random graph? There are some very different ways of making graphs that are going to result in very different species of graph which in turn will result in different relative performances for the algos. It is another "dial" you should probably consider well. – EngrStudent Oct 19 '15 at 20:38
• You can formulate the TSP as a binary integer program and use delayed column generation for the sub-tour elimination. – JBL Jun 6 at 2:32