Descente Discrète Stochastique

L’optimisation stochastique englobe une classe de problèmes d’optimisation mathématique dans lesquels la fonction objectif varie en raison de l’incertitude. Étant donné l’incertitude irréductible de l’avenir, presque tous les problèmes de prise de décision de la supply chain relèvent de problèmes d’optimisation stochastique. Un optimiseur stochastique est un composant central de l’optimization de la supply chain : il utilise des prévisions probabilistes comme entrées et renvoie des décisions optimisées ajustées au risque.

Lokad a été pionnier d’une approche spécifique de cette optimisation, connue sous le nom de descente discrète stochastique. Ce paradigme de programmation aborde spécifiquement la complexité des problèmes de supply chain impliquant de l’incertitude, en s’appuyant sur le concept plus large de l’optimisation stochastique pour fournir des décisions robustes à grande échelle.

Optimisation stochastique en Mouvement

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

Aperçu technologique

Depuis 2016, Lokad a principalement optimisé la supply chain grâce aux prévisions probabilistes. Sans prévisions probabilistes, les décisions optimisées deviennent inévitablement fragiles, sensibles aux moindres variations de la demande ou des délais. En revanche, les décisions optimisées avec des prévisions probabilistes sont robustes. Bien que ces décisions robustes puissent être calculées à l’aide de simples heuristiques gloutonnes, ces heuristiques échouent souvent à gérer des contraintes plus complexes.

En 2021, Lokad a introduit sa première technologie d’optimisation stochastique à usage général, que nous appelons descente discrète stochastique. Cette innovation surmonte les limites des heuristiques gloutonnes face aux situations non linéaires de la supply chain. Conceptuellement, les Supply Chain Scientists de Lokad conçoivent un pipeline de traitement de données comportant les étapes suivantes :

1. Préparer les données historiques.
2. Générer des prévisions probabilistes.
3. Produire des décisions robustes.

Les données historiques sont préparées à l’aide des capacités générales d’ingénierie des données d’Envision, Envision étant le langage spécifique au domaine de Lokad. Les prévisions probabilistes sont ensuite produites grâce à la programmation différentiable, un paradigme idéal pour la modélisation probabiliste — reconnu comme un citoyen de première classe dans Envision. Enfin, des décisions robustes sont obtenues à l’aide de la descente discrète stochastique, proposée sous forme de paradigme de programmation au sein d’Envision.

En fin de compte, les étapes (1), (2) et (3) sont toutes exécutées au sein d’Envision.

Solveurs traditionnels et leurs limites

L’optimisation mathématique est un domaine bien établi de l’informatique. La plupart des produits logiciels dédiés à l’optimisation mathématique sont emballés sous forme de solveurs. Chaque solveur propose généralement son propre langage spécifique au domaine (DSL), permettant aux utilisateurs d’optimiser mathématiquement une classe spécifique de problèmes. Bien que de nombreux solveurs existent sur le marché, y compris plusieurs options open source, aucun ne répond adéquatement aux réalités des problèmes de supply chain.

1. Très peu de solveurs gèrent le cas stochastique. Presque toutes les solutions existantes se concentrent sur le scénario déterministe, où l’incertitude est absente. Malheureusement, on ne peut tout simplement pas « réaffecter » un solveur déterministe pour des cas stochastiques sans introduire un niveau d’approximation inacceptable.

2. La plupart des solveurs ne sont pas suffisamment évolutifs. Les problèmes de supply chain peuvent atteindre une très grande échelle : un million de SKUs peut se traduire par des dizaines de millions de variables une fois modélisées pour l’optimisation. Partitionner la supply chain uniquement pour accommoder le solveur n’est pas envisageable. Le solveur doit pouvoir gérer nativement des dizaines de millions de variables.

3. De nombreux solveurs manquent d’expressivité adéquate. Il ne peut souvent pas être supposé que la fonction objectif soit linéaire, quadratique, ou même convexe. Il est inacceptable de déformer le problème sous des hypothèses mathématiques simplistes uniquement pour satisfaire aux contraintes du solveur. Par conséquent, les solveurs doivent offrir des paradigmes de programmation hautement expressifs.

Après avoir passé en revue le paysage actuel des outils d’optimisation mathématique, nous avons conclu que développer notre propre technologie était la seule solution viable.

Dans les coulisses

Lokad adopte une approche quelque peu peu orthodoxe en matière d’optimisation stochastique. Plutôt que d’emballer la technologie sous la forme d’un solveur conventionnel, nous abordons le problème via un paradigme de programmation dédié connu sous le nom de descente discrète stochastique. Cette approche est cruciale pour tirer parti des connaissances et de l’expertise de nos Supply Chain Scientists.

Ce paradigme de programmation s’appuie sur la descente de gradient stochastique (SGD) car elle est extrêmement évolutive — de plusieurs ordres de grandeur au-delà des méthodes traditionnelles d’optimisation non convexe. Cependant, la SGD n’est pas naturellement adaptée aux problèmes discrets (et pratiquement tous les problèmes de supply chain sont discrets). Puisque les quantités de réapprovisionnement, de production ou de transfert sont des entiers, des résultats fractionnaires n’ont pas de sens.

Pour surmonter cette limitation, la descente discrète stochastique introduit une représentation différentiable alternative du problème original. Cette représentation propose un ensemble plus vaste de dimensions continues à valeurs réelles et sert efficacement de paramétrisation de la solution discrète. Contrairement au modèle discret d’origine — où les gradients se dégradent à zéro en raison des effets d’entiers — cette alternative produit des gradients non dégénérés adaptés à la SGD.

