L’hospitalisation hors les murs est une expression générique qui désigne toutes les formes de structures accueillant des patients pour une prise en charge longue et régulière nécessitant des soins complexes. Les structures hors les murs doivent assurer une prise en charge sure et d’une qualité au moins identique à celle fourni par l’hôpital, tout en contribuant à la diminution des coûts de la prise en charge. D’où la nécessité d’une gestion efficiente des activités des soignants et des ressources humaines. Dans ce travail de recherche, l’intérêt est porté à la problématique générale de gestion des activités de soins en Hospitalisation À Domicile (HAD). Il s’agit d’une problématique très complexe, car elle vise à résoudre simultanément des sous-problèmes réputés NP – difficiles. Dans cette thèse, nous étudions cette problématique au niveau opérationnel de la conception des tournées des soignants. La démarche adoptée pour ce travail de recherche se base sur trois étapes essentielles. Nous commençons par une étude sur le système de santé et les structures d’HAD en France, tout en mettant en claire les facteurs essentiels de leur fonctionnement. Cette étape sera clôturée par une étude du fonctionnement des systèmes d’HAD dans la région Rhône-Alpes, en se basant sur les retours du projet régional Organisation des Soins A Domicile (OSAD). La deuxième étape concerne les problématiques de gestion et la planification des activités de soins et des ressources humaines en HAD. Ce travail conduira à l’élaboration d’une classification des problématiques de la gestion des activités en HAD. En se basant sur la classification identifiée précédemment, nous définissons, les axes de complexité de ce problème : (i) le nombre d’activités de soins par soignant, (ii) la dépendance temporelle entre les activités des patients et (iii) la dimension environnementale. Ensuite, nous proposons un ensemble d’approches et d’outils pour la résolution de la problématique des tournées d’infirmiers en HAD, sous différentes contraintes liées à la réalisation des soins et en particulier aux contraintes de dépendances temporelles. Pour répondre à l’ensemble des contraintes et exigences de performance, nous développons une heuristique originale permettant une résolution en un temps compatible avec les contraintes de mise en oeuvre, pour des instances de grande taille / Home care services, is a generic term that gathers different kind of care: provider, agency, and organization. In France, the most important part of the in-home care is performed by HAD (Hospitalization At Home). The HAD concept is defined by decree. The HAD has to provide only complex care in the patient’s home for 24 motives. HAD are hospitals and have to ensure continuity of care for their patients. Our researches focus on the operation management for home care services. This problem is complex; it needs to solve sub-problems known to be NP - hard. In this work, this problem is studied at the operational level in design of tours of caregivers. The approach followed is based on three essential stages. Firstly, we study the health system and the home care structures in France. At the end of this step, we summarize the outcome obtained of the regional project Organization of Home Care Service (Organisation des Soins A Domicile : OSAD) on the home care structures in the Rhône-Alpes region (France). The second step gathers scientific literature about home care management, particularly about problems of management and planning of activities and human resources in the home care structures. This work leads to design a classification in order to management activities issues in home care structures. Based on this classification, we define three complexity axes of the operation management in home care problem, i.e. (i) the rate of the number of care activities per caregiver, (ii) dependency level between the patients’ activities and (iii) the environmental level. In the third stage, we suggest a set of mathematical approaches and tools for solving the problem of caregivers’ tours. Two MIPL model are developed, the first is based on a Traveling Salesman Problem (TSP) with coordination between the caregivers and the second on RCPSP (Ressources Constrained Project Scheduling Problem). Because the both previous models are time consuming, we suggest an original heuristic to solve the TSP coordinated problem, to resolve the care management activities in home care services

