The Travelling Salesman is one of the oldest computational problems existing in computer science today. It is also one of the most studied computational mathematical problems, as University of Waterloo suggests. The problem describes a travelling salesman who is visiting a set number of cities and wishes to find the shortest route between them, and must reach the city from where he started.

This is a problem that, even when broken down into its components, remains complex and difficult to solve. The reason for this is that it is simply a mathematically intense problems, with the amount of possible likelihoods only increasing with the amount of cities in the problem.

Today, efficient solutions to the TSP have been found, seeing use in astronomy, computer science and actual routing. It also represents one of the most novel methods of approaching a problem.

Why TSP Is So Difficult To Crack

Firstly, TSP becomes more computationally intensive the higher number of cities there are. In an example, problem using only 10 cities, the total number of possibilities for the salesman to travel between them would be close to 180,000. This value is defined by finding the factorial of 9, as per formulae of permutations and combinations. This can further be divided by 2, as there are equal routes that will repeat at least once.

The sheer amount of required calculations itself puts the problem way beyond anything that was possible with computers. Trying every possible outcome, also known as the brute force method, is the most expensive way to solve the problem in terms of compute. However, it is also one of the most simplest solutions to the problem, with a solution being defined as the most efficient and short distance between all the points.

It is commonly visualized in a graph form, with each point on the graph representing one city. This makes it easier to plot a distance between two or more cities, as they can simply be denoted using a line joining the two points together. Interestingly, humans have also been found to be very efficient at gauging this problem, due to something known as heuristics.

What Are Heuristics

Heuristics are like shortcuts for our brain, cutting out a lot of the calculations and math for a quick and easy solution. An example of this would be when going shopping, what is considered expensive or cheap by an individual is based on a baseline price, either checked online or based on past experiences. This is a shortcut used to make quick decisions.

Psychological researchers have found that humans are very good at solving the TSP, with no clear explanation as to how they do it. It has been hypothesized that these are based on a heuristic known as the ‘crossing-avoidance’ heuristic. As the name suggests, this was developed by the mind to navigate in a given space without crossing a specific object or line.

As with everything, however, it is more difficult for algorithms to do the same, as they simply have to try every single solution. Or do they? A prominent solution developed for use with the TSP was the branch and bound algorithm, which was found to hold good for a range of about 40-60 cities. These do not require the amount of computation required by the brute force method, as they do not try to seek out every solution.

The branch and bound algorithm functions in two stages, as suggested by the name. First, the program begins by branching out into multiple smaller branches, splitting the problem and making it easier to solve. Then, certain boundaries are enforced upon the branching, so as to not let it become a brute force algorithm. These bounds are the minimum permissible value of the shortest distance available.

While the brute force method becomes impractical and expensive at around 20 cities, the branch and bound algorithm does so at around 70. However, there is a more efficient version of the branch and bound algorithm known as branch-and-cut algorithm that can work for much larger datasets.

The branch and cut algorithm functions differently by implementing problem specific cut generation, meaning that it will use cutting planes in order to tighten the relaxations of linear programming. This method is currently the record-holding general solution for the TSP, being used to solve a TSP with almost 86,000.

TSP & Its Current Applications

TSP is not only used to find better solutions for existing problems, but can also be used to devise newer ways of looking at existing problems. One of the most fascinating uses of the TSP is to detect how ants move. In a study on ant colony optimization, researcher Marco Dorigo found that it was possible to generate the most optimal ant colony by using the TSP.

The TSP can also be used to, naturally, find the shortest distance between applications that require this for more than 5 points. For example, it is used to find out how a laser should move when boring point into a printed circuit board. It is also used by astronomers to determine the movement of a telescope for the shortest distance between many stars in a constellation.

One of the most difficult variants of the problem, the ‘world tour’ has also been solved to a 0.05% of the optimal solution. Even as the TSP’s time in the sun is over, it still finds applications in all verticals.