Discesa Discreta Stocastica

L’ottimizzazione stocastica comprende una classe di problemi di ottimizzazione matematica in cui la funzione obiettivo varia a causa dell’incertezza. Date l’incertezza irriducibile del futuro, quasi tutti i problemi decisionali della supply chain si qualificano come problemi di ottimizzazione stocastica. Un ottimizzatore stocastico è un componente fondamentale dell’ottimizzazione della supply chain: utilizza previsioni probabilistiche come input e restituisce decisioni ottimizzate corrette per il rischio.

Lokad ha introdotto un approccio specifico a tale ottimizzazione, noto come discesa discreta stocastica. Questo paradigma di programmazione affronta specificamente la complessità dei problemi della supply chain che coinvolgono l’incertezza, basandosi sul concetto più ampio di ottimizzazione stocastica per fornire decisioni robuste su larga scala.

Allegoria astratta della sfida dell'ottimizzazione stocastica

Panoramica della tecnologia

Dal 2016, Lokad ha ottimizzato prevalentemente le supply chain attraverso previsioni probabilistiche. Senza previsioni probabilistiche, le decisioni ottimizzate diventano inevitabilmente fragili, suscettibili anche a lievi variazioni nella domanda o nei tempi di consegna. Al contrario, le decisioni ottimizzate contro previsioni probabilistiche sono robuste. Anche se le decisioni robuste possono essere calcolate utilizzando euristiche relativamente semplici “avide”, tali euristiche spesso falliscono nel gestire vincoli più complessi.

Nel 2021, Lokad ha introdotto la sua prima tecnologia di ottimizzazione stocastica generale, che chiamiamo discesa discreta stocastica. Questa innovazione affronta i difetti delle euristiche avide quando si trovano di fronte a situazioni non lineari della supply chain. Concettualmente, gli Scienziati della Supply Chain di Lokad progettano un flusso di elaborazione dati con i seguenti passaggi:

Preparare i dati storici.
Generare previsioni probabilistiche.
Produrre decisioni robuste.

I dati storici vengono preparati utilizzando le capacità di ingegneria dati generali di Envision, Envision essendo il linguaggio specifico del dominio di Lokad. Le previsioni probabilistiche vengono quindi prodotte attraverso programmazione differenziabile, un paradigma ideale per la modellazione probabilistica, riconosciuto come cittadino di prima classe in Envision. Infine, le decisioni robuste vengono derivate utilizzando la discesa discreta stocastica, fornita come paradigma di programmazione all’interno di Envision.

In definitiva, i passaggi (1), (2) e (3) vengono tutti eseguiti all’interno di Envision.

Risolutori tradizionali e i loro limiti

L’ottimizzazione matematica è un’area ben consolidata all’interno dell’informatica. La maggior parte dei prodotti software dedicati all’ottimizzazione matematica sono confezionati come risolutori. Ogni risolutore offre tipicamente il proprio linguaggio specifico del dominio (DSL), consentendo agli utenti di ottimizzare matematicamente una specifica classe di problemi. Anche se sul mercato esistono molti risolutori, comprese diverse opzioni open-source, nessuno affronta adeguatamente le realtà dei problemi della supply chain.

Molti risolutori gestiscono il caso stocastico. Quasi tutte le soluzioni esistenti si concentrano sullo scenario deterministico, dove l’incertezza è assente. Purtroppo, non è possibile “riutilizzare” semplicemente un risolutore deterministico per casi stocastici senza introdurre un livello di approssimazione inaccettabile.
La maggior parte dei risolutori non è sufficientemente scalabile. I problemi della supply chain possono diventare estremamente grandi: un milione di SKU possono tradursi in decine di milioni di variabili una volta modellate per l’ottimizzazione. Partizionare la supply chain solo per ospitare il risolutore non è fattibile. Il risolutore deve gestire nativamente decine di milioni di variabili.
Molti risolutori mancano di espressività adeguata. Spesso la funzione obiettivo non può essere considerata lineare, quadratica o persino convessa. Non è accettabile distorcere il problema sotto semplici ipotesi matematiche solo per adattarsi ai vincoli del risolutore. Di conseguenza, i risolutori devono offrire paradigmi di programmazione altamente espressivi.

