Planification de rendez-vous avec OptaPlanner

Le contexte

Notre client, Proximum Group avec son produit Vimeet propose à des organisateurs d’événements une plateforme de gestion de rendez-vous B2B.

Avant l’événement les participants s’inscrivent sur la plateforme et consultent le catalogue des participants :

Les participants demandent en rendez-vous d'autres participants, acceptent ou refusent des propositions de rendez-vous :

Avant l’ouverture de l’événement l’agenda des rendez-vous de chaque participant est généré. Toutes les demandes de rendez-vous acceptées ne sont pas satisfaites faute de disponibilité commune entre les participants.

Un événement dure un à plusieurs jours durant le(s)quel(s) des professionnels vont se rencontrer en rendez-vous. La plateforme permet également de gérer d’autres types de rendez-vous comme des recruteurs qui rencontrent des candidats pendant une journée dédiée.

La problématique

L'événement dure un ou plusieurs jours et des créneaux de rendez-vous sont définis par l'organisateur. Une demande de rendez-vous acceptée est transformée en rendez-vous en lui allouant un créneau de rendez-vous et un lieu de rendez-vous.

L'objectif de l'organisateur est de maximiser le nombre de rendez-vous.

L'objectif d'un participant est d'avoir le maximum de ses demandes de rendez-vous positionnées en rendez-vous.

À cela s'ajoutent quelques règles de gestion :

• chaque participant a un nombre limité de rendez-vous selon le forfait qu'il a choisi,
• des priorités entre les types de participants,
• priorisation du positionnement d'un rendez-vous sur le lieu attribué au participant plutôt que sur un lieu mutualisé,
• le participant et les lieux peuvent être en indisponibilité pour certains créneaux de rendez-vous.

Problème difficile à résoudre

Il s'agit d'un __problème NP-complet__ car le problème est difficile à résoudre : pour avoir la solution idéale, il faudrait calculer toutes les combinaisons possibles. Ce qui pourrait prendre des années voire une éternité.

En conséquence, il vaut mieux chercher des solutions approchées en limitant le temps de calcul.

Pour cela, nous avons étudié des algorithmes comme l'algorithme de colonies de fourmis ou l'algorithme génétique.

Ce sont des algorithmes difficiles à maîtriser.

Un proof of concept en PHP a été codé pour positionner séquentiellement des rendez-vous puis évaluer la solution globale. Cela a été intéressant pour comprendre comment modéliser le problème, mais la lenteur des itérations nous a poussés à aller vers d'autres langages ou vers des librairies Open Source.

OptaPlanner

Solution Open Source, OptaPlanner, est décrit comme un solveur de satisfaction de contraintes.

Sous licence Apache Software et chapeauté par Red Hat, OptaPlanner est écrit en Java et Drools, un meta langage pour écrire des règles de gestion.

OptaPlanner est livré avec des exemples variés :

Dont, l'optimisation de l'agenda des professeurs :

L'affectation des lits d'un hôpital :

La minimisation du trajet d'un voyageur de commerce :

Et même l'optimisation du plan de tables d'un mariage :

Sous le capot, OptaPlanner implémente de nombreux algorithmes de construction heuristique et de recherche locale.

Une heuristique est une méthode de calcul par l'exploration et qui fournit rapidement une solution acceptable.

Un algorithme de recherche locale permet de découper le problème en plus petits problèmes pour découvrir des optimums locaux.

Comment démarrer avec OptaPlanner ?

Notre erreur a été de créer notre problème from scratch. La courbe d'apprentissage d'OptaPlanner semble plutôt une falaise à gravir par avis de tempête. La bonne idée est de partir d’un exemple proche fourni par OptaPlanner et l’adapter petit à petit.

Modéliser le problème

Il n'est jamais simple de modéliser un problème de planification. Le moyen d'y arriver est de définir :

• l'Objectif : ici, maximiser le nombre de rendez-vous positionnés c'est à dire avec un créneau et un lieu.
• les ressources : ici, les créneaux de rendez-vous et les lieux de rendez-vous.
• Contraintes :
  • "Hard" : celles qui empêchent la tenue d'un rendez-vous
  • "Soft" : celles permettant d'optimiser le positionnement des rendez-vous

Les annotations de OptaPlanner

Voici un extrait du code de MeetingSchedule :

import org.optaplanner.core.api.domain.solution.PlanningEntityCollectionProperty;
import org.optaplanner.core.api.domain.solution.PlanningScore;
import org.optaplanner.core.api.domain.solution.PlanningSolution;
import org.optaplanner.core.api.domain.solution.drools.ProblemFactCollectionProperty;
import org.optaplanner.core.api.domain.valuerange.ValueRangeProvider;

@PlanningSolution
public class MeetingSchedule {

    private List<Meeting> meetingList;
    private List<Slot> slotList;
    private List<Spot> spotList;
    private List<User> userList;
    private List<Sheet> sheetList;

    @PlanningEntityCollectionProperty
    public List<Meeting> getMeetingList() {
        return meetingList;
    }

