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
- Einleitung
- Allgemein
- Motivation
- Ziele und Abgrenzung
- Aufbau und Struktur der Arbeit
- Grundlagen
- Das Handlungsreisenden-Problem
- Das Vehicle-Routing-Problem
- Lösungsverfahren
- Exakte Lösungsverfahren
- Approximative Lösungsverfahren
- Symmetrisches und asymmetrisches Handlungsreisenden-Problem
- Modellierung der realen Situation als Graph
- Gerichtete und ungerichtete Graphen
- Vollständiger Graph
- Hamiltonischer Kreis
- Euler-Tour
- Kostenberechnung
- Bewertung der Kanten eines Graphen
- Kantenfolgen innerhalb eines Graphen
- Kürzeste Wege in bewerteten Graphen
- Bäume
- Übertragung von Graphen in verarbeitbare Strukturen
- Darstellung als Adjazenzmatrix
- Darstellung als Kostenmatrix
- Tourenplanung
- Bildung von Kundenclustern
- Eröffnungsverfahren
- Verbesserungsverfahren
- Phasen einer Tourenplanung
- Tourenplanung unter Verwendung von Kundenclustern
- Erstellung eines minimal spannenden Baumes
- Greedy-Verfahren
- Verfahren nach Kruskal
- Verfahren nach Prim
- Bildung geeigneter Kundencluster
- Algorithmen zur Bearbeitung von Handlungsreisenden- und Vehicle-Routing-Problemen
- Nachbar-Verfahren
- Nächster-Nachbar-Verfahren
- Doppelter-Nächster-Nachbar-Verfahren
- Einfüge-Verfahren
- Cheapest-Insertion-Verfahren
- Farthest-Insertion-Verfahren
- Opt-Verfahren
- 2-Opt-Verfahren
- 3-Opt-Verfahren
- k-Opt-Verfahren
- Praktische Anwendungsbereiche
- Lieferndes Unternehmen
- Aufgaben eines liefernden Unternehmens
- Erarbeitung einer Kriterienliste für liefernde Unternehmen
- Entsorgungsunternehmen
- Aufgaben eines Entsorgungsunternehmens
- Erarbeitung einer Kriterienliste für Entsorgungsunternehmen
- Energieversorgungsunternehmen
- Aufgaben eines Energieversorgungsunternehmens
- Erarbeitung einer Kriterienliste für Energieversorgungsunternehmen
- Kriterienmatrix
- Lösungsmöglichkeiten für Handlungsreisenden- und Vehicle-Routing-Probleme
- Lösungsmöglichkeiten für liefernde Unternehmen
- Benchmarking der Optimierungsalgorithmen für liefernde Unternehmen
- Auswertung
- Lösungsmöglichkeiten für Entsorgungsunternehmen
- Benchmarking der Optimierungsalgorithmen für Entsorgungsunternehmen
- Auswertung
- Lösungsmöglichkeiten für Energieversorgungsunternehmen
- Benchmarking der Optimierungsalgorithmen für Energieversorgungsunternehmen
- Auswertung
- Nutzwertanalysen
- Liefernde Unternehmen
- Entsorgungsunternehmen
- Energieversorgungsunternehmen
- Zusammenfassung
- Fazit
- Ausblick
Zielsetzung und Themenschwerpunkte
Diese Arbeit untersucht verschiedene Lösungsmöglichkeiten für das Handlungsreisenden-Problem und das Vehicle-Routing-Problem, die in vielen Bereichen der Wirtschaft Anwendung finden. Ziel ist es, die verschiedenen Verfahren und Algorithmen zu analysieren und deren Eignung für bestimmte Einsatzgebiete zu bewerten.
- Analyse verschiedener Algorithmen zur Lösung des Handlungsreisenden- und Vehicle-Routing-Problems
- Bewertung der Effizienz und Effektivität der Algorithmen
- Anwendung der Algorithmen in verschiedenen Anwendungsbereichen wie dem Lieferwesen, der Entsorgung und der Energieversorgung
- Entwicklung einer Kriterienmatrix zur Beurteilung der Eignung der Algorithmen für spezifische Probleme
- Durchführung von Nutzwertanalysen zur Auswahl der optimalen Lösung für verschiedene Unternehmenstypen
Zusammenfassung der Kapitel
Die Einleitung stellt das Handlungsreisenden-Problem und das Vehicle-Routing-Problem vor, erläutert die Motivation und die Zielsetzung der Arbeit sowie die Abgrenzung des Themas.
Kapitel 3 behandelt die Grundlagen des Themas, darunter die Definitionen des Handlungsreisenden-Problems und des Vehicle-Routing-Problems, verschiedene Lösungsverfahren, die Modellierung des Problems als Graph und die Übertragung von Graphen in verarbeitbare Strukturen.
Kapitel 4 beschäftigt sich mit der Tourenplanung, insbesondere mit der Bildung von Kundenclustern, den Phasen der Tourenplanung und der Tourenplanung unter Verwendung von Kundenclustern.
Kapitel 5 stellt verschiedene Algorithmen zur Lösung von Handlungsreisenden- und Vehicle-Routing-Problemen vor, darunter Nachbar-Verfahren, Einfüge-Verfahren und Opt-Verfahren.
Kapitel 6 beleuchtet praktische Anwendungsbereiche, in denen das Handlungsreisenden- und Vehicle-Routing-Problem relevant sind, beispielsweise in liefernden Unternehmen, Entsorgungsunternehmen und Energieversorgungsunternehmen.
Kapitel 7 analysiert Lösungsmöglichkeiten für die in Kapitel 6 vorgestellten Anwendungsbereiche, wobei verschiedene Algorithmen anhand von Kriterien beurteilt und mit Hilfe von Nutzwertanalysen die optimale Lösung für jedes Unternehmen ermittelt wird.
Schlüsselwörter
Handlungsreisenden-Problem, Vehicle-Routing-Problem, Tourenplanung, Optimierungsalgorithmen, Nachbar-Verfahren, Einfüge-Verfahren, Opt-Verfahren, Benchmarking, Nutzwertanalyse, Lieferwesen, Entsorgung, Energieversorgung, Kriterienmatrix
- Quote paper
- Daniel Schmitz (Author), 2012, Lösungsmöglichkeiten des Handlungsreisenden-Problems, Munich, GRIN Verlag, https://www.grin.com/document/490597
