Mit dieser Arbeit wurde eine neue Heuristik für das TSP vorgestellt. Bevor die Ideen dieser Arbeit aufgezeigt wurden, sind zunächst andere, bereits bekannte Verfahren dargestellt worden. Es folgte eine Skizze der Anforderungen an die Verfahren in der Praxis. Die hier eingeführte Heuristik basiert auf iteriertem Matching. Dieses sorgt durch Paarung von Knoten zu Clustern dafür, daß sich die Größe eines zu lösenden Problems immer weiter reduziert, bis nur noch zwei Cluster miteinander verbunden werden müssen. Sie gehört daher zu der Klasse der konstruktiven Heuristiken.
Eine wesentliche Idee bei der Konstruktion der Cluster ist das Speichern mehrerer Hamilton-Touren auf deren Elementarknoten. Es stellte sich heraus, daß die Ergebnisse der Heuristik sich mit zunehmender Zahl an gespeicherten Wegen zunächst deutlich verbessern. Es konnte auch eine Obergrenze von 10 für diese Zahl angegeben werden. Wird diese überschritten, ist das Verhältnis von Qualitätsverbesserung zur Erhöhung der Laufzeit ungünstig.
Wichtige Steuermechanismen für die Berechnung eines Matchings stellen die Benefitfunktionen dar. Sie bestimmen das Gewicht beziehungsweise den Benefit einer Kante im Clustergraphen. Dieses ist abhängig von den in den Endknoten gespeicherten Elementarknoten und Hamilton-Touren, von einem sogenannten Pre-Benefit aller mit den Endknoten inzidierenden Kanten und gegebenenfalls von den Pre-Benefits anderer Kanten des Graphen. Der Pre-Benefit einer Kante ist dabei ein Wert, der -- abhängig von der Wahl der Benefitfunktion -- in etwa den entstehenden Tourkosten bei Verbindung ihrer Endknoten entspricht. Die besten Ergebnisse auf geometrischen Probleminstanzen ergaben sich mit einer Funktion, die im wesentlichen vom Abstand der Schwerpunkte zweier Cluster abhängt. Da sie unabhängig von den gespeicherten Wegen ist, ergeben sich bei ihr die mit Abstand besten Laufzeiten. Die Lösungsqualität ist dabei nicht nennenswert niedriger als bei Benefitfunktionen, die auch die gespeicherten Wege zur Berechnung der Kantengewichte heranziehen.
Verschiedene Parameter haben Einfluß auf die Ergebnisse einer Benefitfunktion. Der Benefit einer Kante (u,v) kann abhängig sein von den Pre-Benefits der Kanten, die mit u oder v inzidieren einerseits, von den Pre-Benefits aller anderen Kanten des Graphen andererseits. Im ersten Fall wird von lokalem Einfluß, im zweiten Fall von globalem Einfluß der Pre-Benefits untereinander gesprochen. Die besten Ergebnisse wurden bei geringem bis keinem globalen Einfluß erzielt. Ein weiterer Parameter für die Benefitfunktion ergibt sich aus einer geforderten Mindestqualität. Eine Kante, die nicht mindestens diese Qualität aufweist, wird mit 0 gewichtet. Sie wird dadurch keinesfalls in ein Matching aufgenommen. Hier ergaben sich gute Resultate bei der Forderung nach einer Mindestqualität von etwa 15%. Der letzte Parameter ist der sogenannte Referenzfaktor. Bei der Berechnung des Benefits einer Kante (u,v) ergibt dieser Faktor multipliziert mit dem bestmöglichen Pre-Benefit aller mit u oder v inzidierenden Kanten den Pre-Benefit, der der Mindestqualität entspricht. Eine gute Wahl dieses Wertes liegt bei etwa 1,75.
Abschließend folgte ein Vergleich mit anderen Heuristiken, speziell der Savings-Heuristik. Es ist festzustellen, daß die Savings-Heuristik in kürzerer Laufzeit bessere Ergebnisse als das iterierte Matching erzielt. Das gleiche gilt für den Greedy-Algorithmus. Das iterierte Matching ist daher in dieser Form keine Alternative zu den bekannten Verfahren. Ein Einsatz empfiehlt sich höchstens dann, wenn die Darstellung der Lösung als Baum für eine Nachoptimierung sinnvoll erscheint.
Zur Visualisierung der Arbeitsweise des Verfahrens sowie der gelieferten Lösungen des Verfahrens wurde eine grafische Oberfläche mit Hilfe von Tcl/Tk implementiert. Unter dieser sind alle beschriebenen Parameter einstellbar und die Suche nach einer Lösung kann Schritt für Schritt verfolgt werden. Während der Implementation des Verfahrens diente sie unter anderem dazu, Schwächen erster Ansätze aufzudecken.
Diese Arbeit kann Ausgangspunkt sein für weitere Arbeiten auf dem Gebiet des Traveling Salesman Problem. Beispielsweise könnte das Verfahren in einen Backtracking-Rahmen integriert werden. Dabei würden berechnete Paarungen schrittweise rückgängig gemacht werden, wenn sie sich im Laufe weiterer Iterationen als nicht geeignet erweisen. Dazu müßten Teiltouren während des Verfahrens beurteilt werden. Dies kann durch die Berechnung von unteren Schranken für eine Lösung auf gegebenen Clustergraphen geschehen.
Weiterhin bietet es sich an, das Verfahren zu parallelisieren. Dazu könnte der Graph einer Probleminstanz in verschiedene Teilgraphen unterteilt werden, die dann auf die zur Verfügung stehenden Prozessoren verteilt werden. Dort werden auf den Teilgraphen Näherungslösungen berechnet, die schließlich miteinander verbunden werden. Denkbar wäre auch, die Berechnung des Matchings und das Erzeugen der Cluster als zeitlich aufwendigste Aktionen des Verfahrens zu parallelisieren. Die Vorgehensweise hier ist aber nicht so offensichtlich, wie im ersten Fall.
Eine andere Möglichkeit, die Arbeit fortzusetzen, wäre eine Modifikation für das Vehicle Routing Problem, beziehungsweise Spezialfällen davon. Man würde dann nicht mehr fordern, genau eine Hamilton-Tour zu finden. Gesucht wäre dann eine Menge von maximal k Touren, wobei k die Anzahl der zur Verfügung stehenden Fahrzeuge ist. Das vorgestellte Verfahren müßte dazu also nur früher abbrechen, wobei sicherzustellen ist, daß jede berechnete Tour auch eines einer gegebenen Menge an Depots enthält, von denen aus Ware verteilt wird. Mit Hilfe von Ergänzungen bei den Benefitfunktionen ließen sich weitere Kostenfaktoren aus der Praxis modellieren. Ein praktischer Einsatz des Verfahrens beispielsweise bei der Verwaltung eines Fuhrparks scheint daher möglich.