Remplissage d'un container avec des cartons

Emmanuel8 · November 2004

Bonjour,

je suis analyste programmeur dans une société informatique et un client aurait besoin d'un programme dont une des sous fonctions est de minimiser le nombre de containers pour embarquer ses cartons sur ses bateaux.
Si je n'ai pas de solution à ce problème nous nous contenterons de l'approche "tous les cartons alignés et de la même dimension", il ne reste qu'à tester les 6 positions, ce qui est déjà fait.
Mais je me disais que peut être un brillant mathématicien avait pondu une théorie ?

Voici l'énoncé.

Il y a 3 tailles de containers.

Les cartons sont par lots, exemple 100 cartons d'une dimension, 200 d'une autre dimension et 165 d'une autre.

Le but est de savoir en fonction des dimensions de cartons comment organiser au mieux les cartons dans les containers, sachant qu'un lot de cartons doit rester groupé et doit quelquefois respecter un ordre (pour le déchargement), par exemple 100 cartons de type 1 doivent être faciles d'accès donc près des portes.
La solution proposée doit être "assez facilement" représentable à l'écran et/ou par un texte francais pour transmettre les informations aux gens qui ont pour tache de charger le container.

Exemple:
Container de 235 cm de large, 238 cm de haut et 590 cm de profondeur.
Carton de 41 cm x 39 cm x 47.5 cm.

Voilà, je ne sais pas comment créer un algorithme de gestion d'espace 3D qui ne mette pas 100 ans à trouver une solution en posant les 300 cartons 1 par 1 dans les 6 positions possibles, et qui soit "assez" efficace en terme de qualité de solution, car la place c'est de l'argent.

J'ai pensé à gérer le contenu du container comme des cubes de 1 centimetre de côté pour gérer l'espace de façon fragmentée, mais cela me parait très difficile même comme cela.

Je suis ouvert à toutes les idées ou suggestions, merci !!!

rémi · November 2004

Ce que tu racontes me semble être de la recherche opérationnelle (j'ai lu en diagonale) je pense que tu auras probablement des réponses.

Kashmir · November 2004

c'est une variante du problème du sac à dos.

Ce sujet est très discuté sur les forums sciences, particulièrement sur les forums anglo-saxons. Tu n'auras donc pas de mal à trouver des choses sur le net.

L'objet des discussions est en général la complexité du problème (c'est un problème NP-complet, en tant que programmeur ça doit te parler), les variantes (binpacking, knapsack), les applications (archivages sur cd, transport, cryptographie), l'arrêt de l'algorithme d'optimisation (et oui, y a un seuil d'optimisation à ne pas dépasser sous peine de perte inutile de temps).

Emmanuel8 · November 2004

Merci pour ces informations, je vais noter les noms que vous m'avez donnés et chercher un peu.
NP-complet j'ai bien peur en effet que ça me dise quelque chose... mais juste le nom, c'est triste de ne pas avoir suivi acidument les cours ! ;-)

Bon hé bien je vais chercher, merci A+

Eric Chopin0 · November 2004

Salut Emmanuel,

etant moi aussi programmeur et ayant eu a faire de
la gestion d'entrepot, je connais un peu ce genre de probleme.
Il existe des logiciels qui te permettent de gerer l'agencement
des stocks et ils sont tres chers car le nombre de contraintes
que tu peux avoir est tres important. Tu sembles ne t'interesser
qu'au volume final. Est-ce que ce sont tous des cartons de la meme
marchandise, y a t'il des criteres de poids? J'imagine que tes cartons
seront surement paletisés, auquel cas il faut surtout s'interesser
au plan de paletisation, car il faut tenir compte de la manutention.

Sinon c'est quoi tes 3 tailles de containers, je pensais qu'il
n'y avait que 20 et 40 pieds?

a+

eric

Emmanuel8 · November 2004

Merci pour ta réponse.

