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

[stephane.combes]

Ok, c'est beaucoup plus clair pour moi avec cet exemple

Alors comme idée je te propose :

1. Trier les commandes par nombre d'articles décroissant
2. Prendre la commande qui a le plus d'article et la mettre dans un lot (je la note CRef)
3. Prendre la commande qui a le plus d'article commun avec CRef et la mettre dans son lot
4. Faire le point 3 tant que le lot n'est pas plein
5. Recommencer au point 2 pour un nouveau lot

Précision : quand je dit "prendre" c'est retirer la commande de la liste établie en 1.

Faut encore adapter un peu pour que tous les lots aient le même nombre d'articles

Dans tous les cas le nombre d'articles minimum est celui de la commande qui contient le plus d'articles.

[Nebulix]

Je ne suis pas sûr que le pb soit bien défini.
Si tu as une commande A..G et d'autres A..B, en les regroupant dans un lot, tu respectes la 2e forme du critère mais pas la 1e.
Que veux-tu obtenir au juste ?

[Vakhyw]

Hmmm, ce qui me gêne c'est le nombre de lots.

Comment tu "calcules" N par rapport à C ? Dans ton exemple, le meilleur cas (et c'est toujours vrai) c'est de faire C lots, chacun contenant une commande. En gros tu veux quelque chose du genre C/N = k = 50 (par exemple) ?

A la fin chaque lot doit contenir le même nombre de commandes (plus ou moins une j'entends) ou des écarts de P% par rapport à k sont envisageables ?

Enfin il te faut LA meilleure solution ou une solution acceptable (et moins chère) ?

[Alikendarfen]

@Vakhyw

La taille des lots est imposée par un critère externe donc k est fixé (le dernier lot a la taille du reste de C/N). Dans la pratique k = 50 (comme j'indiquais dans le premier post) est une grandeur réaliste.

Enfin il te faut LA meilleure solution ou une solution acceptable (et moins chère) ?

Et je cherche surtout une approche car pour le moment je n'ai pas une idée claire de ce qu'est un bon résultat. Donc une solution acceptable peut m'aller si on a une idée de son écart par rapport à la solution idéale.

@Nebulix

Je ne suis pas sûr que le pb soit bien défini.
Si tu as une commande A..G et d'autres A..B, en les regroupant dans un lot, tu respectes la 2e forme du critère mais pas la 1e.
Que veux-tu obtenir au juste ?

Peut être le problème est mal défini ??
Ce que je cherche c'est une partition d'un ensemble de C commandes en N lots chacun d'une taille k imposée. Cette partition doit être telle si Lmax est le lot qui contient le plus de références produit alors le nombre de références produits de Lmax soit le plus petit possible.

@stephane.combes

Alors comme idée je te propose :

Trier les commandes par nombre d'articles décroissant
Prendre la commande qui a le plus d'article et la mettre dans un lot (je la note CRef)
Prendre la commande qui a le plus d'article commun avec CRef et la mettre dans son lot
Faire le point 3 tant que le lot n'est pas plein
Recommencer au point 2 pour un nouveau lot

Merci pour ton idée, mais malheureusement c'est une approche que j'ai déjà testée. Ce qu'il faut garder en tête c'est qu'il y a un grand nombre de références produits (au total quelques milliers, voire beaucoup plus dans certaines situations) ce qui fait qu'accumuler plusieurs commandes autour de la même ref (CRef) fait qu'on ajoute aussi x autres références variées.... et identiquement aux itérations suivantes.
On 'tire' une sorte de grappe de commandes progressivement liées entre elles de par les références qu'elles portent.
Donc cette approche 'désoptimise' les autres lots...

... et c'est justement le problème que je n'arrive pas à maitriser !

[Nebulix]

Lmax est imposé par la commande qui regroupe le + d'articles.
Une fois que tu as tiré une grappe définie par cette commande, faut-il aussi optimiser les autres ?

[Alikendarfen]

Lmax est imposé par la commande qui regroupe le + d'articles.

Je ne crois pas que Lmax soit imposé par la commande qui regroupe le plus d'articles : les commandes sont petites par rapport au nombre total de commandes ; une commande porte en moyenne 3 à 5 lignes de commande dans le cadre qui m'intéresse.

Pour le dire autrement, il y a (à mon avis) très peu de chances que Lmax comporte nécessairement la commande qui regroupe le plus de produits.

Une fois que tu as tiré une grappe définie par cette commande, faut-il aussi optimiser les autres ?

Et, oui, il faut optimiser l'ensemble des lots de commandes.

[Acrim]

Puisqu'il s'agit d'un problème concret, as tu fait des petites "stats" sur tes instances : en moyenne une article se retrouve dans combien de commandes différentes (est ce qu'il y a de fortes disparités entre les articles), etc. Ça peut éventuellement te guider dans le choix de l'approche pour la recherche de solutions.


Actuellement, comment fais tu pour évaluer la qualité de tes solutions ?

[Alikendarfen]

Puisqu'il s'agit d'un problème concret, as tu fait des petites "stats" sur tes instances : en moyenne une article se retrouve dans combien de commandes différentes (est ce qu'il y a de fortes disparités entre les articles), etc. Ça peut éventuellement te guider dans le choix de l'approche pour la recherche de solutions.

Oui, c'est un problème concret. Et pourtant non, je n'ai pas de stats "absolues".

Concret pourquoi : les commandes dont je parle sont des commandes de sites e-commerce (ou VAD). Le profil de ces commandes dépend cependant de l'acteur : parfois, il y a des ABC très marqués parfois non. Parfois le référentiel articles est relativement petit, parfois il peut atteindre plus d'un million de références.

Dans un cadre progiciel, il n'y a donc pas de règles absolues.

Actuellement, comment fais tu pour évaluer la qualité de tes solutions ?

Actuellement, je n'ai pas de critère, seulement quelques algos que j'ai tenté et qui donnent des résultats plus ou moins bons ou performants.

C'est justement le but de ma demande : quelle voie tenter ou emprunter pour résoudre ce type de problème ? Peut être y a-t-il un cadre théorique déjà établi (mais je n'ai pas réussi à le trouver) ?

