Algorithme de Bin Packing en PHP

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 :

Bin Packing 2D en PHP

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 :

Bin Packing 2D en PHP, version 2

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'oeuvre, 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.

Note : le téléchargement n'est pas immédiat, merci de patienter.

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...

Cet article vous a plu ? Merci de le partager sur les réseaux sociaux :
image
Qui est l'auteur ?

Passionné de nouvelles technologies, je propose mes services de développement Web, principalement dans l'élaboration de scripts et d'algorithmes sur mesure, ainsi que plus généralement dans la réalisation de sites internet évolués (e-commerce, etc...) et du référencement (SEO).
N'hésitez pas à me contacter pour toute demande !

Abonnez-vous à ce blog par email

Rentrez votre adresse email pour vous abonner au blog et recevoir un e-mail à chaque nouvel article :

ou suivez nous sur Facebook :

3 commentaires

  1. image Andres

    Hello!! Ive been looking for an algorithm like this for so long, please can you share it with me, how can we do?

  2. image SergentBrico

    Hi Andres, please contact me by email on the "contact" page, in the menu.
    Best regards

  3. Bonjour,

    Dans le description du Binpacking il est indiqué "comment faire rentrer X éléments de dimensions données, dans un contenant de la dimension la plus réduite possible" puis il est aussi indiqué "applicable en 1, 2 ou 3 dimensions".

    Le Binpacking en 1 dimension n'a pas de sens dans le contexte décrit à savoir "ranger X éléments de dimensions données dans un contenant de la dimension la plus réduite possible" car dans ce il n'y a aucune contrainte ils occuperont toujours la dimension la plus réduite mis bout-à-bout.

    cdlt.

Écrire un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec une *

Quelle est la quatrième lettre du mot hznxu ? :