• Langue : Français
• Discipline : Informatique
• Identifiant : Inconnu
• Type de thèse : Doctorat
• Date de soutenance : 01/01/2004

Résumé en langue originale

Les travaux effectués durant cette thèse s'inscrivent dans le domaine de la recherche opérationnelle et plus particulièrement dans le domaine de l'optimisation combinatoire. Ils portent sur la définition et la résolution de problèmes de tournées multi-objectif. Les problèmes de tournées constituent l'une des classes emblématiques de la recherche opérationnelle. Un problème célèbre appartenant à cette famille est le problème du voyageur de commerce. L'optimisation multi-objectif, qui connaît un intérêt de plus en plus important depuis la fin des années 80, traite des outils nécessaires pour aborder des problèmes qui comportent plusieurs objectifs conflictuels en ne favorisant pas un objectif par rapport à un autre. D'un point de vue de la méthodologie, notre approche est centrée sur l'utilisation d'algorithmes génétiques multi-objectif. Ces méthodes connaissent un intérêt, croissant depuis le début, des années 90 car elles sont particulièrement bien adaptées au traitement de problèmes multi-objectif dont la solution est un ensemble de solutions. Pour améliorer l'efficacité des algorithmes génétiques utilisés, un nouveau mécanisme a été proposé ainsi que l'utilisation du parallélisme sous la forme de modèles en îles qui prennent en compte le mécanisme proposé et les particularités des algorithmes génétiques multi-objectif. La coopération entre les algorithmes génétiques multi-objectif et des méthodes de voisinage ou des méthodes exactes a également été étudiée. Plusieurs stratégies ont été proposées. Plusieurs implémentations spécifiques aux problèmes présentés ci-dessous ont été réalisées. Nous avons défini et étudié deux problèmes. Le premier, nommé le problème de la tournée couvrante bi-objectif, est une généralisation d'un problème défini par Gendreau et al. Il s'agit de définir une tournée de longueur minimale, sur un sous-ensemble d'un ensemble de sommets de telle sorte, que la plus grande distance entre un sommet d'un autre ensemble et un sommet visité soit minimale. Ce problème a notamment été résolu sur des données réelles provenant de la recherche de tournées pour une unité de soins mobile dans le district de Suhum au Ghana. Le second problème est une extension du problème d'élaboration de tournées de véhicules qui est l'un des problèmes majeurs rencontrés en logistique et notamment pour la distribution. Dans le problème d'élaboration de tournées de véhicules avec équilibrage des tournées, on ne cherche pas seulement à minimiser le coût des solutions mais aussi a équilibrer les longueurs des tournées qui la composent, pour introduire une notion d'équité entre les tournées. L'apport des différentes méthodes proposées a été évalué sur des jeux de données adaptés à partir d'instances classiques du problème d'élaboration de tournées de véhicules