Les containers du client sont:
20 pieds dry: 590*235*238
40 pieds dry: 1203*235*238
40 pieds HQ: 1203*235*269

Le poids nous importe pour les frais et pour calculer des coûts plus tard, mais on ne m'a pas parlé d'un poids maximum pour un container ni de l'équilibrage des charges dans le container.
En fait le client ne doit pas avoir ce problème j'imagine car il transporte par exemple des trotinettes, des rollers, ce serait autre chose j'imagine s'il transportait des moteurs de camion. ;-)

Eux s'occupent du volume car ils louent les containers.

Oui la palletisation est importante c'est pourquoi nous gardons un lot de cartons ensemble (un lot = un type de cartons pour un client), et c'est une autre partie de la demande justement que de mettre les cartons sur des palettes à l'arrivée... mais bon quand j'aurai fait les containers ce sera facile. ;-)

Je suis en train d'essayer de gérer des "tranches" de profondeur, et pour chaque tranche, je vais essayer de gérer des "segments" d'une même hauteur dans la tranche, comme une gestion de mémoire.
Même comme cela à partir du moment où l'on a 2 types de carton ça devient chaud.
Si j'ai 30 cartons de type 1 qui constituent 2 tranches et 1 rangée de cartons posée par terre et que la suite sont des gros cartons, il serait logique de poser les cartons restants de la première partie par dessus les gros cartons et non en dessous.... bref je suis pas rendu.

Ah oui, j'ai regardé sur internet les théories nommées par les personnes précédentes, mais je n'ai pas le niveau mathématique pour me lancer dans une théorie pareille, sachant qu'après je dois implémenter cela dans un programme qui soit capable de gérer un volume fragmenté (=espace libre au fur et à mesure que l'on met des cartons).

A+

Manu

Eric Chopin0 · November 2004

Pour te rassurer un peu, je crois que les logiciel type gestion
d'entrepot n'utilisent que peu des theories mathematiques
avancées, mais plutot des algos bourrins sur sur serveurs
betes de courses. Tu as tellement de contrainte a gerer
dans un entrepot qu'une theorie mathematique ne peux en general
regler que des cas particuliers. Par exemple ici, si tu pouvais
dire des le depart si tes marchandises sont systematiquement
palletisées ou non dans le container, si les cartons ont des
tailles prédéfinies, ca aiderai grandement la recherche
d'un algo de placement efficace. En plus tu dois gerer la
proximité (comme dans n'importe quel entrepot) ce qui n'est pas simple.
De toute facon, si tes marchandises ne sont pas palletisées, les
gars vont mettre les cartons en commencant par remplir le fond
puis tranche apres tranche (ils n'ont pas le choix
a moins que le container soit du type open-top ou flat rack).
Donc en pratique je pense qu'il te suffit de trouver le meilleur
agencement des cartons sur une tranche.

a+

eric

Emmanuel8 · November 2004

Oui c'est ce que je suis en train de développer, une gestion par tranches puis dans une tranche par segments. Le seul soucis est si l'on complete une tranche non terminée par des cartons d'une taille différente. Je verrai bien les choix que je fais.
Et en effet les cartons ne sont que très rarement palettisés dans le container, ils sont toujours jetés comme ça.

Eric Chopin · November 2004

Cela dit si tu as 2 lots a mettre dans tes containers,
il n'y aura au pire qu'un seul container dans lequel
1 tranche pourrait etre mixte (melange des 2 lots), car
les autres containers seront remplis uniformement avec chaque lot,
donc tu peux faire ton algo en remplissant pour chaque lot
des containers entiers et a la fin tu regardes si les residus de
chaque lot tu peux les caser dans 1 ou plusieurs containers
mixtes. 9 fois sur 10, si ce n'est pas plus,
tu n'auras pas besoin de faire une tranche
mixte parce qu'il te restera un peu de marge dans le dernier
container. Donc il me semble que tu peux meme negliger ce cas
dans ton soft.

Par contre, dans un contexte africain ou sud-americain,
tu as interets a prevoir de la marge autour de tes cartons,
parce que effectivement les cartons sont "jetés" un peu
n'importe comment et ne sont quasi jamais jointifs.
Et il vaut mieux que ton soft prevois un nombre realiste de containers,
parce que si au dernier moment il faut louer un container de plus,
l'expediteur risque de raler. Enfin je te parle par experience
parce que j'ai travaillé sur de la gestion d'entrepot en angola, et
c'est deja pas triste (alors qu'il y a d'autres pays ou c'est encore pire)...