Les problématiques de sécurité sont aujourd’hui un facteur différentiateur clé dans le secteur aéronautique. Bien que certains systèmes d’assistance aux hélicoptères existent et qu’une partie de la connaissance associée aux situations d’urgence ait pu être identifiée, reste que les travaux antérieurs se limitent pour la plupart à une autonomie de bas niveau. Ainsi la génération d’un plan de vol sous fortes contraintes de temps représente à ce jour une voie d’exploration nouvelle, et un défi technologique essentiel pour l’hélicoptère de demain. A cet égard, AIRBUS HELICOPTERS accorde un fort intérêt à la conception d’un système décisionnel capable de générer des plans de vols en temps réel. L’enjeu de l’intelligence répartie au travers de systèmes décisionnels distribués constitue un axe de recherche fort, et un des contributeurs clés pour un positionnement leader d’AIRBUS HELICOPTERS sur la thématique sécurité. Aujourd’hui, l’étude des systèmes décisionnels embarqués dans les engins volants constitue un défi majeur pour divers groupes de travail académiques et industriels. En effet, la résolution de ce défi fait appel généralement à différentes compétences afin de maîtriser plusieurs aspects du système recouvrant les domaines d’acquisition, d’analyse et de traitement de données. Et ce dans le but de prendre des décisions en temps-réel en prenant en considération plusieurs paramètres contextuels et environnementaux. Les défis scientifiques à contourner dans la présente thèse s’articulent sur deux axes majeurs. Dans un premier temps, il faut proposer une approche complète pour une planification en temps réel d’un plan de vol d’hélicoptères. Permettant à cette dernière de faire face à d’éventuels événements dynamiques tel que l’apparition de nouveaux obstacles ou un changement de mission. Ensuite, nous nous intéressons à une implantation embarquée de la solution proposée sur une architecture hétérogène haute performance. / Security issues are today a key-differentiator in the aviation sector. Indeed, it comes to ensure the safety of expensive equipments but above all to save human lives. In this context, it is necessary to offer an important level of autonomy to helicopters. Although some studies have been carried out in this area, the dynamic generation of a sequence of maneuvers under hard time constraints in an unknown environment still represents a major challenge for many academic and industrial working groups. AIRBUS HELICOPTERS as a leader of helicopters manufacturing, looks forward to integrate an assistance system for mission re-planning in the next generation of aircrafts.The work conducted in this PhD thesis falls within a collaboration between AIRBUS HELICOPTERS and UNIVERSITE DE VALENCIENNES ET DU HAINAUTCAMBRESIS. One of the main purposes of this work is efficient flight plan generation. Indeed, for intelligent assistant systems we need to generate a new path planning inorder to face emergency events such as an equipment failure or adverse weather conditions. The second major objective of this work is the deployment of mission planning tasks onto a high performance architecture CPU/FPGA in order to meet real-time requirements for the dynamic optimization process. In the present work, we first studied efficient flight plan generation. Indeed, we developed efficient and effective algorithms for helicopter path planning. Then, in order to obtain a real-time system, we resolved the problem of scheduling optimization on a heterogeneous architecture CPU / FPGA by proposing several scheduling methods including exact approaches and heuristics.

Lorsque la vue, qui est un important moyen de communication, est altérée, alors l'acquisition de l'information s'en trouve modifiée, dégradée ou limitée. A l'ère du monde numérique, le Web regorge d'informations réparties sur différents sites et mises en forme par les développeurs et designers. De nombreuses pathologies visuelles peuvent entraîner des difficultés dans l'accès à ces informations. Au-delà même de ces informations, l'accès aux outils et services est lui aussi limité. Des difficultés dans la perception des couleurs, des taches dans le champ visuel ou un champ visuel réduit sont tout autant de sources de difficultés. Chaque personne a une vision qui lui est propre. Chez les personnes qui ont une basse vision, les pathologies donnent des évolutions spécifiques chez chacune d'entre elles. De plus les méthodes de compensation acquises sont différentes d'une personne à l'autre. Des outils d'assistance existent depuis de nombreuses années et tentent de répondre aux besoins des personnes ayant une basse vision en proposant des adaptations visuelles. Les principales limites de ces outils résident notamment dans le fait qu'ils ne sont pas en capacité de prendre en compte les besoins très spécifiques de chaque personne. Ces travaux de recherche se concentrent donc autour de l'analyse des besoins réels des utilisateurs et de l'élaboration d'une nouvelle approche qui se base sur les préférences personnelles de l'utilisateur. L'objectif final est d'automatiser la transformation des pages Web en fonction des préférences propres à un utilisateur pendant qu'il navigue sur le Web. Divers algorithmes ont été utilisés, notamment des algorithmes évolutionnaires, afin de réaliser des compromis entre les préférences de l'utilisateur et l'apparence originale de la page Web. La thèse développe de manière approfondie les principaux problèmes touchant les personnes en situation de basse vision et des éléments sur les modèles de couleurs et de contrastes. Puis elle présente un langage de modélisation des préférences basé sur la logique, une modélisation du problème comme un problème d'optimisation, des algorithmes de résolution, un démonstrateur, et des expérimentations sur des pages Web réelles. / When the sight, which is the main communication way, is altered, then the information acquisition process is also modified, degraded or limited. In today's digital world, the Web is a wealth of information organized by designers and developers and available on different Websites. Many visual pathologies can lead to difficulties in accessing this information. Beyond this information, the access to the different tools and services is also affected. Difficulties in color perception, cloud-like white patches or dark areas in a visual field, or a reduced visual field are all sources of difficulties. Each person has a particular vision. Several persons with the same pathology may even have different visions. Several assistive tools have been proposed that apply visual adaptation, trying to meet the needs of people with low vision. Main limits of these tools are mainly the unability of taking into account the very specific needs of each person. These research works are focused on the real user's needs analysis and on making a new approach based on the personal user's preferences. The final target consists in automatizing the Web page transformation according to the specific preferences of a particular user. This transformation occurs along the navigation from page to page. Different algorithms have been used, especially evolutionary algorithms, in order to make tradeoffs between the user's preferences and the original appearance of the page. The thesis further develops main problems encountered by people with low vision and some notions on color models and contrast relations. After that, we present a preference modeling language based on logics, a modeling of the problem as an optimization problem, some resolution algorithms, a tool and experiments on several real Web pages.

