Problème d'optimisation - remplissage bourriches d'huitres

[jcthomas3d]

Bonjour,

Quelle approche emploieriez vous pour résoudre ce problème d'optimisation svp ?
Des huitres de calibre 3 sont acheminées sur un convoyeur : leur masse se situe entre 66g et 85g avec une distribution uniforme.
N bourriches sont en attente de remplissage à côté du convoyeur : elles doivent être remplies avec au minimum 12 huitres et atteindre une masse minimale de 1kg.
On ne connait pas la masse des huitres à priori : un robot prend une huitre, mesure sa masse et doit choisir la bourriche de destination.
L'objectif est de minimiser le nombre d'huitres et la masse des bourriches remplies pour produire le plus de bourriches possibles avec une nombre d'huitres donné.

J'ai tenté implémenter plusieurs algorithmes :
- Choix aléatoire de la bourriche de destination
- Choix aléatoire excepté pour la dernière huitre faisant dépasser la masse requise pour obtenir la masse minimale
- Choix selon un critère d'écart à la masse moyenne attendue
- Mélange de ces différents algo en fonction de la masse de l'huitre

Quelque soit l'algo déployé, j'arrive à une moyenne de plus ou moins 13.6 huitres par bourriche.
En considérant une masse moyenne des huitres à (66+85)/2=75.5g, on s'attendrait à obtenir 13.25 huitres en moyenne dans une bourriche de 1kg.

Pensez-vous svp qu'il existe un moyen de prendre une "meilleure" décision quant à la bourriche de destination pour se rapprocher de cette valeur ?
Merci par avance pour vos réflexions
-----

[GBZM]

Bonjour,

Mais combien de bourriches remplis-tu simultanément ?
Une ou vingt, ça fait une différence ...

[titijoy3]

pour moi il faut faire des essais à la main pour affiner les meilleures solutions puis entrer ça dans le programme,

par exemple remplir une bourriche avec de grosses huitres puis en remplacer une partie par des petites de façon à atteindre le nombre imposé de douze ?

pour les petites tailles il y aura forcement un nombre suffisant, à moins qu'il faille panacher obligatoirement avec des petites et des grosses ?

[Deedee81]

Salut,

Le problème optimal est NP-Complet. Donc il vaut mieux trouver un algo raisonnable donnants de bons résultats.

Un point d'entrée sur ce type de problème et les algorithmes :
https://fr.wikipedia.org/wiki/Probl%...sac_%C3%A0_dos

[A voir en vidéo sur Futura]

[MissJenny]

je n'ai pas du tout compris la même chose que deedee. Ce que j'ai compris c'est que le convoyeur apportait les huîtres l'une après l'autre et qu'il fallait prendre la décision d'affecter cette huître à cette bourriche sur l'instant, sans pouvoir revenir en arrière et redistribuer les huîtres, et sans connaître le poids des huîtres à venir. Donc le problème serait à rapprocher du problème de la secrétaire, plus que du problème du sac à dos.

par ailleurs, le fait qu'un problème soit NP-complet n'interdit pas de chercher une solution exacte. On sait juste qu'elle sera impraticable si la taille du problème augmente, mais si en pratique on reste dans des tailles raisonnables tout va bien.

[Deedee81]

SAlut,

je n'ai pas du tout compris la même chose que deedee. Ce que j'ai compris c'est que le convoyeur apportait les huîtres l'une après l'autre et qu'il fallait prendre la décision d'affecter cette huître à cette bourriche sur l'instant, sans pouvoir revenir en arrière et redistribuer les huîtres, et sans connaître le poids des huîtres à venir. Donc le problème serait à rapprocher du problème de la secrétaire, plus que du problème du sac à dos.

En effet, j'ai probablement mal compris. J'ai lu "N bourriches" et là j'ai compris de travers.

[jcthomas3d]

En fait il pourrait y avoir 2, 4 ou 8 bourriches à remplir en même temps. Ce nombre n'est pas défini.
L'algo doit tourner quelque soit le nombre de bourriches à remplir.

[jcthomas3d]

Merci d'avoir pris le temps de réfléchir à cette problématique !
Intéressant la résolution du problème des secrétaires, pas encore compris le truc des 37%, mais je vais regarder ça plus en détail.

Pour affiner l'explication du problème : une caméra visionne par haut-dessus les huitres défilant sur le convoyeur, en retrouvant le contour des huitres, on est capable d'en estimer la masse.
Il y a un certain laps de temps entre la vision et le robot de prise-dépose qui permet de manipuler des "bourriches virtuelles" avant d'informer le robot sur les positions de prise et de dépose.

J'ai trouvé un algo qui a tourné tout le weekend (en C#) et qui a l'air de bien fonctionné pour 2 bourriches à remplir simultanément :
- Remplissage de la première bourriche jusqu'à atteindre 13 huitres ou la masse requise de 1kg
- Ensuite on "échange" intelligemment les huitres suivantes avec des huitres déjà présentes dans la bourriche (une grosse par une petite pour réduire la masse, ou l'inverse pour augmenter la masse de la bourriche)
- On stoppe les échanges quand la masse est à 1kg (+epsilon) ou quand toutes les huitres ont déjà été échangées
- je stocke la première bourriche dans une queue et la seconde devient la première, et ainsi de suite

Bilan après 2 jours de fonctionnement virtuel : 13.22 huitres en moyenne par bourriche (78% de bourriches à 13 huitres et 21% à 14 huitres), 95% des bourriches font 1kg (+epsilon)
Je poursuis mes investigations, merci à vous

[MissJenny]

ah donc j'avais mal compris et Deedee avait mieux compris : si tu peux échanger les huîtres entre bourriches on est plutôt dans un problème du type "sac à dos" que dans un problème du type "secrétaire" où on doit prendre des décisions sans connaître la totalité des données.