Latente Optimierung

Latente Optimierung ist ein Optimierungsparadigma, das von Lokad entwickelt wurde und sich schwierigen, komplexen kombinatorischen Problemen widmet. Sie bewältigt auch stochastische Probleme, die immer dann auftreten, wenn Unsicherheit besteht. Latente Optimierung stellt einen Durchbruch bei Herausforderungen wie der geplanten Ressourcenallokation dar. Im Gegensatz zu klassischen Solvern, die im Lösungsraum arbeiten, operiert die latente Optimierung im Strategieraum. Dieser Ansatz ermöglicht eine schnelle Re-Optimierung, wenn sich die Bedingungen ändern.

Technologieübersicht

Latente Optimierung, die 2024 eingeführt wurde, ist die zweite Generation universell einsetzbarer Optimierungstechnologien, die von Lokad entwickelt wurden. Sie bewältigt schwierigere kombinatorische Probleme als stochastischer diskreter Abstieg, wenn auch mit einer etwas reduzierten Skalierbarkeit.

Konzeptionell entwerfen die Supply Chain Scientists bei Lokad eine Datenverarbeitungspipeline, die folgende Schritte umfasst:

1. Bereite die historischen Daten vor.
2. Erzeuge probabilistische Prognosen.
3. Erzeuge eine robuste Entscheidungsstrategie.
4. Re-optimiere in letzter Minute unter veränderten Bedingungen.

Historische Daten werden unter Verwendung der allgemeinen Data-Engineering-Fähigkeiten von Envision aufbereitet; Envision ist Lokads domänenspezifische Sprache. Anschließend werden probabilistische Prognosen mithilfe von differenzierbarem Programmieren erzeugt, ein Paradigma, das sich ideal für probabilistische Modellierung eignet und in Envision als erstklassiges Element behandelt wird.

Anschließend wird latente Optimierung eingesetzt, um eine Entscheidungsstrategie zu generieren. Im Wesentlichen ist das Ergebnis der latenten Optimierung ein spezialisierter Solver, der passgenau auf das jeweilige Problem zugeschnitten ist. Schließlich kann diese Strategie unter den finalen, sich leicht verändernden Bedingungen ausgeführt – und gegebenenfalls erneut ausgeführt – werden, um die erforderlichen Entscheidungen zu treffen. Da die Strategie schnell läuft, kann sie interaktiv von den Beteiligten genutzt werden.

Alle vier Schritte – (1), (2), (3) und (4) – werden innerhalb von Envision durchgeführt.

Grenzen traditioneller Solver

Mathematische Optimierung ist ein ausgereifter Bereich der Informatik. Eine breite Palette an Solvern – sowohl proprietär als auch Open Source – steht auf dem Markt zur Verfügung. Leider erfüllt keine dieser bestehenden Technologien unsere Anforderungen, insbesondere bei der Bewältigung enger Planungsprobleme.

Branch-and-Bound-Algorithmen (und alle ihre Varianten) beruhen darauf, den zulässigen Bereich in kleinere Teilprobleme zu unterteilen (Branching) und mithilfe von Relaxierungen (Bounding) große Teile des Suchraums auszuschließen. Dieser Ansatz funktioniert bei supply chain problems schlecht, da diese zu offen sind. Obwohl der Lösungsraum strikt eingeschränkt ist, ist er dennoch enorm. Das bloße Erfüllen der Vorgaben reicht bei weitem nicht aus, um eine gute Lösung zu erzielen, was das grundlegende Konzept der Unterteilung untergräbt.

Lokale Suchalgorithmen (und all ihre Varianten) beruhen darauf, über eine oder mehrere aktuelle Lösungen zu iterieren und nahegelegene Varianten zu untersuchen. Leider erweist sich diese Methode ebenfalls als ineffizient, da das Konzept der „Lokalität“ in diesen Problemen nicht klar definiert ist. Angesichts der strengen Einschränkungen in diesen Szenarien verstoßen die meisten lokalen Anpassungen einer Lösung gegen so viele Vorgaben, dass der Suchprozess keine verbesserte Lösung finden kann.

Bei Lokad haben wir uns das Ziel gesetzt, bei schwierigen kombinatorischen Problemen einige Millionen Variablen skalieren zu können, und die Fähigkeit zu besitzen, bei veränderten Bedingungen binnen weniger Sekunden neu zu optimieren – selbst wenn diese Änderungen die ursprüngliche Lösung durch Kaskadeneffekte gänzlich ungültig machen.

Unter der Haube