Les activités de transport et de gestion des stocks ont un impact important les unes sur les autres. Assurer un niveau de stock idéal peut demander des livraisons fréquentes, ce qui entraîne des coûts logistiques élevés. Pour optimiser les compromis entre les coûts de stock et de transport, des systèmes VMI (Vendor Managed Inventory) ont été développés pour gérer ensemble les opérations de stock et de transport. Pour un ensemble de clients ayant des demandes sur un horizon de temps, le problème de détermination des tournées et des quantités à livrer avec un coût minimum de gestion de stock et de transport est connu sous le nom de Inventory Routing Problem (IRP). Les systèmes à deux échelons ont également été étudiés pour améliorer le flux de véhicules dans les zones urbaines. étant donné que des nouvelles politiques de gestion sont apparues, dans le but de limiter le trafic des gros véhicules et leur vitesse dans les centres urbains, des Centres de Distribution (DC) sont mis en place pour coordonner les flux de marchandises à l'intérieur et à l'extérieur des zones urbaines. Les produits sont donc livrés aux clients par les fournisseurs via les DC.Nous proposons de combiner un système à deux échelons avec le IRP. Nous introduisons un Operational Two-Echelon Inventory Routing Problem (O-2E-IRP), ce qui est une nouvelle extension du IRP à notre connaissance. Dans le O-2E-IRP proposé, les clients doivent être servis par un fournisseur strictement via des DC et les tournées doivent être définis dans les deux échelons sur un horizon de temps donné. Trois politiques de réapprovisionnement et de configurations de routage différentes sont modélisées pour ce problème. Nous développons deux formulations mathématiques, ainsi qu'un algorithme Branch-and-Cut (B&C) combiné à une matheuristique pour résoudre le problème. De plus, nous analysons plusieurs inégalités valides disponibles pour le IRP et nous introduisons de nouvelles inégalités valides inhérentes au IRP à deux échelons. Des expériences de calcul approfondies ont été effectuées sur un ensemble d'instances générées de manière aléatoire. Les résultats obtenus montrent que les performances des méthodes sont liées à la politique de stock et à la configuration de routage.Dans le contexte d'un IRP à deux échelons, deux décisions tactiques importantes doivent être prises en plus des décisions de livraison de routage et de quantité de livraison: à partir de quel DC sera fourni chaque client et en utilisant quels véhicules ? Répondre à ces questions est extrêmement difficile car cela implique de pouvoir minimiser les coûts opérationnels d'un système de livraison VMI à deux échelons à long-terme et avec des demandes incertaines. Pour faire face à cela, nous présentons le Tactical Two-Echelon Inventory Routing Problem (T-2E-IRP) qui optimise les décisions en fonction d'un horizon à long-terme et en tenant compte des demandes stochastiques. Trois politiques de gestion des stocks sont modélisées et appliquées à un ou aux deux échelons. Nous développons une approche de simulation pour résoudre le T-2E-IRP sur un horizon de temps à long-terme. Nous proposons quatre formulations et deux algorithmes B&C pour définir l'affectation des clients et des véhicules aux DC en fonction d'un horizon de temps court. Ensuite, nous évaluons ces décisions d'affectation via un outil de simulation qui résout un sous-problème du T-2E-IRP, qui consiste en les décisions de livraisons du fournisseur aux DC et des DC aux clients, sur un horizon glissant. De nombreuses expériences sont effectuées pour un ensemble d'instances générées aléatoirement. L'impact de plusieurs paramètres utilisés pour déterminer l'affectation des clients et des véhicules aux DC sur le coût total est analysé. Basé sur des expériences, nous définissons la combinaison de paramètres qui fournit généralement les meilleurs résultats sur les instances générées. / Transport and inventory management activities have a great impact on each other. Ensuring an ideal inventory level can require frequent deliveries, leading to high logistics costs. To optimize the trade-offs between inventory and transportation costs, VMI (Vendor Managed Inventory) systems have been developed to manage inventory and transportation operations together. Given a set of customers with demands over a time horizon, the problem of determining routes and delivery quantities at a minimum inventory holding and transportation costs is known as Inventory Routing Problem (IRP). Two-echelon systems have also been studied to improve the freight vehicle flow inside urban areas. As new management policies have emerged, with the goal of limiting the traffic of large vehicles and their speed in urban centers, Distribution Centers (DC) are introduced to coordinate freight flows inside and outside the urban areas. Products are then delivered from the suppliers to the customers through the DC.We propose to combine a two-echelon system with the IRP. We introduce an Operational Two-Echelon Inventory Routing Problem (O-2E-IRP), which is a new extension of the IRP to the best of our knowledge. On the proposed O-2E-IRP, the customers must be served by a supplier strictly through DC and routes must be defined in both echelons over a given time horizon. Three different replenishment policies and routing configurations are modeled for this problem. We develop two mathematical formulations, and a Branch-and-Cut (B&C) algorithm combined with a matheuristic to solve the problem. In addition, we analyze several valid inequalities available for IRP, and we introduce new ones inherent to the IRP within two echelons. Extensive computational experiments have been carried out on a set of randomly generated instances. The obtained results show that the performance of the methods is related to the inventory policy and routing configuration.In the context of a two-echelon IRP, two important tactical decisions have to be taken in addition to route and quantity delivery decisions: from which DC will be supplied each customer and using which vehicles? Answering these questions is extremely difficult as it implies being able to minimize operational costs for a two-echelon VMI delivery system on long-term and with uncertain demands. In order to deal with this, we introduce the Tactical Two-Echelon Inventory Routing Problem (T-2E-IRP) that optimizes the decisions based on a long-term horizon and considering stochastic demands. Three inventory management policies are modeled and applied at one or both echelons. We develop a simulation approach to solve the T-2E-IRP on a long-term time horizon. We propose four formulations and two B&C algorithms to define the assignment of customers and vehicles to the DC based on a short time horizon. Then, we evaluate these assignment decisions through a simulation tool that solves a subproblem of the T-2E-IRP, which consists of the decisions of deliveries from the supplier to the DC and from the DC to the customers, on a rolling-horizon framework. Extensive computational experiments are performed for a set of randomly generated instances. The impact of several parameters used to determine the assignment of customers and vehicles to DC on the total cost is analyzed. Based on the experiments, we define the combination of parameters that generally provides the best results on the generated instances.

