La 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 du futur, presque tous les problèmes de prise de décision supply chain se qualifient comme des problèmes d’optimisation stochastique. Un optimiseur stochastique est un élément central de l’optimization de la supply chain : il utilise des prévisions probabilistes comme entrées et renvoie des décisions optimisées tenant compte du risque.

Lokad a été pionnier dans 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 l’incertitude, en 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 aux prévisions probabilistes. Sans prévisions probabilistes, les décisions optimisées deviennent inévitablement fragiles, susceptibles même à de légères variations de la demande ou du délai de livraison. En revanche, les décisions optimisées à partir de prévisions probabilistes sont robustes. Bien que des décisions robustes puissent être calculées à l’aide de simples heuristiques « avides », 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 remédie aux limites des heuristiques avides lorsqu’elles sont confrontées à des situations non linéaires de supply chain. Conceptuellement, les Supply Chain Scientists de Lokad conçoivent un pipeline de traitement des données selon 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 à l’aide des capacités générales d’ingénierie des données d’Envision, Envision étant le langage spécifique à 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 une entité de première classe dans Envision. Enfin, les décisions robustes sont dérivées à l’aide de la descente discrète stochastique, proposée comme 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 logiciels dédiés à l’optimisation mathématique sont présentés sous forme de solveurs. Chaque solveur offre généralement son propre langage spécifique à 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 solutions open source, aucun ne répond adéquatement aux réalités des problèmes de supply chain.

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 aux 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 grands : un million de SKU 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 une option viable. Le solveur doit pouvoir gérer nativement des dizaines de millions de variables.
De nombreux solveurs manquent d’expressivité adéquate. La fonction objectif ne peut souvent pas être supposée linéaire, quadratique ou même convexe. Il est inacceptable de déformer le problème sous des hypothèses mathématiques simplistes simplement pour satisfaire les contraintes du solveur. Par conséquent, les solveurs doivent offrir des paradigmes de programmation hautement expressifs.

Après avoir examiné le panorama existant des outils d’optimisation mathématique, nous avons conclu que le développement de 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 présenter la technologie sous forme de 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 connaissances et de l’expertise de nos Supply Chain Scientists.

Ce paradigme de programmation exploite la descente de gradient stochastique (SGD) car elle s’adapte extrêmement bien—par des ordres de grandeur supérieurs aux méthodes d’optimisation non convexes traditionnelles. Cependant, le SGD n’est pas naturellement adapté aux problèmes discrets (et quasiment tous les problèmes de supply chain sont discrets). Étant donné que les quantités de réapprovisionnement, de production ou de transfert sont des nombres 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 comporte un ensemble plus vaste de dimensions continues et réelles et sert en effet de paramétrisation de la solution discrète. Contrairement au modèle discret original—où les gradients se dégénèrent à zéro en raison des effets d’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 réside dans son incapacité à traiter des problèmes combinatoires véritablement difficiles, où les solutions sont si fortement contraintes qu’elles ne peuvent être améliorées par un quelconque 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 futur incertain est un défi. De nombreux scénarios de supply chain exigent une optimisation stochastique pour une résolution appropriée.

Réapprovisionnements de magasins de mode

Considérons un réseau de distribution 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 crucial 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. Inversement, ne proposer que des couleurs « populaires » ou neutres rend le magasin moins attrayant visuellement, réduisant son attractivité globale. Par conséquent, des articles « aux couleurs vives » doivent être inclus, même si leur volume de ventes peut être inférieur, et leur présence totale dans le magasin doit rester soigneusement équilibrée.

Sans la perspective d’assortiment, la répartition des magasins peut être gérée par une simple optimisation gloutonne, en 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’attractivité 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 les coûts de rupture de stocks tout en prenant simultanément en compte des facteurs économiques supplémentaires—comme garantir la présence (ou l’absence) de certaines couleurs ou tailles—afin d’améliorer l’attrait global du magasin. De plus, puisque cette optimisation est réalisé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 des moteurs d’avions

Considérons maintenant le défi de la réparation des moteurs d’avions. Lorsqu’un moteur arrive, il n’est pas clair quelles 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 requises en dernier lors du remontage. Comme l’ensemble du cycle de réparation peut dépasser deux mois, le maintien en stock de ces premières pièces peut ne pas être immédiatement critique ; elles ne deviennent essentielles qu’à la fin du processus. Inversement, les pièces situées dans les couches les plus intérieures du moteur sont nécessaires immédiatement, car le remontage ne peut 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 dans les pièces, aidant le prestataire MRO (Maintenance, Repair, and Overhaul) à minimiser les temps de réparation des moteurs d’avions. Pour chaque article à acheter, la question fondamentale devient : « Compte tenu de ce budget, combien de jours de retard en réparation puis-je éviter ? » De cette façon, les achats de pièces sont stratégiquement priorisés pour réduire le temps d’arrêt—ce qui est crucial puisque le MRO est rémunéré pour livrer des moteurs en état de fonctionnement, et tout retard représente une perte directe tant pour le MRO que pour 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. Inversement, 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 tout en attendant des composants avec des délais de livraison plus longs. La descente discrète stochastique prend en compte ces interdépendances et les opportunités de sourcing en parallèle.

Approvisionnement multi-sourcing sous contraintes

Considérons maintenant le réapprovisionnement avec de multiples contraintes et plusieurs options de sourcing. Les fournisseurs imposent des MOQ (quantités minimum de commande), 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 viser des conteneurs complets afin de réduire les coûts de transport. Les produits peuvent être sourcés localement—ce qui conduit à des délais de livraison 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 de livraison 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 un seul conteneur par mois au maximum.

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 ne justifie généralement à lui seul un conteneur complet, de sorte que même les articles les plus vendus doivent être regroupés avec d’autres. Par conséquent, si un article venait de manquer de stocks de manière inattendue alors qu’il reste des stocks significatifs pour la plupart des autres produits éligibles au bundle, il n’existe aucune option rentable pour réapprovisionner cet article spécifique plus tôt. Le processus d’optimisation évalue les répercussions à 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 à nouveau être réapprovisionnés dans les mêmes contraintes.