Dopo aver esaminato il panorama esistente degli strumenti di ottimizzazione matematica, abbiamo concluso che lo sviluppo della nostra tecnologia era l’unica soluzione praticabile.

Sotto il cofano

Lokad adotta un approccio piuttosto non convenzionale all’ottimizzazione stocastica. Piuttosto che confezionare la tecnologia come un risolutore convenzionale, affrontiamo il problema attraverso un paradigma di programmazione dedicato noto come discesa discreta stocastica. Questo approccio è cruciale per sfruttare le intuizioni e l’esperienza dei nostri Scienziati della Supply Chain.

Questo paradigma di programmazione sfrutta la discesa del gradiente stocastico (SGD) perché scala estremamente bene, di ordini di grandezza oltre i metodi tradizionali di ottimizzazione non convessa. Tuttavia, SGD non è naturalmente adatto ai problemi discreti (e praticamente tutti i problemi della supply chain sono discreti). Poiché le quantità di riassortimento, produzione o trasferimento sono intere, i risultati frazionari non hanno significato.

Per superare questa limitazione, la discesa discreta stocastica introduce una rappresentazione alternativa differenziabile del problema originale. Questa rappresentazione presenta un insieme più ampio di dimensioni continue, reali e funge efficacemente da parametrizzazione della soluzione discreta. A differenza del modello discreto originale, dove i gradienti degenerano a zero a causa degli effetti interi, questa alternativa produce gradienti non degeneri adatti per SGD.

La principale limitazione della discesa discreta stocastica è la sua incapacità di affrontare problemi combinatori veramente difficili, in cui le soluzioni sono così fortemente vincolate che non possono essere iterate attraverso alcun tipo di discesa diretta. Tali problemi richiedono ottimizzazione latente, una tecnica di ottimizzazione successiva sviluppata anche da Lokad.

Esempi

Ottimizzare le decisioni di fronte a un futuro incerto è una sfida. Molti scenari della supply chain richiedono un’ottimizzazione stocastica per una corretta risoluzione.

Riassortimenti di negozi di moda

Consideriamo una rete di vendita che rifornisce i negozi con specifici obiettivi di assortimento. Ad esempio, garantire la disponibilità di tutte le taglie per un capo d’abbigliamento è spesso più critico che offrire ogni colore, soprattutto se alcuni colori sono molto simili. Se un cliente non trova la taglia giusta, se ne va. Al contrario, tenere in magazzino solo colori “popolari” o neutri rende il negozio meno accattivante visivamente, riducendo la sua attrattiva complessiva. Pertanto, gli articoli “di colore vivace” devono essere inclusi, anche se il loro volume di vendite potrebbe essere inferiore, e la loro presenza complessiva nel negozio deve rimanere attentamente bilanciata.

Senza la prospettiva dell’assortimento, la spedizione dei negozi può essere gestita con una semplice ottimizzazione avida, selezionando ogni unità aggiuntiva in base al calo dei rendimenti economici. Questo approccio avido funziona quando gli articoli sono considerati indipendenti. Tuttavia, una volta introdotti gli obiettivi di assortimento, sorgono interdipendenze e l’aggiunta di un’unità extra influisce sulla desiderabilità di altri prodotti, a causa delle relazioni tra taglia e colore come descritto in precedenza.

