La reconstruction phylogénétique vise à reconstituer l'histoire évolutive d'un ensemble d'espèces sous forme d'un arbre. Parmi les méthodes de reconstruction, le problème Maximum de Parcimonie (MP) consiste à trouver un arbre binaire dont les feuilles sont associées à des séquences de caractères données, et qui minimise le score de parcimonie. Les méthodes de résolution existantes de ce problème NP-complet s'attachent généralement à appliquer des méthodes heuristiques traditionnelles, comme des algorithmes gloutons et de recherche locale. L'une des diffcultés du problème repose sur la manipulation d'arbres et la définition de voisinages d'arbres.<br />Dans cette thèse, nous nous intéressons en premier lieu à l'amélioration des techniques de résolution du problème MP basées sur un algorithme de descente. Après avoir montré de manière empirique les limites des voisinages existants, nous introduisons un voisinage progressif qui évolue au cours de la recherche afin de limiter l'évaluation de voisins infructueux lors d'une descente. L'algorithme obtenu est ensuite hybridé à un algorithme génétique utilisant un croisement d'arbres spécifique fondé sur les mesures de distance entre chaque couple d'espèces dans l'arbre. Cet algorithme mémétique exhibe des résultats très compétitifs, tant sur des jeux de test tirés de la littérature que sur des jeux générés aléatoirement.

This dissertation concerns the development of reduced complexity controllers for<br />hybrid switched systems. A diverse number of applications from automotive industry, fluid dyna-<br />mics and power systems are treated. Some general open loop optimal and predictive control schemes<br />are proposed. The main motivation behind each method is the reduction of the combinatorics. In<br />this thesis, two main contributions can be distinguished. The first one concerns the optimal control<br />of switched nonlinear systems where an algorithm based on strong variations is proposed and some<br />convergence results proven. The complexity of the scheme is linear in the number of locations, this<br />in conjunction with its simplicity makes it attractive for large scale systems. An example from<br />the automotive industry is treated to further illustrate the tractability of the scheme. The second<br />contribution concerns the development of a hierarchical approach for switched nonlinear systems.<br />At the lower level, feedback controllers are associated to each location and at the higher level a<br />predictive approach with a reduced order parametrization is in force. Based on this methodology,<br />two schemes are developed and successfully tested in respectively fluid stabilisation by actuator<br />switching and voltage stabilization in power systems.

Les travaux de cette thèse concernent la conception et l’optimisation de lignes de transfert reconfigurables. L’objectif principal est de concevoir une ligne d’usinage à moindre coût tout en respectant les contraintes techniques, technologiques et économiques du problème. Le problème d’optimisation correspondant est un problème d’équilibrage de lignes d’usinage sujet à des contraintes spécifiques. Il consiste à affecter les opérations aux stations de travail en minimisant les coûts d’installation. En plus des contraintes habituelles de ce type de problème, à savoir, les contraintes de précédence, d’inclusion et d’exclusion, nous avons dû considérer des contraintes d’accessibilité. De plus, la spécificité principale des lignes reconfigurables par rapport aux lignes de transfert dédiées, vient de la réalisation en série des opérations. Celle-ci rend souvent nécessaire la mise en place de stations équipées de plusieurs centres d’usinage travaillant en parallèle pour obtenir les volumes de production souhaités. Enfin, l’utilisation d’une tête d’usinage mono-broche induit la prise en compte de temps inter-opératoire de déplacements et de changement d’outils qui dépendent de la séquence d’opérations. Dans un premier temps, nous avons proposé une modélisation mathématique du problème à l’aide d’un programme linéaire en nombres mixtes. Nous avons aussi développé des méthodes de calcul de bornes inférieures ainsi qu’une procédure de prétraitement. Cependant, les contraintes additionnelles rendent la résolution du problème d’équilibrage plus difficile que dans le cas des lignes dédiées, et l’approche proposée ne permet généralement pas de résoudre des instances de taille industrielle. Pour répondre à ce besoin, nous avons donc développé plusieurs méthodes de résolution approchées du problème en nous inspirant de métaheuristiques efficaces sur des problèmes d’optimisation combinatoire. / This work concerns the design and the optimization of reconfigurable transfer lines. The principle objective is to design a machining line with less cost while respecting the technological and economic constraints of the problem. The corresponding optimization problem is a transfer lines balancing problem subject to specific constraints. It consists to affect operations to workstations minimizing the installations cost. In addition to the habitual constraints of the transfer balancing problem, i.e. precedence, inclusion and exclusion constraints, we consider accessibility constraints. In addition, the principal specificity of reconfigurable lines compared to the dedicated transfer lines, comes from the sequential execution of operations. This often makes it necessary to set up stations with several machining centers working in parallel to achieve desired production volumes. Finally, the utilization of mono-spindle head machining center induces the inclusion of setup times between operations. This setup time is due to the time of displacement and change of tools which it depends of the operational sequence. We proposed firstly a mathematical formalization of the problem using a mixed integer program. We developed also several methods to calculate lower bounds and a pretreatment procedure. However, the additional constraints make the resolution of the considered balancing problem very difficult and the proposed approach generally does not solve instances of industrial size. To meet this need, we have developed several approximate resolution methods of the problem taking inspiration from effective Metaheuristics on combinatorial optimization problems.

