Le 20/01/2009 par cney :
Bonjour,
Je cherche a résoudre le problème suivant et je ne sais quelle méthode utiliser... la RO peut-elle m'aider?
PB: Un groupe important de personnes doivent se rencontrer deux à deux dans un certain nombre de créneaux horaires. Après que chacun ai indiqué qui il souhaite rencontrer et sur quel créneau il est disponible, je cherche à obtenir un agenda des RDVs qui répond au mieux à la demande de chacun.
Merci!
Le 21/01/2009 par cney :
Bonjour,
Merci de votre réponse je vais chercher de ce coté. Il semble que des labo de bio-informatique aient des pb similaires.
merci
Le 21/01/2009 par Fabrice :
Slt Cney,
il faut voir un peu du cote de "constrained macthing problem". Je ne connais pas trop la traduction en francais. Mais je suppose que ton probleme peu etre formule comme probleme de OR; cependant je ne te guaranti pas qu'il soit facile a resoudre.
Amicalement,
Le 21/01/2009 par Heryn :
Bonjour,
Peut etre que ce probleme peut se formuler comme un pb de coloration dans un graphe.
bien à vous.
Le 21/01/2009 par cney :
bonjour Heryn,
Merci de cette suggestion. Comment voyez vous ce modèle? Un graphe avec noeud=personne et arettes=rdv et couleur = horaire? La question serait alors de colorier le graphe pour qu'un noeud n'ai pas 2 arettes de même couleur.... est-ce bien cela?
encore merci
christophe
Le 21/01/2009 par Guelain :
Bonjour Cney,
Voici une proposition avec un algorithme de flot Max (ou couplage parfait)
Construire le graphe suivant :
- 1 noeud source => S
- 1 un noeud puit => T
- Pour tout couple de personnes ajouter un noeud => Ensemble P
- Pour tout créneau horaire ajouter un noeud => Ensemble C
Ajouter les aretes suivantes :
- Pout tout S->n avec n dans P ajouter un arc de capacité Max 1
- Pour tout noeud n->T avec n dans C ajouter un arc de capacité 1
- Enfin pour tout n,c avec n dans P, c dans C si le rendez vous n peut se faire lors du créneau c alors ajouter un arc de capacité infini.
Un planning est alors un Flot Max dans le graphe.
Ensuite pour prendre en compte des préférences, il est possible de mettre une valuation soit sur les arcs S->n dans P soit sur les arcs n,c. Dans ce dernier cas il faudra faire un flot max de cout min.
Cette représentation marchera bien si les creneaux horaires sont basiques et a peu pres de meme type pour tout le monde ...
Cordialement,
Guillaume
Le 21/01/2009 par Guelain :
Je viens de me rendre compte que la solution que je propose n'est pas satisfaisante car des couples d 'intersection vide ne pourrons etre affectés au meme creneau ... Le probleme est en effet un peu plus complexe.
Le 21/01/2009 par Guelain :
un algo de coloration de graphe me semble en effet indiqué :
1 noeud = couple de personne
1 couleur = 1 creneau
si deux couples ne peuvent se rentrer sur le meme creneau alors il existe un arc entre les deux couples
Il faut alors faire une coloration max du graphe.
Toutefois on ne tient pas franchement compte des préférences des rencontres ...
Bon courage a vous.
Cdlt.
Il faut alors déterminer une coloration maximum du graphe. Toutefois il est alors difficile de tenir compte des preférences de rencontres ...
Le 26/01/2009 par opeton :
Pour information, nous allons faire une présentation sur ce sujet à la conférence ROADEF, du 10 au 12 février à Nancy.
Titre : Optimisation de la planification de bourses d'échanges de
technologies,
Auteurs : C. Guéret, O. Morineau, C. Pavageau, O. Péton et D. Poncelet
Cordialement,
Olivier
Le 26/01/2009 par cney :
Morineau
Le 26/01/2009 par cney :
Merci de cette information,
Pourriez vous me donner quelques références d'articles de votre équipe déjà publié sur le sujet.
Très cordialement,
Christophe
Le 27/01/2009 par opeton :
C'est notre première étude sur le sujet, et nous sommes tout juste en train de la terminer, donc pas encore d'article pour le moment. Nous n'avons qu'un résumé de deux pages, et prochainement une présentation.
Le 01/03/2009 par Heryn :
tout a fait d'accord avec la réponse de Guelain. j'ajoutrai qu'on peut tenir compte des préférences dans la valuation des aretes.
Bien à vous,
