Exakte und heuristische Verfahren für unsichere und zeitabhängige Hub-Location-Probleme mittels quadratischer Optimierung

Hintergrund

Für Logistikdienstleister kommt der strategischen Planung von Transportnetzwerken durch die zunehmende Internationalisierung, ein stark wachsendes Güterverkehrsaufkommen und einen intensiveren Wettbewerb eine immer entscheidendere Bedeutung zu. In Transportnetzwerken müssen für eine gegebene Anzahl an Depots Verbindungen untereinander realisiert werden. Da Direktverbindungen zu kostenintensiv sind, werden an einigen Standorten Hubs errichtet. Jede Sendung wird von ihrem Start- zu ihrem Zieldepot über ein oder zwei Hubs geschickt, mit dem Ziel durch Bündelung von Transporten zwischen den Hubs Transportkosten einzusparen. Die Aufgabe des Hub-Location-Problems ist es Standorte für Hubs auszuwählen, so dass die Summe aus Errichtungskosten der Hubs und Transportkosten minimiert wird.

Im Fokus des Forschungsprojektes steht die Single-Allocation-Variante des Hub-Location-Problems, bei der die Sendungen ohne Vorsortierung von einem Depot zu einem bestimmten Hub transportiert werden. Diese Variante besitzt eine quadratische Grundstruktur, so dass sich bisher quadratische Optimierungsmethoden bewährt haben.

Auch nach über 25 Jahren Forschung über das Hub-Location-Problem stellt die strategische Planung von Transportnetzwerken immer noch eine Herausforderung dar. In den bisherigen Modellen wurden die Daten über die zu erwartenden Transportvolumen und -kosten als deterministisch angenommen. In der Praxis sind diese Daten allerdings nicht im Voraus bekannt und können nur approximativ abgeschätzt werden. Ebenso blieben Störungen wie der Ausfall eines Hubs unberücksichtigt.

Vorgehensweise

Für die stark vereinfachten Modelle der Achtziger Jahre stehen mittlerweile ausgereifte Algorithmen zur Verfügung. Hier wird jedoch mit einem Transportkostensatz pro Tonnenkilometer gerechnet, der auf Hub-Hub-Verbindungen mit einem festen Faktor diskontiert wird. Dies führt mitunter zur Einplanung schlecht ausgelasteter Fahrzeuge. Weiterhin werden alle Daten als bekannt vorausgesetzt und mögliche Schwankungen oder Störungen ignoriert. Für anwendungsnahe Modelle besteht noch großer Forschungsbedarf.
In der ersten Projektphase wurden schon wesentliche Fortschritte bezüglich der Modellintegration komplexer Transportkostenfunktionen erzielt. In enger Zusammenarbeit der Projektpartner wurden dabei heuristische und exakte Optimierungsverfahren entwickelt, welche gute Lösungen auch bei großen, realistischen Problemgrößen berechnen. Gerade bei Single-Allocation-Problemen, in denen die Sendungen ohne Sortierung zu dem gewählten Hub transportiert werden (wie etwa in Postnetzen), haben sich die entwickelten quadratischen Optimierungsmethoden bewährt. Wesentlich für die Einsetzbarkeit der diskutierten Modelle ist es nun, den Schritt von deterministischen zu stochastischen Daten zu gehen.
In der Realität sind Transportmengen und –zeiten nicht vorher bekannt und Hubausfälle können ein schlecht geplantes Netzwerk empfindlich stören. Daher wurden in diesem Projekt stochastische und robuste Modelle aufgebaut und mit einer Kombination aus heuristischen und exakten Optimierungsverfahren gelöst. Hierbei wurde der Fokus auf Single-Allocation-Modelle, da diese auf Basis der erfolgreichen Vorarbeiten eine gute Grundlage gelegt haben, um im Projektzeitraum wirklich tragfähige Ergebnisse zu erzielen. Mit dem Projekt wurde ein Beitrag zur Lösung anwendungsnaher Transportplanungsprobleme geleistet, aber auch algorithmisch und mathematisch in neue Bereiche vorgestoßen, besonders in der Kombination von quadratischen Optimierungstechniken mit stochastischen Einflüssen.

Angestrebte Ergebnisse

Das Ziel des Forschungsvorhabens ist das Hub-Location-Problem unter stochastischen Einflüssen zu betrachten. Dabei liegt der Schwerpunkt auf der Konstruktion von stochastischen und robusten Modellen für das Single-Allocation-Hub-Location-Problem, welche mit einer Kombination aus heuristischen und exakten Optimierungsverfahren gelöst werden.

Nach unserer Kenntnis sind quadratischen Optimierungstechniken mit stochastischen Einflüssen noch nicht in der Literatur beschrieben worden. Folglich ist unserer Forschungsvorhaben auch in einem allgemeineren mathematischen Kontext von Interesse.

Ansprechpartner: Prof. Dr.-Ing. Uwe Clausen

Förderung und Partner

Prof. Dr. Christoph Buchheim
Lehrstuhl für Diskrete Optimierung (LSV)
Fakultät für Mathematik
Technische Universität Dortmund