The Traveling Salesman Problem (TSP) asks the following question: Given a list of cities and the distances between each pair of cities, what is the shortest possible tour that visits each city exactly once and returns to the origin city? The TSP is doubtless the most famous of all (combinatorial) optimization problems with high importance in both operations research and theoretical computer science. There exist very good and exciting books (e.g. by Applegate et al. or by Cook) on the TSP.

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, e.g. in DNA sequencing. In many further applications, the TSP with additional constraints, such as limited resources or time windows, is of relevance.

In our interactive presentation the pupils try to plan the shortest tour through 8 cities in the Alpen-Adria-Area. On a computer we present the tours graphically and evaluate them. Along the way the kids also learn that there are 40230 different tours through the eight cities and thus gain insight in an effect denoted as combinatorial explosion.