Algo palettisation = variante "sac à dos"

Bonjour, je doit créer un logiciel de palettisation : rentrer le plus possible de colis (tous de meme taille) dans une palette. De plus, je doit pouvoir afficher l'emplacement de chaque colis !
C'est pourquoi je doit créer un algorithme variant de celui du sac a dos. Cependant je suis un peu perdu....
Si vous pourriez m'indiquer la marche à suivre, je conçoit en faite mal le faite que l'ordinateur soit capable de les placer... j'ai pensé à un repère (x,y,z). L'ordinateur sortirait donc les coordonnées de chaque colis, afin de créer une représentation graphique. ENcore faut-il les trouver ses coordonnées !

Merci,
@+

À mon avis, les questions-clés sont :

• Quelles formes peuvent prendre tes colis ?
• Quelle est la hauteur maximum de ta palette ?
• Dois-tu minimiser cette hauteur ?

Parce que s'ils sont parallélépipédiques , il suffit de les ranger en pavés, et de monter aussi haut que nécessaire.

Les colis sont parallélépipédiques et leur dimenssions sont connues.... La hauteur maximale de la palette est fixée par l'utilisateur. Les dimensions de la palette sont connues.
Je ne doit pas minimiser la hauteur, je doit maximiser le nombre de colis à entrer dans ce volume. Tu peu imaginer que j'ai un conteneur, et que j'ai pleins de colis parallélépipédiques tous identiques. Je doit en entrer le maximum dedans afin d'économiser !
De plus, les colis peuvent etre mis "a plat" mais aussi sur la tranche "longueur" et sur la tranche "profondeur"....

Renseignes-toi sur les algorithmes génétiques, ça pourrait être une piste intéressante.

Bonjour,
j'ai regardé du coté des algos génetiques....
Je ne comprend pas bien comment il faut procéder, puisque je n'ai pas de "population initiale" !
Ou alors... je stock dans chaque "chromosome" les coordonnées (x,y,z) de chacune de mes boites.... :roll:

Tu peux aussi l'initialiser avec un bête algo glouton.

Je suis qu'un débutant en la matière et je ne vois pas comment combiner ces deux algo....
De plus, meme si je rentrai la population initiale de l'algo génetique, je ne vois pas comment il peut prendre en compte que les colis peuvent etre mis sur leur tranche (= verticalement) ou horizonalement....

Argh, je piétine......
Vous n'auriez pas quelques liens, ou autres pour me faire avancer svp ?
Merci !

Dis-toi que les valeurs des individus de première génération (tes valeurs de départ) n'ont aucune importance. Tu peux les initialiser aléatoirement. Le but de l'algorithme génétique est justement de les faire converger vers des valeurs correctes (résolvant ton problème).

Maintenant, pour ta question...
Tes individus sont affublés de valeurs fixes et d'autres variables, dans ton problème.
Les valeurs fixes sont les dimensions des différentes boîtes contenues dans ton espace de rangement.
Les valeurs variables sont la position de ces différentes boîtes.
Un individu est l'ensemble de ces valeurs pour toutes les boîtes. Autrement dit, un individu = une solution de rangement (qui soit valide ou invalide, peu importe).
Une solution valide résout ton problème. Une solution invalide, non.

Comment placer une boîte sur la tranche ?
En réalité, tu peux placer ta boîte selon les trois axes. En clair, tu peux poser chaque boîte sur chacune de ses 6 faces, seulement, tu peux simplifier ce problème en considérant que les faces opposées sont identiques. Donc 3 possibilités de pose.

Tu as deux solutions pour faire ça (au moins).