Avec l’augmentation progressive de la population dans les grandes villes, comme Paris, nous prévoyons d’ici 2050 une augmentation de 50% du trafic routier. En considérant les embouteillages et la pollution que cette augmentation va générer, on voit clairement la nécessité de nouveaux système de mobilité plus durables, comme le covoiturage, ou plus généralement toute la mobilité partagée. En parlant de mobilité partagée, ce n’est pas seulement le partage de trajets de personnes qui ont le même itinéraire au même temps, elle inclut aussi les marchandises.Cette thèse aborde le défi de la synchronisation des flux de passagers et de marchandises dans les systèmes de mobilité urbaine et elle vis à développer des méthodes d’optimisation pour que cette synchronisation dans la mobilité partagée soit faisable. Plus précisément, elle aborde les questions de recherche suivantes:*Q1: Quelles sont les variantes des systèmes de mobilité partagée et comment les optimiser?*Q2: Comment synchroniser les déplacements de personnes et quels gains cette synchronisation peut-elle générer?*Q3: Comment combiner les flux de passagers et de fret et quels sont les avantages attendus?*Q4: Quels sont les effets de l'incertitude sur la planification et l'exploitation de systèmes de mobilité partagée?Dans un premier temps, nous étudions les différentes variantes des systèmes de mobilité partagée et nous les classifions en fonction de leurs modèles, caractéristiques, approches de résolution et contexte d'application. En se basant sur cette revue de littérature, nous identifions deux problèmes de mobilité partagés, que nous considérons en détails dans cette thèse et nous développons des méthodes d'optimisation pour les résoudre.Pour synchroniser les flux de passagers, nous étudions un modèle de covoiturage en utilisant les véhicules autonomes, personnels et partagés, et des points de rencontre où la synchronisation entre passagers peut avoir lieu. Pour cela, une méthode heuristique en deux phases est proposée et une étude de cas sur la ville de New York est présentée.Ensuite, nous développons un modèle d’optimisation qui combine les flux de passagers et de marchandises dans une région urbaine. Le but de ce modèle est d’utiliser les capacités disponibles sur une ligne de transport fixe pour transporter les passagers et des robots transportant des petits colis à leurs destinations finales en considérant que la demande de passagers est stochastique. Les résultats obtenus montrent que les solutions proposées par ces deux modèles peuvent conduire à une meilleure utilisation des systèmes de transport dans les régions urbaines. / The rise of research into shared mobility systems reflects emerging challenges, such as rising urbanization rates, traffic congestion, oil prices and environmental concerns. The operations research community has turned towards more sharable and sustainable systems of transportation. Although shared mobility comes with many benefits, it has some challenges that are restricting its widespread adoption. More research is thus needed towards developing new shared mobility systems so that a better use of the available transportation assets can be obtained.This thesis aims at developing efficient models and optimization approaches for synchronizing people and freight flows in an urban environment. As such, the following research questions are addressed throughout the thesis:*Q1: What are the variants of shared mobility systems and how to optimize them?*Q2: How can people trips be synchronized and what gains can this synchronization yields?*Q3: How can people and freight flows be combined and what are the intended benefits?*Q4: What impacts uncertainty can have on planning and operating shared mobility systems?First, we review different variants of the shared mobility problem where either (i) travelers share their rides, or (ii) the transportation of passengers and freight is combined. We then classify these variants according to their models, solution approaches and application context and We provide a comprehensive overview of the recently published papers and case studies. Based on this review, we identify two shared mobility problems, which we study further in this thesis.Second, we study a ridesharing problem where individually-owned and on-demand autonomous vehicles (AVs) are used for transporting passengers and a set of meeting points is used for synchronizing their trips. We develop a two-phase method (a pre-processing algorithm and a matching optimization problem) for assessing the sharing potential of different AV ownership models, and we evaluate them on a case study for New York City.Then, we present a model that integrates freight deliveries to a scheduled line for people transportation where passengers demand, and thus the available capacity for transporting freight, is assumed to be stochastic. We model this problem as a two-stage stochastic problem and we provide a MIP formulation and a sample average approximation (SAA) method along with an Adaptive Large Neighborhood Search (ALNS) algorithm to solve it. We then analyze the proposed approach as well as the impacts of stochastic passengers demand on such integrated system on a computational study.Finally, we summarize the key findings, highlight the main challenges facing shared mobility systems, and suggest potential directions for future research.

