Im Rahmen eines kleinen Projektes für die Uni beschäftige ich mich im Moment intensiver mit dem Traveling Salesman Problem und Lösungsalgorithmen dafür. Ziel das Projektes, das ich mit zwei Studienkollegen durchführe, ist es, die Funktionsweise dieser Algorithmen in einem Programm zu visualisieren. Von unserem Programm gibt es bisher noch keine öffentliche Version, jedoch gibt es bereits einige sehr schöne JAVA-Applets, die ähnliches leisten:

Ein Applet, das das Traveling Salesman Problem per Simulated Annealing (Simulierte Abkühlung) löst. Das Verfahren orientiert sich dabei am kontrollierten Abkühlen von Metallen zur Beeinflussung der Atom-Struktur. Details dazu gibt es bei Wikipedia 😉

Auch mit genetischen Algorithmen kann man das Traveling Salesman Problem lösen, wie man an diesem Applet sehr schön sehen kann.

Ein weiteres spannendes Verfahren ist die Ant Colony Optimisation, die das natürliche Verhalten von Ameisen bei der Suche nach kürzesten Wegen simuliert.

Natürlich gibt es noch weitere Verfahren, mit denen man das Traveling Salesman Problem lösen kann, jedoch will ich mich hier auf diese 3 bekannten Verfahren beschränken und auf die sehr gute  Seite zum Traveling Salesman Problem des Georgia Institute of Technology verweisen. Dort werden unter anderem die größten Traveling Salesman Probleme vorgestellt, die jemals gelöst wurden.