Travelling Salesman Problem
From Wikipedia, a free encyclopedia written in simple English for easy reading.
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
- TSPLIB
- TSP page
- Private web page with 2 algorithms & demo program to download
- Example of finding approximate solution of TSP problem using a genetic algorithm
- A Java implementation of a TSP-solution using JGAP (Java Genetic Algorithms Package). The technique used is a Genetic Algorithm.
- Solution of the Travelling Salesman Problem using a Kohonen Map
- Solution of the Travelling Salesman Problem using a Kohonen Map (in 3-dimensions!)
- Simulated annealing method for solving this problem, written in the functional programming language Objective Caml
- The Travelling Salesman Problem Talks about the use of simulated annealing to solve this problem and allows download of a DOS/Windows command-line program demonstrating problem solution.
- Most TSP loop families grow polynomially Private web page shows that a method exists for obtaining a set of optimal "travelling salesman" routes that is a member of a family that grows no faster than about 2nIn2. However, even for large n, the method yields a polynomial rate for most sets of fields of nodes.
- VisualBots - Freeware multi-agent simulator in Microsoft Excel. Sample programs include genetic algorithm, ACO, and simulated annealing solutions to TSP.
- TSP Software - Free software for finding approximate solutions to various TSP problem instances with many different approximation algorithms.
This short article can be made longer. You can help Wikipedia by adding to it.
