Problèmes combinatoires :

Contrairement aux problèmes aléatoires, les variables sont mieux maîtrisées et connues dans un problème combinatoire. Mais cela ne le rend pas forcément plus simple à résoudre.

Un problème combinatoire se caractérise par la grande quantité de solutions possibles. L’idée étant de choisir la solution la plus optimale. Prenons un exemple bien connu à Neovision, l’optimisation de tournées. Comment affecter le bon conducteur au bon secteur et comment concevoir la meilleure tournée possible en connaissant tous les points de passage dans le but de limiter le kilométrage. En couplant la difficulté de conception de la tournée et la bonne affectation des conducteurs, nous pouvons énumérer des millions de solutions. Nous nous retrouvons ainsi face à une explosion combinatoire.

Ce type de problème ne peut pas être résolu par un humain, qui ne pourra choisir qu’une solution lui semblant optimale sans pouvoir en être sûr. D’où le recours à la Recherche Opérationnelle.

Problèmes concurrentiels :

Enfin, dernier type de problème qu’il est possible de résoudre grâce à la Recherche Opérationnelle, les problèmes dits concurrentiels. Ici, nous retrouvons des caractéristiques propres aux problèmes aléatoires et combinatoires.
Comme son nom l’indique, un problème concurrentiel consiste à trouver un optimum dans un contexte où ses propres décisions sont également liées à celles d’autres décideurs. Les variables sont interdépendantes et vont s’influencer mutuellement. Il existe à la fois une vraie incertitude concernant celles provenant des autres acteurs et un grand nombre de solutions potentielles.

L’exemple le plus parlant est celui des actions promotionnelles. Il existe tout un tas de décisions possibles : -10 ou -20%, un gratuit pour l’achat de 2, le second à moitié remboursé… En plus de cette multitude d’actions possibles, il faut également prendre en compte les actions promotionnelles de vos concurrents, qui auront un impact direct sur les résultats de vos choix.

Nous voyons donc que lorsqu’il est question de Recherche Opérationnelle, nous pouvons opter pour différentes approches. Un choix qui n’en est pas vraiment un puisque la nature du problème, ses caractéristiques, contraintes et autres variables définiront l’approche la plus pertinente.

Quel type de données et méthode algorithmique visée ?

Effectivement, il n’existe pas de méthode définie pour résoudre un problème de recherche opérationnel parce que – comme présenté précédemment – les problèmes en question peuvent être très variés. La méthode choisie est dépendante de la situation dans laquelle on se trouve et, même pour un problème donné, il va évidemment exister de nombreuses façons différentes de le résoudre.

Néanmoins tout n’est pas perdu : une première étape fondamentale de tout problème de RO est de réussir à modéliser le problème pour le ramener sous une forme abstraite que l’on sait résoudre. Prenons l’exemple discuté plus tôt de l’optimisation de tournée. Il peut se réduire à ce qu’on appelle le problème du voyageur de commerce. Ce problème mathématique bien connu consiste à trouver le chemin le plus court passant par un ensemble de villes définies.

Une fois que l’on est capable de ramener notre problème à un autre plus général de cette façon, on peut alors chercher à le modéliser, c’est-à-dire à le traduire sous une forme mathématique simple qui permettra de le résoudre. Dans le cas du voyageur de commerce, on peut classiquement représenter le problème sous la forme d’un graphe mathématique. C’est-à-dire qu’on fait une abstraction du problème pour ne le représenter plus que comme un ensemble de noeuds (les villes) connectés par des arêtes (les liens entre les villes), ces arêtes étant plus ou moins “chères” (la distance entre les villes). Une fois cette abstraction réalisée, il est plus simple de trouver une solution.

De manière plus générale, c’est la modélisation mathématique qui va déterminer la méthode que l’on utilise. Nous allons en citer quelques-unes ici pour donner un aperçu du domaine sans viser l’exhaustivité.

