Problème d'optimisation combinatoire

Bonjour,

Je dois programmer un algorithme qui répond au problème suivant :

J'ai n colis qui contiennent tous le même article, mais avec des quantités éventuellement différentes pour les tailles (5 tailles dans l'exemple, 25 en pratique).

C1 : T1C1 T2C1 T3C1 T4C1 T5C1
C2 : T1C2 T2C2 T3C2 T4C2 T5C2
...
Cn : T1Cn T2Cn T3Cn T4Cn T5Cn (TiCj >= 0)

J'ai des articles en vrac en quantités : V1 V2 V3 V4 V5 (Vi >= 0)

J'ai une commande pour cet article avec les quantités Q1 Q2 Q3 Q4 Q5 pour les tailles. (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 taille, 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 pour chaque taille : Qi = somme(TiCj) + Ri avec les j tels que 1 <= j <= n et 0 <= Ri <= Vi

Pour l'instant, la seule piste que j'ai est proche d'un algorithme de programmation dynamique pour le problème du sac-à-dos.
http://www.unit.eu/cours/EnsROtice/m...Module_20.html

Je crée une liste d'états en partant d'un état de quantité vide, et j'itère sur les colis.
Pour chaque colis, je crée pour chaque état un nouvel état si les quantités du colis courant + celles de l'état ne dépassent pas les quantités commandées Qi.
Chaque état contient la somme des quantités des colis.

Ce qui m'amène à 2 puissance n états pour n colis, au pire (d'où explosion potentielle au niveau mémoire et/ou temps).
Je ne vois que 3 tests qui limitent le nombre d'états : dépassement des quantités, insuffisance des quantités restantes dans les colis non encore traités, existence d'un état avec les mêmes quantités.

Connaîtriez-vous une autre approche ?

Je vous remercie pour votre aide,

Joyel

Est-ce que tu as des ordres de grandeur.
- Tu dis que tu as 25 tailles. Ok.
- Tu as n colis , quel est l'ordre de grandeur de n ?
- Pour une commande, est-ce qu'on a une idée à l'avance du nombre de colis qu'il faudra utiliser. Si on sait que dans la grande majorité des cas, une commande sera satisfaite avec 1 ou 2 colis, plus du vrac éventuellement, ou si on sait que pour chaque commande, il faudra généralement une quinzaine de colis, ça peut avoir une influence sur l'algorithme.
- le contenu de chaque colis, ça ressemble à quoi. Ca peut être (T1C1=56, T2C1=97, T3C1=23 .... ...) , ou c'est du type (T1C1=50, T2C1=25, T3C1=10 ...) ; autrement dit, c'est des nombres ronds, ou pas ?

Bonjour :coucou:

3 objectifs:

• Pour savoir que c'est faisable ...
  il suffit de faire la somme et vérifier qu'elle dépasse Qi, sinon c'est impossible. (pour chaque i)
  
  
  .
• Pour avoir le maximum de produit venant des colis ...
  Il suffit de calculer la somme des colis. (pour chaque i)
  
  
  
  Si elle dépasse Qi, tout viendra obligatoirement des colis.
  Sinon il faut des éléments en vrac.
  .
• Pour avoir le minimum de colis ...
  Dans cette situation, tu peux partir du nombre de colis, plutôt que de partir de la commande.
  On a déjà une solution (non optimale).

Bonjour, et merci d'avoir répondu rapidement,

@tbc92

Concernant les ordres de grandeur, renseignements pris, c'est difficile de répondre. Il s'agit d'un nouveau module qui sera installé à terme chez différents clients gérant différents articles (chaussures, vêtements...). Tous n'en auront pas forcément la même utilisation. Pour le premier client qui va être installé :

Le nombre maximum de tailles est 25 (gérées en BD), mais en pratique, cela ne devrait pas dépasser 8.

Le nombre de colis existants n peut valoir plusieurs dizaines (50 - 100).

Le nombre de colis utiles ne devrait pas dépasser 10, mais devrait être supérieur à 2.

Les quantités peuvent être quelconques.

Donc je pense que ça ne peut pas être pire :-(.

Pour optimiser, je supprime d'entrée les colis qui contiennent des tailles non demandées, ou dont les quantités dépassent la demande, et je teste au cas où un seul colis suffirait exactement.
Je vais aussi resserrer les tailles demandées non nulles, mais je ne vais pas gagner grand chose...



@Flodelarab

En pratique, les quantités commandées seront inférieures aux quantités disponibles. Il s'agit de valider par morceaux une commande prévisionnelle.
Le problème est de trouver quels sont les bons colis à prendre.

Les cas d'échec seront les cas où on ne peut pas trouver une réponse exacte aux quantités commandées en prenant des colis et du vrac.

L'algorithme que j'ai évoqué s'arrête tout de suite si les quantités sont insuffisantes. (Pour créer un état, je teste si les sommes restantes permettent d'atteindre la demande).

Il boucle sur les colis et construit une liste des différentes quantités atteignables, d'où explosion possible.

Pour avoir le minimum de colis, il faut trier dès le départ les colis par quantité totale décroissante, et ne pas créer l'état si (par chance) on tombe sur une quantité totale d'un état déjà existant.
Mais c'est la cerise sur le gâteau.



