Die Problematik der Tourenplanung ist in Grundzügen seit langem bekannt und gewinnt in der heutigen Zeit immer mehr an Bedeutung. Eine effiziente Tourenplanung kann zur Verringerung der Distributionskosten führen. Dasselbe Optimierungsproblem tritt bei der Rundreise auf.
Vor diesem Hintergrund befasst sich die vorliegende Seminararbeit mit den Problemen der Rundreise und Tourenplanung. Ziel ist es die Grundlagen der Graphentheorie und ausgewählte Praxisthemen zu vermitteln und mit dieser Art Mathematik die wirtschaftlich relevanten Probleme zu lösen.
Kapitel zwei behandelt die Grundlagen der Tourenplanung.
Darüber hinaus werden die Begriffe ”Problem des Handlungsreisenden¨und das ”Briefträgerproblem¨ erklärt sowie eine Reihe weiterer spezieller Briefträgerprobleme aufgezeigt. Insbesonders setzt sich die Arbeit näher mit dem Briefträgerproblem in gerichteten Graphen auseinander und wird ein zugrundeliegendes mathematisches Model und
das Lösungsverfahren vorstellen. Abschliessend werden die wesentlichen Erkenntnisse und der Inhalt der Arbeit zusammengefasst.
Inhaltsverzeichnis
1 Einleitung
2 Tourenplanungsprobleme
2.1 Einordnung der Tourenplanung in die Logistik
2.2 Problem der Tourenplannung
2.3 Lösung des Tourenplanungsproblem
2.3.1 Grundlegende Begriffe
2.3.2 Sweep-Algorithmus zur Lösung des Tourenplanungsproblem
3 Traveling-Salesman-Problem
3.1 Grundlagen und Problem des Traveling-Salesman
3.2 Lösungsverfahren
4 Briefträgerproblem
4.1 Grundlagen und Problem des Briefträgerproblems
4.2 Weitere Briefträgerprobleme
4.3 Euler-Kreise und Euler-Wege
5 Briefträgerproblem in gerichteten Graphen
5.1 Kostenminimale Erweiterung eines gerichteten Graphen
5.2 Formale Problembeschreibung
6 Zusammenfassung und Ausblick in die Zukunft
Zielsetzung & Themen
Die Arbeit analysiert grundlegende mathematische Optimierungsansätze in der Logistik, insbesondere im Bereich der Rundreise- und Tourenplanung, mit dem Ziel, wirtschaftlich relevante Transportprobleme durch graphentheoretische Modelle und Lösungsalgorithmen effizienter zu gestalten.
- Grundlagen der Graphentheorie und deren Anwendung in der Logistik
- Analyse des klassischen Tourenplanungsproblems und des Sweep-Algorithmus
- Untersuchung des Traveling-Salesman-Problems und seiner Lösungsverfahren
- Detaillierte Betrachtung des Briefträgerproblems in gerichteten Graphen
- Bewertung der mathematischen Modellierung zur Kostenminimierung
Auszug aus dem Buch
2.3.2 Sweep-Algorithmus zur Lösung des Tourenplanungsproblem
Es findet eine Unterscheidung bei den Lösungsvorverfahren für das Tourenplanungsproblem statt. Heuristische Lösungsverfahren bestimmen für ein gegebenes Problem in begrenzter Zeit eine zulässige Lösung. Exakte Verfahren hingegen lösen eine gegebene Problemstellung optimal. Heuristische Lösungen versprechen jedoch nicht das Auffinden von Optimallösungen und verfehlen bei zunehmender Problemstellung die Optimallösung. Dafür benötigen sie einen geringern Rechenaufwand als exakte Verfahren. Exakte Lösungsverfahren haben aufgrund des hohen Rechenaufwandes Probleme mit beschränkter Größe in kurzer Zeit. In der Praxis werden aus diesen Gründen kaum exakte Verfahren verwendet.
Das wohl bekannteste Verfahren ist der Sweep-Algorithmus, der zu den heuristischen Lösungsverfahren gehört und bereits 1974 von Gillet und Miller entwickelt wurde. Der Algorithmus ist stark an der geographischen Anordnung der Kunden orientiert. Von einem Koodinatensystem ausgehend, stimmt der Standort des Depot mit dem Ursprung überein. Es erfolgt die Sortierung der Kunden nach aufsteigendem Polarwinkel, zu dessen Bestimmung die Standortkoordinaten der Kunden verwendet werden. Im ersten Schritt findet die Zusammenfassung der Kunden zu Clustern statt, dies findet anhand der Reihenfolge der sortierten Liste statt. Ein Cluster ist abgeschlossen, wenn durch die Kapazitätsrestriktion oder Zeitrestriktion keine Aufnahme eines weiteren Kunden möglich ist.
Zusammenfassung der Kapitel
1 Einleitung: Diese Einleitung führt in die Bedeutung effizienter Tourenplanung für die Logistik ein und umreißt die Zielsetzung der Seminararbeit, graphentheoretische Ansätze zur Lösung von Rundreiseproblemen zu untersuchen.
2 Tourenplanungsprobleme: Dieses Kapitel ordnet Tourenplanung in die Logistik ein, erläutert die Grundproblematik der Routenoptimierung und stellt den Sweep-Algorithmus als heuristisches Lösungsverfahren vor.
3 Traveling-Salesman-Problem: Hier werden die theoretischen Grundlagen des Traveling-Salesman-Problems (symmetrisch vs. asymmetrisch) sowie praxisorientierte Lösungsverfahren wie das Verfahren des besten Nachfolgers behandelt.
4 Briefträgerproblem: Dieses Kapitel widmet sich dem Chinese Postman Problem, diskutiert verschiedene Varianten wie das Rural oder Windy Postman Problem und erläutert die Bedeutung von Euler-Kreisen.
5 Briefträgerproblem in gerichteten Graphen: Der Fokus liegt hier auf der kostenminimalen Erweiterung gerichteter Graphen zu Euler-Graphen sowie der formalen mathematischen Modellierung mittels Transportproblem.
6 Zusammenfassung und Ausblick in die Zukunft: Das letzte Kapitel resümiert die behandelten graphentheoretischen Konzepte und betont die steigende Relevanz dynamischer Tourenplanung im Kontext wachsenden Wettbewerbsdrucks.
Schlüsselwörter
Tourenplanung, Logistik, Graphentheorie, Traveling-Salesman-Problem, Briefträgerproblem, Sweep-Algorithmus, Optimierung, Euler-Tour, Kostenminimierung, Operations Research, Routenplanung, Rundreise, Distanzminimierung, Transportproblem, Dynamische Tourenplanung
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit befasst sich mit der mathematischen Optimierung von Transport- und Tourenplanungsproblemen in der Logistik mittels graphentheoretischer Methoden.
Was sind die zentralen Themenfelder der Publikation?
Die zentralen Themen sind das Tourenplanungsproblem allgemein, das Traveling-Salesman-Problem und speziell das Briefträgerproblem in unterschiedlichen Graphentypen.
Was ist das primäre Ziel der Forschungsarbeit?
Das Ziel ist die Vermittlung graphentheoretischer Grundlagen, um wirtschaftlich relevante Probleme, wie die Minimierung von Transportwegen und Kosten, mathematisch modellieren und lösen zu können.
Welche wissenschaftlichen Methoden werden verwendet?
Es werden heuristische Lösungsverfahren (wie der Sweep-Algorithmus) sowie exakte mathematische Modellierungen (Transportproblem, Branch-and-Bound-Ansätze) zur Lösung von Optimierungsproblemen eingesetzt.
Was wird im Hauptteil der Arbeit behandelt?
Der Hauptteil gliedert sich in die theoretische Einführung in die Tourenplanung, die Analyse spezieller Probleme wie dem Traveling-Salesman- und dem Briefträgerproblem sowie die mathematische Modellierung für gerichtete Graphen.
Welche Schlüsselwörter charakterisieren die Arbeit?
Wichtige Schlüsselwörter sind Tourenplanung, Graphentheorie, Optimierung, Logistik, Traveling-Salesman-Problem und Briefträgerproblem.
Wie unterscheidet sich das Briefträgerproblem vom Traveling-Salesman-Problem?
Während beim Traveling-Salesman-Problem jeder Knoten (Ort) genau einmal besucht werden muss, besteht das Briefträgerproblem darin, jede Kante (Straße) mindestens einmal zu durchlaufen.
Was leistet die kostenminimale Erweiterung in Kapitel 5?
Sie transformiert einen gerichteten Graphen, der keine Euler-Tour besitzt, in einen Euler-Graphen, indem unproduktive Wege durch das Lösen eines Transportproblems minimal ergänzt werden.
- Citar trabajo
- Felix Ritter (Autor), 2015, Logistische Tourenplanung. Lösungsansätzte für effiziente Rundreisen mithilfe von gerichteten Graphen, Múnich, GRIN Verlag, https://www.grin.com/document/306974
