Research Group Formal Methods and Deduction Prof. Dr. J. Avenhaus

 The travelling salesman problem

The travelling salesman problem is an optimization problem. Therefore it is not sufficient to find an arbitrary solution. Instead, one is interested in the best (or at least a very good) solution.
The travelling salesman problem is quite simple: a travelling salesman has to visit customers in several towns, exactly one customer in each town. Since he is interested in not being too long on the road, he wants to take the shortest tour. He knows the distance between each two towns he wants to visit.
The picture shows two possible tours for an example with five cities. For such a small example the problem is easy to solve. But examples with 100 or 1000 cities show that a systematic search for a solution is very expensive.
So far, nobody was able to come up with an algorithm for solving the traveling salesman problem that does not show an exponential growth of run time with a growing number of cities. There is a strong belief that there is no algorithm that will not show this behaviour, but no one was able to prove this (yet). But one was able to prove that the traveling salesman problem is a kind of prototypical problem for a big class of problems (the famous class NP) that show this exponential behaviour. This is the reason why many reasearch groups are interested in the traveling salesman problem, since techniques developed for this problem can be transfered to other problems of this class.