Das Transportwesen und die damit verbundene logistische Planung des Warenflusses sowie die Tourenplanung spielen eine wichtige Rolle im betriebswirtschaftlichen Umfeld. Unter Tourenplanung versteht man allgemein eine Klasse von Planungsproblemen, die verschiedene Ausprägungen bezüglich der Zielfunktion und den Nebenbedingungen aufweisen. Eine konkrete Problemstellung der Tourenplanung sieht etwa folgendermaßen aus: Von einem oder mehreren Lagern ausgehend, sind mit einem vorhandenen Fuhrpark, ein oder mehrere Kunden entsprechend den vorhandenen Aufträgen zu beliefern. Hierbei ist die Kapazität der Fahrzeuge beschränkt. Eine in der betrieblichen Praxis häufig auftretende weitere Restriktion ist die Vorgabe von Zeitfenstern. Unter Zeitfenstern versteht man Intervalle, die den frühesten und spätesten Beginn einer Auftragsdurchführung begrenzen. Ein typisches Beispiel für ein Tourenplanungsproblem mit Zeitfenstern ist die „just-in-time“ Belieferung durch Paketdienste. Im angelsächsischen Sprachbereich wird das Problem auch als „vehicle routing problem with time windows“ (VRPTW) bezeichnet. In der Regel liegt dem VRPTW eine hierarchische Zielsetzung zugrunde, die die benötigte Fahrzeugzahl in einem ersten Schritt und die Minimierung der Gesamtdistanz in einem zweiten Schritt berücksichtigt.
Das VRPTW ist ein kombinatorisches Optimierungsproblem, welches zur Klasse der NP-harten (engl.: non-deterministic polynomial time) Probleme gezählt wird. Dies bedeutet, dass bislang kein Algorithmus bekannt ist, mit dem eine optimale Lösung in polynomialer Zeit gefunden werden kann. Stattdessen wächst der Lösungsaufwand mit der Problemgröße exponentiell. Deshalb bietet sich der Einsatz von heuristischen Verfahren an.
Hierzu zählen insbesondere Metaheuristiken, wie das Tabu Search Verfahren, Simulated Annealing oder Evolutionäre Algorithmen (z.B. genetische Algorithmen). Die ersten Metaheuristiken haben ihren Ursprung in den 70er Jahren. In letzter Zeit wurden besonders hybride und verteilt-parallele Ansätze untersucht. Unter hybriden Ansätzen versteht man eine Kombination von verschiedenen Metaheuristiken. Verteilt-parallele Ansätze versuchen das Problem nicht mehr sequentiell, sondern durch mehrere parallele Prozesse zu lösen.
In dieser Arbeit werden speziell große Probleminstanzen mit mehreren hundert Kunden untersucht. Hierfür werden verschiedene Verfahren, die in der jüngsten Literatur veröffentlicht wurden, miteinander verglichen.
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
3.1 Tabu-Search Verfahren
Das Tabu-Search (TS) Verfahren wurde von GLOVER (1986) und von HANSEN (1986) unabhängig voneinander entwickelt. Es stellt nach HOMBERGER (2000) eine Strategie zur „aggressiven Exploration“ des Lösungsraums dar. In seiner Grundform untersucht TS bei jeder Iteration die vollständige Nachbarschaft der aktuellen Lösung. Zur Steuerung des Suchprozesses und zur Vermeidung von Zyklen verwendet TS ein Gedächtnis, das als „Tabuliste“ bezeichnet wird. Mit Hilfe dieser Liste wird die Nachbarschaft auf eine Menge („Pool“) eingeschränkt, die eine echte Teilmenge der Nachbarschaftsmenge ist. Die anderen Lösungen der Nachbarschaft werden tabu gesetzt. Hierdurch wird verhindert, dass es zu einem Zyklus kommen kann. In jeder Iteration wird die beste nicht tabuisierte Lösung ausgewählt.
Für die Auswahl der besten Lösung stehen verschiedene Verfahren zur Verfügung. Zunächst ist die „Best-Akzeptanz-Strategie“ zu nennen. Hierbei wird die Nachbarlösung ausgewählt, welche die höchste Verbesserung zur aktuellen Lösung darstellt. Falls keine Verbesserung erzielt werden kann, wird im Allgemeinen die Lösung mit der geringsten Verschlechterung ausgewählt. Im Fall von sehr großen Nachbarschaften, die einen sehr großen Rechenaufwand für die Besten-Suche verursachen, werden folgende alternative Vorgehensweisen verwendet:
Best-Akzeptanz-Strategie mit einer eingeschränkten Nachbarschaft und
First-Akzeptanz-Strategie.
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.
- Quote paper
- Dr.-Ing. Stephan Pachnicke (Author), 2005, Vergleich unterschiedlicher heuristischer Verfahren für das "Vehicle routing problem with time windows", Munich, GRIN Verlag, https://www.grin.com/document/51125
