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. Compte tenu de l’incertitude irréductible de l’avenir, presque tous les problèmes de prise de décision en supply chain se qualifient comme des problèmes d’optimisation stochastiques. Un optimiseur stochastique est un composant essentiel de l’optimisation de la supply chain : il utilise des prévisions probabilistes en entrée et renvoie des décisions optimisées ajustées au risque.

Lokad a pionnier une approche spécifique à 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 qui impliquent de l’incertitude, s’appuyant sur le concept plus large de l’optimisation stochastique pour fournir des décisions robustes à grande échelle.

Allégorie abstraite du défi de l'optimisation stochastique

Aperçu de la technologie

Depuis 2016, Lokad a principalement optimisé les supply chains grâce à des prévisions probabilistes. Sans prévisions probabilistes, les décisions optimisées deviennent inévitablement fragiles, susceptibles de variations même légères de la demande ou du délai de livraison. En revanche, les décisions optimisées par rapport aux prévisions probabilistes sont robustes. Bien que des décisions robustes puissent être calculées à l’aide de heuristiques “gourmandes” simples, ces heuristiques échouent souvent à gérer des contraintes plus complexes.

En 2021, Lokad a introduit sa première technologie d’optimisation stochastique polyvalente, que nous appelons descente discrète stochastique. Cette innovation s’attaque aux lacunes des heuristiques gourmandes lorsqu’elles sont confrontées à des situations non linéaires de la supply chain. Conceptuellement, les Supply Chain Scientists de Lokad conçoivent un pipeline de traitement des données avec les étapes suivantes :

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

Les données historiques sont préparées en utilisant les 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éalement adapté à la modélisation probabiliste, reconnu comme un citoyen de première classe dans Envision. Enfin, les décisions robustes sont dérivées en utilisant la descente discrète stochastique, livrée comme un 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 en informatique. La plupart des produits logiciels dédiés à l’optimisation mathématique sont emballés sous forme de solveurs. Chaque solveur offre 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.

Très peu de solveurs traitent 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 pas simplement “recycler” un solveur déterministe pour des cas stochastiques sans introduire un niveau d’approximation inacceptable.
La plupart des solveurs ne sont pas suffisamment évolutifs. Les problèmes de supply chain peuvent devenir extrêmement volumineux : un million de SKUs peuvent se traduire par des dizaines de millions de variables une fois modélisées pour l’optimisation. Partitionner la supply chain juste pour accommoder le solveur n’est pas viable. Le solveur doit gérer nativement des dizaines de millions de variables.
De nombreux solveurs manquent d’expressivité adéquate. La fonction objective ne peut souvent pas être supposée linéaire, quadratique, voire convexe. Il est inacceptable de déformer le problème sous des hypothèses mathématiques simplistes simplement pour s’adapter aux contraintes du solveur. Par conséquent, les solveurs doivent offrir des paradigmes de programmation très expressifs.

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

Sous le capot

Lokad adopte une approche quelque peu non conventionnelle de l’optimisation stochastique. Plutôt que de conditionner la technologie en tant que solveur conventionnel, nous abordons le problème à travers un paradigme de programmation dédié connu sous le nom de descente discrète stochastique. Cette approche est cruciale pour tirer parti des idées et de l’expertise de nos Supply Chain Scientists.

Ce paradigme de programmation exploite la descente de gradient stochastique (SGD) car elle évolue extrêmement bien, par des ordres de grandeur au-delà des méthodes traditionnelles d’optimisation non convexe. Cependant, le SGD n’est pas naturellement adapté aux problèmes discrets (et pratiquement tous les problèmes de supply chain sont discrets). Comme les quantités de réapprovisionnement, de production ou de transfert sont des entiers, les 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 présente un ensemble plus large de dimensions continues et réelles et sert efficacement de paramétrisation de la solution discrète. Contrairement au modèle discret original—où les gradients dégénèrent à zéro en raison des effets entiers—cette alternative produit des gradients non dégénérés adaptés au SGD.

La principale limitation de la descente discrète stochastique est son incapacité à résoudre les problèmes combinatoires vraiment difficiles, où les solutions sont tellement contraintes qu’elles ne peuvent pas être itérées par une descente directe quelconque. Ces problèmes nécessitent une optimisation latente, une technique d’optimisation ultérieure également développée par Lokad.

Exemples

Prendre des décisions optimisées face à un avenir incertain est un défi. De nombreux scénarios de supply chain exigent une optimisation stochastique pour une résolution adéquate.

Réapprovisionnements de magasins de mode

