Programme entier pour la gestion des stocks et l'efficacité de l'exécution des commandes

Combien d'unités de chaque produit doivent être commandées? Quels sont les premiers produits à être emballés? Quels sont les modes de livraison qui donnent le coût le plus bas sans violer les heures de conduite? Ces questions partagent une structure mathématique commune: elles impliquent des choix discrets qui ne peuvent être représentés par des fractions. Un parc de camions ne peut pas être 3.7 véhicules; une chaîne de montage ne peut pas fonctionner 2.4 lots. C'est précisément là où la programmation entière devient indispensable.

La programmation intégrale est une branche d'optimisation mathématique dans laquelle certaines ou toutes les variables de décision sont limitées aux valeurs entières. Elle s'appuie sur la base de la programmation linéaire (LP) mais s'étend à une classe de problèmes connus sous le nom de programmes linéaires mixtes (MILP). En combinant des fonctions objectives linéaires et des contraintes avec des variables entières, la programmation intégrale peut modéliser des complexités du monde réel comme la sélection binaire (navire ou non), les contraintes de cardinalité (au plus cinq fournisseurs) et l'allocation indivisible des ressources (nombre de palettes).

Comprendre la programmation intégrale

De la programmation linéaire à la programmation intégrale

Par exemple, le mélange d'essence pourrait suggérer l'utilisation de 1,5 baril de brut A et 2,3 baril de brut B – une solution réalisable et optimale. Beaucoup de décisions logistiques, cependant, ne permettent pas de tels résultats fractionnels. Un entrepôt ne peut pas commander 0,6 d'un conteneur, et une cellule de fabrication ne peut pas traiter 2,7 emplois simultanément. La programmation entière corrige cela en exigeant que certaines variables soient entières. Lorsque seulement certaines variables sont entières, le modèle est un programme linéaire mixte entier (MILP). Lorsque toutes les variables sont entières, c'est un programme linéaire entier (ILP).

La formulation mathématique

Un programme entier est exprimé comme suit:

]Tx
sous réserve de la mention Ax ≤ b
x ≥ 0
x -n (ou xi -] -]

Pour les problèmes binaires (0–1), les variables sont davantage limitées à {0,1}. Cette structure simple cache une immense complexité : les programmes entiers sont difficiles à utiliser en général, ce qui signifie que de grandes instances peuvent nécessiter des algorithmes sophistiqués et des résolveurs commerciaux.

Pourquoi les variables entières comptent dans les opérations

En inventaire et en réalisation, les variables entières représentent naturellement des éléments discrets, des commandes, des véhicules, des travailleurs et des installations. Sans contraintes entières, une relaxation linéaire de programmation pourrait commander 23,4 unités d'un UGS à mouvement lent, ce qui conduirait à un stock de sécurité fractionnaire – un résultat non faisable dans la pratique.

Programmation intégrale dans la gestion des stocks

La gestion des stocks équilibre les coûts de détention des stocks par rapport aux risques de stockage.Les modèles traditionnels comme la quantité d'ordre économique (QEE) supposent une reconstitution continue et une demande déterministe.Les systèmes d'inventaire du monde réel font face à des commandes discrètes, à des capacités de partage de produits multiples, à des quantités minimales de fournisseurs et à des contraintes de production par lots.

Taille classique du lot avec des variables entières