La première (la moins bonne) consiste à faire varier les dimensions de tes boîtes. Autrement dit, tu transformes tes boîtes de cette façon : X = Y, Y=Z, Z=X, etc...
La merde avec ce système, c'est que c'est compliqué de gérer toutes les transformations, sans se planter. Et que dans une certaine mesure, tu as une perte de donnée : tu ne sais plus, par exemple à quelle dimension correspond la hauteur de la boîte. Du coup, tu es "obligé" (si tu as besoin de ce genre d'information) de recourir à une information supplémentaire pour qualifier chaque face de la boîte. C'est pénible.

La deuxième (la meilleure) consiste à enrichir le système de positionnement de tes boîtes dans l'espace de rangement.
Autrement dit, si tu avais avant les coordonnées X, Z (Y étant la hauteur), et l'indice de l'étage (égal au nombre de boîtes en dessous de la boîte étudiée), tu auras, en plus le qualifiant de la face sur laquelle la boîte doit être posée.

Par exemple, tu pourrais avoir ceci : 20cm, 34cm, 3e étage, posé sur la face X.
X et Z (dans mon exemple) représentant les faces formant les "murs" de la boîte et Y le "plafond" et le "sol", dans l'exemple que je t'ai donné, la boîte serait posée sur la tranche.

La 2e solution est plus simple à mettre en place et te permet en plus, de définir une contrainte supplémentaire (si besoin) : l'interdiction ou l'obligation de déposer une boîte spécifique sur la tranche ou non, par exemple.

Ca répond à ta question ?

Oui, mais justement, toute la difficulté réside non pas dans le fait de représenter l'orientation d'un colis à l'intérieur du volume charrié par la palette, mais de les agencer entre eux, sachant que certains agencements non-optimaux laissent des espaces vides entre les colis et impossibles à combler. Et là encore, on écarte d'emblée la possibilité de faire faire des rotations aux colis. On considère que quelque soit leur position, les faces seront toujours parallèle à celles du volume du « container ». C'est un problème de modélisation.

Il y a une chose par laquelle on peut commencer, en tout cas, c'est calculer le volume total du container et le diviser par celui d'un colis. On connaît ainsi le nombre maximum potentiel de colis que l'on peut charger. Ensuite, en utilisant l'approche la plus naturelle, c'est-à-dire en chargeant tous les colis côte-à-côte et orientés de la même façon, on obtient déjà la densité maximale possible, dans le sens où l'on obtient un parallélépipède aux faces parallèles à celle du container, et ne contenant aucun espace libre.

Les « pertes » se jouent alors sur les « marges » du container, c'est à dire sur le reste de chaque arrête lorsque les longueurs des côtés des colis ne sont pas multiples de celles du container. La technique consiste alors à minimiser ces marges en trouvant les valeurs les plus réduites possibles pour les trois marges simultanément, par incréments de la longueur de ces côtés.

En tout état de cause, on peut rapidement calculer le nombre de colis chargés dans les six cas possibles où les boîtes sont toutes orientées de la même façon et ne retenir que le plus efficace. On obtient donc un minimum (ce cas) et un maximum (volume du container) formant une fenêtre en dehors de laquelle on sait qu'il est inutile de s'aventurer.

Merci !!
Je vais essayer de coder quelque chose, je reviendrai si j'ai des problèmes ;)

Voici quelques liens pour démarrer : D.Pisinger,S.Martello. Son livre "Knapsack problems" est téléchargeable (mais il ne traite pas des problèmes de palletisation).

Cherche du côté du "bin packing 3d", tu devrais trouver pas mal de papier.

Après tu peut aussi ce qui est fait dans le "bin packing 2D", tu trouvera encore plus de papiers et donc de sources d'inspiration (en particulier dans l'utilisation de meta-heuristiques telles que les GA (E.Falkenauer, A.Delchambre) , les fourmis (F.Ducatelle), la recherche taboue (Martello, Pisinger, Vigo), etc...)


Un conseil : fait tes recherches aussi via schoolar.google. Cela permet d'avoir access à pas mal d'article en pdf que je n'ai trouvé accessible que via des sites payants en passant par google "normal" (par contre, cela ne pointe pas sur des sites "classiques", donc il faut faire tes recherches via les deux canaux)

De plus, si tu décompose ton problème en "couches", par exemple, génération/calcul de solution d'un côté et validation/placement de l'autre, rien ne t'empêche de mélanger les approches :utiliser la méthode de placement de x avec la méthode de calcul des solutions de y puis replacer la méthode x par z pour voir si cela fonctionne mieux.

C'est ce que j'ai fait pour une étude de bin packing : 2 méthodes de placement et 3/4 méthodes de calcul des solutions potentielles et tests de toutes les combinaisons entre ces méthodes pour comparer la pertinence de chaque mais avec une base commune à chaque fois.
j'sais pas si je me suis bien fait comprendre là :oops:

Devant bosser sur du bin packing 2D est ayant aussi cherché des ressources je partage ici une chouette trouvaille:
http://www.devx.com/dotnet/Article/36005/
(plusieurs algo expliqués, implémentés et comparés)

Plusieurs méthodes pour aborder le problème en 2D.

Cela pourra toujours servir aux suivants qui passeront par là.