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