    @ValueRangeProvider(id = "slotRange")
    @ProblemFactCollectionProperty
    public List<Slot> getSlotList() {
        return slotList;
    }

    @ValueRangeProvider(id = "spotRange")
    @ProblemFactCollectionProperty
    public List<Spot> getSpotList() {
        return spotList;
    }

    @ProblemFactCollectionProperty
    public List<User> getUserList() {
        return userList;
    }

    @ProblemFactCollectionProperty
    public List<Sheet> getSheetList() {
        return sheetList;
    }

Et un extrait du code de Meeting :

import org.optaplanner.core.api.domain.entity.PlanningEntity;
import org.optaplanner.core.api.domain.variable.PlanningVariable;

@PlanningEntity()
public class Meeting {

    private List<Sheet> sheetList;
    private List<User> userList;

    private Slot slot = null;
    private Spot spot = null;

    @PlanningVariable(valueRangeProviderRefs = {"slotRange"}, nullable = true)
    public Slot getSlot() {
        return slot;
    }

    @PlanningVariable(valueRangeProviderRefs = {"spotRange"}, nullable = true)
    public Spot getSpot() {
        return spot;
    }

On peut voir que ce code comporte des annotations fournies par OptaPlanner :

• @PlanningSolution : définit l'entité d'une solution optimale contenant tous les rendez-vous.
• @PlanningEntityCollectionProperty : définit une collection de PlanningEntity.
• @ProblemFactCollectionProperty : définit qu'une propriété sur une classe PlanningSolution est une collection de données qui sert au planificateur mais qui ne changent pas lors de la résolution.
• @ValueRangeProvider : fournit les valeurs pouvant être utilisées dans une annotation @PlanningVariable.
• @PlanningEntity : définit l'élément d'une solution, ici un rendez-vous (meeting).
• @PlanningVariable : définit la variable (la ressource) que OptaPlanner attribue au PlanningEntity grâce à ses algorithmes de construction heuristique. Ici le créneau (slot) et le lieu (spot).

Les règles de gestion et les contraintes

Décrire les contraintes de notre problème au solveur d'OptaPlanner est fait en Drools. Grâce à ces règles, OptaPlanner évalue le score d'une solution. L'idée est que chaque règle va permettre d'agir sur ce score, en pénalisant la solution plus ou moins fortement.

Contrainte "Medium"

Il s'agit de l'objectif : on souhaite maximiser le nombre de rendez-vous positionnés lors d'un événement. Le score de la solution est pénalisée de -1 pour chaque rendez-vous non positionné :

rule "Assign every meeting"
    when
        Meeting(isNotAssigned())
    then
        scoreHolder.addMediumConstraintMatch(kcontext, -1);
end

Contrainte "Hard"

Ce sont des contraintes ne permettant pas de positionner un rendez-vous.

Prenons un exemple : le rendez-vous ne peut pas être positionné sur un créneau de rendez-vous si les participants sont indisponibles durant ce créneau.

En langage Drools, on peut appeler une méthode du modèle :

rule "Unavailability conflict"
    when
        Meeting(hasUnavailabilityConflict())
    then
        scoreHolder.addHardConstraintMatch(kcontext, -10);
end

et dans le modèle Meeting :

@PlanningEntity()
public class Meeting {
    // ...

    public boolean hasUnavailabilityConflict() {
        if (null == slot) {
            return false;
        }

        for (User user : getUserList()) {
            List<Slot> unavailabilityList  = user.getUnavailabilityList();

            if (unavailabilityList != null) {
                for (Slot unavailability : unavailabilityList) {
                    if (slot == unavailability) {
                        return true;
                    }
                }
            }
        }

        return false;
    }

Prenons un exemple un peu plus complexe : lorsque la fiche de participant a consommé tous ses crédits de rendez-vous, il n'est pas possible de lui positionner un nouveau rendez-vous :

rule "Sheet do not have enought meetings quantity conflict"
    when
        $sheet : Sheet($possibleMeetingsQuantity : possibleMeetingsQuantity)
        accumulate(
            $meeting : Meeting(isAssigned(), sheetList contains $sheet);
            $totalMeetingBySheet : count($meeting);
            $totalMeetingBySheet > $possibleMeetingsQuantity
        )
    then
        scoreHolder.addHardConstraintMatch(kcontext, -1);
end

Contrainte "Soft"

Ce sont les contraintes qui permettent d'optimiser la satisfaction des participants ou d'optimiser l'utilisation des ressources.

Par exemple, nous allons satisfaire équitablement chaque participant en fonction du nombre de rendez-vous possibles. Pour cela, il faut calculer un ratio de nombre de rendez-vous positionnés sur le nombre de rendez-vous à positionner et pénaliser de -1 par palier de 10% :

rule "Satisfaction : add -1 point penalty per 10% satisfaction = meetings assigned / possibleMeetingsQuantity"
    when
        $sheet : Sheet(possibleMeetingsQuantity > 0, $possibleMeetingsQuantity : possibleMeetingsQuantity)
        accumulate(
            $meeting : Meeting(isAssigned(), sheetList contains $sheet);
            $meetingCount : count($meeting)
        )
    then
        scoreHolder.addSoftConstraintMatch(kcontext, - (int) Math.ceil(10 - 10 * (float) $meetingCount / $possibleMeetingsQuantity));
end

Le solveur

Notre configuration du solveur solver-config.xml :

<?xml version="1.0" encoding="UTF-8"?>
<solver>
  <solutionClass>org.vimeet.meetings.domain.MeetingSchedule</solutionClass>
  <entityClass>org.vimeet.meetings.domain.Meeting</entityClass>

