Discussion :

[GoustiFruit]

Bonjour,

Je cherche des pistes pour résoudre ce problème:

- j'ai un certain nombre de paquets tous de même dimension, mais dont le poids varie entre 1 et 20 kg
- à placer dans des conteneurs ayant une capacité totale maxi de 8 paquets et de 20 kg
-> comment faire pour placer l'ensemble des paquets dans un minimum de conteneurs ?

S'il n'y avait que le poids, j'aurai pu m'en tirer avec algorithme "First-Fit Decreasing" mais la contrainte "maximum 8 paquets par conteneur" me pose problème

Je ne cherche pas une solution optimale, mais quelque chose de raisonnablement efficace et rapide...

Merci d'avance.

[pseudocode]

Pourquoi ne pas faire une première passe pour trouver les configurations valides 8 paquets / 20 kg, sans contrainte de dimensions. Et ensuite faire le bin-packing sur ces configuration exclusivement.

[GoustiFruit]

Je ne comprends pas ce que tu veux dire !? Il n'y a pas de contrainte de dimension, seulement de poids et de nombre d'emplacements par conteneur. Un "first-fit decreasing" sur le poids n'est pas suffisant car je pourrais me retrouver avec des associations de paquets totalisant 20 kg (ou moins) mais dépassant la limite de 8 paquets possibles par conteneur. Les conteneurs peuvent contenir de 1 à 8 paquets bien sûr, ce n'est pas fixé à 8.

[pseudocode]

Je ne comprends pas ce que tu veux dire !? Il n'y a pas de contrainte de dimension, seulement de poids et de nombre d'emplacements par conteneur.

Ah, désolé. Quand je vois bin-packing et conteneur, j'ai tendance à penser à Tetris.

Ton problème à l'air d'être connu sous le nom "Bin Packing with Cardinality Constraints".

Je ne connais pas l'état de l'art en la matière, mais ca m'a l'air de passer par des méta-heuristiques du genre 'recherches locales'.

[GoustiFruit]

Merci, avec le nom que tu m'as donné j'ai pu trouver ceci (pdf): http://paginas.fe.up.pt/~esicup/tiki....php?fileId=98
qui semble correspondre à mon problème précis. J'étudierai ça demain, il est trop tard ce soir