Sergent Brico

Concept

Le problème du binpacking consiste à savoir comment faire rentrer X éléments de dimensions données, dans un contenant de la dimension la plus réduite possible. Vous pouvez consulter l'article de Wikipedia à ce sujet.

Il est donc envisageable de résoudre ce problème pour des éléments en 2 dimensions ou 3 dimensions.
En deux dimensions, la problématique est par exemple d'optimiser le rangement de voitures sur un ferry (sans tenir compte de leur hauteur donc, uniquement de leur place au sol).
Pour la 3D, on peut citer un problème logistique courant : comment ranger des petits cartons dans un grand colis, pour qu'il y ait le moins d'espace vide possible.

L'approche scientifique, par le calcul, est très complexe.

Pour ma part, j'ai développé un algo de placement aléatoire simple pour du bin-packing en 2D.

Version 1

Voila par exemple le genre de résultats qu'il me donne :



Dans cet exemple, j'ai donc 15 éléments (de dimensions données, à gauche) à positionner dans un contenant faisant 25x25 (cm, mètres, qu'importe) en faisant en sorte que les 15 éléments prennent le moins de place possible (sous-entendu, on peut donc utiliser un contenant plus petit).

Le nombre de tentatives est paramétrable, et bien sûr proportionnel au temps de calcul.

Il conserve donc la solution prenant le moins de surface possible, parmi toutes les tentatives effectuées.

Version 2

La version 2, plus performante, toujours sur du bin packing 2D, donne ce genre de résultats :

J'ai ajouté un test en ligne qui vous permet de voir le résultat en cliquant ici. Dans cet exemple, il essaie de placer 30 formes de dimensions aléatoires dans un carré de 20x20 unités. Si jamais la page est blanche, actualisez là, cela veut dire qu'il n'est pas arrivé à trouver de solution pour le tirage donné.

Version 3

Dans la version 3, pas de gros changements au niveau du calcul, mais possibilité de dire au script d'essayer plusieurs types de "contenants" (en fait, plusieurs surfaces-types, en précisant largeur x hauteur), ordonnés par surface croissante. Le script s'arrêtera à la première surface-type capable de contenir tous les éléments à placer.

De plus, pour chaque élément, il donnera les coordonnées du coin supérieur gauche, et du coin inférieur droit.

Pour le voir à l’œuvre, c'est ici. La encore, notez que pour avoir des temps d’exécution corrects vu que je suis sur un mutualisé, j'ai paramétré un nombre de combinaisons à tester relativement faible (1000 par surface-type).
L'algorithme est toujours avec un fonctionnement aléatoire, et essaye de placer les différentes pièces en les tournant.

Se procurer le script

Pour vous procurer le script PHP fonctionnel, c'est possible via un paiement Paypal de 9€ grâce au lien ci-dessous. Le fichier ZIP que je vous ferai parvenir contiendra la version 2 et la version 3. L'envoi étant manuel, merci de me laisser le temps de vous l'envoyer !

Je suis également disponible pour toute demande de développement autour de ce script, n'hésitez pas me contacter pour en discuter.

Et la 3D ? Hein ?

Là, c'est l'étape suivante. J'invite ceux qui font des recherches sur le sujet à laisser un commentaire afin de me faire part de leurs idées, ou axes de réflexions...