Bonjour tout le monde.

J'ai besoin pour mon travail de mesurer la surface de grandes pièces afin de déterminer le nombre de camion à affreter pour le transport.

Je suis certain qu'il est possible de développer un programme simple de pavage de plan afin de me simplifier la tâche.

Ce serait également l'occasion d'apprendre à coder. Mais le hic c'est que je n'y connais rien. Je viens donc vers vous pour que vous me donniez des pistes et des conseils afin de m'aider à réaliser moi même ce programme.

Enfin je dis moi même, car ça m'a pas l'air bien complexe, voir même une très bonne approche pour une première expérience mais si vous pensez que c'est trop complexe dites le moi

Merci

Une calculatrice ça fait pas l'affaire ?

Le truc c'est que le pièces ont des dimensions variables et que la surface d'un camion est toujours la même.

Le but étant de mettre le maximum de pièces dans le minimum d'espace.

En soit oui je peux le faire à la main mais c'est pas optimal et c'est l'occasion d'apprendre quelque chose aussi

En soi, tu peux le faire avec le langage que tu veux.
Suis par exemple un cours de python sur openClassRoom.
Une fois que t'auras compris le fonctionnement des boucles et conditions, t'auras juste à faire une interface en console avec les informations à saisir et le programme te répondra le résultat.

Si on parle bien de gerer le chargement de camions pour maximiser le volume, cela fait partie de la famille des algos de "CLP" (Container Loading Problem), et c'est une gamme de problemes de combinatoire et d'heuristique bcp plus delicats qu'il n'y parait. On peut trouver des solutions "acceptables" assez naivement, mais des qu'on cherche á optimiser ou rajouter des contraintes,la complexité explose et il n'y a pas vraiment de solution facile.

