Contributions aux Méthodes d'Optimisation Combinatoire Multi-Objectif

Résoudre un problčme MOCO revient ŕ définir l'ensemble de solutions efficaces en compréhension ou en extension. Les études antérieures montrent ŕ suffisance qu'il est illusoire de caractériser les solutions efficaces ŕ cause du caractčre combinatoire et non convexe du domaine d'admissibilité. En effet, la topologie sous-jacente induit l'existence de deux types de solutions efficaces: supportées et non supportées. Seules les solutions supportées ont pu ętre caractérisées théoriquement. Nous mettons en évidence une caractérisation globale de l'ensemble de solutions efficaces et une nouvelle Méthode du Repčre Préférentiel de Dominance. Nous nous sommes inspiré du théorčme dit "de contact'' énoncé erronément et sans démonstration par Collette & Siarry (2002), théorčme élogieux que nous corrigeons et démontrons formellement pour la toute premičre fois. Pour faire oeuvre utile, deux heuristiques de résolution du problčme multi-objectif de tournées de véhicules ont été développées. La premičre utilise MRPD dans la procédure d'un algorithme dénommé toile d'araignées que nous avons élaboré. La seconde est une adaptation au contexte multi-objectif de l'heuristique de Clarke & Wright.