[Nebulix]

Tu peux restreindre ton référentiel d'articles à l'ensemble des articles effectivement commandés dans l'ensemble à traiter.
J'essaierais de séparer l'ensemble des produits commandés en groupes non-connectés, la connection étant d'apparaitre sur une même commande, chacun de ces groupes pouvant ensuite être traité indépendemment.

[Acrim]

C'est justement le but de ma demande : quelle voie tenter ou emprunter pour résoudre ce type de problème ? Peut être y a-t-il un cadre théorique déjà établi (mais je n'ai pas réussi à le trouver) ?

Le cadre théorique ? Il y a les problèmes de packing. Mais généralement on tente plutôt de minimiser le nombre de "pack" avec des packs de taille limité et sans "overlapping" des objets.

Pour l'approche je tenterai bien la programmation linéaire (le modèle n'est pas trop dur à écrire je pense). Perso, ça m’intéresserait d'essayer. Donc si tu es autorisé (et que c'est possible techniquement) à diffuser une instance anonymisée, je peux tenter.

[Alikendarfen]

Pour l'approche je tenterai bien la programmation linéaire (le modèle n'est pas trop dur à écrire je pense). Perso, ça m’intéresserait d'essayer. Donc si tu es autorisé (et que c'est possible techniquement) à diffuser une instance anonymisée, je peux tenter.

Je te prépare ça dans la journée : un fichier généré sur la base de profils statistiques des commandes.
Il sera de la forme de x lignes comprenant chacune "<identifiant commande>;<identifiant article>" (s'il y a des quantités multiples pour une commande, il y aura plusieurs lignes identiques).

Ca te va ?

Merci beaucoup de le coup de main que tu proposes.


A noter :
Les modèles utilisés pour les profils statistiques des commandes tiennent compte de différents facteurs (comme par exemple les classes de rotation des articles, la répartition des quantités par commande, etc).

Mais ils ne contiennent pas actuellement de "profil commercial" (par exemple le fait qu'un client commandant un produit A a une probabilité donnée de commander aussi un produit B, ou bien un produit de la famille F).

Ce manque va jouer sur les résultats de l'algo recherché... mais pour le moment, je n'ai pas !