Die folgende Arbeit beschäftigt sich mit dem sogenannten "Traveling Salesman Problem". Es werden verschiedene Varianten des Themenkomplexes vorgestellt und mögliche Lösungsansätze ausgearbeitet.
Das Problem des Handlungsreisenden ist ein kombinatorisches Optimierungsproblem. Weiterhin wird es auch als „Rundreiseproblem“ oder im Englischen als „Traveling Salesman Problem (TSP)“ bezeichnet. Das TSP gliedert sich in die Tourenplanung ein. Diese zielt darauf ab Faktoren wie die Entfernung zweier Standorte, die gesamte Fahrzeit der Tour, die variablen Kosten und die eingesetzten Fahrzeuge zu minimieren. Es sollen also alle Kundennachfragen pünktlich und zu optimalen Kosten realisiert werden.
Das TSP ist ein Verfahren, um eine reale Problemstellung in einem Modell zu abstrahieren, in jenem zu lösen und die Lösung dann auf die reale Welt zu übertragen. Weiterhin zählt das TSP zu den harten Problemen, die auch als NP-vollständige Probleme bezeichnet werden. Eine wesentliche Eigenschaft der NP-vollständigen Probleme ist, dass sich nicht effizient, also in einem angemessenen Verhältnis von Aufwand und Zeit, lösen lassen. Die Aufgabe des TSP besteht darin, den kürzesten Weg zwischen den einzelnen Orten einer Tour für den Handlungsreisenden zu bestimmen. Besagte Orte werden als „Knoten“ und die Tour als „Rundreise“ bezeichnet. Ausgehend von einem beliebigen Ausgangspunkt (Depot) werden die einzelnen Kunden (Aufträge) besucht. Man sucht im TSP einen Kreis minimaler Länge (Rundreise), welcher jeden zu beliefernden Knoten nur genau einmal enthalten darf. Einzige Ausnahme sind Anfangs- und Endknoten, die identisch sein müssen. Somit muss der Handlungsreisende am Ende seiner Tour wieder zum Ausgangspunkt zurückkehren. Das TSP findet unter anderem Anwendung bei der Auslieferung von Waren, Planung von optimalen Touren und Fuhrparkkoordination.
Inhaltsverzeichnis
I. EINLEITUNG
II. VARIANTEN DES TRAVELING SALESMAN PROBLEMS
1. SYMMETRISCHES TRAVELING SALESMAN PROBLEM
2. ASYMMETRISCHES TRAVELING SALESMAN PROBLEM
3. METRISCHES TRAVELING SALESMAN PROBLEM (∆- TSP)
4. WESENTLICHE UNTERSCHIEDE ZWISCHEN SYMMETRISCHEM UND ASYMMETRISCHEM TSP
III. UNTERE SCHRANKEN
IV. OBERE SCHRANKEN: HEURISTIKEN
V. OPTIMALE LÖSUNGEN
1. BRANCH-AND-BOUND-VERFAHREN ALLGEMEIN
2. SELBSTGEWÄHLTES BEISPIEL ANHAND DES BRANCH-AND-BOUND-VERFAHRENS
VI. SELBSTGEWÄHLTES BEISPIEL ANHAND DES NÄCHSTER-NACHBAR-ALGORITHMUS
Zielsetzung & Themen
Die vorliegende Arbeit untersucht das „Problem des Handlungsreisenden“ (Traveling Salesman Problem, TSP) als kombinatorisches Optimierungsproblem. Ziel ist es, Methoden zur Tourenplanung vorzustellen, die darauf abzielen, Fahrtstrecken und Kosten bei der Kundenbetreuung unter Einhaltung spezifischer Bedingungen zu minimieren.
- Grundlegende Definition und Einordnung des Traveling Salesman Problems.
- Differenzierung zwischen symmetrischen, asymmetrischen und metrischen Problemvarianten.
- Analyse wissenschaftlicher Lösungsansätze mittels unterer und oberer Schranken sowie Heuristiken.
- Praktische Anwendung des Branch-and-Bound-Verfahrens und des Nächster-Nachbar-Algorithmus zur Routenoptimierung.
Auszug aus dem Buch
3. Metrisches Traveling Salesman Problem (∆ − TSP)
Damit ein Traveling Salesman Problem metrisch ist, müssen zunächst drei Bedingungen erfüllt sein:
Die erste Bedingung, die sogenannte positive Definitheit, besagt, dass jeder Knotenpunkten einen Abstand von 0 zu sich selber haben muss und andere Punkte einen echt positiven Abstand zueinander haben müssen. Mathematisch formuliert: c(i,j) ≥ 0 für alle i,j und c(i,j) = 0 ⇔ i = j
Die zweite Eigenschaft ist die bereits oben erläuterte Symmetrie, welche vorhanden sein muss. Die Entfernung von einem Punkt A nach B muss also der Entfernung von B nach A entsprechen. Mathematisch formuliert: c(i,j) = c(j,i) für alle i,j
Die dritte und letzte Bedingung verlangt, dass die sogenannte Dreiecksungleichung erfüllt wird. Konkret bedeutet das, dass der Weg von einem Punkt i nach j über einen dritten Punkt k, niemals schneller ist als der direkte Weg von i nach j. Einfacher ausgedrückt: Umwege lohnen sich niemals. Mathematisch formuliert: c(i,j) ≤ c(i,k) + c(k,j)
In der Praxis werden beispielsweise die Manhatten-Metrik oder die Maximums-Metrik beim Bohren von Leiterplatten angewendet.
Zusammenfassung der Kapitel
I. EINLEITUNG: Einführung in das kombinatorische Optimierungsproblem des Handlungsreisenden und Verdeutlichung der Relevanz anhand eines praktischen Beispiels.
II. VARIANTEN DES TRAVELING SALESMAN PROBLEMS: Erläuterung der verschiedenen Typen (symmetrisch, asymmetrisch, metrisch) inklusive ihrer mathematischen Eigenschaften und graphischen Darstellungen.
III. UNTERE SCHRANKEN: Vorstellung von Relaxationsmethoden wie MST- und 1-Baum-Relaxation zur Berechnung unterer Schranken bei der Tour-Optimierung.
IV. OBERE SCHRANKEN: HEURISTIKEN: Diskussion von Einfügungsalgorithmen und lokalen Suchverfahren, um effizient gute, wenn auch nicht immer optimale, Touren zu konstruieren.
V. OPTIMALE LÖSUNGEN: Detaillierte Darstellung des exakten Branch-and-Bound-Verfahrens zur Bestimmung optimaler Rundreisen an einem konkreten Beispiel.
VI. SELBSTGEWÄHLTES BEISPIEL ANHAND DES NÄCHSTER-NACHBAR-ALGORITHMUS: Anwendung und Vergleich des Nächster-Nachbar-Verfahrens mit den Ergebnissen der optimalen Lösungsmethode.
Schlüsselwörter
Traveling Salesman Problem, TSP, Tourenplanung, Kombinatorische Optimierung, Rundreiseproblem, Symmetrisches TSP, Asymmetrisches TSP, Metrisches TSP, Branch-and-Bound, Nächster-Nachbar-Algorithmus, Heuristiken, Untere Schranken, Hamiltonscher Kreis, Graphentheorie, Optimale Rundreise.
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit befasst sich mit der theoretischen und praktischen Auseinandersetzung des „Problems des Handlungsreisenden“, um Wege zu finden, die bei der Besuchsplanung von Kunden die zurückgelegte Distanz minimieren.
Was sind die zentralen Themenfelder?
Zentrale Felder sind die Klassifizierung der verschiedenen TSP-Varianten, die mathematische Herleitung von Schranken zur Lösungsfindung sowie die Anwendung sowohl exakter Algorithmen als auch heuristischer Näherungsverfahren.
Was ist das primäre Ziel der Arbeit?
Das primäre Ziel ist es, die Funktionsweise von Optimierungsalgorithmen zu erklären und durch ein Praxisbeispiel zu verdeutlichen, wie man für einen Vertriebsmitarbeiter die kostenoptimalste Route plant.
Welche wissenschaftliche Methode wird verwendet?
Die Arbeit stützt sich auf eine Literaturanalyse wissenschaftlicher Fachliteratur sowie auf die Anwendung mathematischer Optimierungsverfahren, namentlich des Branch-and-Bound-Verfahrens und des Nächster-Nachbar-Algorithmus.
Was wird im Hauptteil behandelt?
Der Hauptteil gliedert sich in die theoretische Unterscheidung von TSP-Typen, die Berechnung unterer und oberer Schranken, die Erläuterung exakter Lösungsverfahren und die praktische Durchführung der Tourenoptimierung.
Welche Schlüsselwörter charakterisieren die Arbeit?
Die Arbeit wird maßgeblich durch Begriffe wie Traveling Salesman Problem (TSP), Tourenplanung, Branch-and-Bound und Heuristiken charakterisiert.
Warum unterscheidet man zwischen symmetrischen und asymmetrischen TSP-Varianten?
Die Unterscheidung ist für die Modellierung entscheidend, da sie bestimmt, ob Wege in beide Richtungen die gleiche Länge haben (symmetrisch) oder ob Faktoren wie Einbahnstraßen und Strömungen unterschiedliche Distanzen/Zeiten verursachen (asymmetrisch).
Was ist die Kernbotschaft bezüglich des Branch-and-Bound-Verfahrens?
Es handelt sich um ein exaktes Verfahren, das für kleine Problemstellungen sehr zuverlässig ist, bei sehr großen Datenmengen jedoch aufgrund des enormen Rechenaufwandes oft durch schnellere, aber weniger präzise Heuristiken ersetzt wird.
- Arbeit zitieren
- Ricardo Escoda (Autor:in), Michael Schäfer (Autor:in), 2016, Das Problem des Handlungsreisenden. Lösungsansätze des Travelling-Salesman-Problem, München, GRIN Verlag, https://www.grin.com/document/367666
