In den verschiedensten Branchen, Bereichen und Unternehmen besteht eine fortwährende Notwendigkeit, eine bestimmte oder auch unbestimmte Anzahl an Kundenterminen wahrnehmen zu müssen. Hierbei stellt sich stets die zentrale Frage nach einer möglichst kostengünstigen Rundreise, bei welcher alle wahrzunehmenden Kundentermine mit einzubeziehen sind.
Ferner lässt sich der Kern dieser Frage auf beliebig viele weitere Bereiche ausweiten, welche mit der eigentlichen Fragestellung nach einer Optimierung von Kundenbesuchen augenscheinlich nichts zu tun haben. So ist zum Beispiel die Planung von Leiterplatten ebenso mit dem Streben nach einer möglichst kostenoptimierten Rundreise verbunden, wie die Planung von Rohrsystemen oder Lochbohrungen in verschiedensten Bauteilen. Jedoch ebenso groß wie die Anzahl an möglichen Anwendungsgebieten für die gesuchten Optimierungsalgorithmen, ist auch die Menge der möglichen Nebenbedingungen, welche an eine solche Aufgabe gestellt werden können und diese erheblich verkomplizieren.
Seit der ersten bekannten Nennung dieses Problems wurden zahlreiche Verfahrensmodelle und Algorithmen von exakten und approximativen Lösungen verschiedenster Varianten des Problems vorgestellt. Besonders durch den Einsatz von immer leistungsfähigeren Computern ist es möglich, immer schneller größere Optimierungsprobleme bearbeiten zu können. Doch auch unter Verwendung der neuesten Computertechnologie ist eine exakte Lösung von größeren Optimierungsproblemen in polynomieller Zeit nicht leistbar.
Inhaltsverzeichnis
1 Einleitung
1.1 Allgemein
1.2 Motivation
1.3 Ziele und Abgrenzung
2 Aufbau und Struktur der Arbeit
3 Grundlagen
3.1 Das Handlungsreisenden-Problem
3.2 Das Vehicle-Routing-Problem
3.3 Lösungsverfahren
3.3.1 Exakte Lösungsverfahren
3.3.2 Approximative Lösungsverfahren
3.4 Symmetrisches und asymmetrisches Handlungsreisenden-Problem
3.5 Modellierung der realen Situation als Graph
3.5.1 Gerichtete und ungerichtete Graphen
3.5.2 Vollständiger Graph
3.5.3 Hamiltonischer Kreis
3.5.4 Euler- Tour
3.5.5 Kostenberechnung
3.5.6 Bewertung der Kanten eines Graphen
3.5.7 Kantenfolgen innerhalb eines Graphen
3.5.8 Kürzeste Wege in bewerteten Graphen
3.6 Bäume
3.7 Übertragung von Graphen in verarbeitbare Strukturen
3.7.1 Darstellung als Adjazenzmatrix
3.7.2 Darstellung als Kostenmatrix
4 Tourenplanung
4.1 Bildung von Kundenclustern
4.1.1 Eröffungsverfahren
4.1.2 Verbesserungsverfahren
4.2 Phasen einer Tourenplanung
4.3 Tourenplanung unter Verwendung von Kundenclustern
4.3.1 Erstellung eines minimal spannenden Baumes
4.3.2 Greedy-Verfahren
4.3.3 Verfahren nach Kruskal
4.3.4 Verfahren nach Prim
4.3.5 Bildung geeigneter Kundencluster
5 Algorithmen zur Bearbeitung von Handlungsreisenden- und Vehicle-Routing-Problemen
5.1 Nachbar-Verfahren
5.1.1 Nächster-Nachbar-Verfahren
5.1.2 Doppelter-Nächster-Nachbar-Verfahren
5.2 Einfüge-Verfahren
5.2.1 Cheapest-Insertion-Verfahren
5.2.2 Farthest-Insertion-Verfahren
5.3 Opt-Verfahren
5.3.1 2-Opt-Verfahren
5.3.2 3-Opt-Verfahren
5.3.3 k-Opt-Verfahren
6 Praktische Anwendungsbereiche
6.1 Lieferndes Unternehmen
6.1.1 Aufgaben eines liefernden Unternehmens
6.1.2 Erarbeitung einer Kriterienliste für liefernde Unternehmen
6.2 Entsorgungsunternehmen
6.2.1 Aufgaben eines Entsorgungsunternehmens
6.2.2 Erarbeitung einer Kriterienliste für Entsorgungsunternehmen
6.3 Energieversorgungsunternehmen
6.3.1 Aufgaben eines Energieversorgungsunternehmens
6.3.2 Erarbeitung einer Kriterienliste für Energieversorgungsunternehmen
6.4 Kriterienmatrix
7 Lösungsmöglichkeiten für Handlungsreisenden- und Vehicle-Routing-Probleme
7.1 Lösungsmöglichkeiten für liefernde Unternehmen
7.1.1 Benchmarking der Optimierungsalgorithmen für liefernde Unternehmen
7.1.2 Auswertung
7.2 Lösungsmöglichkeiten für Entsorgungsunternehmen
7.2.1 Benchmarking der Optimierungsalgorithmen für Entsorgungsunternehmen
7.2.2 Auswertung
7.3 Lösungsmöglichkeiten für Energieversorgungsunternehmen
7.3.1 Benchmarking der Optimierungsalgorithmen für Energieversorgungsunternehmen
7.3.2 Auswertung
7.4 Nutzwertanalysen
7.4.1 Liefernde Unternehmen
7.4.2 Entsorgungsunternehmen
7.4.3 Energieversorgungsunternehmen
8 Zusammenfassung
8.1 Fazit
8.2 Ausblick
Zielsetzung & Themen
Diese Arbeit untersucht verschiedene Lösungsansätze für das Handlungsreisenden-Problem (TSP) und das Vehicle-Routing-Problem (VRP) unter Berücksichtigung branchenspezifischer Nebenbedingungen. Das primäre Ziel ist es, ein systematisches Vorgehen zur Auswahl geeigneter Optimierungsalgorithmen für unterschiedliche Anwendungsfälle zu entwickeln, wobei die Eignung der Algorithmen anhand von Funktions- und Leistungstests sowie Nutzwertanalysen bewertet wird.
- Mathematische Modellierung von Logistikproblemen mittels Graphentheorie
- Vergleich exakter und approximativer Lösungsverfahren (u.a. Greedy, Einfüge- und Opt-Verfahren)
- Analyse branchenspezifischer Anforderungen in der Lieferlogistik, Entsorgung und Energieversorgung
- Benchmarking von Algorithmen hinsichtlich Laufzeit und Lösungsqualität
- Bewertung von Optimierungsergebnissen mittels Nutzwertanalyse
Auszug aus dem Buch
3.1 Das Handlungsreisenden-Problem
Das Handlungsreisenden-Problem, auch bekannt als das „Travelling Salesman Problem (TSP)“, ist eines der am weitesten verbreiteten und meist untersuchten kombinatorischen Optimierungsprobleme aus dem Bereich des Operations Research. Das Operations Research befasst sich im Allgemeinen mit der Entwicklung und dem Einsatz quantitativer Modelle und verschiedenen Methoden zur Entscheidungsunterstützung, das besonders bei komplexen betriebswirtschaftlichen Fragen zum Tragen kommt. Es ist geprägt durch eine enge Zusammenarbeit von Informatik, Mathematik und Wirtschaftswissenschaften.
In der anfänglichen und trivialsten Form des TSP besteht die Aufgabe eines Handlungsreisenden darin, ausgehend von einem festgelegten Standort x, insgesamt n verschiedene Städte genau ein Mal zu bereisen und anschließend wieder an den Ausgangspunkt x zurückzukehren. Die dabei zu bewältigende Schwierigkeit besteht darin, diese Rundreise möglichst kosteneffizient zu gestalten, wobei in dieser Form unter Kosteneffizienz eine möglichst kurze Wegstrecke zu verstehen ist.
Diese einfach anmutende Aufgabenstellung erweist sich bei steigender Anzahl an zu berücksichtigenden Wegpunkten jedoch als zunehmend komplex. So stellt sich eine praktische Anwendung dieser Aufgabenstellung derart dar, dass ausgehend von z.B. insgesamt fünf zu bereisenden Städten (inkl. Ausgangspunkt/Endpunkt) zu Beginn vier Alternativen bestehen, um die weitere Rundreise zu bestimmen und den nächsten Wegpunkt auszuwählen. Wurde der erste Wegpunkt bestimmt, bleiben drei weitere mögliche Orte für die nächste Station usw. Somit ergibt sich eine Anzahl von (n − 1) * (n − 2) * (n − 3) * (n − 4) = 4 * 3 * 2 * 1 (oder auch 4!) verschiedenen Möglichkeiten.
Zusammenfassung der Kapitel
1 Einleitung: Vorstellung der Problemstellung, Motivation und Zielsetzung der Arbeit bezüglich der Optimierung von Rundreisen.
2 Aufbau und Struktur der Arbeit: Erläuterung des methodischen Vorgehens und des Gliederungsaufbaus der Arbeit.
3 Grundlagen: Umfassende Einführung in die Graphentheorie sowie die theoretischen Grundlagen des TSP und VRP.
4 Tourenplanung: Darstellung der Phasen der Tourenplanung und Verfahren zur Clusterbildung.
5 Algorithmen zur Bearbeitung von Handlungsreisenden- und Vehicle-Routing-Problemen: Detaillierte Vorstellung verschiedener heuristischer Lösungsverfahren.
6 Praktische Anwendungsbereiche: Analyse der spezifischen Anforderungen von liefernden Unternehmen, Entsorgern und Energieversorgern.
7 Lösungsmöglichkeiten für Handlungsreisenden und Vehicle-Routing-Probleme: Benchmarking der Algorithmen anhand praktischer Testfälle.
8 Zusammenfassung: Abschließende Betrachtung der Ergebnisse und Fazit der Arbeit.
Schlüsselwörter
Handlungsreisenden-Problem, TSP, Vehicle-Routing-Problem, VRP, Graphentheorie, Optimierungsalgorithmen, Tourenplanung, Clusterbildung, Greedy-Verfahren, 2-Opt-Verfahren, Nutzwertanalyse, Logistik, Nebenbedingungen, Heuristiken, Knotengrad
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit untersucht, wie logistische Rundreisen-Optimierungsprobleme (TSP/VRP) unter Berücksichtigung spezifischer Nebenbedingungen gelöst werden können.
Welche zentralen Themenfelder werden behandelt?
Zentrale Themen sind die mathematische Modellierung mittels Graphen, diverse Lösungsalgorithmen sowie deren Anwendung in Branchen wie Logistik und Energieversorgung.
Was ist das primäre Ziel oder die Forschungsfrage?
Das Ziel ist es, ein systematisches Vorgehen zur Auswahl des am besten geeigneten Optimierungsalgorithmus für ein konkretes logistisches Szenario zu erarbeiten.
Welche wissenschaftliche Methode wird verwendet?
Es werden heuristische Lösungsverfahren (z.B. Greedy, Insert, Opt) mathematisch analysiert, auf praktische Testfälle angewandt und mittels Nutzwertanalysen verglichen.
Was wird im Hauptteil behandelt?
Der Hauptteil gliedert sich in theoretische Grundlagen, Methoden zur Tourenplanung, Algorithmenvorstellung und eine praktische Benchmarking-Analyse in ausgewählten Branchen.
Welche Schlüsselwörter charakterisieren die Arbeit?
TSP, VRP, Graphentheorie, Optimierung, Tourenplanung, Clusterbildung, Heuristik, Nutzwertanalyse.
Warum ist das "Lochbohrungs-Problem" relevant für die Arbeit?
Es dient als anschauliches Praxisbeispiel für ein TSP, bei dem nicht nur die Wegstrecke, sondern auch logische Nebenbedingungen wie Werkzeugumrüstungen optimiert werden müssen.
Welchen Vorteil bietet das "2-Opt-Verfahren" in der Praxis?
Das 2-Opt-Verfahren bietet bei vertretbarem Rechenaufwand eine signifikante Verbesserung der Qualität von Hamiltonischen Kreisen durch sukzessives Tauschen von Kanten.
Warum werden für Entsorgungsunternehmen andere Kriterien als für Lieferdienste angesetzt?
Aufgrund unterschiedlicher operativer Anforderungen, wie etwa die Notwendigkeit von Team-Besatzungen (Personalanzahl) oder die dynamische Erfassung von Abfallmengen (EE statt VE).
- Citar trabajo
- Daniel Schmitz (Autor), 2012, Lösungsmöglichkeiten des Handlungsreisenden-Problems, Múnich, GRIN Verlag, https://www.grin.com/document/490597
