Discussion :

[hubsm]

Bonjour,

On doit préparer plusieurs commandes Cx de produits P avec des quantités différentes :
- Commande C1 qté 2
- Commande C2 qté 1
- Commande C3 qté 3
- Commande C4 qté 1
- ...
- etc pour plusieurs dizaines de commandes.

Je dois regrouper ces commandes afin de déstocker, dans la mesure du possible, des palettes complètes de 50 produits (50 étant variable suivant le produit à traiter).
Un regroupement ne doit pas dépasser 50 produits.
Comment optimiser les regroupements de commandes afin d'avoir un maximum de palettes complètes de 50 produits ?
Et non pas des palettes "presque complètes" de 49, 48, 47 produits.

Je précise que je travaille actuellement en PL/SQL (Oracle) mais peu importe il s'agit d'algorithmique.

Cordialement.

[Flodelarab]

Bonjour

C'est typiquement le "problème du sac-à-dos", pour lequel il n'existe aucune solution mathématiquement parfaite, actuellement. Tu vas être obligé de faire tous les cas possibles jusqu'à trouver une somme égale à 50. Une méthode d'exploration est de commencer par les grosses commandes.

25-20-12-10-10-10, il faut trouver 20 + 10 + 10 + 10. Ce n'est pas la solution qui prend le plus gros.

[dourouc05]

C'est typiquement le "problème du sac-à-dos", pour lequel il n'existe aucune solution mathématiquement parfaite, actuellement.

Ce n'est pas vraiment un problème de sac à dos (pour lequel il existe un algorithme super efficace de programmation dynamique, bien que pas polynomial : https://fr.wikipedia.org/wiki/Probl%...tion_dynamique), puisqu'on n'y considère qu'un seul sac à dos. C'est plutôt du remplissage de conteneurs (bin packing), la version de base cherchant à minimiser le nombre de palettes à remplir (même si aucune n'est remplie à fond) : https://en.wikipedia.org/wiki/Packing_problems, https://en.wikipedia.org/wiki/Bin_packing_problem. Wikipedia propose une série d'algorithmes efficaces (mais pas polynomiaux).

[hubsm]

Bonjour !

Merci pour vos réponses, je vais explorer ces pistes

[dourouc05]

À mon avis, le plus simple serait de t'interfacer avec une solveur d'optimisation mathématique, ça serait tellement plus simple d'adapter une formulation de bin packing pour avoir un maximum de palettes de cinquante items. Maintenant, ça nécessite d'appeler des bibliothèques externes (à la CPLEX ou Cbc, que tu peux appeler en C).