Anwendung hyperheuristischer Methoden auf das Tourenplanungsproblem mit Zeitfensterrestriktionen innerhalb eines deterministisch-heuristischen Frameworks

Lindenthal, Sonja GND

Der Verkehrssektor spielt in der modernen Volkswirtschaft eine zentrale Rolle. Erst die Mobilität von Gütern und Menschen gewährleistet letztlich arbeitsteiliges Wirtschaften und Wertschöpfung in allen Wirtschaftssektoren. Dabei zählt die Logistik neben Organisation und Geld zu den zentralen Voraussetzungen, um Arbeitsteilung und Warenaustausch überhaupt zu ermöglichen. Konkret befasst sich die Logistik mit Fragen der sicheren Versorgung mit Materialien und Gütern zu optimalen Kosten und Beständen. Es geht also darum, die richtige Menge der richtigen Objekte am richtigen Ort zum richtigen Zeitpunkt in der richtigen Qualität zu den richtigen Kosten bereitzustellen. Im Bereich der Transport- bzw. Distributionslogistik stellt die Tourenplanung ein mächtiges Instrument zur Planung von Fahrzeugeinsätzen und Transportwegen dar. Die erfolgreiche Tourenplanung steigert die Effizienz des Transportwesens und trägt damit entscheidend zum Erfolg der Branche bei. Da immer neue Anforderungen an die Transportlogistik gestellt werden, sind auch die Methoden der Tourenplanung beständig weiter zu entwickeln und zu verfeinern. Konkret befassen sich Tourenplanungsprobleme mit der möglichst kostengünstigen Belieferung einer Reihe von Kunden innerhalb einer bestimmten Zeit von einem zentralen Warenlager aus. Tourenplanungsprobleme gehören der Klasse der so genannten NP-schweren Probleme an, wobei „NP“ für „nicht-deterministisch polynomial“ steht, und sich auf den benötigten Zeit- bzw. Rechenaufwand zur exakten Lösung einer Aufgabenstellung bezieht. Alle heute bekannten exakten Algorithmen lösen NP-schwere Probleme lediglich in Exponentialzeit. Das bedeutet, dass die Problemgröße – im Fall der Tourenplanung die Anzahl der zu beliefernden Kunden – den Rechenaufwand zur Problemlösung exponentiell ansteigen lässt. Bereits bei relativ geringen Kunden¬anzahlen ist damit eine exakte Lösung praktisch nicht mehr möglich. Dabei ist gerade die zunehmende Problemgröße vor dem Hintergrund wachsender Märkte bzw. transportlogistischer Aufgabenstellungen besonders praxisrelevant. In der vorliegenden Arbeit wird ein rein deterministischer, hyperheuristischer Ansatz zur Lösung des Tourenplanungsproblems mit Zeitfensterrestriktionen vorgestellt, der sich der Stärken bzw. besonderen Charakteristika verschiedener Verfahren bedient. Die Berück-sichtigung von Zeitfensterrestriktionen trägt zeitlichen Gegebenheiten bei der praktischen Abwicklung transportlogistischer Aufgaben Rechnung. Die Verfahren, die im Rahmen der Hyperheuristik zum Einsatz gelangen, wurden durchweg neu entwickelt, um den vollständigen Determinismus des gesamten Verfahrensrahmens – bestehend aus einfachen, problemorientierten bzw. Low-level Heuristiken und Hyper-heuristiken – zu garantieren. Dadurch werden die jederzeitige Reproduzierbarkeit der vorgestellten Ergebnisse und damit ceteris paribus das Erreichen einer bestimmten Lösungsgüte sichergestellt. Ein weiterer, wesentlicher Aspekt der Heuristiken ist, dass sie speziell für den Umgang mit relaxierten Tourenplänen entwickelt wurden. Dieser relaxationsbasierte Ansatz ermöglicht schließlich die Einführung einer neuen Bewertungsmethode, die eine größere Granularität und Präzision bei der Qualitätsbeurteilung von Problemlösungen ermöglicht. Dies eröffnet neue Möglichkeiten bei der Erweiterung standardisierter Tourenplanungsprobleme hin zu noch praxisnäheren Problemstellungen der Tourenplanung. Die Hyperheuristiken und ihre Einzelverfahren wurden in ein neues Verfahrensframework integriert, um eine einfache externe Konfiguration und eine maximale Flexibilität im Verfahrenseinsatz ohne Rückgriff auf den eigentlichen Sourcecode der Software zu ermöglichen. Die Ergebnisse der vorliegenden Arbeit belegen, dass der Einsatz abstrakter Strategien zur Steuerung der Suche von Einzelverfahren (Hyperheuristiken) in Bezug auf die erzielten Ergebnisse sowohl gegenüber dem Einsatz der einzelnen Verfahren, als auch gegenüber hybridisierten Verfahren überlegen ist. Zudem konnte gezeigt werden, dass die vorgestellte Hyperheuristik bei vergleichsweise geringem Rechenaufwand in der Lage ist, Lösungen zu erzeugen, die in Bezug auf die Anzahl erzeugter Touren teilweise mit den aktuellen Benchmark-Verfahren konkurrenzfähig sind. Insgesamt lässt sich festhalten, dass die vorliegende Arbeit auf die Schaffung einer Basis für weitere Entwicklungen auf dem Gebiet der Anwendung von Hyperheuristiken auf Tourenplanungsprobleme ausgerichtet ist. In diesem Sinne erscheinen die entwickelten Low-level Verfahren als leistungsfähige Bausteine für einen künftigen Einsatz im Rahmen von Meta- oder Hyperheuristiken. Auch die Integration der entwickelten Verfahren in einem nicht-deterministischen Kontext erscheint viel versprechend.

Vorschau

Zitieren

Zitierform:

Lindenthal, Sonja: Anwendung hyperheuristischer Methoden auf das Tourenplanungsproblem mit Zeitfensterrestriktionen innerhalb eines deterministisch-heuristischen Frameworks. Hagen 2013. FernUniversität in Hagen.

Zugriffsstatistik

Gesamt

Volltextzugriffe:
Metadatenansicht:

12 Monate

Volltextzugriffe:
Metadatenansicht:

Rechte

Nutzung und Vervielfältigung:
Alle Rechte vorbehalten

Export

powered by MyCoRe