Lösungsmöglichkeiten des Handlungsreisenden-Problems

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

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).