Groupe d’études et de recherche en analyse des décisions

G-2019-51

Benders decomposition for a stochastic three-level lot sizing and replenishment problem with a distribution structure

, et

Nous étudions un problème stochastique de planification de production et réapprovision-nement sur trois échelons via un processus de décision en deux étapes. Nous prenons en compte une usine de production qui produit un seul type d'article au cours d'un horizon temporel fini et discret. Les articles produits sont trasportés vers des entrepôts puis vers des détaillants, via des livraisons directes. Chaque détaillant est relié à un unique entrepôt et les transferts entre entrepôts ou entre détaillants sont prohibés. L'aspect stochastique vient de l'incertitude entourant la demande au niveau des détaillants, et est modélisée via des scénarios de demande. Les décisions de mise en route sont prises lors de la première étape et les décisions de production, transport et stockage sont prises lors de la deuxième étape, une fois que les demandes ont été révélées. L'objectif est de minimiser la somme des coûts fixes de production et réapprovisionnement, et de l'espérance des coûts variables de stockage à travers tous les scénarios. Nous utilisons une décomposition de Benders et développons un algorithme de branch-and-cut fondé sur la décomposition de Benders pour résoudre efficacement le problème. Nous tirons profit des sous-structures identifiées dans la décomposition et développons des procédures efficaces pour résoudre les sous-problèmes obtenus. Nous intégrons également des améliorations de calcul pour accélérer le processus de résolution. Enfin, nous réalisons de nombreuses expériences numériques pour évaluer la performance de notre approche par décomposition et pour analyser l'impact des améliorations proposées. L'algorithme de branch-and-cut fondé sur la décomposition de Benders que nous proposons surpasse de manière notable CPLEX.

, 22 pages