Qu'est-ce que la Recherche Opérationnelle ?


1. Définition

La Recherche Opérationnelle est, comme la Statistique, une branche des Mathématiques Appliquées. Son objet est, pour un problème donné, d'aider à prendre la meilleure décision possible, voire la décision optimale (maximisation des gains, minimisation des coûts). Pour ce faire, elle s'appuie sur une méthodologie et des outils mathématiques particuliers. La méthodologie se décompose en trois phases :

  1. Modélisation du problème : écriture du problème concret sous forme d'expressions mathématiques impliquant notamment, des variables (quantités qui seront modifiables pendant la seconde phase), des contraintes (à respecter pendant la seconde phase) et de la fonction objectif qui évalue le gain ou le coût associé aux valeurs des variables ;

  2. Calcul de l'optimum (minimisation ou maximisation de la fonction objectif) ;

  3. Prise de décision ou éventuellement, reformulation du problème et retour à la phase 1 si la solution n'est pas satisfaisante.

2. Un peu d'histoire

Gaspard Monge (1746-1818), mathématicien français, qui fut en 1817 le premier directeur de l’Ecole Polytechnique, a publié en 1781 un « Mémoire sur la théorie des déblais et des remblais ».

Mémoire sur la théorie des déblais et des remblais

Sans résoudre complètement le problème, mais se posant la question de comment transporter d'une surface A à une surface B (il étudie ensuite le problème en trois dimensions) des "molécules" en minimisant le coût de transport, qu'il estime proportionnel au poids, il jette les base d'une discipline des mathématiques, le transport optimal, dont les applications sont nombreuses et qui a été un sujet d'étude pour de nombreux mathématiciens jusqu'à Cédric Villani (Topics in Optimal Transportation, 2003, American Mathematical Association).

Le terme Operations Research apparaît en 1937 en Angleterre à l'initiative de A.P. Rowe dans un contexte militaire. Pendant les années qui précédèrent la seconde guerre mondiale et pendant cette dernière, la discipline a connu un essor particulier, la minimisation des coûts de production, des temps d'acheminement, de décision, les efforts de logistique et la maximisation du recueil d'informations (intelligence) ayant été déterminants (cf British Operational Research in World War II, O.R. in World War 2: operational research against the U-boat). Les américains s'approprient la discipline à partir de 1942. Après la guerre, la disciple est peu à peu appliquée dans l'industrie, l'économie, le management et dans ce qui devient peu à peu les sciences de la décision.

3. Les Sociétés Savantes

4. Un écosystème en plein essor

La Recherche Opérationnelle est une discipline qui profite pleinement de l'essor de l'informatique et des sciences de la donnée (data science). Pour son utilisation en entreprise, on peut la placer comme figuré ci-dessous parmi les différents processus faisant intervenir des données.

Recherche opérationnelle et data science

Les moteurs d'optimisation, aussi appelés solveurs, prennent en entrée des données structurées, des prévisions, ou des simulations. La solution proposée génère elle-même de la donnée (par exemple le meilleur ordonnancement pour les tâches à accomplir) qui peut à son tour nourrir le système d'information ou, le plus souvent, amener à une décision opérationnelle.

5. Pratiquer la Recherche Opérationnelle en entreprise

La recherche opérationnelle permet d'améliorer de nombreux processus dans une entreprise. Nous listons ci-dessous quelques exemples de projets qui ont été mis en oeuvre par des entreprises :

  • Planification de camions de gaz (inventory routing problem) (Air Liquide)
  • Planification de publicités télévisuelles (TF1)
  • Optimisation de commandes de matériel de chantier (Bouygues Construction)
  • Planification de chantiers de construction autoroutier (DTP Terrassement)
  • Planification des arrêts de maintenance de centrales nucléaires (EDF)
  • Planification de la maintenance des rames de trains (SNCF)
  • Replanification des RER en cas d’incidents (RATP)
  • Optimisation des stocks de Vélib (JCDecaux)
  • Dimensionnement et allocation des serveurs de stockage (Google)
  • Calcul des plannings du personnel navigant (Air France)
  • Optimisation des tarifs de transport de marchandises (Mersk)

Pour plus d’exemples, vous pouvez consulter le livre blanc de la Recherche Opérationnelle publié par la ROADEF.

