Algorithme de chargement de camion

Version imprimable

10/10/2019, 09h09
Holt.

2 pièce(s) jointe(s)

Algorithme de chargement de camion
Bonjour à toutes et à tous,

Je voudrais coder un programme d'optimisation de chargement de camion, l'objectif étant de minimiser le mètre plancher linéaire.
En un mot pour ceux et celles à qui ça ne parle pas, c'est simplement la longueur occupée par le chargement dans un camion.
Il faut donc tout bien ranger en partant du fond et en avançant le moins possible.

J'ai lu de nombreux articles à ce sujet (thèses, pseudo codes, articles) : il est question ici du problème bien connu de bin-packing :
https://fr.wikipedia.org/wiki/Probl%...de_bin_packing

Pour éviter de réinventer la roue, j'ai cherché des codes existants sur lesquels me baser et j'ai trouvé celui en pièce jointe, "container.c", écrit il y a plus de 20 ans.
Voici le lien vers la page des codes de son créateur, David Pisinger :
http://hjemmesider.diku.dk/~pisinger/codes.html
(Merci beaucoup à lui de m'avoir permis de discuter de son programme sur les forums).

Je l'ai téléchargé et testé, ça fonctionne correctement. J'ai utilisé la pièce jointe "loading.c" (en ajoutant simplement la fonction main) sur le site https://www.onlinegdb.com/online_c_compiler

C'est maintenant que ça se complique... Je voudrais ajouter 3 contraintes :
- Une boîte ne peut pas être placée sur une boîte plus petite
- Les boîtes ne peuvent pas être positionnées sur le côté
- Certaines boîtes ne peuvent pas être empilées
Je suis persuadé que ce n'est pas grand chose mais je suis débutant complet en C alors je perd le fil en essayant de suivre les variables et fonctions... Donc toute aide serait la bienvenue !

J'espère que quelqu'un pourra m'aiguiller.

Merci par avance et bonne journée.
10/10/2019, 10h13
dalfab

Citation:

Envoyé par Holt.

Je suis persuadé que ce n'est pas grand chose mais je suis débutant complet en C alors je perd le fil en essayant de suivre les variables et fonctions... Donc toute aide serait la bienvenue !

Moi je pratique le C depuis plus de 30 ans, et à la vue du code je ne dirais pas que ça n'est pas grand chose. Le code est propre mais il faut le ré-associer aux concepts, y ajouter les tiens, vérifier que le découpage reste compatible, puis adapter. Il est certainement plus simple de tout reposer.

Une question : il existe des tas de langages, pourquoi utiliser le C? Il existe aujourd'hui d'autres candidats.
10/10/2019, 11h30
Holt.

Citation:

Envoyé par dalfab

Une question : il existe des tas de langages, pourquoi utiliser le C? Il existe aujourd'hui d'autres candidats.

Merci dalfab de te pencher sur mon problème.

Je ne tiens pas particulièrement à utiliser le C, je suis parti de ce programme tout simplement parce que c'est la seule implémentation que j'ai trouvée.
Pour ma part je développe essentiellement avec WinDev et je suis parallèlement en train d'essayer d'implémenter mon propre algorithme dans un programme existant.

Pour revenir au code, je pensais (naïvement sans doute) par exemple qu'une retouche de la fonction "turnboxes" permettrait dans un premier temps d'éliminer les rotations non désirées.
Il faudrait pour cela je pense bloquer les swaps longueur/hauteur et largeur/hauteur.

Pour les deux autres points, ce serait au niveau de la recherche d'espace vide : éliminer ceux au-dessus d'une boîte marquée comme non empilable avec un booléen et ceux dont la surface est inférieure à celle de la base de la prochaine boîte à placer.
Mais là c'est déjà plus flou.

En tous les cas si pour quelqu'un d'aussi expérimenté que toi cela paraît être une tâche compliquée, il me semble plus raisonnable de stopper mes recherches dans cette direction...
12/10/2019, 12h42
Sve@r
Bonjour
Citation:
Envoyé par Holt.

C'est maintenant que ça se complique... Je voudrais ajouter 3 contraintes :

Une boîte ne peut pas être placée sur une boîte plus petite
Les boîtes ne peuvent pas être positionnées sur le côté
Certaines boîtes ne peuvent pas être empilées

Je suis persuadé que ce n'est pas grand chose...
C'est énorme. Tu dois modéliser chaque contrainte et les impliquer dans la recherche (déjà modéliser la notion de "certaines boites"...:weird:).
Déjà le problème initial fait "partie de la classe des problèmes NP-difficiles. Sauf si P = NP, on ne peut pas le résoudre à l'aide d'un algorithme de complexité polynomiale" (page wiki dont tu donnes le lien). Donc il faut une recherche récursive (ce qu'il a simulé avec sa pile et les fonctions push() et pop()). A vue de nez en rajoutant tes contraintes ça va complexifier le truc puissance 3.

Ce n'est pas parce qu'un truc est facile "pour toi" qu'il est facile pour un ordi. Il y a quelques années j'étais tombé sur un article qui montrait une position d'échecs évidente pour n'importe quel débutant mais que les ordinateurs n'arrivaient pas à résoudre. Parce que l'un des rois avait quelques pions mais il était bloqué tandis que l'autre roi en avait pas mal mais qui le gênaient. Il lui suffisait donc de faire le tour de son armée et aller bouffer tranquillement les pions adverses puis mener ensuite ses pions à la promotion. Mais cette solution nécessiitait une dizaine de coups ce qui, pour un ordinateur, demandait un examen très profond (un ordinateur ne voit qu'une pièce à la fois) et le nombre de possibilités était alors exponentiel.
Bon c'était avant l'arrivée d'ordinateurs puissants et de logiciels semi-intelligents comme "Fritz" mais c'est pour illustrer.

Autre exemple
Code:

1 2 3 4 unsigned long fib(unsigned short n) { if (n < 2) return 1; return fib(n-2) + fib(n-1); }
fonction assez simple à comprendre... mais qui te gèlera ta bécane à partir de (approximativement) fib(35).
12/10/2019, 22h55
sambia39
Bonsoir,

Citation:

Envoyé par Sve@r

Bonjour
Déjà le problème initial fait "partie de la classe des problèmes NP-difficiles. Sauf si P = NP, on ne peut pas le résoudre à l'aide d'un algorithme de complexité polynomiale" (page wiki dont tu donnes le lien). Donc il faut une recherche récursive (ce qu'il a simulé avec sa pile et les fonctions push() et pop()). A vue de nez en rajoutant tes contraintes ça va complexifier le truc puissance 3.

Je ne suis pas d’accord. Nous ne sommes pas dans un cas NP-Dificiles, mais bien dans un cas NP-Complet dans lequel on cherche à optimiser le rangement des boîtes avec un certain nombre de contraintes établies évoquées par @Holt (réduire le mètre plancher linéaire nécessaire pour le rangement des cartons dans un camion.) en prenant en compte par exemple la taille des cartons.

Et si l’on parle uniquement du cas des contraintes, cela est lié au problème de décision (donc d’instance) ; formulé autrement cela reviendrait à dire que l’on ajoute des contraintes au problème de bin-packing et donc on se trouve dans le cas d’un bin-packing soumis à de divers critères ou contraintes additionnelles exemple:
- Existe-t-il un rangement de "boîte ne pouvant pas être placé sur une boîte plus petite" dans le camion qui a une capacité (volume) de X ?
- Existe-t-il un rangement de "certaine boite ne pouvant pas être placé sur le côté" dans le camion qui a une capacité (volume) de X ?
- Existe-t-il des rangement de " certaine boite qui ne peuvent pas être empilé" dans le camion qui a une capacité (volume) de X .
Ce qui nous amène effectivement sur le terrain des problèmes liés à l'optimisation dont @Holt. en parle au début et il a bien raison de dire que cela devient compliqué parce que si l'on démontre que le problème lié aux décisions est difficile, on peut alors certifier que le problème lié a son optimisation l'ait également.

Donc, implémenter en partant du code source proposé par David Pisinger qui à l'origine traite de rangement de cartons d'une taille rectangulaire dans un box de taille rectangulaire de façon à maximiser l'espace de stockage tout en plaçant les boites dans n'importe quelle direction et sans contrainte en un code dont les contraintes sont définies ou ajoutées. ; comme je l’ai annoncé au début devient un problème d’optimisation multi-contraintes qui implique un certain nombre d’adaptations du code ou tout simplement une autre implémentation, car dans un cas d’un bin-packing soumis à de divers critères ou contraintes additionnelles, les algorithmes de résolution sont soit heuristiques ou génétiques.

Au passage je ne comprends pas ce que tu veux dire par ce qui suit et même le rapport:

Citation:

Envoyé par Sve@r

C'est énorme. Tu dois modéliser chaque contrainte et les impliquer dans la recherche (déjà modéliser la notion de "certaines boites"...).
........
Ce n'est pas parce qu'un truc est facile "pour toi" qu'il est facile pour un ordi. Il y a quelques années j'étais tombé sur un article qui montrait une position d'échecs évidente pour n'importe quel débutant mais que les ordinateurs n'arrivaient pas à résoudre. Parce que l'un des rois avait quelques pions mais il était bloqué tandis que l'autre roi en avait pas mal mais qui le gênaient. Il lui suffisait donc de faire le tour de son armée et aller bouffer tranquillement les pions adverses puis mener ensuite ses pions à la promotion. Mais cette solution nécessiitait une dizaine de coups ce qui, pour un ordinateur, demandait un examen très profond (un ordinateur ne voit qu'une pièce à la fois) et le nombre de possibilités était alors exponentiel.
Bon c'était avant l'arrivée d'ordinateurs puissants et de logiciels semi-intelligents comme "Fritz" mais c'est pour illustrer.

Ceci dit dans le code source il y a des moyens de représenter une boîte à travers les variables W, H, D et w, h, d. La seule crainte ici est peut-être d’éviter d’avoir « n » (la taille du problème) qu’il soit très grand, c'est-à-dire nombre de cartons très grands.

Au finale, le problème qui se pose, ce n’est pas tant l’implémentation du code ou la modification du code en langage de programmation C, mais : existe-t-il une implémentation d’un algorithme permettant de prendre en compte un des critères ou contraintes énoncés et résoudre le problème (ou du moins qui s’en approche) ?

De manière générale, ce qui se fait le plus souvent est l’utilisation des algorithmes heuristiques et dans des cas que je qualifierais de très avancés ;ce sont des algorithmes génétiques qui sont utilisés pour des solutions à un problème dont il n'y a pas de solution pour résoudre un problème en un temps raisonnable.

Bref,en ce qui concerne la résolution du problème, je commencerais par implémenter la contrainte la plus simple et qui permet d’obtenir un résultat, c'est-à-dire « une boîte ne peut pas être placée sur une boîte plus petite » et si vous souhaitez voir un exemple qui y ressemble, essayez le très bon exercice qui est le problème du voyageur de commerce ou du sac à dos ;c’est un très bon point de départ.

À bientôt.
13/10/2019, 09h51
Sve@r

Citation:

Envoyé par sambia39

Je ne suis pas d’accord.

Quoi d'étonnant ? Chaque fois que je dis un truc tu rappliques soit en disant "je suis d'accord mais on peut faire quand-même ..." ou bien "je ne suis pas d'accord"...

Citation:

Envoyé par sambia39

Nous ne sommes pas dans un cas NP-Dificiles, mais bien dans un cas NP-Complet

Admettons (il faudra alors modifier la page wiki qui en parle). Mais ça change quoi hormis une plus grande difficulté ? Les np-complets font partie des problèmes mathématiques non résolus. Remarque si tu arrives à les résoudre tu gagnes 1M$ par problème...

Citation:

Envoyé par sambia39

[*]Existe-t-il un rangement de "boîte ne pouvant pas être placé sur une boîte plus petite" dans le camion qui a une capacité (volume) de X ?

Donc déjà on ne traite plus d'une boite dans un espace vide mais d'une boite dans un espace vide mais aussi en liaison avec la boite située sous-elle. Plus facile ou plus difficile ?

Citation:

Envoyé par sambia39

[*]Existe-t-il un rangement de "certaine boite ne pouvant pas être placé sur le côté" dans le camion qui a une capacité (volume) de X ?[*]Existe-t-il des rangement de " certaine boite qui ne peuvent pas être empilé" dans le camion qui a une capacité (volume) de X .

T'as raison, reste dans le flou. C'est quoi pour toi "certaines boites" (qustion déjà posée) ?

Citation:

Envoyé par sambia39

Donc, implémenter en partant du code source proposé par David Pisinger qui à l'origine traite de rangement de cartons d'une taille rectangulaire dans un box de taille rectangulaire de façon à maximiser l'espace de stockage tout en plaçant les boites dans n'importe quelle direction et sans contrainte en un code dont les contraintes sont définies ou ajoutées. ; comme je l’ai annoncé au début devient un problème d’optimisation multi-contraintes qui implique un certain nombre d’adaptations du code ou tout simplement une autre implémentation, car dans un cas d’un bin-packing soumis à de divers critères ou contraintes additionnelles, les algorithmes de résolution sont soit heuristiques ou génétiques.

Et comme je l'ai dit au début "tout ça c'est énorme", chose avec laquelle tu n'es pas d'accord tout en redisant la même chose en plus volubile

Citation:

Envoyé par sambia39

Au passage je ne comprends pas ce que tu veux dire par ce qui suit et même le rapport:

C'est une métaphore. Un exemple illustratif du fait que 1) certains cheminements pour arriver à un but et qui sont évidents pour toi ne le sont pas forcéement pour un ordinateur (le PO semblait dire "il n'y a pas beaucoup de changements donc ça doit être facile") et 2) certains problèmes mêmes posés de façon simple et même exprimés algorithmiquement de façon tout aussi simple ne sont pas calculables par un ordinateur. Dans ce second exemple (fib) évidemment le souci vient de l'algorithme qui, s'il est écrit de façon itérative, donnera alors des réponses rapides pour des valeurs même très grandes mais déjà il n'est parfois pas possible de remplacer un algorithme récursif par un itératif (ex fonction d'Ackerman) et d'autre part je voulais montrer le fait qu'une solution, même si elle s'appuie sur une formulation mathématique (tout élève de 5° connait la suite de Fibonacci et sa formulation mathématique) peut être catastrophique pour un ordinateur qui n'a pas, (comme pour l'élève), l'instinct de conserver les solutions déjà calculées pour les réutiliser.

Citation:

Envoyé par sambia39

Au finale, le problème qui se pose, ce n’est pas tant l’implémentation du code ou la modification du code en langage de programmation C, mais : existe-t-il une implémentation d’un algorithme permettant de prendre en compte un des critères ou contraintes énoncés et résoudre le problème (ou du moins qui s’en approche) ?

De manière générale, ce qui se fait le plus souvent est l’utilisation des algorithmes heuristiques et dans des cas que je qualifierais de très avancés ;ce sont des algorithmes génétiques qui sont utilisés pour des solutions à un problème dont il n'y a pas de solution pour résoudre un problème en un temps raisonnable.

Bref,en ce qui concerne la résolution du problème, je commencerais par implémenter la contrainte la plus simple et qui permet d’obtenir un résultat, c'est-à-dire « une boîte ne peut pas être placée sur une boîte plus petite » et si vous souhaitez voir un exemple qui y ressemble, essayez le très bon exercice qui est le problème du voyageur de commerce ou du sac à dos ;c’est un très bon point de départ.

T'as raison. Au lieu d'aider le PO à résoudre son souci, tu fais tout un discours pompeux (tu aimes bien t'écouter parler toi non ?) dans lequel on ne sait finalement pas si c'est possible ou pas puis tu lui dis "essaye plutôt d'implémenter cet autre problème tout aussi difficile"...
:applo:
13/10/2019, 22h56
sambia39

@Sve@r Sais-tu de quoi parle l’article de Wikipédia et pourquoi j'arrive à la conclusion que le que bin-packing, tout comme le problème de l’OP, est du type NP-Complet ?

1) Il traduit de façon simple que tout problème ne peut être résolu en temps dit polynomial et à ce jour, aucun algorithme à temps polynomial n'a été découvert pour un problème NP-Complet. Cela ne veut pas dire que personne n'a prouvé qu'il n'existe pas d'algorithme à temps polynomial pour les problèmes de type NP-Complet. Les problèmes NP-Difficile sont des problèmes que l'on peut ramener à un problème de classe NP, mais qui peut appartenir à une classe plus difficile que NP (qui peut être résolu par un algorithme polynomial). Donc, si tu as un problème qui est à la fois NP et NP-Difficile, tu as à faire à un problème NP-complet.

2) En algorithme/mathématique, tu ne peux pas balancer une réponse en disant que c'est NP-Difficile. Qu'est ce qui le prouve ?