Le problème classique de la taille des lots à un seul élément détermine le nombre d'unités à produire ou à commander pour satisfaire la demande connue tout en minimisant les coûts de configuration et de détention. Lorsque les quantités de production doivent être des multiples entiers d'une taille de lot, les variables deviennent entières. L'algorithme Wagner–Whitin résout la version non capacitée dans le temps polynôme, mais en ajoutant des contraintes de capacité ou plusieurs produits force l'utilisation de MILP.

  • Diversité de l'installation:[ Les variables binaires indiquent si une exécution de production se produit dans une période, ce qui permet des coûts à frais fixes.
  • Contraintes de solde des stocks :[ L'inventaire de fin de période est égal à l'inventaire de début plus la production moins la demande, avec des niveaux d'inventaire entier non négatifs.
  • Contraintes de capacité :[ La production totale plus le temps de configuration ne peut dépasser les heures disponibles pour chaque période.

Ces modèles sont maintenant standard dans les systèmes de planification avancés (APS) de fournisseurs comme SAP, Oracle, et Blue Yonder.

Optimisation de l'inventaire multi-échelons

Les chaînes d'approvisionnement couvrent souvent plusieurs niveaux : fournisseurs, entrepôts centraux, centres de distribution et magasins de détail. La programmation d'integer coordonne les décisions de reconstitution entre les échelons. Par exemple, un détaillant peut regrouper les commandes de centaines de magasins en quantités de chargement de camions. Les variables d'integer permettent de saisir le nombre de camions, la sélection de points de regroupement et l'affectation des magasins aux livraisons.

Contraintes relatives au niveau de sécurité et au niveau de service

Dans les systèmes d'examen périodique, le niveau de l'ordre au niveau doit être un nombre entier d'unités. Lorsque la demande suit une distribution discrète, la programmation au niveau entier minimise les coûts de détention et de pénalité tout en veillant à ce que la probabilité d'accumulation demeure inférieure à un seuil donné.

Programmation intégrale pour l'efficacité de l'exécution des commandes

La réalisation des commandes englobe tout, de la réception et de la mise en place à la cueillette, l'emballage et l'expédition.

Commande d'entrepôts et de ramassage

Dans un centre de distribution typique, les piqueurs voyagent dans les allées pour recueillir des articles pour plusieurs commandes. Le problème de lotage des commandes se regroupe en lots afin qu'un seul piqueur puisse récupérer tous les articles en une seule tournée. Les objectifs sont de minimiser la distance totale de déplacement et d'équilibrer la charge de travail entre les piqueurs. Il s'agit d'une variante du problème de routage du véhicule (VRP) avec des contraintes supplémentaires : capacité de piqueur (p. ex., nombre maximal de commandes par lot) et fenêtres de temps pour l'achèvement.

Routage et calendrier de livraison des véhicules

Le problème d'acheminement des véhicules (VRP) est une application classique de programmation intégrale. Un parc de véhicules doit desservir un ensemble de clients d'un dépôt, minimisant la distance totale ou le coût tout en respectant la capacité du véhicule, les fenêtres de temps et les heures de conducteur. Les variables entières représentent la séquence des arrêts, l'attribution des routes aux véhicules et le nombre de véhicules utilisés. Les extensions du monde réel – comme les flottes hétérogènes, les interruptions de conduite et les arrivées dynamiques de commandes – sont naturellement exprimées en MILP. Les entreprises comme UPS et Domino , Pizza, utilisent la programmation intégrale pour planifier des dizaines de milliers de routes par jour.

Allocation de commandes dans les centres d'exécution

Les détaillants de commerce électronique qui ont plusieurs entrepôts doivent décider quel centre de livraison (FC) expédiera chaque article pour minimiser le coût total (expédition plus manutention). Le problème d'attribution est un problème de transport avec les flux entiers. Lorsque les articles sont déjà emballés dans les cas, le nombre de cas expédiés doit être un entier. Ajouter des contraintes de disponibilité des stocks et des fenêtres de temps de livraison permet de transformer l'attribution en MILP.

Algorithmes et logiciels pour la résolution des programmes entiers

Les solveurs de programmation entiers sont parmi les outils les plus sophistiqués en mathématiques appliquées. Ils combinent la recherche, la relaxation et les méthodes de coupe-plan.

Branche-et-Bon

L'algorithme standard pour MILP est branche et lie. Il commence par assouplir les contraintes entières et résoudre la relaxation LP. Si la solution contient des variables fractionnelles, l'algorithme crée des nœuds enfants en rampant sur une variable fractionnelle (par exemple x ≤ 5 ou x ≥ 6). Chaque noeud est un nouveau problème LP. L'algorithme prune des nœuds qui ne peuvent pas produire une meilleure solution que la meilleure solution entière actuelle. Pour les gros problèmes, la branchement seul est trop lent, de sorte que les résolveurs modernes ajoutent des plans de coupe – des contraintes qui coupent des solutions fractionnelles sans enlever des points entiers réalisables.

Solveurs commerciaux et à source ouverte

Le logiciel de programmation entier de qualité de production comprend:

  • IBM ILOG CPLEX[ – Un des résolveurs les plus rapides et les plus fiables, largement utilisés dans la chaîne d'approvisionnement, la finance et la fabrication. (Voir IBM CPLEX Optimizer)
  • Gurobi Optimizer[ – Connu pour son résolveur MILP haute performance et son excellent support pour les applications d'inventaire et de routage. (Voir Gurobi Inventory Management Resources[)
  • Google OR‐Tools – Une bibliothèque libre et open-source qui comprend des solveurs de programmation entiers (via Coin‐OR ou CPLEX) et des algorithmes spécialisés pour l'acheminement et l'ordonnancement. (Voir OR‐Tools Documentation)
  • SCIP (Solving Contraintet Integer Programs) – Un cadre de solveur open-source développé à l'Institut Zuse de Berlin. Il offre de nombreux avions de coupe et d'heuristique primaire.

Pour la plupart des problèmes d'inventaire et de réalisation à l'échelle de l'entreprise, CPLEX ou Gurobi sont les normes de l'industrie.

Études de cas mondiales réelles

Distribution des pièces automobiles

Un important distributeur de pièces automobiles a réapprovisionné 20 000 UGS dans cinq entrepôts. Il a utilisé un MILP à plusieurs échelons pour déterminer les quantités de commandes et les niveaux de stocks de sécurité, compte tenu de la taille des lots entiers (palettes et caisses). Le modèle comprenait des contraintes de capacité d'entreposage, des délais de livraison des fournisseurs et la saisonnalité de la demande.

Exécution de la commande de détail de mode

Un détaillant de mode européen a dû faire face à des coûts d'expédition élevés et à des livraisons tardives pendant sa haute saison. Il a déployé des programmes entiers pour attribuer des commandes en ligne à quatre centres de réalisation en fonction de la disponibilité des stocks, des zones d'expédition et de la capacité. Le modèle a fonctionné toutes les heures, attribuant des commandes au FC le moins cher qui pourrait encore respecter la date de promesse.

Livraison d'épicerie Routage

Une grande chaîne d'épicerie opérant dans des zones urbaines denses a utilisé un MILP pour planifier les routes de livraison quotidiennes de 200 camionnettes. Le modèle a considéré les fenêtres de temps (slots de deux heures), la capacité du véhicule (nombre de tonnes), les limites de quart de conduite et les habitudes de congestion de la circulation.

Défis et orientations futures

Échelle et temps de calcul

Un modèle d'inventaire avec 500 UGS, 52 semaines et une structure multi-echelon peut dépasser 100 000 variables binaires. Même les meilleurs résolveurs peuvent prendre des minutes ou des heures pour prouver l'optimalité. Les praticiens comptent souvent sur des solutions heuristiques limitées dans le temps : accepter la meilleure solution integer trouvée dans un budget de temps (p. ex. 300 secondes). Les avancées dans le calcul parallèle et les résolveurs basés sur le cloud repoussent les limites : Google , OR‐Tools peut maintenant résoudre des problèmes de routage avec des milliers de clients en secondes.

Qualité et intégration des données

Les modèles de programmation intégriste nécessitent des données précises – prévisions de la demande, délais, coûts, capacité et contraintes. Dans la pratique, de nombreuses entreprises font face à des silos de données, à des données de référence incohérentes et à des paramètres dépassés. Un modèle alimenté par de mauvaises données donne des recommandations trompeuses.

Optimisation en temps réel

La programmation intégrale classique suppose des entrées statiques et connues. Le commerce électronique et la livraison du même jour exigent une réoptimisation rapide à mesure que les commandes arrivent. Cela a conduit au développement de MILP à horizon roulant, à une réoptimisation toutes les quelques minutes, ainsi qu'à des modèles hybrides qui combinent la programmation intégrale et l'apprentissage du renforcement. Par exemple, un modèle de sélection dynamique pourrait ré-affecter les commandes toutes les 30 minutes sur la base des 200 dernières commandes.

Intégration avec l'intelligence artificielle

L'apprentissage automatique peut prédire quelles décisions de branchement conduisent à la solution la plus rapide, guidant efficacement l'arbre de branche et de liaison. De même, l'apprentissage profond peut générer des solutions initiales de haute qualité qui accélèrent le résolveur. Ces approches guidées par le MILP , testées dans les applications de la chaîne d'approvisionnement, ont montré une réduction de 50% des temps de résolution.

Conclusion

La programmation intégrale n'est pas seulement un outil théorique – c'est un moteur pratique et éprouvé pour prendre de meilleures décisions en matière d'inventaire et de réalisation des commandes. En reconnaissant la nature discrète des ressources du monde réel, la programmation intégrale crée des plans réalisables, rentables et évolutives.

Pour les professionnels de la chaîne d'approvisionnement, la voie à suivre consiste à construire des pipelines de données propres, à investir dans la technologie du résolveur et à accroître progressivement la complexité des modèles déployés. À mesure que la puissance informatique augmente et que les algorithmes de programmation entiers continuent de progresser, même les problèmes les plus importants et les plus complexes de la chaîne d'approvisionnement deviendront traitables.