Recherche Opérationnelle

Dans le vaste champ couvert par la recherche opérationnelle, le LIA se concentre essentiellement sur deux domaines : l’optimisation discrète et la théorie des jeux. Beaucoup de projets du LIA font appel à d’autres domaines de la recherche opérationnelle (théorie des graphes, théorie des files d’attente, chaînes de Markov), mais ces domaines sont alors plus abordés en tant qu’outils qu’en tant que thèmes de recherche.

Optimisation discrète

L’optimisation discrète concerne les problèmes d’optimisation (minimisation de coûts, maximisation de bénéfices, les deux concepts devant être pris au sens large) où une partie au moins des variables de décision doivent prendre des valeurs discrètes (entières). De manière générale, la politique suivie est de développer des activités selon un axe “ fondamental ” et un axe “ appliqué ”. Ces deux directions nous semblent en réalité, dans une discipline comme la recherche opérationnelle, indissociables et s’enrichissent mutuellement. Pour ces même raisons, les activités sont d’une part regroupées selon des thématiques “ problèmes ” (on s’intéresse avant tout au problème et on cherche des méthodes efficaces de résolution) et, d’autre part, selon des thématiques “ méthodes ” (on focalise sur la méthode pour mieux en comprendre le fonctionnement, la rendre plus performante, la faire évoluer en l’appliquant éventuellement à différents problèmes).

Les principales directions de recherche en optimisation discrète sont :

  • la coopération metaheuristiques – méthodes exactes
  • les méthodes de décomposition
  • la planification de transport
Coopération metaheuristiques – méthodes exactes

Il est de plus en plus couramment admis que l’efficacité des metaheuristiques repose sur des opérateurs de voisinage performants, aussi bien pour les metaheuristiques basées sur une recherche locale (méthode tabou, recuit simulé…), que pour les metaheuristiques évolutionnistes (algorithmiques génétiques, colonies de fourmis…). Schématiquement, ces opérateurs de voisinage permettent de se déplacer dans l’espace des solutions en passant d’une solution courante à une solution de structure proche (solution voisine). Parmi ces solutions voisines, la meilleure, selon l’objectif défini, est généralement sélectionnée.

Les méthodes traditionnelles parcourent toutes ces solutions voisines pour identifier la meilleure. Une alternative est de poser le problème de recherche de la meilleure solution voisine comme un problème d’optimisation. L’intérêt est alors d’explorer de plus grands voisinages, et l’on parle de méthode de recherche à grand voisinage. Ce problème d’optimisation, qui devra être résolu de très nombreuses fois, nécessite l’utilisation d’une méthode exacte adaptée.

Réciproquement, la faiblesse principale des méthodes exactes réside dans leur difficulté à fournir des solutions de bonne qualité rapidement. L’utilisation des principes développés au sein des metaheuristiques peuvent permettre de diriger plus rapidement la recherche en direction des meilleures solutions. C’est ce qui existe notamment dans des méthodes telles que Local Branching ou Reduced Neigborhood Induced search.

Au cours des dernières années, plusieurs travaux prometteurs ont été initiés au LIA dans ces directions. ces travaux doivent poursuivis, à la fois pour des problèmes académiques et pratiques.

Méthodes de décomposition

Pour de nombreux problèmes se modélisant sous forme de programme linéaire en nombre entiers, les formulations classiques ont une relaxation linéaire de très mauvaise qualité (écart important entre les solutions optimales du programme en variable entières et du programme relaxé). Utiliser la relaxation linéaire comme borne dans un schéma de résolution basé sur la séparation et l'évaluation (Branch and Bound) devient alors totalement inapproprié et se révèle inefficace dès que la taille des instances augmente. Une solution consiste à utiliser des méthodes de décomposition (décomposition de Benders, décomposition de Dantzig-Wolfe) donnant à lieu à de nouveaux modèles plus efficaces. En contrepartie, ces modèles nécessitent l'utilisation d'algorithmes complexes : génération de coupes pour la décomposition de Benders (nombre exponentiel de contraintes), génération de colonnes pour la décomposition de Dantzig-Wolfe (nombre exponentiel de variables).
Nos travaux sur la décomposition de Dantzig-Wolfe portent essentiellement sur la technique de génération de colonnes/Branch and Price qui en découle. Le cadre d'étude est pour l'instant restreint aux problèmes de tournées de véhicules. Ces techniques sont en plein essor et nécessitent encore de nombreux développements théoriques et pratiques.
Nos travaux sur la décomposition de Benders consistent essentiellement à en tester l'efficacité dans des cadres originaux (problèmes d'affectation de fréquences, problèmes d'ordonnancement) pour lesquels elle semble a priori bien adaptée.

Panification de transport

D’un point de vue applicatif, nous prévoyons de continuer à porter une attention particulière au domaine des transports, et plus précisément aux problèmes de tournées de véhicules. Les problèmes de tournées de véhicules consistent à planifier des itinéraires de véhicules afin de satisfaire la demande de clients. Il s'agit d'une classe de problèmes très large incluant le célèbre problème du voyageur de commerce (trouver un ordre optimal de visite de n clients avec un véhicule). Les applications de cette classe de problèmes sont très nombreuses en transport, mais aussi dans d'autres domaines tels que la production, où des tâches peuvent parfois être assimilées à des clients et des machines, à des véhicules. Nous nous intéressons à plusieurs problèmes importants de cette classe, tels que le problème de tournées sur les arcs avec contraintes de capacités, les problèmes de tournées avec gains ou le problème de tournées avec préemption de la demande. Notre inclination actuelle serait de nous orienter de plus en plus vers des tournées à but de service plutôt que de distribution. Ce type de tournées connaît un développement très fort, notamment pour des opérations de maintenance, de suivi médical à domicile ou pour du transport de personnes à la demande. Un des objectifs est alors d’intégrer des critères de qualité de service dans des problèmes plus usuels de tournées.

Théorie des jeux

La théorie des jeux est un outil de modélisation important lorsque plusieurs acteurs interviennent dans la prise de décision. Les travaux effectués au LIA autour de cette technique touchent pour l’instant uniquement les réseaux de télécommunications.



Laboratoire Informatique d'Avignon

Université d'Avignon et des Pays de Vaucluse
339 chemin des Meinajaries, Agroparc BP 91228, 84911 Avignon cedex 9
+33 (0)4 90 84 35 00