Avancé Intermédiaire

Devoxx France 2015 : OptaPlanner ou comment optimiser les itinéraires, les plannings et bien plus encore

 

devoxx fr 2015Vous souvenez-vous, durant vos folles années d’étudiant, avoir été confrontés, lors d’un cours d’algorithme, au problème du voyageur de commerce ? (Rappelez-vous, Il s’agit pour un voyageur de commerce, de trouver le plus court chemin passant par un ensemble de villes à visiter). C’est un problème NP-complet, pour lequel on n’a, jusqu’à aujourd’hui, pas de solution exacte tournant dans un temps “acceptable”… Il existe néanmoins, des solutions “approchantes” raisonnables : OptaPlanner en est une ! Voici un petit compte rendu de la présentation qui en a été faite par Geoffrey De Smet, leader technique et fondateur d’OptaPlanner et Frederic Hornain, Solution Architect chez Redhat, lors de la session 2015 de Devoxx France.

Optaplanner, c’est quoi ?

OptaPlannerRésultat de recherche d'images pour "optaplanner" est un moteur Open Source de recherche de solution optimale aux problèmes de satisfaction de contraintes ; en d’autres termes : il  fait comme Winston Wolfe, “il résout les problèmes” !

OptaPlanner est développé chez Redhat JBoss. Ecrit en java, intégrable et léger, il trouve des solutions de manière “efficace” aux problèmes de planification (du type problème du voyageur de commerce, ou problème du sac à dos, dits problèmes NP-complet), en combinant heuristiques d’optimisation et méta heuristiques avec calcul de score : en clair, il trouve une solution “quasi-optimale” en un temps “raisonnable” à des problèmes complexes !

Quelques exemples d’application

Durant leur présentation à Devoxx, Geoffrey De Smet et Frederic Hornain nous ont exposé plusieurs exemples d’utilisation du moteur d’OptaPlanner en entreprise, à travers plusieurs démos…

Le parcours aérien d’un PDG

parcours_aerien

Le problème est identique à celui du problème du voyageur de commerce : un PDG souhaite se rendre en avion dans un certain nombre de villes et cherche à optimiser son temps de trajet.  Durant cette démo utilisant la GUI et le moteur d’OptaPlanner, nous avons vu comment l’outil pouvait calculer en temps réel le trajet optimal (Il est même possible d’ajouter / supprimer une ville pour qu’OptaPlanner recalcule à la volée le nouveau meilleur trajet à effectuer !)

Le chauffeur livreur

Un autre problème du même type est celui du planning du chauffeur livreur, qui doit effectuer sa tournée avec son camion. OptaPlanner s’intègre alors avec Google Maps ou GraphHopper, pour calculer le meilleur trajet sur la carte routière :

optaplanner_google_maps

 Le cloud provider

cloud Enfin, un autre exemple d’utilisation présenté durant le talk, tiré d’un cas réel est celui du Cloud provider, qui cherche à optimiser l’utilisation de son parc de machines : il doit en effet faire tourner l’ensemble des processus de ses clients sur un minimum de machines, en les regroupant de manière optimale tout en respectant certaines contraintes (utilisation CPU, utilisation mémoire, bande passante réseau…)

optaplanner_cloud_provider

Dans ce cas concret, les solutions calculées par OptaPlanner ont apporté une économie de 17% au cloud provider sur ses frais par rapport à sa solution “maison” !

Dans chaque boîte d’OptaPlanner, on trouve…

OptaPlanner est un projet Open Source (Licence Apache) écrit en java (code source sur github), disponible sur le central maven repository :


<dependency>
   <groupId>org.optaplanner</groupId>
   <artifactId>optaplanner-core</artifactId>
   <version>6.2.0.Final</version>
</dependency>

Il existe également sous forme d’un zip téléchargeable depuis le site d’OptaPlanner, qui contient notamment des exemples d’utilisation :

La documentation complète y est incluse (elle est également disponible en ligne, avec un quick start guide), ainsi que la Javadoc et le code source.

Mise en route

Utiliser OptaPlanner pour résoudre un problème se fait de manière programmatique et par configuration ; prenons l’exemple du cloud provider. Il s’agit de suivre les étapes suivantes :

1) Définir le problème

