Planification OptaPlanner - 10 Oct 2017

Planification de rendez-vous avec OptaPlanner

Richard HANNA
Écrit par Richard HANNA

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 :

Catalogue Vimeet

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

Catalogue Vimeet

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 :

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.

Algorithme génétique et algorithme de colonies de fourmis

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 :

Optaplanner exemples

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

Optimisation agenda de profs

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

Optimisation lits d'hôpital

La minimisation du trajet d’un voyageur de commerce :

Optimisation trajet du voyageur de commerce

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

Optimisation du plan de table de 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 :

Les annotations de OptaPlanner

Modèle

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 :

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 :

Demo

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

Agenda utilisateur

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.

Demandes de Rdv acceptées Rdv positionnés % transformation Temps de calcul
Event X 630 560 89% 3 minutes
Event Y 6700 5400 80% 6 heures

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

Axes d’amélioration

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.