Die in dem Artikel von Helsgaun ”An effective implementation of the Lin-Kernighan traveling salesman heuristic“ beschriebene Heuristik ist die zur Zeit führende TSP-Heuristik und hat derzeit die größten TSP-Probleme gelöst bzw. die bisher besten oberen Schranken für eine Lösung geliefert. In dem Artikel wird die Toleranz zum 1-Baum benutzt (ohne den Begriff der Toleranz explizit zu verwenden), um den Graphen auszudünnen, d.h. die Kanten wegzulassen, die wahrscheinlich nicht für optimale Touren in Frage kommen. Das Ziel dieser Arbeit war die Verbesserung der Helsgaun-Heuristik. Es konnte für einige (teilweise schon gelöste) Probleminstanzen die Lösung in geringerer Zeit gefunden werden. Es stellte sich weiterhin heraus, dass unterschiedliche Toleranzen bei verschiedenen Arten von Problemen sowohl Stärken als auch Schwächen besitzen und zu teilweise sehr verschiedenen Ergebnissen führen. Im Laufe der Diplomarbeit konnte die bisher bekannte obere Schranke des Problems xsc6880 von 21537 kosten auf 21535 verbessert werden. Weiterhin werden durch verschiedene Modifikationen auch bessere Touren im Vergleich zur Heuristik von Helsgaun gefunden. Zudem konnte die Laufzeit der Heuristik deutlich verbessert werden, so dass zum Finden von qualitativ hochwertigen Touren nun wesentlich weniger Rechenzeit benötigt wird. Während der Diplomarbeit wurden vor allem verschiedene Toleranzbegriffe und Variationen implementiert und getestet. Die 2-Opt-Toleranz schien insbesondere bei einer fast-optimalen Tour ein gutes Kriterium für die Ausdünnung des Graphen und eine von dieser Tour ausgehenden Suche zu sein. Diese und weitere Vermutungen konnten widerlegt werden. Auf der anderen Seite wurden aber auch vermutete Zusammenhänge nachgewiesen. Dies betrifft zum Beispiel die Güte der BackBone-Approximation oder die schlechten Ergebnisse für die Toleranz zum linearen Zuordnungsproblem für symmetrische Probleme. Asymmetrische Probleme wurden nicht untersucht. Neben diesen eher abstrakten Modifikationen im allgemeinen Verfahren wurden auch verschiedene Aspekte der bestehenden Implementation untersucht, erweitert und verbessert. Des Weiteren wurden wichtige neue theoretische Erkenntnisse aufgeführt und bewiesen. Dazu zählen insbesondere die Sätze 4, 6, 9 und 10. Um aussagekräftige Ergebnisse zu erhalten, wurde der Prozess zur Erfassung, Verarbeitung und Auswertung der Messergebnisse immer weiter automatisiert. Die dabei entstandenen Tools, Messergebnisse und Quellcodes sind auf einer beigelegten CD enthalten.