Les activités de transport jouent un rôle crucial autant dans le domaine de la production que dans celui des services. En particulier, elles permettent d’assurer la distribution de biens et de services entre fournisseurs, unités de production, entrepôts, distributeurs, et clients finaux. Plus spécifiquement, les problèmes de tournées de véhicules (VRP) considèrent la mise au point d’un ensemble de tournées de coût minimal servant la demande en biens ou en services d’un ensemble de clients distribués géographiquement, tout en vérifiant un ensemble de contraintes opérationnelles. Alors qu’il s’agissait d’un problème statique, des avancées technologiques récentes permettent aux organisations de gérer leur flotte de véhicules en temps réel. Cependant, ces nouvelles technologies introduisent également une plus grande complexité dans les tâches de gestion de flotte, révélant une demande pour des outils d’aide à la décision dédiés aux problèmes de tournées de véhicules dynamiques. Dans ce contexte, les contributions de la présente thèse de doctorat s’organisent autour de trois axes : (i) elle présente un état de l’art détaillé des problèmes de tournées dynamiques; (ii) elle introduit des frameworks d’optimisation génériques adaptés à une grande variété de problèmes ; (iii) elle définit un problème de tournées novateur et aux nombreuses applications. / Within the wide scope of logistics management,transportation plays a central role and is a crucialactivity in both production and service industry.Among others, it allows for the timely distributionof goods and services between suppliers, productionunits, warehouses, retailers, and final customers.More specifically, Vehicle Routing Problems(VRPs) deal with the design of a set of minimal costroutes that serve the demand for goods orservices of a set of geographically spread customers,satisfying a group of operational constraints.While it was traditionally a static problem, recenttechnological advances provide organizations withthe right tools to manage their vehicle fleet in realtime. Nonetheless, these new technologies alsointroduce more complexity in fleet managementtasks, unveiling the need for decision support systemsdedicated to dynamic vehicle routing. In thiscontext, the contributions of this Ph.D. thesis arethreefold : (i) it presents a comprehensive reviewof the literature on dynamic vehicle routing ; (ii)it introduces flexible optimization frameworks thatcan cope with a wide variety of dynamic vehiclerouting problems ; (iii) it defines a new vehicle routingproblem with numerous applications.

Dans cette thèse, nous nous intéressons à l'étude des capacités de la méta heuristique d'optimisation par colonie de fourmis (Ant Colony Optimization - ACO) pour résoudre des problèmes d’optimisation combinatoire multi-objectif. Dans ce cadre, nous avons proposé une taxonomie des algorithmes ACO proposés dans la littérature pour résoudre des problèmes de ce type. Nous avons mené, par la suite, une étude expérimentale de différentes stratégies phéromonales pour le cas du problème du sac à dos multidimensionnel mono-objectif. Enfin,nous avons proposé un algorithme ACO générique pour résoudre des problèmes d'optimisation multi-objectif. Cet algorithme est paramétré par le nombre de colonies de fourmis et le nombre de structures de phéromone considérées. Il permet de tester et de comparer, dans un même cadre,plusieurs approches. Nous avons proposé six variantes de cet algorithme dont trois présentent de nouvelles approches et trois autres reprennent des approches existantes. Nous avons appliqué et comparé ces variantes au problème du sac à dos multidimensionnel multi-objectif / In this thesis, we investigate the capabilities of Ant Colony Optimization (ACO) metaheuristic to solve combinatorial and multi-objective optimization problems. First, we propose a taxonomy of ACO algorithms proposed in the literature to solve multi-objective problems. Then, we studydifferent pheromonal strategies for the case of mono-objective multidimensional knapsackproblem. We propose, finally, a generic ACO algorithm to solve multi-objective problems. Thisalgorithm is parameterised by the number of ant colonies and the number of pheromonestructures. This algorithm allows us to evaluate and compare new and existing approaches in thesame framework. We compare six variants of this generic algorithm on the multi-objectivemultidimensional knapsack problem

