Discesa Discreta Stocastica

Ottimizzazione stocastica comprende una categoria di problemi di ottimizzazione matematica nei quali la funzione obiettivo varia a causa dell’incertezza. Dato l’incertezza irriducibile del futuro, quasi tutti i problemi di decision-making della supply chain rientrano nella categoria dei problemi di ottimizzazione stocastica. Un ottimizzatore stocastico è un componente fondamentale nell’ottimizzazione della supply chain: utilizza previsioni probabilistiche come input e restituisce decisioni ottimizzate adeguate al rischio.

Lokad ha introdotto un approccio specifico a tale ottimizzazione, noto come stochastic discrete descent. Questo paradigma di programmazione affronta in maniera specifica 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.

Ottimizzazione stocastica in Movimento

Probabilistic Forecasts and Sequential Decision-Making

Decision-Making under Uncertainty in Supply Chain

Stochastic Optimization of Supply Chain Decisions

The Future shaping the Past in Supply Chain

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 piccole variazioni nella domanda o nei tempi di consegna. Al contrario, le decisioni ottimizzate basate su previsioni probabilistiche sono robuste. Sebbene decisioni robuste possano essere calcolate usando semplici euristiche “greedy”, tali euristiche spesso non riescono a gestire vincoli più complessi.

Nel 2021, Lokad ha introdotto la sua prima tecnologia di ottimizzazione stocastica a scopo generale, che chiamiamo stochastic discrete descent. Questa innovazione affronta le carenze delle euristiche greedy quando si presentano situazioni non lineari nella supply chain. In termini concettuali, i Supply Chain Scientist di Lokad progettano una pipeline di elaborazione dati con i seguenti passaggi:

1. Preparare i dati storici.
2. Generare previsioni probabilistiche.
3. Produrre decisioni robuste.

I dati storici vengono preparati utilizzando le capacità generali di data engineering di Envision, Envision essendo il linguaggio specifico di dominio di Lokad. Successivamente, le previsioni probabilistiche vengono generate tramite programmazione differenziabile, un paradigma particolarmente adatto per la modellazione probabilistica—riconosciuto come un cittadino di prima classe in Envision. Infine, le decisioni robuste sono derivate utilizzando lo stochastic discrete descent, fornito come paradigma di programmazione all’interno di Envision.

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

Risolutori tradizionali e i loro limiti

L’ottimizzazione matematica è un’area ben consolidata nell’informatica. La maggior parte dei prodotti software dedicati all’ottimizzazione matematica è confezionata come solvers. Ogni solver offre tipicamente il proprio linguaggio specifico di dominio (DSL), che consente agli utenti di ottimizzare matematicamente una specifica classe di problemi. Sebbene esistano numerosi solvers sul mercato, inclusi vari opzioni open-source, nessuno di essi affronta adeguatamente le realtà dei problemi della supply chain.

1. Molti pochi solvers gestiscono il caso stocastico. Quasi tutte le soluzioni esistenti si concentrano sullo scenario deterministico, dove l’incertezza è assente. Purtroppo, non è possibile semplicemente “riutilizzare” un solver deterministico per casi stocastici senza introdurre un livello inaccettabile di approssimazione.

2. La maggior parte dei solvers non è sufficientemente scalabile. I problemi della supply chain possono diventare estremamente grandi: un milione di SKU può tradursi in decine di milioni di variabili una volta modellato per l’ottimizzazione. Partizionare la supply chain solo per adattarsi al solver non è una soluzione praticabile. Il solver deve gestire nativamente decine di milioni di variabili.

3. Molti solvers mancano di un’espressività adeguata. Non si può presumere che la funzione obiettivo sia lineare, quadratica o addirittura convessa. È inaccettabile distorcere il problema con assunzioni matematiche sempliste semplicemente per adattarsi ai vincoli del solver. Di conseguenza, i solvers devono offrire paradigmi di programmazione altamente espressivi.

Dopo aver esaminato il panorama esistente degli strumenti di ottimizzazione matematica, abbiamo concluso che sviluppare la nostra tecnologia fosse l’unica soluzione praticabile.

Dietro le quinte

Lokad adotta un approccio alquanto non convenzionale all’ottimizzazione stocastica. Piuttosto che confezionare la tecnologia come un solver convenzionale, affrontiamo il problema attraverso un paradigma di programmazione dedicato noto come stochastic discrete descent. Questo approccio è cruciale per sfruttare le intuizioni e l’esperienza dei nostri Supply Chain Scientist.

Questo paradigma di programmazione sfrutta lo stochastic gradient descent (SGD) perché scala estremamente bene—di ordini di grandezza superiore rispetto ai metodi tradizionali di ottimizzazione non convessa. Tuttavia, l’SGD non è naturalmente adatto a problemi discreti (e praticamente tutti i problemi della supply chain sono discreti). Poiché le quantità di rifornimento, produzione o trasferimento sono intere, i risultati frazionari non hanno significato.

Per superare questa limitazione, lo stochastic discrete descent introduce una rappresentazione differenziabile alternativa del problema originale. Questa rappresentazione presenta un insieme più ampio di dimensioni continue, a valori reali, e serve efficacemente come una parametrizzazione della soluzione discreta. A differenza del modello discreto originale—dove i gradienti degenerano a zero a causa degli effetti degli interi—questa alternativa produce gradienti non degenere adatti per l’SGD.