  <scoreDirectorFactory>
    <scoreDrl>org/vimeet/meetings/solver/meetingsScoreRules.drl</scoreDrl>
  </scoreDirectorFactory>

  <constructionHeuristic/>

  <localSearch>
    <termination>
      <minutesSpentLimit>4</minutesSpentLimit>
    </termination>
  </localSearch>

  <constructionHeuristic/>

  <localSearch />

  <termination>
    <minutesSpentLimit>30</minutesSpentLimit>
  </termination>
</solver>

Le solveur peut être configuré finement. Ici on alterne les phases de construction heuristique et la recherche locale. Enfin avec le paramètre termination / minutesSpentLimit on fixe le temps total de calcul à 30 minutes.

On injecte au solveur nos données meetings-not-solved.xml contenant notre modèle de données avec des rendez-vous sans créneau ni lieu (spot et slot à null) et les ressources disponibles (créneaux, lieux, utilisateurs...) :

import org.optaplanner.core.api.solver.Solver;
import org.optaplanner.core.api.solver.SolverFactory;
import org.optaplanner.meetings.common.persistence.SolutionDao;
import org.optaplanner.meetings.meetings.domain.Meeting;
import org.optaplanner.meetings.meetings.domain.MeetingSchedule;
import org.optaplanner.meetings.meetings.persistence.MeetingsDao;

import java.io.File;

public class MeetingsCliApp {

    public static void main(String[] args) {
        // Build the Solver
        SolverFactory<MeetingSchedule> solverFactory = SolverFactory.createFromXmlResource("path/to/solver-config.xml");
        Solver<MeetingSchedule> solver = solverFactory.buildSolver();

        // Load a problem
        SolutionDao<MeetingSchedule> meetingsDao = new MeetingsDao();

        // Read the input data
        MeetingSchedule unsolvedMeetingSchedule = meetingsDao.readSolution(new File("path/to/meetings-not-solved.xml"));

        // Solve the problem
        MeetingSchedule solvedMeetingSchedule = solver.solve(unsolvedMeetingSchedule);

        // Write the solution
        meetingsDao.writeSolution(solvedMeetingSchedule, new File("path/to/meetings-solved.xml"));
    }

Demo

Visualisation d'une solution optimale des plannings de rendez-vous des participants d'un événement :

• Spot : les lieux
• User : les participants
• Sheet : les rendez-vous par fiche de participation (généralement équivalente à une fiche société).

Le participant a ensuite son agenda des rendez-vous accessible sur son ordinateur ou sur mobile :

Bilan

Notre instance d'OptaPlanner pour Vimeet a maintenant réalisé la planification de dizaines d'événements depuis début

2017. Les organisateurs ont noté en moyenne une augmentation de 10% des rendez-vous positionnés par rapport à l'ancienne application de planification des rendez-vous.

De plus, les organisateurs d’événements sont maintenant autonomes pour réaliser la planification de rendez-vous. Depuis le backoffice Vimeet, ils cliquent sur un bouton "Planifier" et quelques minutes plus tard, les agendas de rendez-vous sont créés. L'application de planification est maintenant dépourvue d'UI et est appelée comme une API.

Le temps de calcul pour obtenir une solution acceptable est variable. Il est fonction des ressources en créneaux et en lieux de l'événement et du nombre de demandes acceptées. En réalité, on pourrait faire tourner le planificateur autant qu'on le souhaite. Plus il a de temps de calcul, plus il va tendre vers une meilleure solution.

Les statistiques et les planifications successives réalisées pour un événement

Axes d'amélioration

• Améliorer la vitesse du solveur : améliorer le modèle, ré-écrire les règles, benchmarker les algorithmes...
• Ajouter des règles métier pour satisfaire encore plus le participant : par exemple à la fois diluer les rendez-vous d’un participant sur la journée mais aussi réduire les écarts entre rendez-vous (par exemple pas de rendez-vous en début puis en fin de journée).
• Faire de la planification en continu même pendant l’événement pour positionner des rendez-vous en temps réel.

Quand utiliser OptaPlanner ?

Lorsqu'un problème possède des objectifs, des règles de gestion et tout cela avec des ressources limitées, c'est très probablement un problème de planification auquel OptaPlanner peut répondre.