[ALGO] Packing 2d

Salut, salut,

Je dois réaliser un solver du problème de packing 2d.

Pour ceux qui connaissent pas, j'expose une des formes du problème (celle que je dois résoudre).
On dispose d'une boite container de longueur L et largeur l et de n objets rectangulaires de longueur L1...Ln et de largeur l1...ln. On cherche la meilleure combinaison d'objets tel que le remplissage du container soit optimal (on veut maximiser la surface utilisée). On peut placer les objets dans le container de manière orthogonal (parallèle au coté du container, donc pas d'objets en travers).

L'idée qu'on nous a proposé c'est de partager le container en bande, et de remplir de manière optimal chaque bande. Effectivement, si les bandes sont remplies de la meilleure des facons, on répondra au problème (maximisation de la surface utilisée).

Bon, partant de ce principe là, j'ai trouvé comment remplir de façon optimal chaque bande via l'algorithme de sac à dos. Mais je me heurte à un autre problème. C'est le choix des largeurs de bandes. Pour le moment, je teste toutes les largeurs de bande en les plaçant dans un arbre et dès qu'un remplissage partiel est moins optimal que la solution trouvée j'arrête ce remplissage et je teste un autre remplissage. Mais tester toutes largeurs de bandes sur n objets c'est bien trop long.

Donc y'a-t-il moyen de trouver une heuristique pour choisir directement les largeurs de bandes les plus efficaces (pas forcément les plus optimales, mais qui se rapprochent de la meilleure solution) ?

Merci !

bonjour

:recherch:

Déjà posé et répondu à de nombreuses reprises..

Je trouve un peu énervant ce genre de réponse qui n'apporte rien, et qui dénote une certaine flemmardise de la part de son auteur... Personne ne vous oblige à répondre, donc si vous pensez que c'est une perte de temps, ne répondez pas, c'est mieux.

Pour en revenir au problème que je pose, si j'avais trouvé la solution sur le forum ou google, je n'aurais pas posé la question, surtout que ca fait bien 3 semaines que je travaille sur le sujet. Ce que je veux, c'est surtout discuter des heuristiques possibles pour trouver les largeurs de bande.

Pour le moment, la solution que j'ai trouvé c'est de trier les objets à placer selon 3 groupes en fonction de leur largeur, ensuite affiné les largeurs en fonction des groupes. Mais, cette solution produit-elle une solution satisfaisante ? Surtout sachant qu'on peut tourner les objets.... Comment être sur que le remplissage, à défaut d'être le meilleur, est une solution pas trop mauvaise ?

Citation:

---

Envoyé par Picolo18

Pour en revenir au problème que je pose, si j'avais trouvé la solution sur le forum ou google, je n'aurais pas posé la question, surtout que ca fait bien 3 semaines que je travaille sur le sujet. Ce que je veux, c'est surtout discuter des heuristiques possibles pour trouver les largeurs de bande.

---

Faudrait peut-être se poser la question : si au bout de 3 semaines de recherche tu n'as rien trouvé sur cette "heuristiques de largeur de bandes", est-ce que ca ne vaudrait pas la peine de regarder d'autres méthodes de résolution ?

Par exemple un algorithme Glouton/GRASP (Alvarez-Valdes), Exact (Kenmochi), Genetique (Bortfeldt), Heuristique (Hopper), MetaHeuristique (Iori), ...

Enfin, moi je dis ça, c'est toi qui voit...

* Pour ta question relative aux largeur de bande, cherche avec "strip packing", tu trouvera pleins de méthodes aussi.

* Pour savoir si ta solution est la meilleure ou non...Perso, j'ai utilisée une fonction de fitness qui me retournait une valeur entre 0 et 1 : 0, rien n'est placé, 1 : 0% de perte > solution idéale.
Après, il faut boucler/générer de nouvelles solutions tant que a) ton délai n'est pas écoulé, b) tant que tu n'a pas de solution, dont la valeur de fitness est égale à 0.

J'ai en effet travaillé quelques temps sur ce sujet (mémoire d'ingé. au cnam) , ma technique - n'étant pas mathématicien, j'ai exclu les solution exactes et autres à base de prog.linéaire/dynamique - était d'utiliser deux heuristiques/méta-heuristiques travaillant de concert.

Grosso modo, c'était
a) calcul de solutions potentielles par une méta-heuristique (au choix, alg.génétique, colonie de fourmis, recuit simulé, hillcimbing, etc...) : Chaque solution calculée représente un ordre dans lequel les pièces seront utilisées par l'heuristique de placement (pe : p1, p4, p2, etc...).

b) pour chaque solution calculée, appel d'une l'heuristique de placement :
SHF modifiée par mes soins dans mon cas (de travail en bande, je l'ai fait travailler sur la totalité de la surface) pour arriver à placer des pièces comme dans la PJ, exemple venant "Recursive Computational Procedure for Two-dimensional Stock Cutting" de Herz.


Après à toi de voir selon l'objectif final de tes calculs : travailler en bande permet une "découpe" relativement facile et c'est facile à coder mais génère de la perte (voir toujours ?) alors que travailler sur une heuristique comme la mienne permet si les pièces sont dans le "bon" ordre d'arriver à une perte de 0.
Maintenant, c'est aussi selon la probalité d'avoir à traiter des cas ou il existe une solution sans perte. J'utilisé comme étalon l'exemple de herz car il est justement extrême en partant du principe, que si mon heuristique de placement pouvait l'obtenir, elle devrait s'en sortir avec des cas plus simples.
Sans compter que le fait de savoir qu'il existe une solution idéale permet à mon humble avis de débugger plus facilement. 8-)

voili-voila

j'espère avoir été compréhensible et ne pas avoir répondu à côté de la plaque.

Bonsoir !

pseudocode > en réalité, j'ai pas le choix, on m'impose la méthode des largeurs de bandes.

250rgv > je te remercie d'avoir pris le temps de m'expliquer ta méthode. Je commence à mieux voir comment ca pourrait se faire. Je vais creuser un peu ta méthode et voir les références que tu cites, ca m'éclairera un peu plus je pense. Enfin en tout cas, ca m'a donné quelques idées. Encore merci.

Je vous tiens au courant de mes avancées. Bonne soirée !