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

FESTIVAL Christmas

Fachzeitschriften für Weihnachtsartikel, Geschenke, Floristik, Papeterie und vieles mehr! FESTIVAL Christmas: Die erste und einzige internationale Weihnachts-Fachzeitschrift seit 1994 auf dem ...

Altenheim - Lösungen fürs Management

Altenheim ist die Fachzeitschrift für Träger, Heimleitungen und leitende Mitarbeiter/innen der teilstationären und stationären Altenhilfe. Hier erfahren Sie, wie Sie Ihre Einrichtung zu ...

Argumente + Fakten der Medizin

Medizin und Gesundheit Aktuell zu Konzepten, Forschung, Therapie, Diagnostik und Klinik Seit April 1991 erscheint regelmäßig eine monatliche Fachzeitschrift für den jungen niedergelassenen ...

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

Blätter für deutsche Landesgeschichte

Einzelbeiträge und Sammelrezensionen zur vergleichenden Landesgeschichte. Im Gesamtverein der deutschen Geschichts- und Altertumsvereine haben sich die deutschen Geschichtsvereine, die Historischen ...

BONSAI ART

Auflagenstärkste deutschsprachige Bonsai-Zeitschrift, basierend auf den renommiertesten Bonsai-Zeitschriften Japans mit vielen Beiträgen europäischer Gestalter. Wertvolle Informationen für ...

care konkret

care konkret ist die Wochenzeitung für Entscheider in der Pflege. Ambulant wie stationär. Sie fasst topaktuelle Informationen und Hintergründe aus der Pflegebranche kompakt und kompetent für Sie ...

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

Die Steuerfachangestellten

Prüfungs- und Praxiswissen für Steuerfachangestellte Mehr Erfolg in der Ausbildung, sicher in alle Prüfungen gehen, im Beruf jeden Tag überzeugen: „Die Steuerfachangestellten“ ist die ...

Extracts from European Patent Specifications (3 parts)

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