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

Sintesi Tecnica: Proxy di Apprendimento per Programmi Stocastici Contestuali Sequenziali

Formulazione del Problema

Il documento affronta la sfida dei programmi stocastici contestuali sequenziali nei sistemi decisionali in tempo reale, concentrandosi specificamente sull'adempimento degli ordini omnicanale nella grande distribuzione elettronica. In questo contesto, un decisore deve assegnare gli ordini in arrivo a centri di distribuzione (DC) e servizi di trasporto sotto incertezza riguardante i tempi di consegna e la domanda futura.

La difficoltà principale risiede nel vincolo di latenza: sebbene sia possibile generare decisioni di alta qualità offline utilizzando la Approssimazione della Media Campionaria Contestuale (C-SAA) risolta tramite solver di ottimizzazione commerciali, questi solver richiedono tipicamente secondi o minuti per singola istanza. Ciò è insufficiente per i periodi operativi di picco (ad esempio, vendite festive) dove sono richieste risposte nell'ordine dei sub-secondi per gestire centinaia di ordini al minuto. Di conseguenza, i sistemi operativi spesso ricorrono a euristiche più semplici che ignorano l'incertezza modellata, portando a costi e livelli di servizio subottimali.

Il problema è formalizzato come un programma stocastico contestuale a due stadi:

1. Primo Stadio: Assegnazione immediata dei prodotti di un ordine a DC e vettori sulla base del contesto corrente (attributi dell'ordine, livelli di inventario, costi dei vettori) e di scenari campionati dell'incertezza futura.
2. Secondo Stadio: Ricorso aggregato per ordini futuri ($t+1 \dots T$), che rappresenta il costo atteso futuro di spedizione e di rottura dello stock (stockout) dato il consumo di inventario dalla decisione del primo stadio.

L'obiettivo è minimizzare i costi totali attesi, inclusi le spese di spedizione, le penalità asimmetriche sui tempi di consegna (ritardo vs anticipo), gli sconti per consolidamento e le penalità per stockout, rispettando i vincoli di inventario.

Metodologia

Gli autori propongono un proxy di ottimizzazione basato sull'apprendimento che sostituisce la chiamata al solver per ogni epoca con un singolo passaggio in avanti (forward pass) di una rete neurale, seguito da un decoder che garantisce la fattibilità.

1. Architettura: Rete Neurale Gerarchica con Scenari Incorporati
A differenza dei precedenti proxy di ottimizzazione che si affidano a previsioni puntuali, questo modello è consapevole degli scenari (scenario-aware). Prende come input:

• Caratteristiche Contestuali: Dettagli dell'ordine, stati dell'inventario dei DC e matrici dei costi dei vettori.
• Insiemi di Scenari: Realizzazioni campionate della domanda futura e delle deviazioni nei tempi di consegna, generate da previsori adattati (Multi-Horizon Quantile RNN per la domanda, Multi-Quantile MLP per i tempi di consegna).

La rete utilizza un encoder di tipo DeepSets per elaborare insiemi di scenari non ordinati, mediando gli embedding per approssimare la struttura di aspettativa dell'obiettivo C-SAA. L'architettura è gerarchica:

• Testa DC: Predice un logit per ogni centro di distribuzione.
• Testa Vettore: Predice un logit per ogni servizio di trasporto condizionato al DC selezionato.
  Questa fattorizzazione ($p(j) \cdot p(k|j)$) riduce la complessità dell'apprendimento dell'intero spazio di assegnazione congiunta.

2. Strategia di Addestramento: Funzione di Perdita Composta
Il proxy viene addestrato offline su etichette generate dal solver C-SAA. L'obiettivo di addestramento combina tre termini:

• Imitazione delle Etichette (Perdita di Selezione): Perdita di entropia incrociata rispetto alle scelte primarie di DC e vettore derivate dalla soluzione C-SAA.
• Penalità di Violazione dei Vincoli: Un termine autosupervisionato che utilizza lo Straight-Through Gumbel-Softmax per penalizzare le assegnazioni che eccedono l'inventario disponibile, assicurando che il modello impari a rispettare i vincoli rigidi.
• Allineamento dei Costi: Un regolarizzatore autosupervisionato che sposta la massa di probabilità verso coppie (DC, vettore) a basso costo basandosi sui costi immediati osservati negli scenari campionati.

3. Inferenza: Decodifica Pesata sull'Inventario
Al runtime, la rete neurale produce logit che vengono convertiti in probabilità. Un decoder dedicato garantisce quindi la fattibilità:

• Ripesa le probabilità predette in base alla copertura frazionaria dell'inventario ($min\{Inv/q, 1\}$) di ogni DC.
• Esegue una scansione greedy di DC e vettori idonei, assegnando la domanda finché l'ordine non è soddisfatto o l'inventario non è esaurito.
• Questo processo assicura che la decisione finale sia strettamente fattibile (rispettando i limiti di inventario e la soddisfazione della domanda) in un tempo di $O(|J| \log |J| + |J||K|)$.

Contributi Chiave

Il documento presenta quattro contributi principali:

1. Proxy Condizionato agli Scenari: Un'architettura innovativa che si condiziona esplicitamente su insiemi di scenari campionati anziché su previsioni puntuali, catturando sia i costi stocastici immediati che l'impatto sequenziale del consumo di risorse.
2. Modello di Adempimento Sequenziale: Una formulazione stocastica contestuale a due stadi che collega esplicitamente le assegnazioni immediate degli ordini al costo opportunità del consumo di inventario per ordini futuri.
3. Garanzie Teoriche: Gli autori dimostrano che il decoder pesato sull'inventario produce una decisione fattibile con una complessità di tempo logaritmo-lineare. Dimostrano inoltre che il costo atteso del proxy è un limite superiore dell'obiettivo ottimale a due stadi e che le sue prestazioni fuori campione ammettono stimatori non distorti e coerenti.
4. Validazione Empirica: Uno studio computazionale completo utilizzando un simulatore calibrato con i dati transazionali di JD.com e dati proprietari dei vettori.

Risultati

Nel simulatore calibrato, il proxy proposto dimostra miglioramenti significativi rispetto sia ai baseline basati su solver che alle consolidate politiche euristiche:

• Latenza: La latenza decisionale è ridotta di circa 2.800× rispetto al riferimento C-SAA a campione finito online, consentendo risposte sub-secondo.
• Efficienza dei Costi: Il proxy migliora i costi di adempimento realizzati del 3,3% rispetto al baseline C-SAA (che è già di alta qualità ma lento) e riduce i costi totali realizzati di almeno il 10,7% rispetto alle politiche di adempimento consolidate.
• Livello di Servizio: Il proxy riduce di circa la metà il tasso di ritardo nelle consegne rispetto ai più forti baseline classici, migliorando direttamente la metrica di consegna puntuale che guida la soddisfazione del cliente.

Significato

Il documento sostiene che per operazioni ad alto volume e critiche per la latenza, come l'e-commerce, il compromesso tra qualità dell'ottimizzazione e velocità computazionale è un collo di bottiglia critico. Sviluppando un proxy che apprende da etichette generate da solver pur modellando esplicitamente l'incertezza attraverso gli scenari, gli autori dimostrano che è possibile ottenere una qualità decisionale quasi ottimale con velocità di inferenza in tempo reale. Questo approccio colma il divario tra i benefici teorici dell'ottimizzazione stocastica contestuale e i vincoli pratici dei sistemi decisionali su scala industriale in tempo reale. Il lavoro suggerisce che tali proxy possono essere un'alterna valida alle euristiche in contesti in cui i solver tradizionali sono troppo lenti per essere implementati online.