Lokad verwendet einen unkonventionellen Ansatz bei der kombinatorischen Optimierung. Anstatt einen Standard-Solver anzubieten, gehen wir das Problem mittels eines spezialisierten Programmierparadigmas namens latente Optimierung an. Diese Methode ist entscheidend, um die Erkenntnisse und das Fachwissen unserer Supply Chain Scientists zu integrieren.

Die latente Optimierung führt eine alternative Darstellung des ursprünglichen Problems ein. Diese alternative Darstellung ist eine hochdimensionale Parametrisierung eines einfachen Solvers, der speziell für das jeweilige Problem zugeschnitten ist. Diese Parameter werden dann gelernt, indem der parametrisierte Solver iterativ auf das ursprüngliche Problem angewendet wird (von dem viele stochastische Varianten beinhalten). Im Kern ist die latente Optimierung ein Lernprozess.

Das Ergebnis der latenten Optimierung ist ein gut parametrisierter, einfacher Solver, der hochwertige Lösungen für das ursprüngliche Problem sowie dessen Varianten liefert.

Beispiel: Einsatzplanung an einem Luftfahrt-Produktionsstandort

Betrachten Sie einen Luftfahrtproduzenten und einen seiner Produktionsstandorte. An diesem Standort wird eine wichtige Flugzeugkomponente montiert. Ziel ist es, den Durchsatz des Standorts unter Berücksichtigung der verfügbaren Ressourcen (Personal und Industrieanlagen) zu maximieren.

Dieser Montageprozess umfasst etwa 100 unterschiedliche Arbeitsgänge. Außerdem gibt es rund 20 verfügbare Zeitfenster für die Durchführung dieser Arbeitsgänge, wobei jedes Zeitfenster unterschiedliche Eigenschaften aufweist. Bestimmte Arbeitsgänge können nur in spezifischen Zeitfenstern ausgeführt werden. Ein komplexer Abhängigkeitsgraph verbindet die Arbeitsgänge, doch im Gegensatz zu einer Automobilproduktionslinie bildet dieser Graph keine lineare Abfolge; es besteht erhebliche Flexibilität in der endgültigen Reihenfolge der Aufgaben.

Zudem erfordern einige Arbeitsgänge spezielle Ausrüstungsgegenstände, die am Standort nur in begrenzter Stückzahl vorhanden sind. Viele Arbeitsgänge hängen auch davon ab, dass der notwendige Lagerbestand zur Verfügung steht; manchmal verzögern sich essenzielle Teile. Bei den Arbeitsgängen variiert die Anzahl der Personen, die gleichzeitig daran arbeiten können, um die Fertigstellung zu beschleunigen – von 1 bis zu 5 Personen.

Eine Belegschaft von etwa 100 Technikern betreibt den Standort in Schichten von 20 bis 30 Personen. Jeder Techniker verfügt für jeden Arbeitsgang über einen von drei Qualifikationsstufen. Die höchste Stufe ermöglicht es dem Techniker, einen Arbeitsgang auszuführen und die von anderen geleistete Arbeit zu überprüfen. Die mittlere Stufe befähigt einen Techniker, seine eigene Arbeit auszuführen und selbst zu überprüfen. Die niedrigste Stufe erlaubt es einem Techniker, einen Arbeitsgang durchzuführen, setzt jedoch eine Überprüfung durch einen Kollegen auf der höchsten Qualifikationsstufe voraus.

Das Management des Produktionsstandorts wünscht einen minutengenauen Einsatzplan für die nächsten Wochen, in dem genau festgelegt wird, welcher Techniker an welchem Arbeitsgang für welche Komponente arbeitet (wobei jede Komponente einzeln durch eine Seriennummer identifiziert wird). Dieses Detailniveau ist entscheidend, um Sicherheit in die Solidität des Plans zu bringen.

Allerdings können sich die Bedingungen zu Beginn jeder Schicht verändern. Ein Mitarbeiter könnte aufgrund von Krankheit ausfallen oder ein Teil verzögert und somit nicht verfügbar sein. Wenn diese Probleme nicht umgehend behoben werden, führen sie schnell zu einer Kaskade von Ineffizienzen, wodurch Techniker und Ressourcen ungenutzt bleiben, während die Probleme behoben werden.

Mit latenter Optimierung kann das Standortmanagement einen detaillierten Einsatzplan erstellen, der in den kommenden Wochen Zehntausende von Aufgaben umfasst. Darüber hinaus kann das Tool im letzten Moment erneut ausgeführt werden, um unvorhergesehene Änderungen zu berücksichtigen. Zudem ist die neu generierte Lösung keine umfassende, willkürliche Neuanordnung des ursprünglichen Plans, sondern ein Zeitplan, der der anfänglichen Version sehr ähnlich ist und lediglich geringfügige Anpassungen zur Berücksichtigung der neuesten Bedingungen erfordert.