Dans les problèmes de localisation-routage classiques (LRP), il s'agit de combiner des décisions stratégiques liées aux choix des sites à ouvrir (centres de traitement) avec des décisions tactiques et opérationnelles liées à l'affectation des clients aux sites sélectionnés et a la confection des tournées associées. Cette thèse propose de nouveaux modèles de localisation-routage permettant de résoudre des problématiques issues de réseaux logistiques, devenus aujourd'hui de plus en plus complexes vu la nécessité de mutualisation de ressources pour intégrer des contraintes de développement durable et des prix de carburants qui semblent augmenter de manière irrémédiable. Plus précisément, trois aspects ont été intégrés pour généraliser les modèles LRP classiques de la littérature : 1) l'aspect pickup and delivery, 2) l'aspect multi-produits, et 3) la possibilité de visiter un ou plusieurs centres de traitement dans une tournée donnée. Nous avons étudié deux schémas logistiques, qui ont donné lieu à deux nouveaux modèles de localisation et de routage, le MPLRP-PD (LRP with multi-product and pickup and delivery), qui peut être vu comme une extension des problèmes de tournées de véhicules avec collecte et livraison, intégrant une décision tactique liée à la localisation des centres de traitement (noeud avec collecte et livraison) dans un réseau de distribution à un seul échelon, et le 2E-MPLRP-PD (Two-echelon LRP with multi-product and pickup and delivery) qui est une généralisation du LRP à deux échelons avec les contraintes citées plus-haut. Ces deux modèles ont été formalisés par des programmes linéaires en variables mixtes (MIP). Des techniques de résolution, basées sur des méthodes de type heuristique, clustering, métaheuristique, ont été proposées pour résoudre le MPLRP-PD et le 2E-MPLRP-PD. Les jeux d'essais de la littérature ont été généralisés pour tester et valider les algorithmes proposés / In the framework of Location-Routing Problem (LRP), the main idea is to combine strategic decisions related to the choice of processing centers with tactical and operational decisions related to the allocation of customers to selected processing centers and computing the associated routes. This thesis proposes a new location-routing model to solve problems which are coming from logistics networks, that became nowadays increasingly complex due to the need of resources sharing, in order to integrate the constraints of sustainable development and fuels price, which is increasing irreversibly. More precisely, three aspects have been integrated to generalize the classical LRP models already existed in the literature: 1) pickup and delivery aspect, 2) multi-product aspect, and 3) the possibility to use the processing centers as intermediate facilities in routes. We studied two logistics schemes gives us two new location-routing models: (i) MPLRP-PD (Multi-product LRP with pickup and delivery), which can be viewed as an extension of the vehicle routing problem with pick-up and delivery, including a tactical decision related to the location of processing centers (node with pick-up and delivery), and (ii) 2E-MPLRP-PD (Two-echelon multi-product LRP with pickup and delivery), which is a generalization of the two-echelon LRP. Both models were formalized by mixed integer linear programming (MIP). Solving techniques, based on heuristic methods, clustering approach and meta-heuristic techniques have been proposed to solve the MPLRP-PD and the 2E-MPLRP-PD. The benchmarks from the literature were generalized to test and to validate the proposed algorithms

