Travelling Salesman Optimization

The aim of this project is to solve the well-known problem of the traveling salesman with the help of various optimization techniques. The results of the different techniques are visualized so that they can be directly compared.

Problem Statement

The problem of the salesman consists in the fact that the salesman tries to visit different cities consecutively and returns at the end again to the starting city. In the process the salesman tries to find a route that is as short as possible. The problem can be described as a complete, weighted graph . The cities can be described as nodes and the distance between two cities and with and as a weighted edge . For more information, see Wikipedia.

Path Representation

To represent the way of the traveling salesman in this project we use the direct enumeration of the successively visited cities. For this purpose the cities are numbered from to . A path can then be described as a tuple . In other words, the traveler travels from city directly to city for . If city is the starting point, we require that .

Optimization

To solve the problem, compile and execute the main code in TravellingSalesman.java. In this class you can specify all optimizers of interest and their parameters.

Simulated Annealing

Ant Colony Optimization

Visualization

Authors

• Philip Rinkwitz

License

This project is licensed under the MIT License - see the LICENSE.md file for details

References

Acknowledgements:

The formulas of this README were create using:

• Codecogs online Latex editor