Après un bref aperçu historique, j'évoquerai quelques exemples concrets afin de mettre en évidence l'intérêt d'une modélisation faisant intervenir des critères multiples.

J'aborderai ensuite le choix de modélisation des préférences auquel est confronté le chercheur opérationnel. Je montrerai qu'en combinant les deux grandes options qui s'offrent à lui (approche monocritère et approche multicritère) avec le rôle attendu de l'optimisation pour aboutir à des résultats, on est conduit à distinguer six types de prati-ques opératoires possibles (effectivement utilisées).

Le reste de l'exposé sera consacré à un examen rapide des difficultés conceptuelles, méthodologiques, théoriques et de mise en uvre effective auxquelles se heurte le cher-cheur opérationnel selon le rôle qu'il entend faire jouer à l'optimisation lorsqu'il a fait le choix de travailler avec des critères multiples.

En aide à la décision, on est souvent amené à devoir prendre en compte des préférences qui ne sont pas nécessairement représentables par une fonction coût scalaire (préférences non-complètes, non-nécessairement transitives, multicritères, ). Même lorsque une telle fonction existe, elle ne jouit pas toujours de propriétés permettant d'obtenir facilement les solutions préférées. Dans cet exposé, nous illustrons les problèmes posés par la prise en compte de telles préférences dans des problèmes combinatoires divers (arbres couvrants, chemins, PLNE, ). Nous cherchons à identifier des structures de préférences pour lesquelles les algorithmes classiques restent admissibles, puis envisageons quelques voies possibles pour l'obtention ou l'approximation de solutions préférées en présence de structures de préférence plus complexes.

Travail réalisé en en collaboration avec Matthias Ehrgott (University of Auckland).

L'exposé fait une revue des méthodes de résolution approchées, habituellement appelées heuristiques et métaheuristiques, pour la résolution de problèmes d'optimisation combinatoire multiobjectifs.

Des questions concernant le concept d'approximation dans ce contexte sont abordées : ratio de performances, bornes et ensembles de bornes, ou encore des mesures de qualité.

Des exemples d'heuristiques sont donnés, toutefois il est essentiellement question de métaheuristiques, et plus particulièrement de méthodes non-évolutionnaires.

Les méthodes pionnières, ainsi que leurs dérivées, sont décrites d'une manière unifiée. Les tendances dans le domaine sont mentionées.