Discussion :

[Joyel]

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

[tbc92]

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 ?

[Joyel]

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

[tbc92]

@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.

[Flodelarab]

@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.

[anapurna]

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

[Nebulix]

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

[Joyel]

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

[anapurna]

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'')

[Nebulix]

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.

[Flodelarab]

Bonjour

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).