Optimal zum Bestimmungsort

Partner

Seit dem Sommersemester 2015 besteht eine Kooperation zwischen dem Lehrstuhl für Operations Research, dem Ford Global Data Insights & Analytics (GDIA) Team in Aachen und dem Ford Global Trade Services (GTS) Team aus Dearborn (USA). GTS ist innerhalb von Ford für die weltweite Verschiffung von Autos über weite Distanzen zuständig. Dabei geht es neben dem Aushandeln von Verträgen mit Spediteuren vor allem um die Zuteilung von produzierten Fahrzeugen zu Schiffen als kurzfristige, und um die Vorhersage der benötigten Schiffskapazitäten als mittelfristige Planungsaufgabe. Da Ford in den nächsten Jahren einen signifikanten Anstieg der auf dem Seeweg transportierten Autos erwartet (ca. 2 Millionen Autos pro Jahr), ist eine der höchsten Prioritäten diesen Prozess zu automatisieren und Fehler durch die manuelle Bearbeitung von unterschiedlichen Abteilungen zu vermeiden. Im gleichen Zug bietet die Steigerung des Volumens mehr Potential zur Optimierung verschiedener Zielfunktionen. Der OR Lehrstuhl liefert mit der eigens entwickelten und auf das Problem zugeschnittenen Software den Optimierungskern des Gesamtprojektes. 

Das Optimierungsproblem

Das zugrundeliegende Zuordnungsproblem ist intuitiv. Produzierte Autos müssen, nachdem sie von der Fabrik an den zugehörigen Hafen geliefert worden sind, auf Schiffe verladen werden,

1. deren Kapazität ausreicht,
2. die einen Hafen im Zielmarkt des Autos anfahren,
3. die später ablegen als das Auto am Hafen sein kann.

Da Autos unterschiedlicher Automobilfirmen durch den gleichen Spediteur verschifft werden, besteht zusätzlich ein gewisser Konkurrenzkampf um die Schiffskapazitäten. Die zur Verfügung stehende Kapazität eines Schiffes ergibt sich am Ende durch das vorher angefragte und später vom Spediteur bestätigte Volumen.

Eine qualitativ hochwertige Zuordnung wird von einer Vielzahl an zu optimierenden Zielen beeinflusst. So ist ein oft hoch priorisiertes Ziel die Reduzierung der Dwell Time, weniger treffend übersetzt als Verweildauer der Fahrzeuge an der Fabrik. Jedes Fahrzeug soll so schnell wie möglich verschifft werden, um Ressourcen zu sparen und eine hohe Kundenzufriedenheit zu generieren. Tendenziell ist dieses Kriterium für bereits an Kunden verkaufte Fahrzeuge, im Gegensatz zu Fahrzeugen die für den Händler bestimmt sind, wichtiger. Desweiteren sollen einzelne Zielmärkte oder bestimmte Fahrzeugtypen nicht bevorzugt werden. In diesem Fall ist das Ziel eine möglichst faire Verteilung von Fahrzeugtypen über die Zielmärkte eines Schiffes zu gewährleisten. Einige Schiffe besitzen zusätzlich zu ihrer Kapazität eine möglichst einzuhaltende untere Schranke an zu verschiffenden Fahrzeugen. Dieses Volumen ist vertraglich festgelegt, im Voraus bezahlt und gilt es somit nach Möglichkeit einzuhalten.

Zu guter Letzt, ist der erwirtschaftete Profit seitens Ford als Konzern zu berücksichtigen. Dieser ist abhängig von dem Fahrzeugtyp, der Ausstattung, dem Status (Fahrzeug verkauft/nicht verkauft), dem gewählten Spediteur und vielen weiteren Faktoren. Um diese offensichtlich zum Teil widersprüchlichen Ziele in Einklang zu bringen und das Resultat für den Anwender (soweit möglich) nachvollziehbar zu machen, braucht es einen auf das Problem zugeschnittenen Optimierungsalgorithmus, der flexibel auf die Wünsche der Anwender reagieren kann.

Kombiniert man die resultierende mehrwöchige robuste Zuordnung der Autos auf Schiffe mit dem geplanten Produktionsvolumen der Fabriken, lässt sich für die mittelfristige Planung (2-3 Monate im Voraus) eine möglichst genaue, benötigte Schiffskapazität für einzelne Schiffe in der Zukunft vorhersagen. Diese Vorhersage wird genutzt, um die benötigte Schiffskapazität bei den Spediteuren anzufragen und mit fortschreitender Zeit zu verfeinern. 

Wissenschaftlicher Hintergrund

Eine Möglichkeit das bereits beschriebe Zuordnungsproblem zu modellieren bieten gemischt-ganzzahlige lineare Programme (MILP) auf der Basis von Flussnetzwerken. In diesem Fall repräsentiert eine Einheit Fluss ein Auto. Es existieren Knoten für Autos und Schiffe, wobei die Schiffskapazität beispielsweise durch die Flusskapazität der ausgehenden Kanten kodiert wird. Eine Kante von Autoknoten zu Schiffsknoten symbolisiert die Möglichkeit einer Zuordnung, die durch Versenden von Fluss realisiert wird.

Jede der oben genannten Zielfunktionen lässt sich generisch durch Definition der Kantenkosten, Anpassung der Flusskapazitäten oder Veränderung des Flussnetzwerkes realisieren. Die Priorisierung der Zielfunktionen wird vom Anwender vorgegeben. Der Graph wird in ein MILP übersetzt, das als Lösung die optimale Zuordnung von Autos auf Schiffe mit Bezug auf die gerade aktive Zielfunktion besitzt. Der optimale Zielfunktionswert wird gespeichert und für alle weiteren Durchläufe durch eine zusätzliche Nebenbedingung im MILP sichergestellt. Die Lösungsstruktur, also die explizite Zuordnung von Autos auf Schiffe, wird „vergessen“, um für niedriger priorisierte Zielfunktionen den maximalen Grad an Freiheit zu garantieren. Mit absteigender Priorität werden die restlichen Zielfunktionen optimiert.

Im Gesamten erhält man eine, unter der hierarchische Ordnung der Zielfunktionen definierte, optimale Zuordnung von Autos auf Schiffe. Durch Relaxierung der hinzugefügten Nebenbedingungen kann dieser Prozess auf Wunsch des Kunden, und zu Gunsten der Nachvollziehbarkeit, flexibler gestaltet werden.