Problème de Remplissage de Sacs

bins


1. Données

Pour télécharger les données de ce cas d'utilisation et la version d'essai de XLOPTIM, veuillez cliquer sur les liens suivants:

Télécharger les données du problème de remplissage de sacs

Télécharger la version d'essai

2. Le Problème

Dans le problème de remplissage de sacs, un certain nombre d'objets dont la taille est connue doivent être affectés à des sacs de capacité uniforme. L'objectif est de minimiser le nombre de sacs utilisés de sorte que tous les objets soient placés. C'est un exemple typique d'un problème NP-difficile.

Le problème de bin packing peut être par exemple appliqué au rangement de fichiers sur un support informatique, à la découpe de câbles ou encore au remplissage de camions ou de containers (contrainte sur la taille ou le volume des objets).

La capacité des sacs est ici de 1000. Pour chacun des 30 objets, nous connaissons leur taille donné dans le tableau ci-dessous :

table1

Nous cherchons à proposer une modélisation linéaire de ce problème de remplissage de sacs, ainsi qu’un outil d’aide à la décision dans XLOPTIM®.

3. Modélisation

Nous proposons une modélisation suivant les 5 étapes suivantes :

Étape #1 : Quelles sont les dimensions / indices du problème ?

  • i : 1.. 30 : les objets
  • j : 1 .. 30 : les sacs

Étape #2 : Quelles sont les données du problème ?

  • La taille de chaque objet i :

$$P_{i}$$

  • La capacité maximale des sacs :

$$K$$

Étape #3 : Quelles sont les variables de décision ?

  • Est-ce que je positionne l’objet i dans le sac j ou pas (booléen) :

$$X_{ij}$$

  • Est-ce que j’utilise le sac j ou pas (booléen) :

$$Y_{j}$$

Étape #4 : Quelles sont les contraintes ?

  • Chaque objet apparaît dans un sac :

$$\forall \,\ i \in [1;30], \sum_{j=1}^{30}{X_{ij}=1}$$

  • Le volume calculé pour chaque sac ne doit pas dépasser pas la capacité K :

$$\forall \,\ j \in [1;30], \sum_{i=1}^{30}{X_{ij}.P_i \leqslant Y_j.K}$$

Étape #5 : Quel est l’objectif du problème ?

$$Min\sum_{j=1}^{30}{Y_j}$$

4. Traduction en XLOPTIM®

xloptim1

Définition des 2 variables de décision principales booléennes :

xloptim2 xloptim3

Ajout de la contrainte “chaque objet est dans un sac” :

xloptim4

Ajout de la contrainte sur la capacité de chaque sac :

xloptim5

Fixation de l’objectif :

xloptim6

Calcul de la solution optimale :

xloptim7

qui donne une valeur de la fonction objective optimale suivante :

xloptim8

5. Conclusion

L'affectation des objets aux sacs nous a permis d'ouvrir seulement 15 sacs pour 30 objets initial soit 2 objets par sac. La solution affichée est réalisable et obtenue après 2 secondes.

Cette étude de cas vous a permis de découvrir un exemple de problème de remplissage de sacs. Ils sont fréquents dans les problèmes industriels de remplissage de camions, chargement, découpe de câble. Vous pouvez modifier la taille du problème et les hypothèses pour faire varier le problème et donc les solutions. N'hésitez pas à nous contacter si vous avez des questions suite à l'utilisation de notre solveur XLOPTIM®.