Dans cette thèse nous nous sommes intéressés à l’extension du problème job-shop en ajoutant la contrainte du transport des jobs entre les différentes machines. Dans cette étude nous avons retenu l’existence de deux types de robots, les robots de capacité de chargement unitaire (capacité=1 veut dire qu’un robot ne peut transporter qu’un seul job à la fois) et les robots de capacité de chargement non unitaire (capacité>1 veut dire qu’un robot peut transporter plusieurs job à la fois). Nous avons traité cette extension en deux étapes. Ainsi, la première étape est consacrée au problème du job-shop avec plusieurs robots de capacité de chargement unitaire et en seconde étape en ajoutant la capacité de chargement non unitaire aux robots. Pour les deux problèmes étudiés nous avons proposé :• Une modélisation linéaire ;• Une modélisation sous forme de graphe disjonctif ;• Plusieurs heuristiques de construction de solutions ;• Plusieurs recherches locales qui améliorent les solutions obtenues ;• Utilisation des algorithmes génétiques / mémétiques comme schéma global d’optimisation ;• De nouveaux benchmarks, des résultats de test de nos approches sur nos benchmarks et ceux de la littérature et ces résultats sont commentés et comparés à ceux de la littérature. Les résultats obtenus montrent la pertinence de notre modélisation ainsi que sa qualité. / In this thesis we are interested in the extension of the job-shop problem by adding the constraint of transport of jobs between different machines. In this study we used two types of robots, robots with unary loading capacity (capacity =1 means that each robot can carry only one job at a time,) and robots with non unary loading capacities (robot with capacity >1 can carry more than one job at time). Thus, the first step is devoted to the problem of job-shop with several robots with unary loading capacity. In the second step we extend the problem by adding the non-unary loading capacities to the robots. For both problems studied we have proposed :• A linear modeling ;• A Disjunctive graph Model ;• Several constructive heuristics ;• Several local searches methods that improve the obtained solutions ;• Use of genetic / memetic algorithms as a global optimization schema ;• New benchmarks, test results of our approaches on our benchmarks and those present in the literature and these results are commented and compared with those of literature. The results show the relevance of our model and its quality.

