Discussion :

[Alikendarfen]

Bonjour,

Voici un petit problème, je ne sais pas par quel bout le prendre...

Le problème :

On dispose d'un ensemble de commandes.
Chaque commande est constituée de lignes et chaque ligne correspond à une quantité Q d'une référence article R donnée.

On appelle coefficient de recouvrement, pour un ensemble de commandes, le nombre moyen d'articles commandés par référence
CR = somme( Qi ) / nombre( Rj )

Comment partitionner cet ensemble de commandes en x lots de taille égale tels que pour chacun des lots de commandes obtenu le coefficient de recouvrement soit maximal et le plus homogène possible entre ces lots ?


Merci d'avance de vos retours...

[pseudocode]

Bonsoir,

Ca a l'air intéressant comme problème. Pour résumer, on a au final (toutes commandes confondues) R types d'articles différents, chaque type d'article étant en quantité Q(r).

Et le but est de créer X lots (ensemble d'articles) tels que le coefficient CR des lots soit maximum - et si possible homogène.


Bref que le contenu de chaque lot soit le moins disparate possible, c'est ça ?

[Alikendarfen]

Oui c'est ça. Plus précisément : "X lots (ensembles de commandes)"

Et on peut peut-être traduire "homogène" par : tel que le plus petit des CR obtenus soit le plus grand possible.

J'ai tenté quelques méthodes mais je n'ai aucune vision mathématique du problème.

Il faut noter que les commandes ont une forte disparité en termes d'articles. Ce qui fait que prendre les commandes des références d'une commande et répéter l'opération n fois couvre l'ensemble des commandes au bout de 4 à 5 itérations.

A titre indicatif : je cherche un algo qui soit capable de traiter de l'ordre de 50000 commandes chacune d'environ 4 articles en moyenne.

Voici ces méthodes en résumé, avec quelques coefficients indicatifs pour fixer les idées (les chiffres, dans la pratique, dépendent du profil des commandes) :

1/ Tirage aléatoire
On prend les commandes au hasard.
Résultat (moyenne) : 1,32

2/ Répartition par les articles les plus demandés
Tri des articles du plus demandé au moins demandé.
Pour chaque lot (en bouclant sur les X lots) "consommation" des articles dans l'ordre et affectation au lot des commandes correspondant à cet article.
Résultat (moyenne) : 1,62

3/ Répartition par les articles les plus demandés V2
Même principe que 2/, mais cette fois :
- on identifie l'article le plus demandé
- on identifie les commandes correspondantes
- on identifie tous les articles de ces commandes
- puis on affecte au lot les commandes correspondant à tous ces articles
Résultat (moyenne) : 1,75

Note : ces trois méthodes ne cherchent pas à homogénéiser les CR des lots

4/ Algo génétique (j'en suis à une toute première version)
- Tirage aléatoire de N ensembles de X lots chacun
- Evaluation des ensembles
- Garder les meilleurs
- Reproduire la population : dans cette première version, pas de croisement. La reproduction se fait par mutation de chaque ensemble de lots : les lots échangent aléatoirement leurs commandes
Résultat (moyenne) : 1,50

Note : ici par contre (4) on prend en compte la contrainte contrainte d'homogénéisation, ce qui fait qu'on obtient un moins bon résultat moyen même en partant des résultats du 3.

[Alikendarfen]

Bonjour,

Voici une autre formulation du problème.

Les données sont représentées sous la forme d'une matrice :
- En ligne : les commandes
- En colonne : les références articles
- Sur une cellule : la quantité d'articles (colonne) pour la commande (ligne)

Le but serait d'effectuer des permutations de lignes et de colonnes pour que d'une matrice de départ, on obtienne une matrice cible, comme sur le schéma en attachement.

Dans ce cadre, la matrice de départ présente une densité moyenne de cellules non nulles.
La matrice cible présente N blocs de lignes et M blocs de colonnes pour lesquels la diagonale (au sens des blocs) est de forte densité et les autres parties (hors diagonale) sont de faible densité.

Dans la pratique, la matrice de départ comporte de l'ordre de 5000 à 10000 lignes pour 10000 colonnes. Une ligne (une commande) comporte de 2 à 10 articles. Un article est utilisé par une vingtaine de commandes au plus et 50% des articles ne sont utilisés qu'une fois (loi normale).

Des idées ??

Merci d'avance

[Alikendarfen]

Bonjour,

Je cherche une approche pour résoudre le problème suivant :

Une commande =

- 1 entête (= un identifiant)
- n lignes de commande =

- 1 quantité
- 1 référence produit

On dispose d'un ensemble de C commandes.

Comment découper cet ensemble en N lots (de commandes) de même taille tels que chaque lot regroupe le moins de références produit possible (ou encore tels que le lot qui contient le plus de références en ait le moins possible).

Ordres de grandeur :
- C : 10000 à 50000
- N : 200 à 1000 (environ 50 commandes par lot)
- Chaque commande comporte en moyenne 4 produits
- Nombre de références produit : qq milliers

Merci de vos idées !

PS : j'avais déjà posté sur le sujet il y a qq mois... mais toujours pas de solutions en perspective ... donc je retente ma chance

[stephane.combes]

Une idée : pondére chaque commande par le nombre de ligne qu'elle contient.
Exemple :
c1 contient 2 lignes => c1p vaut 2.
c2 contient 5 lignes => c2p vaut 5.
c3 contient 10 lignes => c3p vaut 10.

Tu fais ensuite tes lots en fonction du nombre de lignes que tu veux.
Si tu veux 10 lignes par lots avec l'exemple tu met c1 et c2 dans un lot l1 et c3 dans un lot l2.

Enfin, si j'ai bien compris ta problématique

[Alikendarfen]

Merci de cette réponse...

... mais non, ça n'est pas le nombre de lignes, mais c'est le nombre de références (distinctes) portées par l'ensemble des commandes d'un lot qu'il faut minimiser.

[stephane.combes]

Je n'arrive pas bien à saisir la problématique mais ne peut-elle pas se rapprocher du "problème du sac à dos" ?

http://fr.wikipedia.org/wiki/Probl%C...sac_%C3%A0_dos

[Alikendarfen]

Je vais prendre un exemple :

La commande C1 correspond à des lignes avec les produits A, B
C2 produits C, D
C3 produits A, C
C4 produits D, E

Si on veut deux lots de commandes, on peut par exemple prendre :

Découpage 1 :
L1 = C1 + C3 => 3 références (A, B, C)
L2 = C2 + C4 => 3 références (C, D, E)

Mais si on choisit:

Découpage 2 :
L1 = C1 + C2 => 4 références (A, B, C, D)
L2 = C3 + C4 => 4 références (A, C, D, E)

Découpage 2 est moins bon que découpage 1.

La différence avec le sac à dos (enfin tel que je le vois, ce qui ne veut pas dire que ce soit une mauvaise piste ?) :
- C'est un problème multi sacs (ça ok)
- Mais la taille des sacs n'est pas connue à l'avance et doit être la plus petite possible
- Et on ne compte pas les objets (ou leur poids) mais on identifie les objets distincts qui s'y trouvent