C'est une branche tres etudiee, avec de multiple approches, donc la documentation et les articles de recherches sont nombreux.
Mais pour qqun qui se presente comme debutant, c'est d'un niveau assez peu accessible pour commencer.
(un debutant va, au mieux, arriver á un algo naif qui teste toutes les combinaisons en brute-force ; meme si on peut ameliorer avec des principes d'exploration de graphes, en pratique la complexité algorithmique exponentielle ne permet pas d'obtenir un resultat concret exploitable - sauf pour de tres petits echantillons, c-a-d oú c'est le moins utile)

Merci pour toutes ces infos mais dans mon cas il n'y a pas d'empilement de la marchandise donc il s'agit là de maximiser la surface et non le volume ce qui simplifie énormément le problème j'imagine.

De plus les éléments que je dois transporter sont assez volumineux. J'en mets donc rarement plus d'une douzaine par camions.

Donc le brute force pourrait tout à fait fonctionner dans mon cas il me semble.

124emePseudo,
Je doute que tu veuille programmer ca toi meme. Il y a des companies qui vendent des produit tout fait pour resoudre ces problemes la. Ou alors contacte le labo de RO locale et offre leur un contrat, ils te feront ce donttu as besoin.
Programmer ces trucs la toi meme, c'est complique. La tu n'y connais rien, tu vas passer des mois a apprendre des trucs avant d'arrive a une solution qui va probablement etre bancale.
Embauche un expert en RO et tu auras une solution la semaine prochaine.

D'autant que le moindre bug peut vite couter cher si le deployement a un impact sur une chaine logistique lourde. Rien que cela me parait une raison suffisante pour vouloir confier la tache a un expert

Il semblerait que j'ai sous estimé la difficulté du projet.

Je vais m'en remettre à des tiers pour trouver une solution efficace.

Merci pour vos réponses

Si j'ai bien compris ton problème j'utiliserai un algo génétique qui optimise le rangement des pièces dans un camion et après c'est juste une division

Le 07 novembre 2020 à 15:17:12 PinteDeSirop a écrit :
Si j'ai bien compris ton problème j'utiliserai un algo génétique qui optimise le rangement des pièces dans un camion et après c'est juste une division

Je ne voulais pas repondre techniquement pour commencer pour ne pas donner l'impression a OP que resoudre le probleme lui meme etait une bonne idee. OP lui meme n'a pas l'air de savoir quel est son probleme, parcequ'il appelle ca un probleme de pavage de plan. Mais regardons les situations:

Le probleme est peut etre vraiment un probleme de pavage de plan. Tu as des n objets de taille longueur_i X largeur_i et tu veux les mettre dans un espace de taille longueur_camion X largeur_camion. La comme ca, OP nous dit qu'il y a rarement plus de 12 objets dedans. Ca nous donne une solution simple: tu peux calculer une solution exacte. Une fois que tu as exprime toutes tes symmetries et contrainte d'espace un branch and bound va resoudre le probleme. Tu peux ecrire un algorithme genetique, mais un B&B va resoudre le probleme optimalement rapidement, du coup pourquoi se faire chier avec un algo adhoc?

Le probleme est que tu ne sais pas que le probleme est un pavage de plan. Tes boites ne font pas largeur x longeur, tu peux les tourner de 90 degree, auquel cas elles font longeur x largeur. Tu peux aussi les tourner de 45 degree, ou a n'importe quel angle tu veux. Et ca a l'air con comme ca, mais il y a plein de cas ou c'est ce que tu veux faire.

Et tu penses que tes boites font longeur x largeur, mais en fait, elles font longeur x largeur x hauteur. Et tu pourrais tourner les boites sur un de leur cote. Du fait, pour chaque boite, tu as trois facons de les poser au sol, et l'une des facon est certainement bien mieux que les autres. Sauf qu'il y a certainement des boites que tu peux tourner sur le cote et des boites que tu ne peux pas tourner sur le cote.

Et si tu pense que le probleme est complique quand tu arrives la, en fait, on ne fait que commencer. Parceque tu pense que tous les plans au sol sont equivalent, mais dans plein de cas, ils ne le sont pas. Il y a desplacement qui sont preferable a d'autre. Par exemple, tu peux vouloir assurer que tu ne met pas toutes les boites lourdes du meme cote du camion pour ne pas sucharger un des essieux du camion. Ou tu peux vouloir mettre certaines boites a l'arriere du camion parceque ce sont les premieres qu'il faut decharger.

Mais le vrai probleme d'OP est que ce n'est pas un probleme de pavage de plan, c'est un probleme de minimization du nombre de plan qui peuvent paver toutes les boites. Le probleme d'OP est de minimiser le nombre de camion. Donc son vrai probleme est plus un probleme de bin packing 2d qu'autre chose. C'est le probleme d'allouer les boites a des camions de facon a ce que chaque camion puisse etre paver, en tenant compte des rotations et companie.

Et c'est pour ca que tu parles a un expert en recherche operationel. Parcequ'un novice va croire qu'il a compris le probleme et il va pondre un code potentiellement complique et optimiser pour ce qu'il a compris alors que le probleme est different.

Un expert en logistique va probablement commencer par pondre un programme lineaire en nombre entier pour resoudre le probleme et utiliser un solver pour faire l'optimisation. Ca prends quelques heures pour prendre les onne en parametres, quelques heures pour ecrire le ILP, probablement une journee pour encoder le ILP dans un solveur ou une interface de solveur, et quelques heures pour generer un plan utilisable par le client.

Parceque le vrai probleme est un probleme de modelisation avant d'etre un probleme de resolution. Les solveurs modernes savent reconnaitre les structures des contraintes et savent applique tout un tas de technique super fute pour ameliorer les performances du solveur. Ils ont des heuristique internes qui sont configurable pour utiliser des algos de voisinages, des algo a population, un B&B tronque et ce genre de chose. Et modeliser le probleme avec un outils de programmation mathematique c'est faisable en une journee, alors que adapter un algo genetique construit pour un probleme pour en resoudre un autre, c'est le bordel.

Si vraiment une fois le probleme ecrit, le temps de resolution est trop eleve, tu peux commencer a reflechir a comment optimiser le bousin, ou acheter un solveur commercial. Mais probablement, ce n'est pas vraiment le probleme du client final.

En bon informaticien qu'on est on a tendance a penser que le probleme est a la resolution, mais vraiment le probleme est de modelisation et d'exploration de l'espace de solution, c'est pas un probleme de resolution.

Tu mets quoi dans ton carton, c’est des tailles standard ?

Ce ne sont pas des cartons, ce sont d'imposantes pièces métalliques usinés de tailles variables et pesant plusieurs centaines de kg.

Ce sont toujours des pièces rectangulaires. Donc il y a deux possibilités, dans le sens de la longueur ou dans le sens de la largeur.

Impossible également de les tourner sur le côté.

Merci en tout cas pour les réponses apportés jusqu'à présent, c'est très intéressant

(et ca les amis, c'est la question d'un mec qui a deja vu un probleme du meme genre)

Si c’est des rectangles standard avec un seul sens ça limite les possibilités, je me demande si tu peux pas gérer ça avec excel