Vergleich unterschiedlicher heuristischer Verfahren für das "Vehicle routing problem with time windows"

Inhaltsverzeichnis

1 Einleitung

1.1 Zielsetzungen der Arbeit

1.2 Vorgehensweise und Aufbau der Arbeit

2 Grundlagen und Abgrenzungen

2.1 Das allgemeine Tourenplanungsproblem

2.2 Tourenplanung unter Berücksichtigung zeitkritischer Restriktionen

2.3 Komplexitätsanalyse

3 Metaheuristiken für Optimierungsprobleme

3.1 Tabu-Search Verfahren

3.2 Simulated Annealing Verfahren

3.3 Evolutionsstrategien

3.4 Parallele Lösungsansätze

4 Vergleich unterschiedlicher Verfahren für die Lösung von großen Tourenplanungsproblemen mit Zeitrestriktionen

4.1 Probleminstanzen in der Literatur

4.2 Vergleichskriterien für die Verfahrensevaluation

4.3 Verfahren zur Lösung großer Tourenplanungsprobleme

4.3.1 Die kooperativ-parallele Metaheuristik von LE BOUTHILLIER und CRAINIC

4.3.2 Die adaptiven Suchheuristiken von PISINGER und ROPKE

4.3.3 Aktive gesteuerte Evolutionsstrategien von MESTER und BRÄYSY

4.3.4 Die Multi-Start lokale Suche (MSLS) Heuristik von BRÄYSY et al.

4.3.5 Ebenen-Schnittverfahren von KALLEHAUGE et al. sowie COOK und RICH

4.4 Gegenüberstellung der unterschiedlichen Verfahren

5 Zusammenfassung

Zielsetzung & Themen

Das Hauptziel dieser Diplomarbeit ist der Vergleich verschiedener heuristischer Verfahren zur Lösung des „Vehicle Routing Problem with Time Windows“ (VRPTW), insbesondere bei großen Probleminstanzen mit mehreren hundert Kunden, um die Effizienz und Lösungsqualität unterschiedlicher Metaheuristiken zu bewerten.

• Grundlagen des Tourenplanungsproblems und zeitkritischer Restriktionen
• Analyse und Vergleich von Metaheuristiken wie Tabu-Search, Simulated Annealing und Evolutionsstrategien
• Untersuchung von parallelen Lösungsansätzen bei kombinatorischen Optimierungsproblemen
• Evaluierung moderner Algorithmen anhand der sogenannten Homberger Benchmarkprobleme
• Beurteilung adaptiver Ansätze und der Balance zwischen Exploration und Exploitation

Auszug aus dem Buch

Zusammenfassung der Kapitel

1 Einleitung: Vorstellung des VRPTW als NP-hartes kombinatorisches Optimierungsproblem und Definition der Zielsetzungen der Arbeit.

2 Grundlagen und Abgrenzungen: Beschreibung des allgemeinen Tourenplanungsproblems unter Berücksichtigung von Zeitfensterrestriktionen und mathematischer Komplexität.

3 Metaheuristiken für Optimierungsprobleme: Erläuterung von Metaheuristiken (Tabu-Search, Simulated Annealing, Evolutionsstrategien) und deren parallelen Implementierungsformen.

4 Vergleich unterschiedlicher Verfahren für die Lösung von großen Tourenplanungsproblemen mit Zeitrestriktionen: Detaillierte Analyse und Vergleich verschiedener Lösungsverfahren anhand von Benchmarkproblemen, inklusive deren Implementierung und Performanz.

5 Zusammenfassung: Resümee der Arbeit, Bewertung der untersuchten Verfahren und Ausblick auf künftige Forschungsaktivitäten im Bereich der Tourenplanung.

Schlüsselwörter

VRPTW, Tourenplanung, Metaheuristiken, Tabu-Search, Simulated Annealing, Evolutionsstrategien, Homberger Probleme, NP-hart, parallele Lösungsansätze, Lösungsqualität, Benchmarkprobleme, adaptive Heuristiken, Optimierungsprobleme, Logistikplanung, kombinatorische Optimierung.

Häufig gestellte Fragen

Worum geht es in dieser Diplomarbeit?

Die Arbeit befasst sich mit dem Vergleich unterschiedlicher heuristischer Optimierungsverfahren für das „Vehicle Routing Problem with Time Windows“ (VRPTW), insbesondere für große Datenmengen.

Welche Themenfelder stehen im Fokus?

Im Zentrum stehen die Grundlagen der Tourenplanung, verschiedene Metaheuristiken wie Tabu-Search und Simulated Annealing sowie Ansätze zur Parallelisierung von Suchprozessen.

Was ist das primäre Ziel der Arbeit?

Das Ziel ist die Beschreibung und der kritische Vergleich aktueller, in der Literatur vorgestellter Metaheuristiken, um deren Eignung für komplexe Probleminstanzen mit mehreren hundert Kunden zu evaluieren.

Welche wissenschaftliche Methode kommt zum Einsatz?

Die Arbeit nutzt eine umfassende Literaturrecherche und eine vergleichende Analyse bekannter Benchmark-Verfahren (Homberger Probleme) zur Bewertung der Lösungsansätze.

Was wird im Hauptteil der Arbeit behandelt?

Der Hauptteil analysiert spezifische Metaheuristiken sowie deren hybride und parallele Varianten, die bei der Lösung von VRPTW-Problemen Anwendung finden.

Welche Schlagworte charakterisieren diese Arbeit?

Kernbegriffe sind Metaheuristiken, VRPTW, Tourenplanung, adaptive Suchverfahren, parallele Optimierung und Homberger Benchmarkprobleme.

Was unterscheidet das „Solution Warehouse“-Konzept von herkömmlichen Ansätzen?

Es ermöglicht mehreren parallelen Prozessen (Threads) einen asynchronen Informationsaustausch, was die Robustheit und Qualität der gefundenen Lösungen signifikant erhöht.

Warum sind die sogenannten „Homberger Probleme“ für den Vergleich wichtig?

Da sie mit mehreren hundert Kunden deutlich größere und anspruchsvollere Instanzen darstellen als klassische kleine Datensätze, erlauben sie eine fundierte Bewertung der Skalierbarkeit moderner Optimierungsalgorithmen.