Travelling Salesman Problem

From Wikipedia, a free encyclopedia written in simple English for easy reading.

S salesman wants to visit all cities,A, B, C and D. What is the best way to do this (cheapest airline tickets, and minimal travel time)?
Enlarge
S salesman wants to visit all cities,A, B, C and D. What is the best way to do this (cheapest airline tickets, and minimal travel time)?

The Travelling Salesman Problem (often called TSP) is a problem to solve. It is about optimisation. Optimisation is about finding a better solution or answer to a problem that will lessen costs. It is a mathematical problem. But it can be shown as a picture very easily with graph theory.

[edit] Stating the problem

The problem is that of a salesman. To do his job, he has a number of places (cities) he should go to. Some of those cities are connected with each other, for example by airplanes, or by road or railway. Each of those links between the cities has one or more weights (cost) attached. The cost is how much it takes to travel the route, for example, the cost of an airplane ticket or train ticket. The question is how to find the best route for the salesman to go to the cities. The salesman wants to keep both the travel costs, as well as the distance he travels as low as possible. He must go to each city exactly once, and at the end, he must be in the city he started in.

[edit] How hard the problem is

The travelling salsesman problem is among the problems that are very hard to solve. If there is a way to break this hard problem into smaller problems, the smaller problems will be at least as hard as the original one. This is what computer scientists call NP-hard problems.

Many people have studied this problem. The easiest (and most expensive solution) is to simply try all possibilities. The problem with this is that for N cities you have N factorial possibilities. This means that for only 10 cities there are about 3.5 million combinations to try.

  • Exact solutions to the problem can be found, using branch and bound algorithms. This is currently possible for about 40-60 cities
  • There are heuristics out there. Heuristics are approximations. They will not give the best solution, but hopefully a good one. These give either seemingly good or seemingly accurate solutions. But it is not possible to prove that those solutions are optimal or the best. See Monte Carlo algorithms and Las Vegas algorithms
  • Some people try to find special cases of the problem, which are usually easier to solve.

[edit] External links

This short article can be made longer. You can help Wikipedia by adding to it.