Travelling Salesman Problem

Die Klasse Node bietet einen Wrapper für die Koordinaten und abstrahiert die Ausgabe im Plot und als Text.

Des weiteren wurden einige Funktionen abstrahiert um die Lesbarkeit zu verbessern:

• distance() ermittelt den Abstand zwischen zwei Punkten.
• total_distance bildet die Summe aller Abstände entlang der Punkte in der übergebenen Liste. Der Parameter circle schließt den Kreis von letzter zu erster Node.
• plot_path() und plot_route() abstrahieren die Interkation mit plt.
• get_closest_node() ermittelt die nahgeliegenste Node zu current_node. Ist current_node in nodes enthalten wird sich der Abstand 0 ergeben. Entsprechend sollte diese vor dem Aufruf entfernt werden.
• parse_data_file() liest Dateien im Format von tsp01.data und erstellt eine entsprechende Liste von Nodes.

Brute Force

Hier werden alle möglichen Kombinationen der Nodes überprüft. Dafür kommt die Funktion itertools.permutations() zum Einsatz. Sie erlaubt das durchlaufen aller Möglichkeiten in einer for-Schleife und so einen sehr klaren Algorithmus: Für jede mögliche Route merke Kombination und Länge, falls diese kürzer als die bislang kürzeste Route ist. Zuletzt wird die Kürzeste ausgegeben.

Nearest Neighbour

Durch diese Heuristik können erheblich mehr Punkte in die Berechnung einbezogen werden, allerdings weist das Ergebnis meist sehr lange Sprünge und Wegkreuzungen auf.

1. Es wird eine Liste aller noch nicht verbundenen, übrigen Nodes erstellt.
2. Als Startpunkt wird das erste Element der Route hinzugefügt.
3. Der selbe Punkt wird aus den übrigen Nodes entfernt.
4. Solange noch Nodes übrig sind:
   1. Ermittle die nächste Node zur zuletzt verbundenen,
   2. füge sie der Route hinzu und
   3. entferne sie aus den übrigen Nodes.
5. Gib die entstandene Route aus.

2-opt

Der 2-opt-Heuristik soll Kreuzungen finden und sie durch geschicktes Vertauschen die Nodes eliminieren. So wird das Ergebnis der Nearest-Neighbour-Heuristik erheblich verbessert.

Ich konnte nicht die Ruhe finden das ordentlich umzusetzen. Die auftretenden Fehler haben sehr wahrscheinlich mit den Zugriffen auf die einzelnen Elemente und deren erneute Zuweisung zu tun.