🔢 mathematics

Learning Optimization Proxies for Sequential Contextual Stochastic Programs: An Order Fulfillment Application

Dieses Paper schlägt eine lernbasierte Optimierungsproxy vor, die ein szenarioeingebettetes neuronales Netzwerk mit einem durchführheitserzwingenden Decoder kombiniert, um sequentielle kontextuelle stochastische Programme für die Omnichannel-Auftragsabwicklung zu lösen, wobei eine Entscheidungslatenz im Sub-Sekundenbereich erreicht wird, während gleichzeitig die Erfüllungskosten und die Raten verspäteter Lieferungen im Vergleich zu traditionellen Solvern und etablierten Policies signifikant reduziert werden.

Ursprüngliche Autoren: Tinghan Ye, Shuaicheng Tong, Changkun Guan, Beste Basciftci, Pascal Van Hentenryck

Veröffentlicht 2026-06-25

📖 4 Min. Lesezeit🧠 Tiefgang

CC0 1.0

Ursprüngliche Autoren: Tinghan Ye, Shuaicheng Tong, Changkun Guan, Beste Basciftci, Pascal Van Hentenryck

Originalarbeit unter CC0 1.0 der Gemeinfreiheit gewidmet (http://creativecommons.org/publicdomain/zero/1.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie sind der Manager eines riesigen, superschnellen Online-Shops (wie JD.com). Jede Sekunde geben tausende Kunden Bestellungen auf. Ihre Aufgabe ist es, sofort zu entscheiden, aus welchem Lager jedes Teil verschickt wird und welcher Lieferwagen verwendet werden soll.

Dies ist nicht nur ein einfaches Spiel nach dem Motto „Wähle das nächste Lagerhaus“. Es ist ein hochriskantes Puzzle mit drei großen Problemen:

Unsicherheit: Sie wissen nicht genau, wann der LKW ankommt (Verkehr, Wetter) oder wie viele weitere Bestellungen in der nächsten Stunde eingehen werden.
Inventar: Wenn Sie ein beliebtes Produkt jetzt aus Lager A an einen Kunden senden, haben Sie es Ihnen vielleicht nicht mehr übrig für einen Kunden, der 10 Minuten später bestellt.
Geschwindigkeit: Sie haben weniger als eine Sekunde Zeit, um diese Entscheidung zu treffen. Wenn Sie zu lange mit der Berechnung des „perfekten“ Ergebnisses warten, wird der Kunde verärgert und das System stürzt ab.

Der alte Weg: Der „Supercomputer“, der zu langsam ist

Traditionell nutzen Unternehmen zur Lösung dieses Problems einen „Supercomputer“ (einen Optimierungs-Solver). Er betrachtet alle möglichen zukünftigen Szenarien (Was wäre, wenn es regnet? Was wäre, wenn 1.000 weitere Leute Schuhe bestellen?) und berechnet einen mathematisch perfekten Plan.

Das Gute: Er findet einen sehr guten Plan.
Das Schlechte: Er benötigt Sekunden oder sogar Minuten zum Ausführen. In einem Echtzeit-System, in dem man Antworten in Millisekunden benötigt, ist das nutzlos. Es ist, als würde man versuchen, ein Sudoku-Rätsel mit einem Supercomputer zu lösen, während ein Rennwagen an einem vorbeirauscht.

Der neue Weg: Der „smarte Stellvertreter“ (Die Lösung der Arbeit)

Die Autoren haben einen lernbasierten Optimierungs-Proxy entwickelt. Stellen Sie sich dies als einen superintelligenten Praktikanten vor, der die Antworten des Supercomputers monatelang studiert hat.

So arbeitet dieser „Praktikant“:

Das Training (Offline): Der Praktikant sitzt in einem ruhigen Raum (offline) und beobachtet den Supercomputer bei der Lösung tausender fiktiver Bestellszenarien. Er lernt die Muster: „Wenn es regnet und der Kunde in New York ist, wählt der Supercomputer normalerweise Lager B.“ Er lernt, den Experten nachzuahmen.
Das „Szenario-eingebettete“ Gehirn: Im Gegensatz zu einer normalen KI, die nur rät, ist dieser Praktikant szenariobewusst. Er schaut nicht nur auf die aktuelle Bestellung; er blickt in eine „Kristallkugel“ möglicher Zukünfte (Szenarien), die vom System generiert wurden. Er fragt sich: „Wenn ich jetzt Lager A wähle, was passiert mit meinem Inventar für die nächsten 100 Bestellungen?“ Er versteht die Kettenreaktionen.
Der „Decoder“ (Das Sicherheitsnetz): Manchmal macht der Praktikant einen Fehler und schlägt einen Plan vor, der unmöglich ist (wie etwa den Versand von 5 Artikeln, obwohl das Lager nur 3 hat). Um dies zu korrigieren, besitzt das System einen Decoder.
- Analogie: Stellen Sie sich vor, der Praktikant schreibt eine Einkaufsliste. Der Decoder ist der Filialleiter, der die Regale überprüft. Wenn auf der Liste „5 Äpfel“ steht, das Regal aber nur „3“ hat, passt der Manager die Liste sofort auf „3 Äpfel“ an und verschiebt den Rest in ein anderes Geschäft. Dies geschieht in einem Bruchteil einer Sekunde und stellt sicher, dass der Plan immer zulässig und machbar ist.
Das Ergebnis: Anstatt auf den Supercomputer zu warten, liefert der Praktikant in Millisekunden eine Antwort (ein einziger Vorwärtspass).

Was haben sie herausgefunden?

Das Team hat dieses System unter Verwendung realer Daten von JD.com in einer Simulation getestet. Hier sind die Ergebnisse:

Geschwindigkeit: Das neue System ist 2.800 Mal schneller als die alte Supercomputer-Methode. Es verkürzt die Zeit von Sekunden auf einen Bruchteil einer Sekunde.
Kosten: Obwohl es schneller ist, hat es sogar 3,3 % mehr Geld gespart als die langsame Supercomputer-Methode.
Kundenzufriedenheit: Im Vergleich zu den heute üblichen Standardregeln, hat dieses neue System verspätete Lieferungen halbiert und die Gesamtkosten um über 10 % gesenkt.

Das große Ganze

Diese Arbeit beweist, dass man sich nicht zwischen Geschwindigkeit und Qualität entscheiden muss. Indem man ein neuronales Netzwerk darauf trainiert, wie ein Experte zu agieren, und dann einen schnellen „Sicherheitscheck“ (den Decoder) hinzufügt, um unmögliche Züge zu korrigieren, kann man nahezu perfekte Entscheidungen in Echtzeit treffen.

Es ist, als würde man einen langsamen, perfekten Schachgroßmeister durch einen blitzschnellen Großmeister ersetzen, der die besten Züge auswendig kennt und einen Schiedsrichter hat, der ihn sofort bei illegalen Zügen korrigiert. Das Ergebnis ist ein System, das sowohl schnell als auch intelligent ist, die Kunden glücklich macht und die Kosten niedrig hält.

Technisches Resümee: Lernbasierte Optimierungs-Proxies für sequentielle kontextuelle stochastische Programme

Problemformulierung

Die Arbeit adressiert die Herausforderung sequentieller kontextueller stochastischer Programme in Echtzeit-Entscheidungssystemen, mit einem spezifischen Fokus auf die Omnichannel-Auftragsabwicklung im großflächigen E-Commerce. In diesem Szenario muss ein Entscheidungsträger eingehende Bestellungen unter Unsicherheit bezüglich der Lieferzeiten und der zukünftigen Nachfrage bestimmten Distributionszentren (DCs) und Speditionsdiensten zuordnen.

Die Kernschwierigkeit liegt in der Latenzbeschränkung: Während hochwertige Entscheidungen offline mittels kontextueller Sample Average Approximation (C-SAA) unter Verwendung kommerzieller Optimierungs-Solver generiert werden können, benötigen diese Solver typischerweise Sekunden bis Minuten pro Instanz. Dies ist unzureichend für Spitzenzeiten im operativen Betrieb (z. B. Feiertage), in denen eine Reaktion im Sub-Sekunden-Bereich erforderlich ist, um hunderte Bestellungen pro Minute zu bearbeiten. Folglich greifen operative Systeme oft auf einfachere Heuristiken zurück, welche die modellierte Unsicherheit ignorieren, was zu suboptimalen Kosten und Service-Level führt.

Das Problem wird als zweistufiges kontextuelles stochastisches Programm formalisiert:

Erste Stufe: Unmittelbare Zuweisung der Produkte einer Bestellung an DCs und Spediteure basierend auf dem aktuellen Kontext (Bestellattribute, Lagerbestände, Frachtkosten) und den Stichproben-Szenarien zukünftiger Unsicherheit.
Zweite Stufe: Aggregierte Erholung (Recourse) für zukünftige Bestellungen ( $t+1 \dots T$ ), welche die erwarteten zukünftigen Versand- und Out-of-Stock-Kosten darstellt, gegeben den durch die erststufige Entscheidung konsumierten Bestand.

Das Ziel ist die Minimierung der gesamten erwarteten Kosten, einschließlich Versandkosten, asymmetrischer Lieferzeit-Strafen (verspätet vs. frühzeitig), Konsolidierungsrabatte und Out-of-Stock-Strafen, unter Einhaltung der Lagerbestandsbeschränkungen.

Methodik

Die Autoren schlagen einen lernbasierten Optimierungs-Proxy vor, der den pro Epoche erfolgenden Solver-Aufruf durch einen einzigen Vorwärtsdurchlauf eines neuronalen Netzes ersetzt, gefolgt von einem fertigkeitserzwingenden Decoder.

1. Architektur: Szenario-eingebettetes hierarchisches neuronales Netzwerk
Im Gegensatz zu bisherigen Optimierungs-Proxies, die auf Punktprognosen basieren, ist dieses Modell szenariobewusst. Es nimmt als Input:

Kontextuelle Merkmale: Bestelldetails, Lagerbestände der DCs und Frachtkostenmatrizen.
Szenario-Sets: Realisierungen der zukünftigen Nachfrage und der Abweichungen der Lieferzeiten, die durch angepasste Forecaster (Multi-Horizon Quantile RNN für die Nachfrage, Multi-Quantile MLP für die Lieferzeiten) generiert wurden.

Das Netzwerk verwendet einen DeepSets-ähnlichen Encoder, um ungeordnete Szenario-Sets zu verarbeiten, wobei die Einbettungen gemittelt werden, um die Erwartungsstruktur der C-SAA-Zielfunktion zu approximieren. Die Architektur ist hierarchisch aufgebaut:

DC-Head: Prädiziert einen Logit für jedes Distributionszentrum.
Carrier-Head: Prädiziert einen Logit für jeden Speditionsdienst bedingt durch das gewählte DC.
Diese Faktorisierung ( $p(j) \cdot p(k|j)$ ) reduziert die Komplexität beim Erlernen des vollen gemeinsamen Zuweisungsraums.

2. Trainingsstrategie: Komposit-Verlustfunktion
Der Proxy wird offline auf Labels trainiert, die vom C-SAA-Solver generiert wurden. Das Trainingsziel kombert drei Terme:

Label-Imitation (Selection Loss): Cross-Entropy-Loss gegenüber den primären DC- und Carrier-Wahlen, die aus der C-SAA-Lösung abgeleitet wurden.
Constraint-Verletzungsstrafe: Ein selbstüberwachter Term unter Verwendung von Straight-Through Gumbel-Softmax, der Zuweisungen bestraft, die die verfügbaren Bestände überschreiten, um sicherzustellen, dass das Modell lernt, harte Constraints einzuhalten.
Kosten-Ausrichtung: Ein selbstüberwachter Regularisierer, der die Wahrscheinlichkeitsmasse hin zu kostengünstigen (DC, Carrier)-Paaren zieht, basierend auf den unmittelbar beobachteten Kosten in den Stichproben-Szenarien.

3. Inferenz: Bestandsgewichtete Dekodierung
Zur Laufzeit gibt das neuronale Netz Logits aus, die in Wahrscheinlichkeiten umgewandelt werden. Ein dedizierter Decoder erzwingt anschließend die Durchführbarkeit:

Er gewichtet die prädizierten Wahrscheinlichkeiten durch die fraktionelle Bestandsabdeckung ( $\min\{Inv/q, 1\}$ ) jedes DCs neu.
Er führt einen Greedy-Scan über berechtigte DCs und Carrier durch und weist die Nachfrage zu, bis die Bestellung erfüllt oder der Bestand erschöpft ist.
Dieser Prozess stellt sicher, dass die endgültige Entscheidung strikt durchführbar ist (unter Einhaltung der Bestandsgrenzen und der Bedarfsdeckung) in einer Laufzeit von $O(|J| \log |J| + |J||K|)$ .

Zentrale Beiträge

Die Arbeit leistet vier wesentliche Beiträge:

Szenario-konditionierter Proxy: Eine neuartige Architektur, die explizit auf Stichproben-Szenario-Sets konditioniert statt auf Punktprognosen, wodurch sowohl unmittelbare stochastische Kosten als auch die sequentiellen Auswirkungen des Ressourcenverbrauchs erfasst werden.
Sequentielles Fulfillment-Modell: Eine zweistufige kontextuelle stochastische Formulierung, die die unmittelbaren Auftragszuweisungen explizit mit den Opportunitätskosten des Bestandsverbrauchs für zukünftige Bestellungen verknüpft.
Theoretische Garantien: Die Autoren beweisen, dass der bestandsgewichtete Decoder eine durchführbare Entscheidung mit logarithmisch-linearer Laufzeitkomplexität liefert. Sie etablieren zudem, dass die erwarteten Kosten des Proxys die optimale zweistufige Zielfunktion nach oben begrenzen und dass dessen Out-of-Sample-Performance unverzerrte, konsistente Schätzer zulässt.
Empirische Validierung: Eine umfassende computergestützte Studie unter Verwendung eines Simulators, der mit Transaktionsdaten von JD.com und proprietären Speditionsdaten kalibriert wurde.

Ergebnisse

Im kalibrierten Simulator zeigt der vorgeschlagene Proxy signifikante Verbesserungen gegenüber sowohl Solver-basierten Baselines als auch etablierten Heuristik-Policies:

Latenz: Die Entscheidungs-Latenz wird im Vergleich zur Online-Finite-Sample-C-SAA-Referenz um etwa das 2.800-fache reduziert, was Antworten im Sub-Sekunden-Bereich ermöglicht.
Kosteneffizienz: Der Proxy verbessert die realisierten Fulfillment-Kosten um 3,3 % relativ zur C-SAA-Baseline (welche bereits qualitativ hochwertig, aber langsam ist) und reduziert die gesamten realisierten Kosten um mindestens 10,7 % im Vergleich zu etablierten Fulfillment-Policies.
Service-Level: Der Proxy halbiert in etwa die Rate verspäteter Lieferungen im Vergleich zu den stärksten klassischen Baselines, was die Kennzahl der rechtzeitigen Lieferung, welche die Kundenzufriedenheit maßgeblich beeinflusst, direkt verbessert.

Bedeutung

Die Arbeit argumentiert, dass für hochvolumige, latenzkritische Operationen wie den E-Commerce-Fulfillment der Trade-off zwischen Optimierungsqualität und Rechengeschwindigkeit ein kritischer Flaschenhals ist. Durch die Entwicklung eines Proxys, der von Solver-generierten Labels lernt und gleichzeitig die Unsicherheit durch Szenarien explizit modelliert, zeigen die Autoren, dass es möglich ist, nahezu optimale Entscheidungsqualität mit Echtzeit-Inferenzgeschwindigkeiten zu erreichen. Dieser Ansatz schließt die Lücke zwischen den theoretischen Vorteilen der kontextuellen stochastischen Optimierung und den praktischen Beschränkungen industrieller, echtzeitfähiger Entscheidungssysteme. Die Arbeit legt nahe, dass solche Proxies eine praktikable Alternative zu Heuristiken in Umgebungen darstellen können, in denen traditionelle Solver zu langsam für den Online-Einsatz sind.