6. Déroulement d'un projet de Recherche Opérationnelle

De l'identification du problème à sa résolution pratique :

Un projet de recherche opérationnelle

7. Quelques définitions :

Qu'est-ce qu'un problème d'Optimisation ?

Un problème de Recherche opérationnelle consiste en la recherche de la solution optimale, si possible, ou sinon d'une bonne solution, au regard d'un critère donné appelé fonction objectif.

Pour que la recherche d'une solution au problème soit possible, ce dernier doit être modélisé sous forme logique, mathématique, puis informatique (avec un logiciel ou un programme appelé solveur) au travers de variables de décision (les éléments que l'on peut faire varier lors de la recherche de la solution), de contraintes (qui bornent l'espace de variation des variables) et bien entendu de la fonction objectif qui correspond au coût ou au gain dont on cherche l'optimum.

Qu'est-ce qu'une Modélisation ?

La modélisation d’un problème consiste à identifier les données du problème (objectif recherché, variables pouvant influer sur l'objectif), puis à écrire les contraintes évidentes ou connues pour les variables et éventuellement l'objectif, pour finalement écrire la fonction objectif qui relie l'objectif aux variables. La phase de modélisation est critique car elle seule permet de s'assurer que le problème est bien posé, compris et traduit en termes mathématiques et informatique.

Qu'est-ce qu'une fonction Objectif ?

La fonction objectif permet de représenter l’attente du problème, que l'on cherchera parfois à maximiser (plus de rapidité, plus de satisfaction, plus de profit, etc.) et parfois à minimiser (moins de temps, de coûts, de ressources, etc.). Elle peut également englober plusieurs critères, en s'écrivant alors sous la forme d'une combinaison de ces derniers.

Qu'est-ce qu'une Variable de Décision ?

Une variable de décision représente une valeur du problème que l'on va pouvoir faire varier lors de la recherche d'une solution. La fonction objectif fait intervenir directement ou indirectement les valeurs des variables de décision. En fonction du problème, le nombre de variables peut varier d'un à plusieurs dizaines de milliers.

Qu'est-ce qu'une Contrainte ?

Les contraintes permettent d'encadrer la recherche de la solution. Elles permettent, d'une part, de rendre la recherche possible et, d'autre part, lorsqu'elles sont bien définies, d'accélérer la recherche de la solution. Les contraintes s'appliquent aux variables de décision, ainsi que parfois à la fonction objectif. Par exemple, les contraintes permettront d'indiquer qu'un pH doit être entre compris entre 0 et 14 ou que le nombre de trajets est un entier positif inférieur à une valeur donnée.

Les contraintes sont des données d'entrée du problème qui ne sont pas modifiées lors de la recherche d'une solution.

Qu'est-ce qu'une Solution ?

A chaque ensemble (n-uplet) de valeurs des variables de décision respectant les contraintes correspond une solution. La solution se traduit par une valeur unique de la fonction objectif. Il se peut qu'à plusieurs solutions correspondent des valeurs identiques de la fonction objectif. Dans le cas de problèmes très complexes, on pourra se contenter d'une solution sans être parfaitement sûr qu'il s'agisse de la solution optimale (temps de calcul trop long, ou problème trop complexe).

Qu'est-ce qu'une Solution Optimale ?

Une solution optimale d'un problème est la ou une des solutions auxquelles correspond la meilleure valeur possible de la fonction objectif. Elle se matérialise par l'ensemble (n-uplet) de valeurs qui respectent les contraintes tout en optimisant la fonction objectif (minimum ou maximum en fonction du critère).

fonction objectif présentant une solution optimale

Qu'est-ce qu'un Solveur ?

Un solveur est un logiciel qui permet de modéliser un problème (variables, contraintes, fonction objectif) pour ensuite trouver soit une solution, soit une solution optimale.

Il existe différents solveurs sur le marché. Tous ne s’appuient pas sur les mêmes méthodologies/approches/techniques mathématiques ou informatiques pour trouver la solution (simplexe, recherche locale, heuristique, …).

Après avoir analysé les différentes solutions du marché, la société Addinsoft a retenu le solveur développé par la société LocalSolver, afin de mettre à disposition de ses utilisateurs le logiciel XLOPTIM®, intégré à Microsoft Excel.

Vous trouverez sur le site quelques cas d’usage du logiciel.