Prenons un exemple simplissime sur les graphes (un cas d'école) pour la compréhension : imaginons que tu as un graphe et que tu souhaites déterminer si ce graphe à un chemin hamiltonien, tu vas commencer par retirer ou occulté les différents arcs ou arrêtes pour trouver un chemin/cycle hamiltonien et le fait de les retirer/ occulté va permettre de le réduire. Tu ramènes donc le problème en un autre, appelé problème de décision. L'action que tu entreprends pour le savoir peut-elle se faire dans un temps raisonnable ? Admets que c’est difficile à déterminer. On est dans le cas d‘un problème NP-complet. Donc, au lieu de chercher une solution qui permet de répondre à ta question, tu opteras pour un algorithme qui donnera une réponse approximative. Ce qui nous ramène à ce que dit l’article de Wikipédia : S'il existe un problème NP-Complet qui est résoluble en temps polymonial, alors P=NP ; tant dit que s'il existe un problème NP qui n'est pas résoluble en temps polynomial alors aucun problème de type NP-Complet n'est résoluble en temps polynomial.

Les NP-Complets sont donc des problèmes liés aux décisions et d’optimisation, car si le problème lié aux décisions est difficile (voir mon précédent poste), tu peux alors être sûr que le problème lié à son optimisation l'est également. Tu ne vas pas tenter de trouver un algorithme qui va résoudre ton problème, car quand on démontre qu'un problème est NP-Complet, on énonce son degré de difficulté. On n'essaye pas de prouver qu'il existe un algorithme efficace qui répond au problème, mais la probabilité qu'il n'existe pas un tel algorithme sur le problème donné.

Passons au cas de ma réponse à l'OP. Il souhaite ranger des box ou cartons dans un camion, mais avec des contraintes alors comment doit ton faire pour ranger nos cartons tout en respectant ces diverses contraintes ? N'a-t-on pas là un problème NP-Complet ? Comprends-tu maintenant pourquoi je ne suis pas d'accord sur le fait que c’est un problème NP-Difficiles ?

Dans mon précédent poste, dis-moi alors de quel floue il s’agit ? A croire que tu ne sais absolument pas de quoi il est question ici. Comprends-tu également pourquoi j'oriente l'OP vers une implémentation d'algorithmes heuristiques ou génétiques ?. Et pour faciliter la compréhension, rien de plus pratique que de traiter un cas similaire (problème de décision donc NP-Complet) le problème du voyageur de commerce et le problème du sac à dos comme bon point de départ.

Je préfère donc être précis : c’est un problème NP-complet et pas NP-Difficile et je ne suis pas d'accord avec ta réponse.
14/10/2019, 15h24
Médinoc

En cherchant la différence entre NP complet et NP-difficile, je suis tombé là-dessus:
https://fr.quora.com/Quelle-est-la-d...t-NP-Difficile

Si NP-Complet = NP ∩ NP-Difficile, ça veut dire que NP-Complet ⊂ NP-Difficile, et que donc, qualifier un problème NP-Complet de NP-Difficile n'est pas faux.
15/10/2019, 15h24
Holt.
Bonjour,

Merci à tous pour vos interventions.
Je ne pensais pas avec ma question initiale déclencher un débat...

En fait lorsque je disais "Je suis persuadé que ce n'est pas grand chose", j'imaginais pouvoir m'en sortir avec quelques retouches de code.
Je suis parti sur cette piste car M. Pisinger lui même m'a dit que cela devrait être possible sans trop d'efforts.

Donc en regardant le code, je me suis dit :
- Pour ne pas mettre une boîte sur le côté, mettre en commentaire les rotations selon les axes horizontaux
- Pour ne pas empiler une boîte sur une plus petite, ne pas prendre en compte les espaces vides disponibles dont la surface est inférieure à la boîte qu'on veut placer
- Pour ne pas recouvrir du tout une boîte, ne pas prendre en compte sa surface supérieure lors de la mise à jour des espaces vides
Et comme je n'y connais pas grand chose en C, je suis venu poster cette demande ici.

Mais j'ai bien compris maintenant que ce ne serait pas chose aisée alors j'ai continué sur mon autre programme (dans un langage que je maîtrise) et j'avance bien.
Je me base sur l'algo Best Fit Decreasing et je m'inspire aussi de la méthode du Wall Building.
J'ai dans un premier temps simulé ce que ça aurait donné avec quelques boîtes, le résultat me paraît satisfaisant, je verrai bien lorsqu'il sera terminé et que je lancerai les tests.

Bonne journée à vous.