Sie sind hier

E-Book

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

Autor	André Rohe
Verlag	diplom.de
Erscheinungsjahr	1998
Seitenanzahl	104 Seiten
ISBN	9783832407391
Format	PDF
Kopierschutz	kein Kopierschutz
Geräte	PC/MAC/eReader/Tablet
Preis	38,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

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

Linearoptimierung Format: PDF

Operations Research

Linearoptimierung Format: PDF

Change Management - Prozesse strategiekonform gestalten

Prozesse strategiekonform gestalten Format: PDF

Im Wettbewerb müssen Unternehmen ihre Organisation und Prozesse kontinuierlich verändern. Die Führung produzierender Unternehmen kann die Dynamik der Unternehmensorganisation gezielt beeinflussen, um…

Change Management - Prozesse strategiekonform gestalten

Prozesse strategiekonform gestalten Format: PDF

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

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

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

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

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

Atalanta

Atalanta ist die Zeitschrift der Deutschen Forschungszentrale für Schmetterlingswanderung. Im Atalanta-Magazin werden Themen behandelt wie Wanderfalterforschung, Systematik, Taxonomie und Ökologie. ...

Auszüge aus den Patentschriften (2 Ausgaben)

Vom Deutschen Patent- und Markenamt erteilte Patente. Bibliographie, Patentanspruch, wichtigste Zeichnung. Thomson Reuters is the world’s leading source of intelligent information for businesses ...

Berufsstart Bewerbung

»Berufsstart Bewerbung« erscheint jährlich zum Wintersemester im November mit einer Auflage von 50.000 Exemplaren und ermöglicht Unternehmen sich bei Studenten und Absolventen mit einer ...

Burgen und Schlösser

aktuelle Berichte zum Thema Burgen, Schlösser, Wehrbauten, Forschungsergebnisse zur Bau- und Kunstgeschichte, Denkmalpflege und Denkmalschutz Seit ihrer Gründung 1899 gibt die Deutsche ...

Card-Forum

Card-Forum ist das marktführende Magazin im Themenbereich der kartengestützten Systeme für Zahlung und Identifikation, Telekommunikation und Kundenbindung sowie der damit verwandten und ...

CE-Markt

CE-Markt ist Pflichtlektüre in der Unterhaltungselektronik-Branche. Die Vermarktung von Home und Mobile Electronics mit den besten Verkaufsargumenten und Verkaufsstrategien gehören ebenso zum ...

küche + raum

Internationale Fachzeitschrift für Küchenforschung und Küchenplanung. Mit Fachinformationen für Küchenfachhändler, -spezialisten und -planer in Küchenstudios, Möbelfachgeschäften und den ...

Das Hauseigentum

Das Hauseigentum. Organ des Landesverbandes Haus & Grund Brandenburg. Speziell für die neuen Bundesländer, mit regionalem Schwerpunkt Brandenburg. Systematische Grundlagenvermittlung, viele ...

SPORT in BW (Württemberg)

SPORT in BW (Württemberg) ist das offizielle Verbandsorgan des Württembergischen Landessportbund e.V. (WLSB) und Informationsmagazin für alle im Sport organisierten Mitglieder in Württemberg. ...

EineWelt

Lebendige Reportagen, spannende Interviews, interessante Meldungen, informative Hintergrundberichte. Lesen Sie in der Zeitschrift „EineWelt“, was Menschen in Mission und Kirche bewegt Man kann ...