Parallele Heuristiken fur sehr grosse Travelling Salesman Probleme

Diplomarbeit aus dem Jahr 1997 im Fachbereich BWL - Beschaffung, Produktion, Logistik, Note: 1,0, Rheinische Friedrich-Wilhelms-Universitt Bonn (Unbekannt), Sprache: Deutsch, Abstract: Inhaltsangabe:Einleitung:
Das Traveling Salesman Problem (TSP) besteht darin, fr eine gegebenen Mengen von Orten eine mglichst kurze Rundreise zu finden (ausgehend von einem Ort mssen alle anderen Orte angefahren werden, dann wird zum "Heimatort" zurckgekehrt).
Das TSP ist eines der bekanntesten kombinatorischen Optimierungsprobleme, es ist sowohl von theoretischer als auch von praktische Bedeutung. Anwendungen fr das TSP sind z.B. die Herstellung von Leiterplatten oder das Vehicle Routing Problem. Oft knnen auch Methoden, die zuerst fr das TSP entworfen wurden, spter fr andere Problemklassen mit Erfolg eingesetzt werden.
Da das TSP zu der Klasse der besonders schweren (NP schweren) Optimierungsprobleme gehrt, ist es oft nicht mglich, die bewiesenermaen beste Lsung zu finden, es wird daher fr die praktische Lsung nach leistungsfhigen Heuristiken gesucht.
Gang der Untersuchung:
In der vorliegenden Arbeit wurde unter Anleitung von Professor Korte von der Universitt Bonn und Professoren von AT&T und den Bell Laboratories eine Parallelisierung der besten bekannten Heuristik (der sogenannten iterated Lin-Kernighan Heuristik) fr das TSP vorgenommen.
Oft werden in der Literatur und auch in der Presse die in letzter Zeit modern gewordenen "Metaheuristiken" Simulated Annealing (SA), Genetic Algorithms (GA) oder auch Tabu Search erwhnt. All diese Anstze knnen jedoch kaum mit speziell fr das TSP entwickelten Anstzen konkurrieren, wie auch die Ergebnisse der Diplomarbeit zeigen. Mit dem Algorithmus knnen in kurzer Zeit fr Probleme mit 10.000 und weniger Punkten Touren der Gte 0.2 % und besser berechnet werden (d.h. die gefundene Tour ist maximal um den Faktor 1.002 lnger als die bestmgliche Tour). Doch auch fr sehr groe Probleminstanzen eignet sich der beschriebene