Comment répartir de façon optimale ... — Les-mathematiques.net The most powerful custom community solution in the world

Comment répartir de façon optimale ...

Modifié (July 2023) dans Combinatoire et Graphes
Titre initil "Comment répartir de façon optimale les bénévoles dans les magasins (collecte des Restos du Cœur) ?"
[Le titre doit être informatif mais court. Le corps du message est là pour les détails. AD]
Voici le problème.
Durant une même journée, la collecte des Restos du Cœur aura lieu dans plusieurs magasins. M magasins ont accepté d'y participer, et R bénévoles ont accepté d'être affecté(e)s dans l'un de ces magasins durant la journée entière en tant que responsables d'équipe. On doit tenter d'affecter un(e) responsable à chaque magasin. Mais les R bénévoles volontaires ne sont pas disponibles pour la totalité des magasins, à cause de contraintes géographiques notamment. Donc il ne sera pas forcément possible d'affecter un(e) responsable à tous les magasins acceptant de participer, et dans ce cas, la collecte ne sera pas effectuée dans ces magasins.
1. Existe-t-il un algorithme polynomial (en fonction de M et R) permettant de répartir les bénévoles dans les magasins de manière à maximiser le nombre de magasins dans lesquels la collecte sera effectuée ?
2. Si oui, pouvez-vous en donner un ?
3. Si non, pouvez-vous proposer un algorithme polynomial (en fonction de M et R) intéressant, même s'il ne maximisera pas toujours le nombre de magasins dans lesquels la collecte sera effectuée ?
Mêmes questions en attribuant un poids à chaque magasin (l'estimation du poids total des produits qui y seront collectés durant la journée par exemple), et en essayant cette fois-ci de maximiser la somme des poids de chaque magasin dans lequel la collecte sera effectuée.

Réponses

  • Modifié (July 2023)
    Pour le premier, je dirais oui. Tu as en entrée un graphe biparti d'ensemble de sommets $[[1,R]] \sqcup [[1,M]]$ et tu cherches un couplage maximal. L'algorithme d'Edmonds fait notamment le travail et est assez simple sur les graphes bipartis.
    Il me semble que l'algorithme des forêts hongroises permet, en temps polynomial, de gérer des couplages avec poids, à regarder plus précisément.
  • Modifié (July 2023)
    Merci Heuristique. Je ne connaissais pas ces algorithmes. Voici un algorithme simple en 3 étapes pour tenter de maximiser le nombre de magasins dans lesquels la collecte sera effectuée. Soient M la liste des magasins acceptant de participer, et R la liste des bénévoles volontaires pour assurer la fonction de responsable d'équipe :
    Étape 1 (Classement)
    Pour chaque magasin de la liste M, on dresse la liste des bénévoles de R qui sont disponibles pour ce magasin. Puis on retire de la liste M les magasins pour lesquels aucun(e) bénévole n'est disponible. Si au moins une des deux listes M et R est vide, c'est fini. Sinon, on classe les magasins de la liste M par ordre croissant suivant le nombre de bénévoles disponibles pour le magasin. En cas d'égalité entre plusieurs magasins, l'ordre de ces magasins peut être choisi au hasard.
    Étape 2 (Premier magasin)
    Il faut affecter un(e) responsable au premier magasin de la liste M en limitant le risque de diminuer dangereusement le nombre de responsables potentiel(le)s disponibles pour les autres magasins de cette liste. Donc pour chaque responsable potentiel(le) disponible pour ce magasin, on examine le nombre de magasins de la liste M pour lesquels elle/il est disponible, et on choisit celle/celui pour laquelle/lequel ce nombre est le plus faible. En cas d'égalité entre plusieurs responsables potentiel(le)s, il faut voir pour chacun(e) d'elles/eux :
    • le rang dans la liste M de chacun des magasins de M (autres que le premier magasin de cette liste) pour lesquels elle/il est disponible
    • le nombre (noté P) le plus faible parmi les rangs de ces magasins
    Puis on choisit la/le responsable potentiel(le) pour laquelle/lequel le nombre P est le plus élevé. En cas d'égalité entre plusieurs responsables potentiel(le)s, on en choisit un(e) au hasard. Lorsque le choix est fait, le premier magasin de la liste M dégage de cette liste, la/le responsable qui a été affecté(e) à ce magasin dégage de la liste R, et on passe à l'étape 3.
    Étape 3 (Magasin suivant)
    Si au moins une des deux listes M et R est vide, c'est fini. Sinon, il faut reprendre à l'identique les étapes 1 et 2. Cette boucle s'arrête quand au moins une des deux listes M et R est vide.
  • Modifié (July 2023)
    Pas de solution toute faite, mais quelques remarques.

    Ici, tu détailles la solution pour le cas 'tous les magasins ont le même poids'.
    C'est plus pertinent de travailler directement le cas 'chaque magasin a un poids'. Et si on n'a pas de poids, c'est juste un cas particulier du cas général.

    Je commencerais par une étape préliminaire : déterminer des territoires.
    C'est quoi un 'territoire' : 
    - on prend un magasin au hasard, on prend tous les bénévoles qui peuvent aller dans ce magasin, puis tous les autres magasins de ces bénévoles, puis tous les bénévoles qui peuvent aller dans ces magasins, et ainsi de suite. 
    Tous les magasins ainsi recensés, ainsi que tous ces bénévoles, ça forme un territoire.
    Et on recommence avec les magasins restants et les bénévoles restants.
    A priori, si les bénévoles sont très mobiles, on trouvera 2 territoires : la Corse et le continent.

    Ensuite, on peut travailler sur chaque territoire, indépendamment des autres territoires. On gagne en performance, mais pas uniquement, et on ne perd rien en terme d'optimisation. 

    L'algorithme que tu proposes peut générer une boucle infinie. Si au début, tu as 10 bénévoles sur Nantes pour 5 magasins, et 5 bénévoles sur Brest pour 10 magasins, tu risques fort d'avoir à la fin 5 bénévoles sur Nantes, et 5 magasins sur Brest, mais aucune affectation possible.

    A priori, si au début tu as un seul territoire (avec la définition ci-dessus), je pense que l'algorithme que tu envisages fait que tout au long du processus, tu auras toujours un seul territoire. Mais ça peut être utile de le vérifier. 
    Tu boucles sur les étapes 1/2/3 une cinquantaine de fois, et tu vérifies si il y a toujours un seul territoire. 

    Dans ton algorithme, tu essaies de qualifier les bénévoles en disant : tel bénévole, qui est disponible pour plein de magasins, je vais l'affecter le plus tard possible, je le garde en joker. Tu dis : 'Pour chaque bénévole, je calcule un nombre P qui est le $min$ d'une certaine variable, puis je sélectionne le bénévole pour lequel P est le plus grand.
    Et donc, entre différents bénévoles qui a comme nombres (3,3,7)  ou (3,7) ou (3,6,7) ou (3,5,6,6,7), tu vas choisir au hasard.
    Tu dois certainement avoir une préférence, et donc trouver une fonction plus adaptée que la fonction $min()$

    Par ailleurs, ces algorithmes où on cherche à chaque étape une association 'la plus prometteuse' ne conduisent pas forcément au résultat optimal.
    Ca peut être utile d'ajouter une phase de vérification/optimisation.

    1) tu déroules l'algorithme comme actuellement.
    2) tu sauvegardes le résultat, et tu regardes les magasins qui manquent ( si les magasins ont des poids différents, si tous les bénévoles sont affectés à un magasin, et si on a bien sélectionné tous les magasins qui ont les poids les plus élevés, alors la solution atteinte est optimale, inutile de continuer). On regarde donc quels magasins ont été écartés, et parmi eux, quel est le magasin qui a le poids le plus élevé.
    3) Pour ce magasin, on regarde les bénévoles qui auraient pu aller le faire, et on regarde la dernière étape où on a utilisé un de ces bénévoles. Et on dit : à cette étape là, on a pris une mauvaise décision, on change le choix fait à cette étape, et on boucle. 
    Et on regarde si on arrive à un meilleur résultat.

    J'ajoute un point.
    Il faut ajouter une phase préliminaire de vérification des données. Si un bénévole dit qu'il peut aller dans 5 magasins, dont 4 à Strasbourg et 1 à Poitiers, c'est suspect. 
    Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
  • Modifié (July 2023)
    Merci pour ta réponse lourrran !
    En fait c'est déjà découpé en territoires car chaque asso départementale des Restos du Cœur gère son propre département indépendamment des autres. Même chose pour la Banque Alimentaire. Les départements sont des territoires suffisamment petits pour qu'un ordinateur exécutant un algorithme efficace puisse générer tous les plannings en moins de 10 secondes sans qu'il soit nécessaire de les découper encore plus.
    L'algorithme que tu proposes peut générer une boucle infinie. Si au début, tu as 10 bénévoles sur Nantes pour 5 magasins, et 5 bénévoles sur Brest pour 10 magasins, tu risques fort d'avoir à la fin 5 bénévoles sur Nantes, et 5 magasins sur Brest, mais aucune affectation possible.
    Non, car l'étape 1 dit que les 5 magasins de Brest vont être retirés de la liste M et qu'on va s'arrêter ici (Pour chaque magasin de la liste M, on dresse la liste des bénévoles de R qui sont disponibles pour ce magasin. Puis on retire de la liste M les magasins pour lesquels aucun(e) bénévole n'est disponible. Si au moins une des deux listes M et R est vide, c'est fini.).
    C'est étrange que tu parles de Nantes car j'y habite justement.
    Ca peut être utile d'ajouter une phase de vérification/optimisation.
    Oui. En fait, le problème que j'ai présenté ici est une version simplifiée du vrai problème, pour lequel il y a beaucoup plus de contraintes. L'algorithme que j'ai expliqué dans ce document comporte une étape Nouvel essai afin de tenter à plusieurs reprises de trouver une meilleure combinaison. Une démo de cet algorithme est disponible ici.
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!