Arbeitsgruppe für Supply Chain Services des Fraunhofer IISKostenminimale Transportplanung unter Zeitdruck
Die Disposition von Warenlieferungen steht häufig vor der Herausforderung täglich mehrere tausend Lieferungen zu verplanen und dabei aus unzähligen interkontinentalen Alternativrouten auszuwählen. Auf den einzelnen Teilabschnitten muss zudem zwischen verschiedenen Verkehrsträgern und Verträgen mit komplexen Staffelpreisen sowie starren Ladungsrestriktionen gewählt werden. Diese Aufgaben sind durch manuelle Planung kaum zu bewältigen.
Deshalb hat sich die Arbeitsgruppe für Supply Chain Services des Fraunhofer IIS gemeinsam mit Praxispartnern der Herausforderung angenommen, mittels Methoden der Mathematischen Optimierung nicht nur automatisiert gültige Transportpläne in einer ambitionierten Rechenzeit zu generieren, sondern dabei auch die entstehenden Transportkosten zu minimieren.
Mittels Mixed-Integer Programming hin zur Optimalität
Diese Komplexität kann aufgelöst werden, indem die Fragestellung in einer für das Lösungsverfahren geeigneten Art und Weise modelliert wird. Ein sogenanntes gemischt ganzzahliges Optimierungsmodell (Mixed.Integer Programm) beschreibt das Problem mathematisch und dient als Basis, weil es sich für besonders effiziente Suchstrategien eignet. Das eigentliche Lösungsverfahren namens Branch and Cut sucht innerhalb von allen möglichen, zulässigen Sendungs-Plänen nach dem Besten und erlaubt es zudem eine Schranke für das bestmögliche zu erreichende Ergebis zu ermitteln. Daraus ergibt sich für die gegebende Problemklasse mit ausreichend Laufzeit ein mathematisch beweisbares, globales Kostenoptimum.
In die Modellierung fließen unter anderem Zeitfenster und diverse Restriktionen der Ladungskonsolidierung bezüglich der drei Eigenschaften – Gewicht, Volumen und Lademeter – ein. Hinzu kommt die darauf basierende Kostenkalkulation, welche diverse multidimensionale Staffelpreis-Typen nach denselben drei Ladungseigenschaften abbildet.
Da eine solche staffelbasierte Ladungskonsolidierung ein mathematisch anspruchsvolles Teilproblem darstellt, kann die Berechnungsdauer für eine Instanz über tausende Ladungen mit dem Basisalgorithmus durchaus viele Stunden dauern. Häufig bleibt im Praxiseinsatz jedoch nicht so viel Zeit, da die Sendungen für den Folgetag zeitnah beauftragt werden müssen.
Aufteilung der Probleme als Lösungsansatz
Um das Problem zu lösen unterteilt im ersten Schritt eine auf graphentheoretischen Algorithmen basierende Partitionierung die Tagesplanung in mehrere kleine, möglichst unverflochtene Teilprobleme. Dabei werden die Sendungsanfragen zusammengepackt, welche potenziell auf gemeinsamen Teilstrecken konsolidiert werden könnten, während nahezu unabhängige Sendungen in andere, ähnlich große Teilprobleme gepackt werden. Eine solche Dekomposition ermöglicht dann im zweiten Schritt das separate Lösen in sehr geringer Laufzeit und behält dennoch das ökonomische Potential der günstigsten Ladungskonsolidierungen bei.
Das entwickelte, mehrstufige Lösungsverfahren kann grundsätzlich auf einige verwandte Fragestellungen übertragen werden. Sowohl bezüglich einzelner Details der Unternehmens-Merkmale als auch bezüglich der Perspektive der Akteure: eine optimierte intermodale Ladungskonsolidierung kann zum einen den Speditionen und zum anderen den Planenden bei der Beauftragung von hohen Sendungsanzahlen zugutekommen. Und dabei kann mit adäquater Rechenzeit stets eine mathematisch nachweisbar günstigste Lösung gewährleistet werden.