La principale limitation de la descente discrète stochastique est son incapacité à traiter des problèmes combinatoires véritablement difficiles, où les solutions sont tellement contraintes qu’elles ne peuvent être itérées par aucun type de descente directe. De tels problèmes nécessitent l’optimisation latente, une technique d’optimisation ultérieure également développée par Lokad.

Exemples

Optimiser les décisions face à un avenir incertain est un défi. De nombreux scénarios de supply chain nécessitent une optimisation stochastique pour une résolution adéquate.

Réapprovisionnements de magasins de mode

Considérez un réseau de distribution réapprovisionnant des magasins avec des objectifs spécifiques d’assortiment. Par exemple, garantir que toutes les tailles soient disponibles pour un vêtement est souvent plus crucial que d’offrir toutes les couleurs — surtout si certaines couleurs se ressemblent beaucoup. Si un client ne trouve pas la bonne taille, il part. À l’inverse, approvisionner uniquement avec des couleurs « populaires » ou neutres rend le magasin moins attrayant visuellement, réduisant ainsi son attractivité globale. Par conséquent, les articles aux couleurs vives doivent être inclus, même si leur volume de ventes peut être inférieur, et leur présence totale en magasin doit rester soigneusement équilibrée.

Sans la perspective de l’assortiment, la répartition en magasin peut être gérée avec une optimisation gloutonne simple, sélectionnant chaque unité supplémentaire en fonction de rendements économiques décroissants. Cette approche gloutonne fonctionne lorsque les articles sont traités comme indépendants. Cependant, une fois les objectifs d’assortiment introduits, des interdépendances apparaissent, et l’ajout d’une unité supplémentaire affecte l’attrait des autres produits — en raison des relations de taille et de couleur décrites ci-dessus.

Grâce à la descente discrète stochastique, Lokad fournit des plans de répartition robustes qui optimisent le compromis classique entre les coûts de surstock et de rupture de stock tout en prenant en compte des facteurs économiques supplémentaires — tels que garantir la présence (ou l’absence) de couleurs ou de tailles spécifiques — pour améliorer l’attractivité globale du magasin. De plus, puisque cette optimisation est effectuée au niveau du réseau, chaque unité allouée à un magasin particulier est évaluée en fonction des besoins de tous les autres magasins.

Réparations de moteurs d’avions

Considérez maintenant le défi de réparer des moteurs d’avions. Lorsqu’un moteur arrive, il n’est pas clair quelles pièces seront requises car sa nomenclature varie en fonction de son état spécifique — une nomenclature véritablement stochastique. De plus, en raison de l’agencement du moteur (essentiellement une série de couches concentriques), les premières pièces identifiées comme nécessaires lors du démontage finissent par être requises en dernier lors du remontage. Étant donné que le cycle complet de réparation peut dépasser deux mois, conserver ces premières pièces en stock pourrait ne pas être immédiatement critique ; elles ne deviennent essentielles qu’à la fin du processus. À l’inverse, les pièces situées dans les couches les plus internes du moteur sont nécessaires immédiatement, car le remontage ne peut pas se poursuivre sans elles.

Une optimisation stochastique — plus précisément, la descente discrète stochastique — permet de prioriser de manière robuste les investissements en pièces, aidant le prestataire MRO (Maintenance, Repair, and Overhaul) à réduire les temps de réparation des moteurs d’avions. Pour chaque article à acheter, la question essentielle devient : « Compte tenu de ce budget, combien de jours de retard de réparation puis-je éviter ? » De cette manière, les achats de pièces sont stratégiquement priorisés pour réduire les temps d’arrêt — ce qui est crucial car le MRO est rémunéré pour fournir des moteurs opérationnels, et tout retard constitue une perte directe tant pour le MRO que pour la compagnie aérienne. Une approche gloutonne simple échoue ici car les dépendances entre pièces peuvent déclencher des retards en cascade. À l’inverse, si le MRO décide de ne pas stocker certaines pièces, cela pourrait ne pas affecter le calendrier global si ces pièces peuvent être sourcées en parallèle pendant l’attente de composants à délais plus longs. La descente discrète stochastique prend en compte ces interdépendances et ces opportunités d’approvisionnement parallèle.

Multi-approvisionnement contraint

Considérez maintenant le réapprovisionnement avec de multiples contraintes et plusieurs options d’approvisionnement. Les fournisseurs imposent des MOQ (quantités minimales de commande), qui peuvent être exprimées en unités (pour l’ensemble de la commande) ou en termes monétaires (pour la commande totale). De plus, il faut viser des conteneurs complets afin de réduire les coûts de transport. Les produits peuvent être approvisionnés localement — ce qui conduit à des délais plus courts et à des MOQ plus faibles mais à des coûts unitaires plus élevés — ou auprès de fournisseurs éloignés, qui offrent des coûts unitaires inférieurs mais impliquent des délais plus longs et des MOQ plus élevés. Bien que l’entreprise puisse commander plusieurs conteneurs par semaine, un produit spécifique apparaît généralement dans au plus un conteneur par mois.

L’optimisation stochastique — avec la descente discrète stochastique comme technique facilitatrice — prend en compte le fait que passer une commande aujourd’hui peut empêcher de passer une autre commande pour le même produit demain. Aucun produit individuel ne justifie généralement un conteneur complet à lui seul, si bien que même les articles les plus vendus doivent être regroupés avec d’autres. Par conséquent, si un article s’épuise de manière inattendue alors qu’il reste d’importants stocks pour la plupart des autres produits éligibles au regroupement, il n’existe aucune option rentable pour réapprovisionner cet article spécifique plus tôt. Le processus d’optimisation évalue les ramifications à long terme de chaque commande — comme la programmation d’un conteneur complet — et tient compte du temps nécessaire pour que tous les produits concernés puissent à nouveau être réapprovisionnés dans les mêmes contraintes.