Accueil > Manifestations > Thèses et HDR > Thèses > Thomas Vincent

Thomas Vincent

Directeur de thèse

Xavier Gandibleux
Anthony Przybylski

Résumé

Dans ce travail, nous nous intéressons à la résolution exacte de problèmes d’optimisation multiobjectif en variables mixtes binaires. La nature mixte des variables introduit d’importantes différences
par rapport aux contextes purement discrets ou continus. Nous proposons donc de prendre en compte ces différences grâce à une représentation appropriée des ensembles de solutions ainsi qu’une
procédure de mise à jour dédiée.

Ces propositions nous permettent, dans le contexte biobjectif, d’adapter deux méthodes de résolution usuellement appliquées aux problèmes combinatoires : la procédure de Branch & Bound et la méthode
en deux phases. Nous proposons de nombreux affinements pour ces méthodes, comme de nouveaux ensembles bornant ou des stratégies de cheminement. À partir de nos observations sur leurs performances,
nous proposons une nouvelle routine pour la seconde phase de la méthode en deux phases, reprenant les points forts des méthodes étudiées.

Dans le contexte triobjectif, nous étendons notre représentation des ensembles de solutions en procédant par analogie avec le cas biobjectif. Les méthodes de résolution sont également adaptées à ce
contexte et étudiées. En particulier, la décomposition de la zone de recherche lors de la seconde phase est décrite en détail.

La solution logicielle proposée a été appliquée sur un problème réel : l’évaluation d’une politique de choix de véhicules. Les choix concernés vont de véhicules conventionnels aux véhicules
électriques, eux-mêmes alimentés par une source d’électricité classique ou par panneaux solaires.

Mots-clés : programmation linéaire multiobjectif en variables mixtes, branch & bound, méthode en deux phases, résolution exacte.

Composition du jury :

  • Daniel Vanderpooten, Professeur, Université Paris-Dauphine, Rapporteur,
  • Jacques Teghem, Professeur, Université de Mons, Rapporteur,
  • Matthias Ehrgott, Professeur, Lancaster University, Rapporteur,
  • Marc Sevaux, Professeur, Université de Bretagne Sud, Examinateur,
  • Stefan Ruzika, Professeur, Universität Koblenz-Landau, Examinateur,
  • Xavier Gandibleux, Professeur, Université de Nantes, Directeur de thèse
  • Anthony Przybylski, Maître de conférences, Université de Nantes, Co-encadrant,

Abstract :

The purpose of this work is the exact solution of multiple objective binary mixed integer linear programmes. The mixed nature of the variables implies significant differences with purely continuous or
purely discrete programmes. Thus, we propose to take these differences into account using a proper representation of the solution sets and a dedicated update procedure.

These propositions allow us to adapt for the biobjective case two solution methods commonly used for combinatorial problems : the Branch & Bound algorithm and the two phase method. Several improvements
are proposed, such as bound sets or visiting strategies. We introduce a new routine for the second phase of the two phase method that takes advantage of all the relevant features of the previously
studied methods.

In the 3-objective context, the solution sets representation is extended by analogy with the biobjective case. Solutions methods are extended and studied as well. In particular, the decomposition of
the search area during the second phase is thoroughly described.

The proposed software solution has been applied on a real world problem : evaluation of a vehicle choice policy. The possible choices range from classical to electric vehicles that are powered by grid
or solar power.

Keywords : multiple objective mixed integer linear programmes, branch & bound, two-phases method, exact solution.

Dernière modification : vendredi 13 décembre 2013