a+

eric

Emmanuel8 · November 2004

Je ne peux pas tabler sur 2 lots car le container va regrouper la fabrication de plusieurs usines prêtes à la même date. Ce nombre est variable.
Mais même si la jointure est approximative, je pense que l'humain peut dire "j'en ajoute 3 ici" (si vraiment c'est important pour économiser un container à quelques cartons près). De toutes façons j'affiche un plan de remplissage en 3D isométrique pour se donner une idée donc on voit si on peut "bourrer" un gros carton au dessus d'une pile de petits si nous avons un carton en trop.
Je pense tout de même comme tu dis que de toutes façons des jointures il n'y en aura pas trop (enfin je table là dessus) et je pense que leur problème sera rarement de l'ordre "j'ai 3 cartons qui ne rentrent pas" mais plutôt au moins de l'ordre 10-20 cartons.
Dans les calculs actuels la cliente qui fait tout à la main, enfin sous excel, calcule par exemple entre 300 et 336 cartons dans un container en fonction du sens du carton, 36 cartons c'est important, mais à 2 ou 3 près ce ne sera pas intolérable vu le besoin je pense.
Au pire cette partie du logiciel sera une aide à la décision qui a déjà mâché le plus gros du boulot au lieu de prendre la décision seule.

Trop fort pour le coup des cartons en angola, bien marrant.
En fait les gars mettent le container vertical et le remplissent avec une pelleteuse ? ;-)

Trop fort.
Concernant mon client, au lieu de "raler", au chine là bas si des cartons ne rentrent pas hé bien... on pourrait penser qu'ils vont les caser dans un container non rempli et leur facturer la location de la place comme c'est parfois le cas... Hé bien non !
Ils ne ralent pas, ils laissent simplement les cartons sur le quai !!!
Je trouve ça trop fort quand même.
Sinon pour eux la jointure est respectée car c'est mon client qui donne les consignes de remplissage (sens des cartons et ordre des lots).

Eric Chopin · November 2004

Ah ben je vois que c'est le mme cirque la bas. En angola
on essayait de trouver une geometrie de rangement de sacs de
riz pour pouvoir caser 10000 tonnes dans un entrepot.
On avait trouvé une geometrie pyramidale qui pouvait convenir mais
dans la pratique, c'est plutot 6000 a 8000 tonnes seulement
qu'on arrive a caser dans le plus grand entrepot,
du fait du rangement anarchique des sacs....

a+

eric

halouma · May 2011

slt tt le monde je suis en stage de projet de fin d eutude mon sujet c l 'optimisation de chargement d un conteneur . je suis a la recherche d un programme qui permet de remplir un conteneur par des carton de plusieurs dimension ;svpppppppppppppp c vous avez trouver une piste pour un telle programme aide moi voila mon email: halouma_coul@hotmail.com

gerard0 · May 2011

Chercher :
problème du sac à dos.
algorithmes gloutons.

halouma · May 2011

Merci, mais j'ai déjà lu le problème de sac à dos, mais c'est un peu dur à comprendre et très complexe.

gerard0 · May 2011

Désolé pour toi,

mais le problème que tu poses est lui-même très complexe, sauf dans des cas très particuliers.
Vois ton responsable de projet.

Cordialement.