In den letzten Jahrzehnten rückte ein Bereich der kombinatorischen Optimierungsprobleme immer mehr in den Brennpunkt der Forschung:
die Klasse der Tourenplanungsprobleme. Immer mehr Güter müssen in immer kürzerer Zeit von einem Ort zum anderen transportiert werden. Bei der Tourenplanung werden daher Fragestellungen diskutiert, wie eine Zusammenstellung von Auslieferungs- und Sammelaufträgen aussehen muss, um einen möglichst effizienten Ablauf zu gewährleisten. Die Schwierigkeit dieser Organisation liegt darin, die dem Problem zu Grunde liegenden Restriktionen einzuhalten. In der Praxis treten häufig Einschränkungen in Form einer begrenzten Ladekapazität der zur Verfügung stehenden Fahrzeuge oder zeitlicher Vorgaben der Kunden auf. Diese zeitlichen Vorgaben beinhalten den frühest beziehungsweise den spätest möglichen Belieferungszeitpunkt des Kunden. Beispielsweise kann ein Kunde aus der Just-in-Time Fertigung keine Lieferung vor diesem Zeitfenster annehmen, da ihm dafür schlicht Lagerkapazitäten fehlen. Eine Belieferung nach Ende des Zeitfensters ist ebenfalls nicht erlaubt, da es in diesem Szenario unter Umständen zu einem Stillstand der Produktion in Folge fehlender Ressourcen kommen kann.
In der Literatur wird dem Tourenplanungsproblem mit Zeitfensterrestriktionen meist eine hierarchische Zielstellung zu Grunde gelegt, einem primären sowie einem sekundären Ziel. Vorrangig ist hierbei die Minimierung der benötigten Fahrzeuge, nachrangig die Minimierung der zurückgelegten Gesamtfahrstrecke. Seit Mitte der Siebziger Jahre werden zur Lösung des VRPTW die dafür entwickelten Metaheuristiken eingesetzt. Sie basieren auf der Grundidee, physikalische oder biologische Prozesse nachzuahmen. Typische Vertreter solcher Verfahren sind Genetische und Evolutionäre Algorithmen, Simulated Annealing und Tabu-Search.
Eine Zielsetzung dieser Arbeit ist es, einen geeigneten Algorithmus zur Lösung des Tourenplanungsproblems mit Zeitfensterrestriktionen vorzustellen und diesen zu evaluieren. Ein zweites Ziel wird sein, ein weiteres, von der Literatur bisher unbeachtetes Kriterium zur Bewertung einer gefundenen Lösung umzusetzen: eine möglichst gleichmäßige Verteilung der Kunden auf die jeweiligen Touren. Damit soll erreicht werden, dass jeder Fahrer einer Tour zeitlich annähernd gleich lange unterwegs ist wie seine Kollegen auf den anderen Touren. Dabei wird dieses Kriterium nicht als Ziel sondern als Wunsch formuliert.
Inhaltsverzeichnis
1 Einleitung
1.1 Problemstellung
1.2 Zielstellung der Arbeit
1.3 Aufbau und Gliederung der Arbeit
2 Grundlagen und Abgrenzung
2.1 Tourenplanung im Allgemeinen
2.2 Tourenplanung mit zeitlicher Restriktion
2.2.1 Voraussetzungen und Realitätsbeschränkung
2.2.2 Mathematische Modellbildung
2.2.3 Komplexitätsuntersuchung des VRPTW
2.2.4 Typologie der Zeitfensterrestriktionen
2.3 Ansätze zur Lösung kombinatorischer Optimierungsprobleme
2.3.1 Problemspezifische Heuristiken
2.3.2 Metaheuristiken
3 Verfahren zur Lösung des VRPTW
3.1 Konstruktionsverfahren
3.2 Definition der Nachbarschaftsstrukturen
3.3 Bewertungsfunktion eines Tourenplans
3.4 Aufbau des Gesamtverfahrens
3.4.1 Minimierung der Fahrzeuganzahl
3.4.2 Minimierung der Gesamtfahrstrecke
4 Algorithmische Beschreibung des Verfahrens
4.1 Repräsentation elementarer Komponenten
4.1.1 Repräsentation der Kunden
4.1.2 Repräsentation der Tourenpläne
4.2 Elementare Zugriffe
4.3 Elementare Berechnungen
4.4 Elementare Zulässigkeitsbedingungen
4.5 Elementare Operationen
4.6 Konstruktion der Ausgangslösung
4.7 Algorithmische Umsetzung der Nachbarschaftsstrukturen
4.7.1 Operator Or-Opt
4.7.2 Operator 2-Opt*
4.7.3 Operator Single-Interchange
4.7.4 Operator Single-Insertion
4.7.5 Auswahl des Operators
4.8 Bewertung von Tourenplänen
4.9 Verbesserungsverfahren
4.9.1 Ejection-Chain Heuristik
4.9.2 Rekursion der Ejection-Chain
4.9.3 Lokale Suche zur Minimierung der Tourenanzahl
4.9.4 Lexikographischer Vergleichsoperator
4.9.5 Akzeptanz einer verschlechterten Lösung
4.9.6 Metaheuristik: Threshold Accepting
4.9.7 Verfahren zur Minimierung der Gesamtfahrstrecke
5 Evaluation des Gesamtverfahrens
5.1 Probleminstanzen von Solomon und Homberger
5.2 Parametrisierung des Gesamtverfahrens
5.3 Darstellung der berechneten Lösungen
5.4 Auswertung der berechneten Lösungen
6 Zusammenfassung
Zielsetzung & Themen
Die Arbeit befasst sich mit der Entwicklung und Evaluierung eines Algorithmus zur Lösung des Tourenplanungsproblems mit Zeitfensterrestriktionen (VRPTW), wobei ein besonderer Fokus auf der Minimierung der benötigten Fahrzeuganzahl sowie der Gesamtfahrstrecke liegt, ergänzt durch das Ziel einer gleichmäßigen Verteilung der Kunden auf die Touren.
- Fahrzeugtourenplanung mit Zeitfenstern (VRPTW)
- Metaheuristiken zur kombinatorischen Optimierung
- Ejection-Chain-Heuristik und Threshold Accepting
- Leistungsvergleich anhand von Benchmarks (Solomon/Homberger)
- Lexikographische Zielfunktionsoptimierung
Auszug aus dem Buch
1.1 Problemstellung
In den letzten Jahrzehnten rückte ein Bereich der kombinatorischen Optimierungsprobleme immer mehr in den Brennpunkt der Forschung: die Klasse der Tourenplanungsprobleme. Immer mehr Güter müssen in immer kürzerer Zeit von einem Ort zum anderen transportiert werden. Bei der Tourenplanung werden daher Fragestellungen diskutiert, wie eine Zusammenstellung von Auslieferungs- und Sammelaufträgen aussehen muss, um einen möglichst effizienten Ablauf zu gewährleisten. Die Schwierigkeit dieser Organisation liegt darin, die dem Problem zu Grunde liegenden Restriktionen einzuhalten. In der Praxis treten häufig Einschränkungen in Form einer begrenzten Ladekapazität der zur Verfügung stehenden Fahrzeuge oder zeitlicher Vorgaben der Kunden auf. Diese zeitlichen Vorgaben beinhalten den frühest beziehungsweise den spätest möglichen Belieferungszeitpunkt des Kunden. Beispielsweise kann ein Kunde aus der Just-in-Time Fertigung keine Lieferung vor diesem Zeitfenster annehmen, da ihm dafür schlicht Lagerkapazitäten fehlen. Eine Belieferung nach Ende des Zeitfensters ist ebenfalls nicht erlaubt, da es in diesem Szenario unter Umständen zu einem Stillstand der Produktion in Folge fehlender Ressourcen kommen kann.
Wie Lenstra u. Kan (1981) zeigten, gehört das Tourenplanungsproblem mit Zeitfensterrestriktionen, das in der angelsächsischen Literatur unter dem Namen „Vehicle Routing Problem with Time Windows“ (VRPTW) zu finden ist, zu den NP-harten Optimierungsproblemen. In der Klasse der NP-harten Probleme fasst man all diejenigen Optimierungsprobleme zusammen, deren optimale Lösung nach gegenwärtigem Wissen praktisch nicht in polynomialem Zeitaufwand gefunden werden kann. Charakteristisch für solche Probleme ist vielmehr, dass die Zeitkomplexität für das Finden der optimalen Lösung exponentiell mit der Problemgröße wächst. Auf Grund dessen werden solche Probleme meist mit heuristischen Verfahren untersucht. Sie zeichnen sich dadurch aus, in akzeptablem Zeitaufwand gute Lösungen zu erzielen. Im Unterschied zu exakten Lösungsmethoden, wie beispielsweise dem Branch and Bound Algorithmus oder den Dekompositionsverfahren ist das Finden der optimalen Lösung jedoch nicht garantiert.
Zusammenfassung der Kapitel
1 Einleitung: Einführung in die Problemstellung der Tourenplanung, Definition des VRPTW und Formulierung der Ziele sowie des Aufbaus der Arbeit.
2 Grundlagen und Abgrenzung: Theoretische Einordnung der Tourenplanung, mathematische Modellierung des VRPTW und Diskussion der Komplexität sowie der Typologie von Zeitfensterrestriktionen.
3 Verfahren zur Lösung des VRPTW: Vorstellung von Konstruktions- und Verbesserungsverfahren sowie der Bewertungsfunktionen und der Gesamtkonzeption des Lösungsansatzes.
4 Algorithmische Beschreibung des Verfahrens: Detaillierte Darstellung der Datenstrukturen, elementarer Funktionen, Zulässigkeitsprüfungen und der Implementierung der Metaheuristiken.
5 Evaluation des Gesamtverfahrens: Anwendung des Algorithmus auf Benchmark-Probleme und Auswertung der Ergebnisse hinsichtlich der Güte und Rechenzeit.
6 Zusammenfassung: Abschließende Reflexion über die erzielten Ergebnisse und Ausblick auf zukünftige Forschungsrichtungen.
Schlüsselwörter
Tourenplanung, Zeitfensterrestriktionen, VRPTW, Metaheuristik, Ejection-Chain, Threshold Accepting, Optimierung, Fahrzeuganzahl, Gesamtfahrstrecke, Scheduling, Routing, Heuristik, Komplexitätstheorie, Benchmarks, Solomon-Instanzen
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Diplomarbeit widmet sich dem „Vehicle Routing Problem with Time Windows“ (VRPTW), einem klassischen kombinatorischen Optimierungsproblem, bei dem Lieferungen unter Einhaltung zeitlicher und kapazitiver Einschränkungen effizient geplant werden müssen.
Was sind die zentralen Themenfelder?
Zentrale Themen sind die mathematische Modellierung, die algorithmische Umsetzung von Metaheuristiken sowie die Evaluierung der Leistungsfähigkeit dieser Verfahren anhand bekannter Benchmark-Probleme.
Was ist das primäre Ziel oder die Forschungsfrage?
Das primäre Ziel ist die Entwicklung eines Algorithmus, der eine lexikographische Optimierung vornimmt: Zuerst wird die benötigte Fahrzeuganzahl minimiert, anschließend die Gesamtfahrstrecke reduziert.
Welche wissenschaftliche Methode wird verwendet?
Der Autor verwendet eine hybride Strategie aus einem modifizierten Savingsverfahren zur Initialisierung und einer Kombination aus lokaler Suche (Ejection-Chain-Heuristik) und der „Threshold Accepting“ Metaheuristik zur Lösungsverbesserung.
Was wird im Hauptteil behandelt?
Der Hauptteil gliedert sich in die theoretischen Grundlagen (Kapitel 2), die methodische Konzeption (Kapitel 3), die technische Realisierung (Kapitel 4) und die empirische Testreihe (Kapitel 5).
Welche Schlüsselwörter charakterisieren die Arbeit?
Die Arbeit lässt sich durch Begriffe wie VRPTW, Metaheuristiken, Tourenreduktion, Ejection-Chain, Zeitfensterrestriktionen und kombinatorische Optimierung beschreiben.
Welche Bedeutung hat die „Ejection-Chain-Heuristik“ für das Verfahren?
Sie ist das Herzstück zur Minimierung der Fahrzeuganzahl, indem sie versucht, Kunden aus einer „kleinsten Tour“ systematisch in andere Touren zu verdrängen und so ganze Tourenpläne zu optimieren.
Wie unterscheidet sich „Threshold Accepting“ von anderen Metaheuristiken?
Threshold Accepting ist eine vereinfachte, aber effiziente Variante des „Simulated Annealing“, bei der Verschlechterungen in der Lösungsgüte akzeptiert werden, solange sie einen definierten Schwellenwert nicht überschreiten, um so aus lokalen Optima auszubrechen.
- Quote paper
- Armin Bayer (Author), 2008, Zweistufen-Metaheuristik zur Lösung des Standardproblems der Tourenplanung mit Zeitfensterrestriktionen unter Verwendung Lokaler Suche in zufallsgesteuerten Nachbarschaften, Munich, GRIN Verlag, https://www.grin.com/document/123841