Le volet applicatif de cette thèse porte sur l'agencement d'un logement destiné à une personne en situation de handicap. L'agencement désigne le choix de la position, de la forme et des dimensions des pièces, des portes et des couloirs. L'agencement est généralement élaboré par un architecte, dans le respect d'un nombre si élevé de contraintes qu'il lui est difficile de parvenir qu'il parvienne à toutes les satisfaire : il y a d'abord des contraintes architecturales évidentes : non recouvrement des pièces, largeur suffisante des couloirs, accessibilité à tout point du lieu à partir de tout autre point, nécessité de placer certaines pièces sur des arrivées ou évacuations … Il y a ensuite les contraintes imposées par le handicap : largeur accrue des couloirs (déplacement en fauteuil), nécessité d'assurer un effort quotidien minimum (lutte contre le vieillissement), limitation des escaliers (asthme sévère), éloignement d'une pièce des murs mitoyens (surdité) .... Et il y a finalement les souhaits exprimés par le futur occupant, par exemple minimiser certains trajets, maximiser l’éloignement entre deux pièces ou imposer l’orientation d’une pièce. D’un point de vue formel, notre travail a consisté à développer d'une part des modèles mathématiques et des méthodes algorithmiques capables de gérer ces contraintes et d'autre part des prototypes logiciels opérationnels. Les méthodes élaborées relèvent de deux approches : l'optimisation d'un agencement conçu par l'architecte et la synthèse d'un agencement sans suggestion initiale de l'architecte. La synthèse d'un plan a été abordée comme un problème de type « bin-packing » (réputé NP-difficile) avec des contraintes additionnelles : les objets à placer - les pièces - ont des tailles variables et ils sont soumis à des contraintes fonctionnelles. La méthode de résolution s'appuie sur un premier modèle mathématique, qui prend la forme d’un programme quadratique (linéarisé par la suite) en variables mixtes. Elle a été appliquée avec succès pour placer les pièces d'un logement, pour les dimensionner, pour déterminer les couloirs assurant une complète accessibilité au logement et pour prendre en compte certaines contraintes imposées par le handicap du futur occupant. Un deuxième modèle mathématique a été élaboré pour le placement des portes et une heuristique a enfin été développée pour affecter l'espace occupé par les couloirs non indispensables aux pièces avoisinantes. La totalité de cette démarche a été programmée dans un prototype logiciel pleinement opérationnel. Le deuxième ensemble de contributions concerne l'optimisation d'un agencement existant. Cette optimisation a été conçue comme un processus itératif enchaînant évaluation et modification (amélioration) d'un agencement. Il est décliné de quatre manières : une métaheuristique de type « recuit simulé » et trois méthodes de type « recherche locale », qui explorent l’espace des solutions en utilisant des voisinages spécialement définis. Cette approche a d'une part permis d’appréhender le caractère multicritère de cette problématique et a d'autre part exigé la mise en œuvre de nombreux algorithmes géométriques. Ces travaux sont implantés dans un deuxième prototype logiciel. Ce projet a nécessité la participation à de nombreuses manifestations au-delà du domaine de l’informatique, nationales et régionales, scientifiques et non-scientifiques, organisées par différents organismes politiques et associatifs travaillant sur la problématique du handicap et de l’accessibilité, afin de bien appréhender les attentes du monde scientifique et socioprofessionnel. Cette phase prospective a été concrétisée par la rédaction de nombreux rapports qui ont alimentés la bibliographie du mémoire de thèse / At an application level, this thesis deals with the layout of an accommodation intended for a disabled person. Determining the layout means choosing the position, shape and dimensions of rooms, doors and corridors. It is usually an architect's job but the complexity is such that it is very unlikely that he succeeds in optimally fulfilling all the constraints: first, there are architectural constraints: no room overlapping, sufficient width for the corridors, accessibility to and from any point, mandatory positioning of some rooms on some areas (e.g. water supply and outlet) … Then, there are constraints imposed by disabilities: enlarged corridors (wheelchairs), mandatory daily amount of efforts (fight against aging), reducing the number of steps (severe asthma), moving a room away from shared walls (deafness)... Finally, there are the wishes expressed by the future occupant, such as minimizing some journeys, maximizing the distance between two rooms or fixing a room's orientation. From a formal point of view, our work has consisted, firstly, in developing mathematical models and algorithmic methods to deal with all these constraints and, secondly, in realizing software prototypes applying these concepts. The tools we propose aim either at optimizing a layout previously designed by an architect or at synthesising a layout without any initial suggestions from the architect. Synthesis has been tackled as bin-packing-type problem (known to be NP-hard) but with additional constraints: the objects to be placed (the rooms) have variable sizes and they are submitted to functional constraints. The resolution is based on a first, initially quadratic and then linearized, mixed integer mathematical model. It has been successfully applied to position and dimension the rooms of an accommodation, to determine corridors allowing a full accessibility to all the rooms and to take into account a number of constraints coming from the disabilities of the future occupant. A second mathematical model has been formulated for the positioning of the doors and, finally, a heuristic method has been designed to assign the space used by useless corridors to adjacent rooms. The whole process has been embedded in a fully operational software. The second set of contributions is about the optimization of an existing layout. This task has been tackled through an iterative process, looping on evaluation and modification (improvement) of an accommodation. It has been implemented in four different ways: a metaheuristic (simulated annealing) and three local-search-type methods, which traverse the solution space by using specific definitions of the neighbourhood. This approach has firstly underlined the multicriteria feature of our problem and, secondly, has required the development of many computational geometry algorithms. All this work is integrated in another functional prototype software. To understand the expectations of the scientific, social and professional worlds, this project has implied to take part to various manifestations which were national or regional, in the computer science domain or in others, scientific or non-scientific, organised by various political or non-political organisations working in the field of disabilities and accessibility. This phase has resulted in many reports which have directly fed into the bibliography of this thesis.

