Wohl jeder Mensch hat sich schon einmal -- bewußt oder unbewußt -- mit dem Traveling Salesman Problem (TSP) beschäftigt. Es ist gleichzeitig ein sehr alltägliches wie mathematisch schwer lösbares Problem. Es geht darum, eine Rundreise durch eine gegebene Menge von Orten zu finden, bei der jeder Ort genau einmal besucht wird und die Streckenlänge minimal ist. Anwendungen finden sich nicht nur für den dem Problem den Namen gebenden Handlungsreisenden, sondern auch für Platinenhersteller, in der Textilindustrie und in der Kristallographie, um nur eine kleine Auswahl zu nennen.
Das TSP gehört zu der Klasse der Optimierungsprobleme. Ein Optimierungsproblem ist charakterisiert durch eine Menge von Variablen, einigen Bedingungen und einer Zielfunktion. Letztere gilt es zu minimieren, wobei die Bedingungen, die den möglichen Wertebereich der Variablen einschränken, einzuhalten sind. Das ist wohl der bekannteste Vertreter der Optimierungsprobleme.
Wie bereits angedeutet, gehört das Traveling Salesman Problem zu den mathematisch schwierigsten Problemen, es ist -schwierig. Das bedeutet, daß im allgemeinen eine exakte Lösung nicht oder nur mit nicht vertretbarem Aufwand zu finden ist. Daher versucht man, sich mit Heuristiken zu helfen, die in deutlich geringerer Laufzeit recht gute Näherungslösungen berechnen. Die Lösungsqualität solcher Verfahren ist meistens umgekehrt proportional zur Laufzeit: In kurzer Rechenzeit sind meist nur relativ schlechte Näherungslösungen zu finden.
Obwohl viel Energie in die Suche nach effizienten Heuristiken für das TSP gesteckt wurde, werden immer noch neue Erfolge auf diesem Gebiet erzielt. Zum einen erlaubt die wachsende Leistung moderner Computer die Implementierung von Algorithmen, deren Umsetzung bisher an praktischen Grenzen (zu wenig Speicherplatz, mangelnde Rechenleistung) scheiterten. Es werden aber auch neue Verfahren entwickelt oder aus anderen Einsatzgebieten auf das TSP übertragen.
Auch diese Arbeit stellt eine neue Heuristik vor. Sie basiert auf Iteriertem Matching, einem Verfahren, welches bereits bei der Anwendung auf zweidimensionale Packprobleme gute Ergebnisse lieferte. Die Idee besteht darin, die Menge von Orten durch Zusammenfassen sukzessive zu verkleinern. Dazu werden geeignete Ortspaare gebildet. Allgemein bedeutet geeignet so viel wie nah beieinander. Diese Ortspaare werden dann wie ein einzelner neuer Ort aufgefaßt.
Durch diese Maßnahme ist das Problem auf die Suche einer Tour durch eine etwa halb so große Anzahl von Orten reduziert. Zu jedem dieser Orte werden Wege durch die Teilorte gespeichert, aus denen sie bestehen. Wird das Verfahren nun wiederholt auf die immer größer werdenden Orte angewandt, so müssen am Ende nur noch die Wege der letzten beiden Orte verbunden werden. Es entsteht eine Tour durch alle Orte des ursprünglichen Problems.
In Kapitel 1 werden die wichtigsten Grundlagen der Graphentheorie und zur Komplexität von Problemen und Algorithmen vorgestellt. Außerdem werden Testinstanzen vorgestellt, anhand derer das hier erläuterte Verfahren getestet werden soll. In Kapitel 2 werden Probleme aus der Praxis beschrieben, die mit Hilfe von TSP-Heuristiken zu lösen sind. Kapitel 3 faßt eine Reihe von Verfahren für das TSP zusammen. Sie dienen als Grundlage für einen Vergleich mit der neuen Heuristik. Diese wird in den Kapiteln 4 und 5 ausführlich beschrieben. Im ersten Teil werden die einzelnen Schritte des Verfahrens erläutert, im zweiten dann die Ergebnisse aufgezeigt.
Um die Suche nach einer Lösung verfolgen zu können, wurde neben einer rein textorientierten Fassung des Programms auch eine grafische Benutzeroberfläche implementiert. Ihre Möglichkeiten werden in Kapitel 6 dargelegt. Eine zusammenfassende Betrachtung bildet neben einem Ausblick den Abschluß dieser Arbeit.