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

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.0

Author: André Rohe

Publisher: Diplom.de

Publication Date: Mar 16, 1998

Number of Pages: 110 pages

Binding: Paperback or Softback

ISBN-10: 3838607392

ISBN-13: 9783838607399