L’objectif de ce projet de trois ans est de proposer des avancées conceptuelles et technologiques dans la résolution de problèmes d’ordonnancement du personnel. L’atteinte de cet objectif passe par la proposition de nouveaux algorithmes basés sur les métaheuristiques et leur implémentation sur les architectures de calcul haute performance. Ce projet s’inscrit en complémentarité du projet HORUS qui bénéficie d’une subvention ANR et qui réunit les expertises scientifiques de deux laboratoires universitaires spécialisés en optimisation et en calcul parallèle : l’équipe SysCom du laboratoire CReSTIC de l’URCA et l’équipe CaRO du laboratoire PRiSM de l’UVSQ. Les avancées technologiques proposées s’appuient également sur les moyens de calcul haute performance offerts par le Centre de Calcul Régional Champagne-Ardenne. / .Many academic and industrial optimization problems are multi-objective and have been of particular interest to researchers in recent years. These problems usually do not have a single optimal solution but a set of best trade-off solutions which form the so-called Pareto front in the objective space. In order to approximate the Pareto front, multi-objective evolutionary algorithms (MOEAs) have been largely investigated in the fields of continuous and combinatorial optimization. Contrary to some classical algorithms, MOEAs have the ability to provide a number of solutions in one single run and are less sensitive to the shape of the Pareto front.As they often require a high amount of computing resources to explore large portions of the search space and handle complex real-life constraints, MOEAs could greatly benefit from today's high-performance computing architectures. Although significant progress has been made in recent years in the design and improvement of parallel models for evolutionary algorithms, most of these models have limited scalability and ability to solve various problems. In fact, solving multi-objective combinatorial optimization problems efficiently on a large number of processors remains a challenge today.This thesis aims to propose an island model which is based on objective space division. The main features of the proposed model are the following (i) An organizer has a global view of the current search via a global archive (ii) Asynchronous cooperation between islands, especially for the exchange of local archives with the organizer to limit model overheads (iii)Control islands to guide the exploration of the search space and improve diversity (iv) A periodic use of a specific local search procedure to improve convergence. Extensive experiments have been conducted to evaluate the performance of the approach and more particularly of each component in the resolution of two classical combinatorial problems, the travelling salesman problem and quadratic assignment problem. Extensibility and quality of the solutions are analyzed compared to state-of-the-art parallel models.

Les problèmes de découpe et de placement sont des problèmes combinatoires. Ils sont classes dans la catégorie des problèmes NP-Complets et admettent de nombreuses applications en industrie, en systèmes multiprocesseurs. Nous proposons dans cette thèse, plusieurs méthodes de résolution exactes et approchées, séquentielles et parallèles du problème de découpe et de placement à deux dimensions.

Le polyèdre associé à un problème d'optimisation combinatoire est l'enveloppe convexe des (vecteurs d'incidence des) solutions réalisables de ce problème. De nombreux problèmes d'optimisation combinatoire se formulent comme une maximisation de fonctions linéaires sur les polyèdres qui leurs sont associés. La description du polyèdre par un système d'inéquations linéaires est intimement liée à la résolution du problème correspondant, par le biais de la programmation linéaire. Afin de déterminer un tel système, une approche classique consiste à décomposer le problème en sous-problèmes tels que les polyèdres associés soient connus ; une composition ultérieure de ces derniers conduit à une description du polyèdre associé au problème considéré. L'objet principal de cette thèse est l'étude de la composition des polyèdres. Dans un premier temps, une approche de composition, basée sur la programmation dynamique et les méthodes de projection polyédrale, est étudiée et des résultats généraux sont proposés, permettant ainsi d'unifier des recherches existantes dans ce domaine. Cette approche est, ensuite, appliquée à la composition de polyèdres associés au problème du voyageur de commerce. En seconde partie, considérant le problème du stable, des opérations sur les graphes (composition par identification de sous-graphes de deux graphes donnés, adjonction d'une nouvelle arête) sont traitées. Des résultats polyédraux sont donc donnés, et des conséquences concernant la perfection et la h-perfection des graphes sont montrés