Les décisions de localisation sont souvent soumises à des aspects dynamiques comme des changements dans la demande des clients. Pour y répondre, la solution consiste à considérer une flexibilité accrue concernant l’emplacement et la capacité des installations. Même lorsque la demande est prévisible, trouver le planning optimal pour le déploiement et l'ajustement dynamique des capacités reste un défi. Dans cette thèse, nous nous concentrons sur des problèmes de localisation avec périodes multiples, et permettant l'ajustement dynamique des capacités, en particulier ceux avec des structures de coûts complexes. Nous étudions ces problèmes sous différents points de vue de recherche opérationnelle, en présentant et en comparant plusieurs modèles de programmation linéaire en nombres entiers (PLNE), l'évaluation de leur utilisation dans la pratique et en développant des algorithmes de résolution efficaces. Cette thèse est divisée en quatre parties. Tout d’abord, nous présentons le contexte industriel à l’origine de nos travaux: une compagnie forestière qui a besoin de localiser des campements pour accueillir les travailleurs forestiers. Nous présentons un modèle PLNE permettant la construction de nouveaux campements, l’extension, le déplacement et la fermeture temporaire partielle des campements existants. Ce modèle utilise des contraintes de capacité particulières, ainsi qu’une structure de coût à économie d’échelle sur plusieurs niveaux. L'utilité du modèle est évaluée par deux études de cas. La deuxième partie introduit le problème dynamique de localisation avec des capacités modulaires généralisées. Le modèle généralise plusieurs problèmes dynamiques de localisation et fournit de meilleures bornes de la relaxation linéaire que leurs formulations spécialisées. Le modèle peut résoudre des problèmes de localisation où les coûts pour les changements de capacité sont définis pour toutes les paires de niveaux de capacité, comme c'est le cas dans le problème industriel mentionnée ci-dessus. Il est appliqué à trois cas particuliers: l'expansion et la réduction des capacités, la fermeture temporaire des installations, et la combinaison des deux. Nous démontrons des relations de dominance entre notre formulation et les modèles existants pour les cas particuliers. Des expériences de calcul sur un grand nombre d’instances générées aléatoirement jusqu’à 100 installations et 1000 clients, montrent que notre modèle peut obtenir des solutions optimales plus rapidement que les formulations spécialisées existantes. Compte tenu de la complexité des modèles précédents pour les grandes instances, la troisième partie de la thèse propose des heuristiques lagrangiennes. Basées sur les méthodes du sous-gradient et des faisceaux, elles trouvent des solutions de bonne qualité même pour les instances de grande taille comportant jusqu’à 250 installations et 1000 clients. Nous améliorons ensuite la qualité de la solution obtenue en résolvent un modèle PLNE restreint qui tire parti des informations recueillies lors de la résolution du dual lagrangien. Les résultats des calculs montrent que les heuristiques donnent rapidement des solutions de bonne qualité, même pour les instances où les solveurs génériques ne trouvent pas de solutions réalisables. Finalement, nous adaptons les heuristiques précédentes pour résoudre le problème industriel. Deux relaxations différentes sont proposées et comparées. Des extensions des concepts précédents sont présentées afin d'assurer une résolution fiable en un temps raisonnable. / Location decisions are frequently subject to dynamic aspects such as changes in customer demand. Often, flexibility regarding the geographic location of facilities, as well as their capacities, is the only solution to such issues. Even when demand can be forecast, finding the optimal schedule for the deployment and dynamic adjustment of capacities remains a challenge. In this thesis, we focus on multi-period facility location problems that allow for dynamic capacity adjustment, in particular those with complex cost structures. We investigate such problems from different Operations Research perspectives, presenting and comparing several mixed-integer programming (MIP) models, assessing their use in practice and developing efficient solution algorithms. The thesis is divided into four parts. We first motivate our research by an industrial application, in which a logging company needs to locate camps to host the workers involved in forestry operations. We present a MIP model that allows for the construction of additional camps, the expansion and relocation of existing ones, as well as partial closing and reopening of facilities. The model uses particular capacity constraints that involve integer rounding on the left hand side. Economies of scale are considered on several levels of the cost structure. The usefulness of the model is assessed by two case studies. The second part introduces the Dynamic Facility Location Problem with Generalized Modular Capacities (DFLPG). The model generalizes existing formulations for several dynamic facility location problems and provides stronger linear programming relaxations than the specialized formulations. The model can address facility location problems where the costs for capacity changes are defined for all pairs of capacity levels, as it is the case in the previously introduced industrial problem. It is applied to three special cases: capacity expansion and reduction, temporary facility closing and reopening, and the combination of both. We prove dominance relationships between our formulation and existing models for the special cases. Computational experiments on a large set of randomly generated instances with up to 100 facility locations and 1000 customers show that our model can obtain optimal solutions in shorter computing times than the existing specialized formulations. Given the complexity of such models for large instances, the third part of the thesis proposes efficient Lagrangian heuristics. Based on subgradient and bundle methods, good quality solutions are found even for large-scale instances with up to 250 facility locations and 1000 customers. To improve the final solution quality, a restricted model is solved based on the information collected through the solution of the Lagrangian dual. Computational results show that the Lagrangian based heuristics provide highly reliable results, producing good quality solutions in short computing times even for instances where generic solvers do not find feasible solutions. Finally, we adapt the Lagrangian heuristics to solve the industrial application. Two different relaxations are proposed and compared. Extensions of the previous concepts are presented to ensure a reliable solution of the problem, providing high quality solutions in reasonable computing times.

