This website is about the socalled "Traveling Salesman Problem".
It deals with the question, how to plan a complete round trip through a certain number of cities to obtain the shortest tour possible. This question can be answered quite easily for four cities. However, it gets complicated when the number of cities is increased. There exist for example 181.440 different tours through just ten cities.
How can one find the shortest tour on twenty or even more cities?
For this reason, various algorithms have been invented, which try to solve the Traveling Salesman Problem as fast as possible.
Create a new game in the next tab and try to find a shortest tour yourself! Afterwards, you may have a look at the solution and the calculation steps of the applied algorithms.
Have fun!
Euclidean metrics  
√
(x_{1}x_{2})^{2} + (y_{1}y_{2})^{2}


One metrics  
x_{1}x_{2}+y_{1}y_{2}


Maximum metrics  
max{x_{1}x_{2},y_{1}y_{2}}

Length of your tour: 
0 km 
Do not forget to visit every city exactly once!
There is no way back to the "Play game" tab.
Length of the optimal tour: 
0 km 
Length of your tour: 
0 km 
Calculation time: 
0 ms 
Optimal tour:  
Your tour: 
In this tab you may have a look at the optimal tour and the corresponding calculation steps.
In the Description of the algorithm you may find more details on the applied algorithms of the different steps.
Chair M9 of Technische Universität München does research in the fields of discrete mathematics, applied geometry and the optimization of mathematical problems. The problem and corresponding algorithms presented here are a famous example for the application of mathematics on an applied problem (and can be assigned to the field of combinatorial optimization). This page shall help the reader to recognize the application of mathematics to real life problems and to understand easy mathematical solution methods used. The algorithms presented were chosen according to understandability, they do not represent fields of research of the chair.
To cite this page, please use the following information:
The calculation of the solution is still in progress. Please try again later.
The calculation of the solution has been aborted. Please return to the Create game tab and start a new game.