Le problème est celui défini précédemment : il s’agit d’assigner des processus à des machines, en tenant compte de leurs capacités (CPU, mémoire, bande passante), et en optimisant l’utilisation du parc de machines pour en minimiser le coût… Plus formellement, on pourra dire que ce problème doit :

  • respecter les contraintes fortes suivantes:
    • La puissance CPU d’une machine doit être supérieure ou égale à la somme des puissances CPU requises par chaque processus hébergé
    • La taille mémoire d’une machine doit être supérieure ou égale à la somme des tailles mémoire requises par chaque processus hébergé
    • La bande passante consommée par l’ensemble des processus est inférieure ou égale à la bande passante maximale de la machine
  • optimiser la contrainte faible suivante :
    • le coût d’utilisation du parc de machines doit être minimal

2) Modéliser le métier

Nous allons définir nos objets métier sous forme de POJO, qui permettront de modéliser le problème :

  • Computer représentera une machine, avec ses capacités (CPU, mémoire, bande passante) et un coût d’utilisation
  • Process un processus devant tourner sur une machine
  • CloudBalance qui modélise le problème proprement dit : il référence un dataset de machines et de processus clients que l’on souhaite associer

Nous utiliserons ensuite des annotations OptaPlanner pour interagir avec le moteur :

3) Injecter le dataset

OptaPlanner peut s’intégrer avec toutes sortes de datasource, pour récupérer le dataset sur lequel on souhaite résoudre un problème :

  • flux XML (via XStream, JAXB…)
  • base de données (JDBC, JPA…)
  • REST/SOAP
  • Infinispan, Hadoop…

Dans cet exemple, nous utiliserons un générateur aléatoire de Computer / Process :

// Load a problem with 400 computers and 1200 processes
CloudBalance unsolvedCloudBalance = new CloudBalancingGenerator().createCloudBalance(400, 1200);

4) Implémenter les contraintes

Cette étape (la plus difficile !) consiste à traduire les contraintes définies ci-dessus en contraintes compréhensibles par OptaPlanner, lui permettant de calculer un score pour chaque solution testée, et ainsi trouver la solution “optimale”. Elles peuvent être écrites sous 3 formes possibles :

5) Configurer le moteur de résolution

Le moteur de résolution est configuré via un fichier XML, dans lequel on déclare notamment :

  • Les POJO utilisés pour modéliser le métier
  • Comment calculer le score (quelle classe java ou fichier DRL utiliser)
  • Éventuellement, comment optimiser l’algorithme de résolution utilisé (fonctionnalités avancées)

6) Assembler et exécuter !

Enfin, l’assemblage et l’exécution du planner se fait simplement par API :

public class CloudBalancingHelloWorld {

   public static void main(String[] args) {
      // Build the Solver
      SolverFactory solverFactory = SolverFactory.createFromXmlResource("org/optaplanner/examples/cloudbalancing/solver/cloudBalancingSolverConfig.xml");
      Solver solver = solverFactory.buildSolver();

      // Load a problem with 400 computers and 1200 processes
      CloudBalance unsolvedCloudBalance = new CloudBalancingGenerator().createCloudBalance(400, 1200);

      // Solve the problem
      solver.solve(unsolvedCloudBalance);
      CloudBalance solvedCloudBalance = (CloudBalance) solver.getBestSolution();

      // Display the result
      System.out.println("\nSolved cloudBalance with 400 computers " +
                         "and 1200 processes:\n" +
                         toDisplayString(solvedCloudBalance));
   }

 ...

}

NB : Pour plus de détails sur cet exemple, consulter le Quick Start guide

Conclusion

OptaPlanner est un outil fort prometteur de recherche de solution optimale à des problèmes sous contraintes, relativement simple à prendre en main, et intégrable dans une application java. Même si durant leur démonstration, Geoffrey De Smet et Frederic Hornain nous ont montré un outil performant et réactif, on peut s’interroger sur sa scalabilité, face à un problème comportant un grand nombre de contraintes, ou un dataset big data. Même si aujourd’hui la librairie ne peut fonctionner sur un cluster, ce qui ouvrirait la porte à une scalabilité horizontale, Frederic et Geoffrey nous l’ont promis : ils y travaillent déjà !

Nombre de vue : 525

COMMENTAIRES 1 commentaire

  1. Geoffrey De Smet dit :

    La vidéo est ici.

AJOUTER UN COMMENTAIRE