Salesman problems

What is the problem?


The Travelling Salesman Problem (TSP) is a problem in combinatorial optimisation studied in operations research and computer science. Given a list of cities and their pair-wise distances, the task is to find a shortest possible circuit that starts at a city, visits each of the other cities exactly once, and then returns to the starting city.

The problem was first formulated as a mathematical problem in 1930 and is one of the most intensively studied problems in optimisation. It is used as a benchmark for many optimisation methods. Even though the problem is computationally difficult, a large number of heuristics and exact methods are known, so that some instances with tens of thousands of cities can be solved. In general terms for n cities, the number of possibilities is (n-1)!

Real life situations

The TSP has several applications even in its purest formulation, such as planning, logistics, and the manufacture of microchips. Slightly modified, it appears as a sub-problem in many areas, such as DNA sequencing. In these applications, the concept city represents, for example, customers, soldering points, or DNA fragments, and the concept distance represents travelling times or cost, or a similarity measure between DNA fragments. In many applications, additional constraints such as limited resources or time windows make the problem considerably harder. Below is an activity in which the same principle applies into guiding the character to the shortest possible route to its intended destination:

Applet courtesy of www.pbskids.org