# Wikenigma - an Encyclopedia of Unknowns Wikenigma - an Encyclopedia of the Unknown

# 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.

### The problem in detail

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 real-world implications

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.)

### Currently used approximations

- 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

**Show another (random) article**

Suggestions for corrections and ideas for articles are welcomed :

**Get in touch!**

Further resources :