Vergleich und Implementierung verschiedener Optimierungsverfahren anhand des Traveling-Salesman-Problems

 

Das Traveling-Salesman-Problem - ein Reisender sucht die kürzeste Rundtour durch verschiedene Städte - läßt sich zwar ganz einfach und anschaulich darstellen, doch ist es auf internationaler Ebene nach wie vor Forschungsgegenstand ganzer Expertengruppen. Der Grund hierfür liegt auf der Hand: bis heute ist kein Algorithmus bekannt, der weniger als exponentiellen Zeitaufwand benötigt, um die optimale Rundreise zu ermitteln. In gewisser Hinsicht kann das TSP sogar als klassisches Grundproblem der kombinatorischen Optimierung (z.B. Reihenfolgeprobleme) angesehen werden, was den repräsentativen Umgang mit Lösungsalgorithmen, gerade in Hinblick auf komplizierter gestaltete Alltagsoptimierungsprobleme, um so interessanter macht.

'Näherungsverfahren' ist hier das große Schlagwort. Verschiedene Tourkonstruktions- und Tourverbesserungsverfahren werden in dieser Arbeit vorgestellt, diskutiert und nicht zuletzt auch empirisch untersucht. Bei der Auswahl der Optimierungsverfahren wurde durch breit angelegte Recherche auf Aktualität geachtet. Als Eröffnungsverfahren (Tourkonstruktion) wurden Greedy-Verfahren, Nearest Neighbor und Savings-Verfahren implementiert, die in relativ kurzer Zeit mäßig bis mittel gute Ergebnisse liefern. Die Visualisierung der drei Verfahren verdeutlicht die unterschiedlichen Ansätze.

Zur Tourverbesserung kommen vielfach Näherungsheuristiken zum Einsatz, die nach gewissen naturwissenschaftlichen Fortschrittserkenntnissen (sowohl im physikalischen als auch im biologischen Bereich) arbeiten. Implementiert wurden: Genetischer Algorithmus, Simulated Annealing, Threshold Accepting, Sintflut-Algorithmus und COSA-Verfahren. Aber auch klassische Verbesserungsverfahren, wie 2-Opt- und 3-Opt-Verfahren, finden ihre Anwendung in dieser Arbeit.

Außerdem wurde ein exaktes Verfahren (Branch-and-Bound-Verfahren), das die kürzeste Rundtour eines TSPs ermitteln kann, hinzugezogen. Gerade hier wurde darauf geachtet, eines der schnellsten B&B-Verfahren zu implementieren, da sonst schon bei geringen Problemgrößen wegen der exponentiellen Laufzeit dessen Anwendung sinnlos werden kann.

Neben dem Vergleich der Lösungsgüte und Laufzeit dieser Verfahren, soll die Arbeit auch einen Einblick in den Implementierungsaufwand der Optimierungsmethoden geben und den Leser auf geeignete Quellen und Ideen hinweisen, selbst solche Verfahren zu implementieren.

Eine komfortable Testumgebung (zugehöriges Windows-Programm) verschafft dem Leser zusätzlich die Möglichkeit eigene Tests durchzuführen.


Weitere Links zum Traveling-Salesman-Problem


Autor: David März

Tips und Anregungen an: mebib@informatik.fh-augsburg.de
Stand: 21.03.2003