Les problèmes d'packing visent à trouver le meilleur moyen d'empaqueter un ensemble d'éléments de tailles données dans des conteneurs ayant des packing fixes. Une application classique consiste à charger efficacement des cartons sur des camions de livraison. Souvent, il n'est pas possible d'empaqueter tous les éléments en raison des contraintes de capacité. Dans ce cas, le problème consiste à trouver un sous-ensemble d'éléments avec une taille totale maximale pouvant tenir dans les conteneurs.
Il existe de nombreux types de problèmes d'emballage. Deux des plus importants sont les problèmes de sac à dos et le bin packing.
Problèmes de sac à dos
Dans le problème simple du sac à dos, il y a un seul conteneur (un sac à dos). Les éléments ont des valeurs ainsi que des tailles. L'objectif est d'empaqueter un sous-ensemble d'éléments ayant la valeur totale maximale.
Dans le cas particulier où la valeur est égale à la taille, l'objectif est de maximiser la taille totale des articles emballés.
OR-Tools fournit plusieurs résolveurs de problèmes de sac à dos dans sa bibliothèque d'algorithmes.
Il existe également des versions plus générales du problème du sac à dos. Voici quelques exemples:
Les problèmes de sac à dos multidimensionnel, dans lesquels les articles ont plusieurs quantités physiques, telles que le poids et le volume, et le sac à dos a une capacité pour chaque quantité. Ici, le terme dimension ne fait pas nécessairement référence aux dimensions spatiales habituelles (hauteur, longueur et largeur). Cependant, certains problèmes peuvent concerner les dimensions spatiales, par exemple la recherche du moyen optimal d'emballer des boîtes rectangulaires dans un bac de stockage rectangulaire.
Plusieurs problèmes de sac à dos, qui impliquent plusieurs sacs à dos. L'objectif est de maximiser la valeur totale des objets emballés dans tous les sacs à dos.
Notez que vous pouvez avoir un problème multidimensionnel avec un seul sac à dos, ou un problème multidimensionnel avec une seule dimension.
Le problème de bin packing
L'un des problèmes d'empaquetage les plus connus est le bin-packing, dans lequel il existe plusieurs conteneurs (appelés bin-packing) de capacité égale. Contrairement au problème du sac à dos multiple, le nombre de classes n'est pas fixe. L'objectif est plutôt de trouver le plus petit nombre de classes pouvant contenir tous les éléments.
Voici un exemple simple illustrant la différence entre le problème du sac à dos multiple et celui du bin packing. Supposons qu'une entreprise dispose de camions de livraison, chacun d'une capacité de 7 500 kg et de 68 000 kg de marchandises à livrer.
Plusieurs sac à dos: vous avez cinq camions et vous voulez charger un sous-ensemble des articles qui ont le poids maximal sur eux.
Préparation du bin
Les sections suivantes expliquent comment résoudre différents types de problèmes d'empaquetage avec OR-Tools, à commencer par le problème du sac à dos.