La principale limitazione dello stochastic discrete descent è la sua incapacità di affrontare problemi combinatori realmente complessi, in cui le soluzioni sono così fortemente vincolate da non poter essere iterate tramite alcun tipo di discesa diretta. Tali problemi richiedono ottimizzazione latente, una tecnica di ottimizzazione successiva sviluppata anch’essa 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 risoluzione adeguata.

Rifornimenti nei negozi di moda

Consideriamo una rete di vendita al dettaglio che rifornisce i negozi con obiettivi di assortimento specifici. Ad esempio, garantire la disponibilità di tutte le taglie per un capo è 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, fornire esclusivamente colori “popolari” o neutri rende il negozio meno attraente visivamente, riducendo il suo fascino complessivo. Pertanto, devono essere inclusi articoli “vivacemente colorati”, anche se il loro volume di vendite potrebbe essere inferiore, e la loro presenza totale nel negozio deve rimanere attentamente bilanciata.

Senza la prospettiva dell’assortimento, la distribuzione nei negozi può essere gestita con una semplice ottimizzazione greedy, selezionando ogni unità aggiuntiva in base a ritorni economici decrescenti. Questo approccio greedy 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à degli altri prodotti—a causa delle relazioni tra taglia e colore come descritto sopra.

Grazie allo stochastic discrete descent, Lokad fornisce piani di distribuzione robusti che ottimizzano il classico equilibrio tra costi di sovraccarico e costi di stockout, affrontando al contempo ulteriori fattori economici—come garantire la presenza (o l’assenza) di specifici colori o taglie—per migliorare l’attrattiva complessiva del negozio. Inoltre, poiché questa ottimizzazione viene eseguita a livello di rete, ogni unità assegnata a un particolare negozio viene valutata rispetto alle necessità di tutti gli altri negozi.

Riparazioni dei motori degli aerei

Consideriamo ora la sfida della riparazione dei motori degli aerei. Quando un motore arriva, non è chiaro quali parti saranno necessarie poiché il suo bill of materials varia in base alla sua condizione specifica—un vero bill of materials 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 quelle prime parti in magazzino 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 subito, poiché il rimontaggio non può procedere senza di esse.

Un’ottimizzazione stocastica—più specificamente, lo stochastic discrete descent—consente una robusta prioritizzazione degli investimenti in parti, aiutando il fornitore MRO (Maintenance, Repair, and Overhaul) a ridurre i tempi di riparazione dei motori degli aerei. Per ogni articolo da acquistare, la domanda centrale diventa: “Con questo budget, quanti giorni di ritardo nella riparazione posso evitare?” In questo modo, gli acquisti delle parti vengono prioritizzati strategicamente per ridurre i tempi di inattività—elemento cruciale in quanto l’MRO viene pagato per consegnare motori operativi, e ogni ritardo rappresenta una perdita diretta sia per l’MRO che per la compagnia aerea. Un semplice approccio greedy fallisce qui poiché le interdipendenze tra le parti possono innescare ritardi a catena. Al contrario, se l’MRO decide di non tenere in magazzino alcune parti, ciò potrebbe non influenzare la tempistica complessiva se tali parti possono essere acquisite in parallelo mentre si attende per componenti con tempi di consegna più lunghi. Lo stochastic discrete descent considera queste interdipendenze e opportunità di approvvigionamento parallelo.

Multi-sourcing con vincoli

Consideriamo ora il rifornimento con molteplici vincoli e diverse opzioni di approvvigionamento. I fornitori impongono MOQs (quantità minime d’ordine), che possono essere espresse in unità (per l’intero ordine) o in termini monetari (per l’ordine totale). Inoltre, si dovrebbe puntare a container pieni per ridurre i costi di trasporto. I prodotti possono essere approvvigionati localmente—con tempi di consegna più brevi e MOQs inferiori ma costi unitari più elevati—oppure da fornitori distanti, che offrono costi unitari inferiori ma comportano tempi di consegna più lunghi e MOQs più elevati. Sebbene l’azienda possa ordinare più container a settimana, un prodotto specifico compare tipicamente in non più di un container al mese.

L’ottimizzazione stocastica—con lo stochastic discrete descent come tecnica abilitante—affronta il fatto che effettuare un ordine d’acquisto oggi può impedire di effettuare un altro ordine per lo stesso prodotto domani. Nessun singolo prodotto giustifica tipicamente un container pieno da solo, quindi anche gli articoli più venduti devono essere raggruppati con altri. Di conseguenza, se un articolo si esaurisce inaspettatamente mentre rimane un inventario significativo per la maggior parte degli altri prodotti idonei al bundle, non esiste un’opzione economicamente vantaggiosa per riordinare quell’articolo specifico in anticipo. Il processo di ottimizzazione valuta le ripercussioni a lungo termine di ogni ordine—come la programmazione di un container pieno—e considera quanto tempo ci vorrà affinché tutti i prodotti coinvolti possano essere nuovamente riforniti sotto gli stessi vincoli.