J'ai aussi des articles en vrac en quantités : V1 V2 V3 V4 V5 (Vi >= 0 pour l'article Ai)
.
J'ai une commande avec les quantités respectives demandées Q1 Q2 Q3 Q4 Q5 pour les articles Ai. (Qi >= 0)
.
Le problème :
- Déterminer quels colis doivent être choisis pour répondre à la commande, de manière que :
* le nombre maximum d'articles soient issus des colis * le nombre minimum de colis soient utilisés (facultatif) * Pour chaque article, si la somme issue des colis est inférieure à la somme demandée, il FAUT pouvoir compléter avec la quantité de vrac.
Dans le cas contraire, l'algorithme doit rendre KO.
.
Il faut donc déterminer les colis Cj tels pour chaque quantité Qk commandée : Qk = somme(AkQj) + Rk avec les j tels que 1 <= j <= n et 0 <= Rk <= Vk
.
Pour fixer les idées, on peut penser aux colis comme contenant des pointures différentes d'un même modèle de chaussure. Le magasin commande une certaine quantité de chaque pointure. Cette commande doit être livrée en utilisant prioritairement des colis déjà existants, et complétée si nécessaire avec du stock en vrac.
.
L'approche que j'ai trouvée pour l'instant consiste à utiliser la programmation dynamique en générant les différentes combinaisons possibles sous forme d'états.
Mais cela reste très coûteux en mémoire (et probablement en calcul), le nombre de colis pouvant dépasser la centaine avec au plus 25 articles différents. En effet, cela donne au pire 2 puissance n états pour n colis (2 puissance 100 vaut environ 10 puissance 31).
.
Quelqu'un connaîtrait-il une autre approche ?
.
Je vous remercie pour votre aide,
.
Joyel
- Edité par Joyel 26 mars 2019 à 22:34:30
Problème d'optimisation combinatoire
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