Attraverso la discesa discreta stocastica, Lokad fornisce piani di spedizione robusti che ottimizzano il classico compromesso tra costi di sovrastoccaggio e costi di esaurimento scorte, affrontando contemporaneamente ulteriori fattori economici, come garantire la presenza (o l’assenza) di colori o taglie specifiche, per migliorare l’attrattiva complessiva del negozio. Inoltre, poiché questa ottimizzazione viene eseguita a livello di rete, ogni unità allocata a un determinato negozio viene valutata in base alle esigenze di tutti gli altri negozi.

Riparazioni di motori aeronautici

Consideriamo ora la sfida di riparare i motori aeronautici. Quando un motore arriva, non è chiaro quali parti saranno necessarie perché il suo bollettino di materiali varia in base alla sua condizione specifica, un vero bollettino di materiali stocastico. Inoltre, a causa della disposizione del motore (essenzialmente una serie di strati concentrici), le prime parti identificate come necessarie durante lo smontaggio finiscono per essere richieste per ultime durante il rimontaggio. Poiché l’intero ciclo di riparazione può superare i due mesi, mantenere in magazzino quelle prime parti potrebbe non essere immediatamente critico; diventano essenziali solo alla fine del processo. Al contrario, le parti situate negli strati più interni del motore sono necessarie immediatamente, poiché il rimontaggio non può continuare senza di esse.

Un’ottimizzazione stocastica, in particolare la discesa discreta stocastica, consente una robusta prioritizzazione degli investimenti in parti, aiutando il fornitore MRO (Manutenzione, Riparazione e Revisione) a ridurre al minimo i tempi di riparazione dei motori aeronautici. Per ciascun articolo da acquistare, la domanda fondamentale diventa: “Con questo budget, quanti giorni di ritardo nella riparazione posso evitare?” In questo modo, gli acquisti di parti vengono prioritizzati strategicamente per ridurre i tempi di inattività, cruciali poiché il MRO è pagato per consegnare motori funzionanti e ogni ritardo è una perdita diretta sia per il MRO che per la compagnia aerea. Un approccio avido semplice fallisce qui perché le dipendenze tra le parti possono innescare ritardi a cascata. Al contrario, se il MRO decide di non tenere in magazzino determinate parti, potrebbe non influire sul cronoprogramma complessivo se quelle parti possono essere reperite in parallelo mentre si attendono componenti con tempi di consegna più lunghi. La discesa discreta stocastica tiene conto di queste interdipendenze e delle opportunità di approvvigionamento in parallelo.

Approvvigionamento multi-restrizione

Consideriamo ora il rifornimento con molteplici vincoli e diverse opzioni di approvvigionamento. I fornitori impongono MOQ (quantità minima d’ordine), che possono essere espressi in unità (per l’intero ordine) o in termini monetari (per l’ordine totale). Inoltre, bisogna puntare a container completi per ridurre i costi di trasporto. I prodotti possono essere acquistati localmente, con tempi di consegna più brevi e MOQ più bassi ma costi unitari più alti, oppure da fornitori distanti, che offrono costi unitari più bassi ma comportano tempi di consegna più lunghi e MOQ più alti. Anche se l’azienda può ordinare più container settimanalmente, un prodotto specifico di solito compare in non più di un container al mese.

L’ottimizzazione stocastica, con la discesa discreta stocastica come tecnica abilitante, affronta il fatto che effettuare un ordine oggi potrebbe impedire di effettuarne un altro per lo stesso prodotto domani. Nessun singolo prodotto giustifica tipicamente un container completo da solo, quindi anche gli articoli più venduti devono essere raggruppati con altri. Di conseguenza, se un articolo finisce inaspettatamente fuori stock mentre rimane un inventario significativo per la maggior parte degli altri prodotti idonei al raggruppamento, non c’è un’opzione conveniente per riordinare quel particolare articolo in anticipo. Il processo di ottimizzazione valuta le ramificazioni a lungo termine di ciascun ordine, come la pianificazione di un container completo, e tiene conto di quanto tempo passerà prima che tutti i prodotti coinvolti possano essere nuovamente riforniti in modo fattibile sotto gli stessi vincoli.