Avez-vous des suggestions d'optimisation ? une approche différente ?

Je vous remercie,

Joyel

@Flodelarab
le test que tu proposes pour déterminer s'il y a une solution n'est pas bon.

Imaginons le cas où on a une seule taille.
J'ai différents colis, tous contiennent 100 produits de cette taille.
En vrac, j'ai 50 produits de cette taille.
Et ma commande, ... elle contient 75 produits de cette taille. Pas de solution.

Le contenu des colis est-il aléatoire ou y a-t-il des colis "standards' et selon quelle logique ?

Bonjour Nebulix,

Je ne peux rien présumer sur les colis, même si je pense que les colis seront souvent standards (par exemple n packs, 1 pack contenant 1 quantité fixée par taille).
Mais je veux bien savoir ce que cela apporterait (dans l'algorithme, cela réduit les états car on retombe sur des quantités existantes).

Merci pour ton aide,

Joyel

salut

bon si on résume

on a une commande K de n articles
on a des colis C contenant n' article
on a du vrac V de n'' article

K = Max(C)+min(V)

on veut donc a*n = Max(a*n')+min(a*n'')
=> n = Max(n')+min(n'')

Bonjour Anapurna,

C'est plus compliqué que cela.
Chaque colis contient potentiellement des quantités différentes selon les tailles.

Il faut déterminer quels colis et quelle quantité complémentaire de vrac satisfont les quantités de la commande.

Merci,

Joyel

Citation:

---

Envoyé par tbc92

@Flodelarab
le test que tu proposes pour déterminer s'il y a une solution n'est pas bon.

---

D'accord.
Il n'était pas clair pour moi que les colis n'avaient pas le droit d'être utilisés de façon incomplète.

salut

tu as une ligne distingue par article je suppose

donc on aurais potentiellement

L = max(C)+min(V)

Et K = somme(L)

pour moi le problème n'est pas beaucoup plus compliqué
a moins que tes colis varie pour un article donnée le problème est le même
sauf qu'il faut le réaliser pour chaque article
c'est en faites une gestion de stock ni plus ni moins
il te faut maximiser l'utilisation des colis plutôt que le vrac

Salut Anapurna,

En fait, tous les colis contiennent le même article, mais avec des quantités différentes selon les tailles.
J'ai parlé de commande mais en fait il s'agit de déterminer comment construire une ligne de commande.
Le programme doit rendre quels colis utiliser.

C'est probablement un problème de gestion de stock mais je ne connais pas quel algorithme ou quel type d'algorithme utiliser.
Je pense que le problème est NP donc je ne m'attends pas à des miracles, mais j'aurais voulu trouver un algorithme meilleur que celui que j'ai brièvement décrit dans mon premier message.
Si tu as des références, elles sont les bienvenues.

Merci,

Joyel

salut

c'est encore plus simple si c'est toujours le meme article.
si ce n'est que le conditionnement qui change ( le nombre d'article par colis)
le premier truc tu trie tes commandes du plus grand au plus petit
le second tu te sert des colis les plus gros pour remplir les commande
ensuite tu prend le colis inférieur et tu recommence a remplir les éléments manquant dans tes commandes
et ainsi de suite jusqu'au vrac
le vrac n'etant qu'un colis de quantité 1

il y avais eu une discution il y a for longtemps sur minimiser le colisage vois ici

Citation:

---

c'est encore plus simple si c'est toujours le meme article.

---

Mais non. Tu as bien compris qu'il fait la blague récurrente de l'industrie de l'habillement.
Il dit que c'est le même produit sauf que ce n'est pas la même taille, pas le même coloris. Donc pas la même chose. :roll:
Il faudra expliquer, un jour, à ces gens, que si ce n'est pas la même taille, il ne faut pas dire que c'est le même objet.

Tout à fait Flodelarab.
Un article avec 25 tailles différentes... et insister sur le fait que c'est le même article, c'est très maladroit.

Il faut prendre de la hauteur, généraliser le problème. On a 25 références en stock. On se fout de savoir si c'est 25 tailles du même article, 25 coloris du même article, ou 1 article avec 5 tailles et 5 coloris, ou que sais-je encore. On a 25 références différentes.

Citation:

---

Envoyé par Joyel

Mais je veux bien savoir ce que cela apporterait (dans l'algorithme, cela réduit les états car on retombe sur des quantités existantes).
Joyel

---

Mon idée est de remplacer l'énumération des tailles par des quantités plus globales. Par exemple tu pourrais avoir trois types de colis avec 1 : une distribution standard de tailles, 2 : des petites tailles, 3: des grandes tailles. En fonction de la proportion de ces tailles dans ta commande tu pourrais faire une première approximation rapide, qui pourrait être ajustée précisément avec du vrac.

Bonsoir,

Effectivement, ma présentation du problème peut être trompeuse…J'aurais dû parler de 25 articles différents.
Je travaille sur un autre sujet pour quelques jours…mais j'indiquerai quelle solution sera mise en œuvre.

Merci à tous les contributeurs.

Joyel