Traveling Salesman Problem

Question

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.

Answer 1

Randomized algorithms often work surprisingly well. An example is Simulated Annealing or its many variants.

Answer 2

For my thesis, I make use of ESA's open source optimization toolbox PaGMO, of which also a Python implementation called PyGMO is available. This page provides a written tutorial on how to solve the Traveling Salesman Problem using PyGMO. Since both PaGMO and PyGMO contain a large number of different optimization algorithms, it might be useful to play around these algorithms and see how well they perform.

Answer 3

Ants have a way of doing a random walk (more or less) and when they find a food-source they go back to the den and release a pheromone on the way. If the other ants happen to walk over one of these pheromone-lines, they follow it to the food source. They also cut corners a bit while releasing their own pheromone, so that the route from den to food is slowly optimized. I have read that there are analogous algorithms in place to find the shortest pathway for network packages in a network of servers (routing).

wiki: ant algorithm

It might be that the simulated annealing algorithms are similar in spirit, but thinking of ants is way more fun. I would not be surprised if there are similar algorithms for the TSP problem, and that investigation should be interesting.