Lade Inhalt...

Parallele Heuristiken für sehr große Travelling Salesman Probleme

©1997 Diplomarbeit 104 Seiten

Zusammenfassung

Inhaltsangabe:Einleitung:
Das Traveling Salesman Problem (TSP) besteht darin, für eine gegebenen Mengen von Orten eine möglichst kurze Rundreise zu finden (ausgehend von einem Ort müssen alle anderen Orte angefahren werden, dann wird zum "Heimatort" zurückgekehrt).
Das TSP ist eines der bekanntesten kombinatorischen Optimierungsprobleme, es ist sowohl von theoretischer als auch von praktische Bedeutung. Anwendungen für das TSP sind z.B. die Herstellung von Leiterplatten oder das Vehicle Routing Problem. Oft können auch Methoden, die zuerst für das TSP entworfen wurden, später für andere Problemklassen mit Erfolg eingesetzt werden.
Da das TSP zu der Klasse der besonders schweren (NP schweren) Optimierungsprobleme gehört, ist es oft nicht möglich, die bewiesenermaßen beste Lösung zu finden, es wird daher für die praktische Lösung nach leistungsfähigen Heuristiken gesucht.
Gang der Untersuchung:
In der vorliegenden Arbeit wurde unter Anleitung von Professor Korte von der Universität Bonn und Professoren von AT&T und den Bell Laboratories eine Parallelisierung der besten bekannten Heuristik (der sogenannten iterated Lin-Kernighan Heuristik) für 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 erwähnt. All diese Ansätze können jedoch kaum mit speziell für das TSP entwickelten Ansätzen konkurrieren, wie auch die Ergebnisse der Diplomarbeit zeigen. Mit dem Algorithmus können in kurzer Zeit für Probleme mit 10.000 und weniger Punkten Touren der Güte 0.2 % und besser berechnet werden (d.h. die gefundene Tour ist maximal um den Faktor 1.002 länger als die bestmögliche Tour). Doch auch für sehr große Probleminstanzen eignet sich der beschriebene Algorithmus: Es wurde ein TSP mit 18.837.227 Punkten behandelt und eine Tour mit einer Gütegarantie von 0,91 % gefunden. In der Literatur wurden bisher nur Probleme mit maximal 1.000.000 Orten vorgestellt.

Inhaltsverzeichnis:Inhaltsverzeichnis:
1.Einleitung3
2.Der Lin-Kernighan-Algorithmus11
2.1Konstruktionsheuristiken11
2.22-OPT und 3-OPT13
2.3Der Lin-Kernighan-Algorithmus14
2.4Iterierter Lin-Kernighan20
2.5Laufzeitverhalten und Güte23
3.Lin-Kernighan für das Matching Problem33
3.1Einführung34
3.2Beschreibung des Algorithmus35
3.3Laufzeitverhalten und Güte39
4.Parallele Ansätze51
4.1Allgemeine Einführung51
4.2Bisherige Arbeiten zum […]

Leseprobe

Inhaltsverzeichnis


Details

Seiten
Erscheinungsform
Originalausgabe
Jahr
1997
ISBN (eBook)
9783832407391
ISBN (Paperback)
9783838607399
DOI
10.3239/9783832407391
Dateigröße
3.5 MB
Sprache
Deutsch
Institution / Hochschule
Rheinische Friedrich-Wilhelms-Universität Bonn – Unbekannt
Erscheinungsdatum
1998 (März)
Note
1,0
Schlagworte
optimierung rundreiseproblem traveling sales problem vehicle routing
Zurück

Titel: Parallele Heuristiken für sehr große Travelling Salesman Probleme
book preview page numper 1
book preview page numper 2
book preview page numper 3
book preview page numper 4
book preview page numper 5
book preview page numper 6
book preview page numper 7
book preview page numper 8
book preview page numper 9
book preview page numper 10
book preview page numper 11
book preview page numper 12
book preview page numper 13
book preview page numper 14
book preview page numper 15
book preview page numper 16
book preview page numper 17
book preview page numper 18
book preview page numper 19
book preview page numper 20
book preview page numper 21
book preview page numper 22
104 Seiten
Cookie-Einstellungen