18,99 €
Mehr erfahren.
- Herausgeber: GRIN Verlag
- Sprache: Deutsch
Bachelorarbeit aus dem Jahr 2013 im Fachbereich Informatik - Wirtschaftsinformatik, Note: 1.3, Leuphana Universität Lüneburg, Veranstaltung: Bachelorarbeit, Sprache: Deutsch, Abstract: Ein Handlungsreisender soll eine gewisse Anzahl von Kunden in verschiedenen Städten besuchen, in jeder Stadt einen Kunden, und anschließend zum Ausgangspunkt zurückkehren. Doch wie ist diese Reise zu wählen, sodass der Handlungsreisende den möglichst kürzesten Gesamtweg beschreitet? Diese Fragestellung wird als das Problem des Handlungsreisenden bzw. das Traveling Salesman Problem (kurz TSP) bezeichnet. Diese etwas einfache Beschreibung trifft die Gesamtheit des Problems aber bei weiten nicht. Bei dem Problem des Handlungsreisenden handelt es sich um ein Minimierungsproblem aus dem Bereich der theoretischen Informatik. Genauer gesagt gehört es zu einer sehr wichtigen Klasse der theoretischen Informatik; den sogenannten NP-vollständigen Problemen, für die keine effizienten und exakten Lösungsverfahren existieren bzw. existieren können (unter der Annahme das P≠NP gilt). Intuitiv kann ein Mensch mit Blick auf eine Karte und einer geringen Anzahl an Städten, die es für eine Rundreise zusammenzuführen gilt, eine gute, gar optimale, Lösung sehen. Dieses gilt aber nicht für Maschinen und Softwareprogramme, denn diese können die Gesamtheit nicht wie ein Mensch begreifen. Somit müssen andere, konkretere, Lösungen genutzt werden. Ziel dieser Arbeit ist es, einen Überblick über die Geschichte, Definition und Arten des Problems des Handlungsreisenden zu geben. Die Einordnung in der theoretischen Informatik zu klassifizieren und zu beschreiben sowie eine ausführliche Übersicht und Beschreibung von bekannten exakten und annähernden Lösungsverfahren zu geben. Ziel soll ein Kompendium für das Problem des Handlungsreisenden sein. Für diese Arbeit wird vorausgesetzt, dass der Leser grundlegende Kenntnisse der Mathematik, Graphentheorie und theoretischen Informatik besitzt.
Das E-Book können Sie in Legimi-Apps oder einer beliebigen App lesen, die das folgende Format unterstützen:
Veröffentlichungsjahr: 2013
Ähnliche
Impressum:
Copyright (c) 2013 GRIN Verlag GmbH, alle Inhalte urheberrechtlich geschützt. Kopieren und verbreiten nur mit Genehmigung des Verlags.
Bei GRIN macht sich Ihr Wissen bezahlt! Wir veröffentlichen kostenlos Ihre Haus-, Bachelor- und Masterarbeiten.
Jetzt beiwww.grin.com
Inhaltsverzeichnis
1. Einleitung und Motivation dieser Arbeit
2. Definitionen, Konventionen, Begriffe und Problemstellung des TSP
2.1. Aktuelle Ergebnisse und Rekorde - Die Geschichte des TSP
2.2. Einordnung des TSP
2.2.1. Komplexitätstheorie
2.2.2. Entscheidungs- und Optimierungsproblem
2.2.3. TSP in NP und NP-schwere des Problems
2.3. Asymmetrisches, symmetrisches und metrisches TSP
2.4. Hamiltonischer Kreis (Hamiltonkreis) und Euler Weg
2.5. Multiple-TSP (mTSP) und Vehicle Routing Problem (VRP)
3. TSP exakt lösen
3.1. Brute Force
3.2. Dynamische Programmierung
3.3. Branch and Bound
4. Approximierbarkeit des TSP
4.1. Nearest Neighbor und Greedy
4.2. Insertion Heuristiken
4.3. Minimum Spanning Tree (MST)
4.4. Christofides
4.5. K-Opt Verbesserungsverfahren
4.6. Lin-Kernighan (LK) und Lin-Kernighan-Helsgaun (LKH)
5. Fazit und Ausblick
6. Literaturverzeichnis
7. Abbildungsverzeichnis
1. Einleitung und Motivation dieser Arbeit
Ein Handlungsreisender soll eine gewisse Anzahl von Kunden in verschiedenen Städten besuchen, in jeder Stadt einen Kunden, und anschließend zum Ausgangspunkt zurückkehren. Doch wie ist diese Reise zu wählen, sodass der Handlungsreisende den möglichst kürzesten Gesamtweg beschreitet? Diese Fragestellung wird als das Problem des Handlungsreisenden bzw. das Traveling Salesman Problem (kurz TSP) bezeichnet.
Diese etwas einfache Beschreibung trifft die Gesamtheit des Problems aber bei weiten nicht. Bei dem Problem des Handlungsreisenden handelt es sich um ein Minimierungsproblem aus dem Bereich der theoretischen Informatik. Genauer gesagt gehört es zu einer sehr wichtigen Klasse der theoretischen Informatik; den sogenannten NP-vollständigen Problemen, für die keine effizienten und exakten Lösungsverfahren existieren bzw. existieren können (unter der Annahme das gilt).
Intuitiv kann ein Mensch mit Blick auf eine Karte und einer geringen Anzahl an Städten, die es für eine Rundreise zusammenzuführen gilt, eine gute, gar optimale, Lösung sehen. Dieses gilt aber nicht für Maschinen und Softwareprogramme, denn diese können die Gesamtheit nicht wie ein Mensch begreifen. Somit müssen andere, konkretere, Lösungen genutzt werden.
Ziel dieser Arbeit ist es, einen Überblick über die Geschichte, Definition und Arten des Problems des Handlungsreisenden zu geben. Die Einordnung in der theoretischen Informatik zu klassifizieren und zu beschreiben sowie eine ausführliche Übersicht und Beschreibung von bekannten exakten und annähernden Lösungsverfahren zu geben. Ziel soll ein Kompendium für das Problem des Handlungsreisenden sein.
2. Definitionen, Konventionen, Begriffe und Problemstellung des TSP
Als erster Schritt soll das Problem des Handlungsreisenden allgemein und mathematisch beschrieben werden. Des Weiteren bietet dieses umfangreiche Problem eine Vielzahl an Begrifflichkeiten, die miteinander verknüpft werden sollen.
Bei dem Traveling Salesman Problem handelt es sich um ein Rundreiseproblem. Es wird nach einer Rundreise (auch Tour genannt) für eine unbestimmte endliche Anzahl an Städten gesucht. Diese Anzahl wird mit bezeichnet. Bei dieser Rundreise handelt es sich um eine Reise von einem Ort über mehrere andere Orte zurück zum Ausgangsort, wobei jede Stadt nur einmal besucht wird. Gesucht wird dabei nach der kleinsten bzw. kürzesten Rundreise. Diese wird optimale Rundreise oder optimale Tour genannt. Eine Rundreise heißt dann optimal, wenn es keine weitere Tour gibt, die eine kleinere Kantensumme besitzt. Ein Optimum und die Abweichung zu dem Optimum können mithilfe einer unteren Schranke bestimmt werden. Diese untere Schranke gibt den Wert einer optimalen Lösung an, welcher z.B. durch das reine Addieren aller kürzesten Strecken erzeugt werden kann. Hat ein vorliegendes TSP z.B. die untere Schranke von insgesamt 100 Einheiten und eine gefundene Lösung erbringt 110 Einheiten, dann liegt diese Lösung 10% vom Optimum entfernt. Die obere Schranke hingegen kann auch als Worst-Case-Wert betrachtet werden, denn dieser gibt, z.B. für Näherungslösungen an, welcher Wert durch ein entsprechendes Verfahren schlechtesten falls ausgegeben werden kann. Diese Problemstellung ist nicht nur auf Städte und deren Entfernung begrenzt, sondern überträgt sich auch auf viele andere Bereiche. In der Praxis findet das Problem des Handlungsreisenden z.B. Relevanz bei Postdienstleistern, Kunden- und Pannendiensten oder der Software für Navigationshilfen. Mit Städten und Entfernungen können aber auch, z.B. in der Fertigungsindustrie von Mikrochips bzw. Platinen, Löcher und Verbindungen gemeint sein und je nach Anwendungsbereich können damit Entfernungen u.a. im Kontext von Preis- oder Zeitspanne definiert werden.