L’objectif général de cette thèse de doctorat est de mieux comprendre comment le public interprète les nouvelles scientifiques portant sur la génétique humaine, plus précisément les nouvelles portant sur la génétique des comportements et celles portant sur la génétique des groupes raciaux. L’ouvrage prend la forme d’une thèse par article. Le Chapitre 1 introduit le lecteur aux buts et aux pratiques de la vulgarisation scientifique, présente un sommaire de la recherche sur les effets des médias, résume les principaux travaux produits par le champ de la génopolitique, et définit la structure des croyances du public à l’égard de l’influence de la génétique sur les traits humains. Le Chapitre 2 présente les fondements de la méthode expérimentale, il en explique les atouts et il offre des exemples de différents types de devis expérimentaux utilisés en science politique. Toutes les recherches produites dans cette thèse reposent au moins en partie sur cette méthode. Le Chapitre 3 présente les résultats d’une expérience de sondage qui vise à mesurer l’effet de la lecture d’une nouvelle à propos de la recherche en génétique des comportements sur des participants. L’étude démontre que le public interprète la nouvelle avec maladresse et tend à généraliser l’influence de la génétique à d’autres traits humains qui n’y sont pas mentionnés. J’avance l’hypothèse qu’un raccourci psychologique amplement documenté puisse expliquer cette réaction : l’heuristique de l’ancrage et de l’ajustement. Le Chapitre 4 présente lui aussi les résultats d’une expérience de sondage. L’étude consiste à manipuler certaines informations du contenu d’une nouvelle sur la génopolitique de manière à vérifier si certains éléments sont particulièrement susceptibles de mener à la généralisation hâtive mise en évidence dans le Chapitre 3. Les analyses suggèrent que cette généralisation est amplifiée lorsque la nouvelle présente de hauts niveaux d’héritabilité tirés d’études de jumeaux, ainsi que lorsqu’elle présente des travaux de génétique des populations visant à étudier l’origine des différences géographiques. Ce chapitre présente des recommandations à l’égard des journalistes scientifiques. Le Chapitre 5 s’intéresse à un aspect différent de la génétique humaine : celui de la génétique des races. L’objectif de cette recherche est de comprendre comment le public réagit aux travaux qui invalident l’idée selon laquelle les humains sont divisés en différentes races génétiquement distinctes. Les analyses de données transversales ainsi que les résultats d’une expérience de sondage convergent et indiquent que les conservateurs et les libéraux réagissent de manière diamétralement opposée à cette information. D’un côté, les libéraux acceptent le constat scientifique et réduisent leur impression que la génétique explique en partie les inégalités sociales; de l’autre, les conservateurs rejettent l’argument avec une intensité si forte que le rôle qu’ils attribuent aux différences génétiques s’en voit bonifié. Ces résultats sont interprétés à partir de la théorie du raisonnement motivé. Enfin, le Chapitre 6 résume les principaux constats, met en évidence les contributions que ma thèse apporte à la science politique et à la communication scientifique, et présente quelques pistes pour la recherche future. / The main objective of this doctoral thesis is to improve our understanding of how the public interprets scientific news about human genetics, specifically, behavioral genetics and the genetic underpinnings of racial groups. The core of the dissertation is a collection of three research articles and one book chapter. Chapter 1 introduces the readers to the goals and practices of science journalism, presents a summary of the literature on media effects, summarizes research on genopolitics, and discusses findings in public opinion on how people understand genetic influence on human characteristics. Chapter 2 presents the rationale behind the experimental method, explains its pros and cons, and provides examples of how different types of research designs have been used in political science. All the empirical evidence presented in this dissertation rests at least in part on experiments. Chapter 3 presents the results of a survey experiment that aims to measure the effects on individuals of reading a news article about behavioral genetics research. The study suggests that the public has difficulty in making sense of such research findings. The results show that participants tend to generalize the conclusions of one particular genetic study to other characteristics not mentioned by the study. I hypothesize that these results can be explained by a well-known and widely documented psychological process: the use of anchoring and adjustment heuristics. Chapter 4 presents the results of a second survey experiment. This experiment manipulates the content of a news article about behavioral genetics. The purpose of the manipulation is to test whether particular aspects of article’s message are more likely than others to cause the hasty generalizations revealed in Chapter 3. The findings show that the tendency to generalization is greater when the news presents high heritability estimates derived from twin studies or insights from research using population genetics methods to account for aggregate geographic difference. Based on these findings, the chapter develops recommendations for science journalists interested in covering behavioral genetics. Chapter 5 focuses on a different field of human genetic research, namely, that investigating the genetic bases of racial differences. The chapter’s aim is to improve our understanding of how the public reacts when exposed to scientific claims arguing against the idea that that human beings belong to different, genetically distinct races. Both cross sectional survey data and experimental data suggest that conservatives and liberals react to this information in opposing ways. Liberals tend to accept such arguments and temper their beliefs that genetic differences account for racial inequalities. By contrast, conservatives reject the arguments so strongly that exposure to them actually strengthens these citizens’ beliefs that genetics explain a proportion of racial inequality. These results are interpreted from the perspective of motivated reasoning theory. Finally, Chapter 6 summarizes the main findings of the doctoral dissertation, highlights its contribution to the discipline of political science and the field of science communication, and suggests directions for future research.

