Travelling Salesman Problem

The Travelling Salesman (TSP) is a problem of Theoretical Computer Science and Graph Optimization.

Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city just once and returns to the origin city?"

The problem has been examined since the 1930s. but a formal mathematical 'proof' - which could enable a quick and exact computation, has not yet been found.

Computing algorithms (using so-called 'Monte Carlo' processes) can now tackle the TSP with thousands of destinations and give an almost exact answer.

In graph theory terms, the TSP consists of finding a Hamiltonian circuit with the minimum total weight.

While the existence of a Hamiltonian circuit in a graph appears as a straightforward identification task for mathematicians, developing an algorithm that can find these circuits in polynomial time for any given graph remains an open challenge in computer science.

As the number of cities gets bigger, the number of possible routes between them grows factorially. This rapid growth results in a vastly increasing number of possible iterations to find the optimal path. The greater the number of cities, the longer the time required for a full computation of every possible route.

Thus, from a computational standpoint, the problem is known as 'NPplugin-autotooltip__plain plugin-autotooltip_bigThe 'P versus NP' problem

The 'P versus NP' problem is a major unsolved enigma in mathematical computer science,

It was first described in 1971 by mathematician Stephen Cook in his paper entitled 'The complexity of theorem-proving procedures' Proceedings of the Third Annual ACM Symposium on Theory of Computing-hard ' - that's to say that there is always a way to find a solution to the problem, but on a large scale it can be computationally impractical for a computer program to iterate though the every possible combination and check if it's the best possible route. (see Wikipedia for more NP-hard info.).

The TSP has very important real-world applications. For example, in the sector of logistics and transportation TSP solvers are used to reduce transportation costs and minimise carbon emissions. It is also important for electronic circuit-boards and chip-layout designs - with the same aim of reducing costs and improving performances. However, it's unlikely that an exact solution to the problem will seriously benefit TSP-based companies, since the currently used algorithms, which are almost perfect, already provide high-level solutions.(example ref.)

• The Concorde TSP Solver is an open-access program combining exact algorithms with heuristics to quickly find optimal solutions for small graphs, and high-quality approximations when the graphs get bigger.
• Genetic Algorithms use concepts of natural selection and genetics to evolve a population of solutions over time. They are useful for small to medium-sized graphs.
• Ant Colony Optimization imitates the behaviour of ants looking for food, simulating pheromone-like trails to gradually identify better paths in small and medium-sized graphs.

Importance Rating