… ist der Titel der besten Diplom- bzw. Magisterarbeiten aller Studien der Technischen Fakultät an der Universität Klagenfurt und wurde vom Förderverein Technische Fakultät mit EUR 1500,– ausgezeichnet. Der Autorin und Preisträgerin, Frau Dipl.-Ing. Karin Kruggel, wurde der Preis im Rahmen der Eröffnung des akademischen Jahres 2011/2012 übergeben und die Arbeit wird hier kurz vorgestellt:
Das Rundreiseproblem, auch als Problem des Handlungsreisenden, kurz TSP, bekannt, ist ein kombinatorisches Optimierungsproblem. Dieses mathematische Problem ist sehr einfach zu beschreiben. Die Aufgabe besteht darin eine Reihenfolge für den Besuch mehrerer Orte so zu wählen, dass die Gesamtreisestrecke nach der Rückkehr zum Ausgangspunkt möglichst kurz ist. Weiters muss jeder Ort genau einmal besucht werden.
Die einfache Beschreibung dieses Problems macht das TSP zur idealen Plattform um neue algorithmische Ideen zu entwickeln. Daher ist das Traveling Salesman Problem wohl eines der populärsten und meist erforschten Probleme der Mathematik.
Derartige Fragestellungen spielen in der Praxis eine große Rolle wie beispielsweise im Design von Mikrochips, der Verteilung von Waren, der kostenoptimalen Belegung von Maschinen, bei der optimalen Wegplanung eines Bohrers auf einer Leiterplatte oder bei der Tourenplanung eines Kunden- oder Pannendienstes. In vielen praktischen Anwendungen müssen zudem Zusatzbedingungen wie eingeschränkte Ressourcen, Zeitfenster oder automatisierte Bohrer, die sich nur vertikal und horizontal bewegen können beachtet werden, was die Lösung des Problems erheblich erschwert.
Die Probleme mit denen man sich in der kombinatorischen Optimierung beschäftigt sind meist sehr schwierig. Komplexitätstheoretisch gehört das TSP zur Klasse der NP-vollständigen Probleme. Es stellt sich die Frage, wie man mit solchen Problemen umgeht, da es für diese Klasse von Problemen keine effizienten Algorithmen gibt. Die Laufzeit des worst-case-Szenarios jedes deterministischen Algorithmus, der für dieses Problem stets optimale Lösungen liefert, hängt im besten Fall exponentiell von der Anzahl der Städte ab. Solch ein Algorithmus benötigt bereits für eine geringe Anzahl von Städten enorm viel Zeit. Aus diesem Grund ist man an der Berechnung von guten und zufrieden stellenden Approximationen interessiert.
Zur Lösung dieser Optimierungsprobleme können Methoden der differenzierbaren Optimierung wie das Verfahren des steilsten Abstiegs nicht angewendet werden, weil mathematische Eigenschaften wie Stetigkeit und Differenzierbarkeit in der kombinatorischen Optimierung nicht gelten. In der Literatur wird zur Minimierung von nichtglatten Funktionen häufig auf die Subgradienten Methode verwiesen. Die Idee meiner Masterarbeit war es für die Minimierung anstatt dieser die Bundle Methoden zu verwenden.
Das Ziel war es mit Hilfe der Bundle Methoden eine gute untere Schrankenberechnung für das TSP zu finden. Umfangreiche numerische Berechnungen lieferten sehr gute Resultate und zeigten die praktische Brauchbarkeit dieses Zugangs. So konnte zum Beispiel bei einem getesteten Städteproblem mit 2392 Knoten eine untere Schranke von lediglich 1,19 Prozent Abweichung zur optimalen Rundreise gefunden werden. Weiters wurde bei einer Problemgröße von 100 zufällig gewählten Knoten eine Abweichung von 0,13 Prozent zum Optimum erzielt.
Zusammenfassend kann somit gesagt werden, dass die Bundle Methoden eine gute Wahl zur Berechnung von brauchbaren unteren Schranken für das Rundreiseproblem darstellen.