Considérons un réseau de vente au détail réapprovisionnant des magasins avec des objectifs d’assortiment spécifiques. Par exemple, s’assurer que toutes les tailles sont disponibles pour un vêtement est souvent plus critique que d’offrir toutes les couleurs—surtout si certaines couleurs sont très similaires. Si un client ne trouve pas la bonne taille, il part. En revanche, ne stocker que des couleurs “populaires” ou neutres rend le magasin moins attrayant visuellement, réduisant ainsi son attrait global. Par conséquent, les articles “de couleur vive” doivent être inclus, même si leur volume de ventes peut être plus faible, et leur présence totale en magasin doit rester soigneusement équilibrée.

Sans la perspective de l’assortiment, la distribution en magasin peut être gérée avec une simple optimisation gloutonne, sélectionnant chaque unité supplémentaire en fonction des rendements économiques décroissants. Cette approche gloutonne fonctionne lorsque les articles sont traités de manière indépendante. Cependant, une fois que les objectifs d’assortiment sont introduits, des interdépendances apparaissent, et l’ajout d’une unité supplémentaire affecte la désirabilité d’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 distribution robustes qui optimisent le compromis classique entre les coûts de surstock et de rupture de stock tout en abordant simultanément des facteurs économiques supplémentaires—comme garantir la présence (ou l’absence) de couleurs ou de tailles spécifiques—pour améliorer l’attrait global du magasin. De plus, parce que cette optimisation est effectuée au niveau du réseau, chaque unité allouée à un magasin particulier est évaluée par rapport aux besoins de tous les autres magasins.

Réparations des moteurs d’avion

Considérons maintenant le défi de réparer les moteurs d’avion. Lorsqu’un moteur arrive, il n’est pas clair quels pièces seront nécessaires car sa nomenclature varie en fonction de son état spécifique—une nomenclature véritablement stochastique. De plus, en raison de la disposition 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 nécessaires en dernier lors du remontage. Comme tout le cycle de réparation peut dépasser deux mois, maintenir ces premières pièces en stock peut ne pas être immédiatement critique ; elles ne deviennent essentielles qu’à la fin du processus. En revanche, les pièces situées dans les couches les plus internes du moteur sont nécessaires immédiatement, car le remontage ne peut pas continuer sans elles.

Une optimisation stochastique—plus précisément, une descente discrète stochastique—permet une priorisation robuste des investissements en pièces, aidant le fournisseur MRO (Maintenance, Réparation et Révision) à minimiser les temps de réparation des moteurs d’avion. Pour chaque article à acheter, la question centrale devient : “Avec 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—essentiel puisque le MRO est payé pour livrer des moteurs en état de fonctionnement, et tout retard est une perte directe pour le MRO et la compagnie aérienne. Une approche gloutonne simple échoue ici car les dépendances entre les pièces peuvent déclencher des retards en cascade. En revanche, si le MRO décide de ne pas stocker certaines pièces, cela peut ne pas affecter le calendrier global si ces pièces peuvent être sourcées en parallèle en attendant les composants à plus long délai. La descente discrète stochastique prend en compte ces interdépendances et les opportunités d’approvisionnement en parallèle.

Approvisionnement multi-sourcing contraint

Considérons maintenant le réapprovisionnement avec de multiples contraintes et plusieurs options d’approvisionnement. Les fournisseurs imposent des MOQ (quantités de commande minimales), qui peuvent être exprimées en unités (pour la commande entière) ou en termes monétaires (pour la commande totale). De plus, il convient de cibler des conteneurs complets pour réduire les coûts de transport. Les produits peuvent être sourcés localement—entraînant des délais plus courts et des MOQ plus bas mais des coûts unitaires plus élevés—ou auprès de fournisseurs éloignés, qui offrent des coûts unitaires plus bas 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 pas plus d’un conteneur par mois.

L’optimisation stochastique—avec la descente discrète stochastique comme technique habilitante—aborde 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, donc même les articles les plus vendus doivent être regroupés avec d’autres. Par conséquent, si un article se retrouve inopinément en rupture de stock alors qu’il reste un inventaire important pour la plupart des autres produits éligibles au regroupement, il n’y a pas d’option rentable pour réapprovisionner cet article spécifique plus tôt. Le processus d’optimisation évalue les conséquences à long terme de chaque commande—comme la planification d’un conteneur complet—et tient compte du temps qu’il faudra avant que tous les produits concernés puissent être réapprovisionnés de manière réalisable sous les mêmes contraintes.