Optimisation combinatoire multi-objectif : des méthodes aux problèmes, de la Terre à (presque) la Lune
Résumé
This manuscript presents some of the works I have done since I obtained my Ph.D. degree. The document focuses primarily on studies dealing with multi-objective combinatorial optimization. A first part is dedicated to optimization methods in general. First, desired properties of the methods are exposed as well as a framework to study multi-objective problems. Then, three contributions are done. The first one is about crossover operators for genetic algorithm. It is shown how crossover operators that consider multiple objective at once can be designed. The second point is about the use of branch-and-cut algorithms for multi-objective optimization. Mechanisms are proposed that take into account particularities linked to the presence of multiple objective. Finally, the use of column generation to compute dual bounds is investigated. The remaining of the document is about application to problems. First, two vehicle routing problems are studied. The first one is a variant where labels are associated to the edges of the graph. The second problem deals with covering issues in vehicle routing problems. Every node must not be visited but they must be covered by the solution. The last application is selection and planning of requests for an Earth observing satellite. The study is done in a multi-user context and solutions that are fair between the users are searched.
Ce manuscrit présente une partie des travaux que j'ai réalisés à la suite de ma thèse. Le document se focalise particulièrement sur les études menées dans le cadre de l'optimisation combinatoire multi-objectif. Une première partie se consacre aux méthodes d'optimisation en général. Après avoir fixé un cadre pour les propriétés souhaitées dans les méthodes proposées, trois points sont présentés. Le premier porte sur la définition d'opérateurs de croisement pour les algorithmes génétiques qui prennent en compte l'ensemble des objectifs. Le second point est sur la définition d'un algorithme de séparations et coupes pour l'optimisation multi-objectif. Le dernier point est l'étude de l'utilisation de la génération de colonnes en optimisation combinatoire multi-objectif pour le calcul de bornes inférieures. La seconde moitié du mémoire porte sur l'application de ces méthodes. Deux problèmes de tournées de véhicules sont tout d'abord présentés. Le premier problème consiste en la prise en compte de labels associés aux arêtes du graphe. Le second problème est une variante où une notion de couverture est utilisée pour ne pas avoir à visiter tous les sommets du graphe. Une dernière application est la sélection et la planification de prises de vue par un satellite d'observation de la Terre dans un cadre multi-utilisateur où l'on souhaite garantir une équité entre les utilisateurs.