====== 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~~