====== Travelling Salesman Problem ======

The [[https://en.wikipedia.org/wiki/Travelling_salesman_problem|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 [[https://en.wikipedia.org/wiki/Monte_Carlo_method|'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 //[[https://en.wikipedia.org/wiki/Hamiltonian_path|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 '[[content:computer_science:p_vs_np|NP]]-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 [[https://en.wikipedia.org/wiki/NP-hardness#Examples|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 [[https://www.routific.com/blog/how-do-experts-like-fedex-plan-delivery-routes|ref.]])

==== Currently used approximations ====

  * [[https://en.wikipedia.org/wiki/Concorde_TSP_Solver|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.
  * //[[https://en.wikipedia.org/wiki/Genetic_algorithm|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.
  * [[https://en.wikipedia.org/wiki/Ant_colony_optimization_algorithms|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.

~~stars>3/5~~