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 und Themenschwerpunkte
Diese Diplomarbeit untersucht die effiziente Lösung großer Tourenplanungsprobleme mit Zeitfenstern (VRPTW). Ziel ist es, verschiedene heuristische Verfahren zu vergleichen, um die bestmögliche Methode für die Bewältigung komplexer Logistikaufgaben zu identifizieren.
- Analyse von Metaheuristiken, insbesondere Tabu Search, Simulated Annealing und Evolutionsstrategien
- Bewertung der Performance verschiedener Verfahren für VRPTW-Probleme mit mehreren hundert Kunden
- Vergleich von hybriden und verteilt-parallelen Lösungsansätzen
- Untersuchung der Einsatzmöglichkeiten verschiedener Algorithmen in realen Logistikumgebungen
- Erstellung eines umfassenden Vergleichs der untersuchten Verfahren hinsichtlich ihrer Effizienz, Robustheit und Skalierbarkeit
Zusammenfassung der Kapitel
Die Arbeit beginnt mit einer Einführung in das VRPTW und seiner Relevanz für das Transportwesen. Anschließend werden die Grundlagen und Abgrenzungen des Problems erläutert. Kapitel 3 widmet sich den Metaheuristiken, die in dieser Arbeit als Lösungsansätze für VRPTW-Probleme untersucht werden. In Kapitel 4 werden verschiedene, in der aktuellen Literatur vorgestellte Verfahren miteinander verglichen. Die Arbeit endet mit einer Zusammenfassung der Ergebnisse und Schlussfolgerungen.
Schlüsselwörter
Tourenplanung, Vehicle Routing Problem with Time Windows (VRPTW), Metaheuristiken, Tabu Search, Simulated Annealing, Evolutionsstrategien, Hybride Ansätze, Verteilt-parallele Ansätze, Logistik, Optimierung, Komplexitätsanalyse, Verfahrensevaluation, Probleminstanzen.
- Arbeit zitieren
- Dr.-Ing. Stephan Pachnicke (Autor:in), 2005, Vergleich unterschiedlicher heuristischer Verfahren für das "Vehicle routing problem with time windows", München, GRIN Verlag, https://www.hausarbeiten.de/document/51125
