Eine mehrstufige evolutionäre Hyperheuristik für das Tourenplanungsproblem mit Zeitfensterrestriktionen

Hölscher, Matthias

Die Logistik ist ein bedeutender Faktor innerhalb der deutschen Wirtschaft. Eine herausragende Stellung innerhalb der Logistik nimmt der Transport von Gütern ein. Den größten Anteil an der Gesamttransportleistung hat der Straßengüterverkehr in Form der Beförderung von Gütern mit LKW. Für Unternehmen stellt der Transport von Gütern und insbesondere die direkte Belieferung von Kunden eine enorme Herausforderung und ein großer Kostenfaktor dar. Die in diesem Kontext relevanten Transportkosten, also die Kosten der direkten Auslieferung von Gütern an Kunden, werden im Wesentlichen durch Personalkosten, Fahrzeug-Bereitschaftskosten sowie Fahrzeug-Betriebskosten bestimmt. Die sogenannte Tourenplanung, die aus unternehmerischer Sicht eine Minimierung der Transportkosten zum Ziel hat, kann unmittelbar auf die Entstehung der genannten Kosten einwirken. Dieser Dissertation liegt das sogenannte Tourenplanungsproblem mit Zeitfensterrestriktionen (engl. Vehicle Routing Problem with Time Windows - VRPTW), bei dem Lieferaufträge unter Einhaltung der Gütermengen, der Transportmittel und Bedienzeitpunkte zu erfüllen sind, zugrunde. Das VRPTW zielt zur Kostenoptimierung auf eine Minimierung der Fahrzeuganzahl sowie der Länge der Transportwege ab. Das VRPTW ist ein NP-schweres Optimierungsproblem, das bei praxisrelevanten Problemgrößen mit vertretbarem Aufwand nicht optimal gelöst werden kann. In der unternehmerischen Praxis kommen deshalb zur Lösung dieser Planungsprobleme Heuristiken, die hinreichend gute Lösungen mit vertretbarem Aufwand bestimmen, zum Einsatz. Eine spezielle Ausprägung stellen die sogenannten Hyperheuristiken, dar. Das hyperheuristische Lösungskonzept basiert auf einem problemunabhängigen Verfahren, das einfache problemspezifische Heuristiken (Low-level-Heuristiken) selektiert und zur Lösung auf das zugrundeliegende Optimierungsproblem anwendet. Die vorliegende Arbeit stellt die Entwicklung einer Hyperheuristik für das VRPTW, die einen dreistufigen Ansatz zur Problemlösung verfolgt, vor. Als grundlegendes Lösungskonzept setzt die Hyperheuristik auf einen an evolutionäre Algorithmen angelehnten Ansatz, der zur Lösung aus der Menge der Low-level-Heuristiken Sequenzen bildet. Zur Erhöhung der Lösungsgüte werden zwei Optimierungsstufen eingesetzt, die die Low-level-Heuristik-Sequenzen optimieren. Im ersten Schritt werden mittels eines genetischen Algorithmus die Sequenzen durch Austausch von Low-level-Heuristiken verändert und im zweiten Schritt werden die in den Heuristiken enthaltenen Parameter mittels einer Partikelschwarmoptimierung verbessert. Zur zusätzlichen Unterstützung des Lösungsprozesses werden vier Lernkomponenten, die Sequenzen und Parameter lernen und in den Lösungsprozess einbringen, eingesetzt. Basierend auf umfangreichen Messungen kann gezeigt werden, dass evolutionäre Algorithmen als hyperheuristische Strategie geeignet sind. Zudem kann verdeutlicht werden, dass der Einsatz von Optimierungskomponenten die Lösungsgüte erhöht. Die eingesetzten Lernkomponenten nehmen positiv Einfluss auf den Lösungsprozess, indem sie in der Lage sind, die erforderlichen Rechenaufwand deutlich zu reduzieren. Insgesamt liefert die entwickelte Hyperheuristik Ergebnisse, die im Vergleich mit in der Literatur bekannten Hyperheuristiken für das VRPTW in Bezug auf die Lösungsgüte und den erforderlichen Rechenaufwand konkurrenzfähig sind.

Vorschau

Zitieren

Zitierform:

Hölscher, Matthias: Eine mehrstufige evolutionäre Hyperheuristik für das Tourenplanungsproblem mit Zeitfensterrestriktionen. Hagen 2021. FernUniversität in Hagen.

Zugriffsstatistik

Gesamt:
Volltextzugriffe:
Metadatenansicht:
12 Monate:
Volltextzugriffe:
Metadatenansicht:

Grafik öffnen

Rechte

Nutzung und Vervielfältigung:
Alle Rechte vorbehalten

Export

powered by MyCoRe