Sie sind hier
E-Book

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

AutorAndré Rohe
Verlagdiplom.de
Erscheinungsjahr1998
Seitenanzahl104 Seiten
ISBN9783832407391
FormatPDF
Kopierschutzkein Kopierschutz
GerätePC/MAC/eReader/Tablet
Preis38,00 EUR
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 [...]

Kaufen Sie hier:

Horizontale Tabs

Blick ins Buch

Weitere E-Books zum Thema: Produktion - Industrie

Operations Research

E-Book Operations Research
Linearoptimierung Format: PDF

Linearoptimierung wird als mathematische Methode innerhalb des Operations Research bei der Mengenplanung für Absatz und Produktion sowie für Transport-, Netzfluss- oder Maschinenbelegungs-Probleme…

Operations Research

E-Book Operations Research
Linearoptimierung Format: PDF

Linearoptimierung wird als mathematische Methode innerhalb des Operations Research bei der Mengenplanung für Absatz und Produktion sowie für Transport-, Netzfluss- oder Maschinenbelegungs-Probleme…

Operations Research

E-Book Operations Research
Linearoptimierung Format: PDF

Linearoptimierung wird als mathematische Methode innerhalb des Operations Research bei der Mengenplanung für Absatz und Produktion sowie für Transport-, Netzfluss- oder Maschinenbelegungs-Probleme…

Warehouse Management

E-Book Warehouse Management
Organisation und Steuerung von Lager- und Kommissioniersystemen Format: PDF

Professor Dr. Michael ten Hompel ist Inhaber des Lehrstuhls für Förder- und Lagerwesen an der Universität Dortmund und Institutsleiter am Fraunhofer-Institut für Materialfluss und Logistik IML. Er…

Logistik

E-Book Logistik
Grundlagen - Strategien - Anwendungen Format: PDF

Zentrale Aufgabe der operativen Logistik ist das effiziente Bereitstellen der benötigten Mengen materieller Objekte zur rechten Zeit am richtigen Ort. Zu diesem Zweck muß die analytisch-planende…

Logistik

E-Book Logistik
Grundlagen - Strategien - Anwendungen Format: PDF

Zentrale Aufgabe der operativen Logistik ist das effiziente Bereitstellen der benötigten Mengen materieller Objekte zur rechten Zeit am richtigen Ort. Zu diesem Zweck muß die analytisch-planende…

Logistik

E-Book Logistik
Grundlagen - Strategien - Anwendungen Format: PDF

Zentrale Aufgabe der operativen Logistik ist das effiziente Bereitstellen der benötigten Mengen materieller Objekte zur rechten Zeit am richtigen Ort. Zu diesem Zweck muß die analytisch-planende…

Anwendung von RFID-Systemen

E-Book Anwendung von RFID-Systemen
Format: PDF

Die Radio-Frequenz-Identifikation (RFID) dient seit etwa 15 Jahren zur Identifikation von Personen, Objekten und Tieren. Mit der inzwischen gut entwickelten Technologie können heute…

Weitere Zeitschriften

FREIE WERKSTATT

FREIE WERKSTATT

Die Fachzeitschrift FREIE WERKSTATT berichtet seit der ersten Ausgaben 1994 über die Entwicklungen des Independent Aftermarkets (IAM). Hauptzielgruppe sind Inhaberinnen und Inhaber, Kfz-Meisterinnen ...

Gastronomie Report

Gastronomie Report

News & Infos für die Gastronomie: Tipps, Trends und Ideen, Produkte aus aller Welt, Innovative Konzepte, Küchentechnik der Zukunft, Service mit Zusatznutzen und vieles mehr. Frech, offensiv, ...

DHS

DHS

Die Flugzeuge der NVA Neben unser F-40 Reihe, soll mit der DHS die Geschichte der "anderen" deutschen Luftwaffe, den Luftstreitkräften der Nationalen Volksarmee (NVA-LSK) der ehemaligen DDR ...

DULV info

DULV info

UL-Technik, UL-Flugbetrieb, Luftrecht, Reiseberichte, Verbandsinte. Der Deutsche Ultraleichtflugverband e. V. - oder kurz DULV - wurde 1982 von ein paar Enthusiasten gegründet. Wegen der hohen ...

elektrobörse handel

elektrobörse handel

elektrobörse handel gibt einen facettenreichen Überblick über den Elektrogerätemarkt: Produktneuheiten und -trends, Branchennachrichten, Interviews, Messeberichte uvm.. In den monatlichen ...