Une méthode régulièrement utilisée en RO est la programmation linéaire. Contrairement à ce que peut laisser penser son nom, il s’agit avant tout d’une méthode mathématique souvent utilisée pour trouver la solution d’un problème combinatoire. C’est-à-dire que l’on va chercher à trouver une combinaison de valeurs permettant, par exemple, de minimiser une fonction de coût. Un algorithme connu du domaine pour résoudre ce problème est celui du Simplex. Le problème devient plus complexe lorsque les valeurs que l’on cherche à trouver sont, au moins en partie, des nombres entiers.

Et puisque nous parlions un peu plus tôt de graphes, de nombreux algorithmes spécifiques ont été développés pour ce genre de modélisation. Une branche des mathématiques, la théorie des graphes, s’intéresse en effet à la résolution de problématiques liés à des graphes. Il s’agit notamment du genre de modélisation utilisée pour résoudre automatiquement un certain nombre de jeux tels que les échecs ou le go.

Si le problème est plus complexe et qu’il ne peut être modélisé sous cette forme mathématique, on va alors s’orienter vers des méthodes qui recherchent une approximation. C’est-à-dire qu’on n’est pas sûr de trouver le résultat optimal mais qu’on va chercher à en donner une approximation la plus proche possible. Ceci est par exemple le cas pour les problèmes que l’on dit NP-complet. Pour résumer grossièrement, ce que signifie ce terme c’est qu’il s’agit de problèmes dont il est rapide de vérifier la faisabilité d’une solution mais presque impossible d’énumérer l’ensemble des solutions possibles. Pour ce genre de problèmes, on va utiliser ce qu’on appelle des méta-heuristiques.

Ce terme un peu barbare décrit des méthodes générales qui vont spécifier une procédure de recherche itérative permettant de s’approcher petit à petit d’une solution. Elles sont basées sur des processus aléatoires pour trouver de nouvelles solutions et sont souvent inspirées de processus naturels. Par exemple, l’algorithme du recuit simulé tire son inspiration de la physique, les algorithmes évolutionnaires s’inspirent de l’évolution naturelle et l’algorithme de la colonie de fourmis du comportement de ces insectes.

C’est donc la modélisation du problème qui est capitale en RO et par conséquent, l’apport des données est très différent lorsqu’on compare à d’autres domaines applicatifs de l’IA présentés dans les épisodes précédents. Dans le cadre de la RO, ce qui est important c’est de connaître les problématiques métiers afin de fournir une modélisation la plus précise possible. Dans certains cas, il peut être nécessaire de créer une simulation informatique du problème avant d’être capable de le résoudre. C’est notamment le cas pour un certain nombre d’utilisation d’apprentissage par renforcement.

Pour ce genre de problèmes complexes où une résolution purement mathématique n’est pas possible, on utilise aussi parfois de l’apprentissage par renforcement. Ce type d’apprentissage automatique est très différent dans son fonctionnement des apprentissages supervisés et non-supervisés. Nous en avons déjà parlé dans les premiers épisodes et un épisode plus conséquent y sera consacré mais, pour résumer rapidement, le modèle apprend par la distribution de récompenses en fonction d’actions prises au cours du temps. Le but d’un algorithme d’apprentissage par renforcement est d’optimiser la séquence d’actions prises pour maximiser la récompense et ainsi résoudre le problème.

Bon, toute cette théorie, c’est bien, cela nous aide à mieux comprendre comment fonctionne la RO, mais comment est-elle réellement appliquée dans les entreprises ? D’ailleurs, l’est-elle vraiment ?

Applications concrètes et en production

La recherche opérationnelle est utilisée dans les entreprises à différents niveaux. À un niveau stratégique, elle permet de venir en aide sur des prises de décision, qui peuvent aussi bien concerner des investissements que des changements structurels. Et, sur un niveau plus opérationnel, elle intervient sur certains processus complexes.

Quand on va faire un tour du côté de la logistique et des transports, le premier cas d’usage qui apparaît est l’optimisation des tournées. Fini les kilomètres inutiles et bonjour les économies de temps, d’argent, mais également d’énergie ! Et à la clé, un pas de plus vers la réduction de notre impact sur l’environnement.