La distance de Kendall-τ compte le nombre de paires en désaccord entre deux permuta- tions. La distance d’une permutation à un ensemble est simplement la somme des dis- tances entre cette permutation et les permutations de l’ensemble. À partir d’un ensemble donné de permutations, notre but est de trouver la permutation, appelée médiane, qui minimise cette distance à l’ensemble. Le problème de la médiane de permutations sous la distance de Kendall-τ, trouve son application en bio-informatique, en science politique, en télécommunication et en optimisation. Ce problème d’apparence simple est prouvé difficile à résoudre. Dans ce mémoire, nous présentons plusieurs approches pour résoudre le problème, pour trouver une bonne solution approximative, pour le séparer en classes caractéristiques, pour mieux com- prendre sa compléxité, pour réduire l’espace de recheche et pour accélérer les calculs. Nous présentons aussi, vers la fin du mémoire, une généralisation de ce problème et nous l’étudions avec ces mêmes approches. La majorité du travail de ce mémoire se situe dans les trois articles qui le composent et est complémenté par deux chapitres servant à les lier. / The Kendall-τ distance counts the number of pairwise disagreements between two permutations. The distance between a permutation and a set is simply the sum of the distances between the considered permutation and the permutations of the set. Given a set of permutations, we want to find the permutation, called median, that minimise that distance to the set. The problem of finding a median of permutations under the Kendall-τ distance, finds applications in bioinformatics, political science, telecommunications and optimization. This simple appearing problem is proven difficult to solve. In this master thesis, we present a few approaches to solve the problem, to find a good approximate solution, to separate it into caracteristic classes, to deepen our understanding of its complexity, to reduce the search space and to accelerate calculations. We also present, at the end of this thesis, a generalization of this problem and we study it with the same approaches. The majority of the work in this thesis is located in the three papers which compose it and is complemented by two chapters, that bound them all together.

Les problèmes de satisfaction de contraintes distribués (DisCSP) permettent de formaliser divers problèmes qui se situent dans l'intelligence artificielle distribuée. Ces problèmes consistent à trouver une combinaison cohérente des actions de plusieurs agents. Durant cette thèse nous avons apporté plusieurs contributions dans le cadre des DisCSPs. Premièrement, nous avons proposé le Nogood-Based Asynchronous Forward-Checking (AFC-ng). Dans AFC-ng, les agents utilisent les nogoods pour justifier chaque suppression d'une valeur du domaine de chaque variable. Outre l'utilisation des nogoods, plusieurs backtracks simultanés venant de différents agents vers différentes destinations sont autorisés. En deuxième lieu, nous exploitons les caractéristiques intrinsèques du réseau de contraintes pour exécuter plusieurs processus de recherche AFC-ng d'une manière asynchrone à travers chaque branche du pseudo-arborescence obtenu à partir du graphe de contraintes dans l'algorithme Asynchronous Forward-Checking Tree (AFC-tree). Puis, nous proposons deux nouveaux algorithmes de recherche synchrones basés sur le même mécanisme que notre AFC-ng. Cependant, au lieu de maintenir le forward checking sur les agents non encore instanciés, nous proposons de maintenir la consistance d'arc. Ensuite, nous proposons Agile Asynchronous Backtracking (Agile-ABT), un algorithme de changement d'ordre asynchrone qui s'affranchit des restrictions habituelles des algorithmes de backtracking asynchrone. Puis, nous avons proposé une nouvelle méthode correcte pour comparer les ordres dans ABT_DO-Retro. Cette méthode détermine l'ordre le plus pertinent en comparant les indices des agents dès que les compteurs d'une position donnée dans le timestamp sont égaux. Finalement, nous présentons une nouvelle version entièrement restructurée de la plateforme DisChoco pour résoudre les problèmes de satisfaction et d'optimisation de contraintes distribués. / Distributed Constraint Satisfaction Problems (DisCSP) is a general framework for solving distributed problems. DisCSP have a wide range of applications in multi-agent coordination. In this thesis, we extend the state of the art in solving the DisCSPs by proposing several algorithms. Firstly, we propose the Nogood-Based Asynchronous Forward Checking (AFC-ng), an algorithm based on Asynchronous Forward Checking (AFC). However, instead of using the shortest inconsistent partial assignments, AFC-ng uses nogoods as justifications of value removals. Unlike AFC, AFC-ng allows concurrent backtracks to be performed at the same time coming from different agents having an empty domain to different destinations. Then, we propose the Asynchronous Forward-Checking Tree (AFC- tree). In AFC-tree, agents are prioritized according to a pseudo-tree arrangement of the constraint graph. Using this priority ordering, AFC-tree performs multiple AFC-ng processes on the paths from the root to the leaves of the pseudo-tree. Next, we propose to maintain arc consistency asynchronously on the future agents instead of only maintaining forward checking. Two new synchronous search algorithms that maintain arc consistency asynchronously (MACA) are presented. After that, we developed the Agile Asynchronous Backtracking (Agile-ABT), an asynchronous dynamic ordering algorithm that does not follow the standard restrictions in asynchronous backtracking algorithms. The order of agents appearing before the agent receiving a backtrack message can be changed with a great freedom while ensuring polynomial space complexity. Next, we present a corrigendum of the protocol designed for establishing the priority between orders in the asynchronous backtracking algorithm with dynamic ordering using retroactive heuristics (ABT_DO-Retro). Finally, the new version of the DisChoco open-source platform for solving distributed constraint reasoning problems is described. The new version is a complete redesign of the DisChoco platform. DisChoco 2.0 is an open source Java library which aims at implementing distributed constraint reasoning algorithms.