La composition chimique des comètes revêt un intérêt du point de vue de la chimie prébiotique, mais également de la formation et de l'évolution du système solaire. Cette thèse présente la première étape d'un programme de longue durée dont l'objectif final est la détermination de la composition chimique du noyau cométaire.<br />Parmi les différentes méthodes employées jusqu'à aujourd'hui, l'analyse in situ est la seule capable de nous procurer des informations directes sur le noyau cométaire. C'est cette approche que nous avons choisi d'employer en contribuant à l'expérience COmetary Sampling And Composition (COSAC). Cette dernière fait partie des expériences embarquées dans la sonde Rosetta dédiée à l'analyse d'une comète et de son environnement. Compte tenu du nombre important de composés probablement présents dans le noyau cométaire et de la robustesse de cette technique analytique, la chromatographie en phase gazeuse (CPG) apparaît comme la plus appropriée pour l'identification et la quantification des composés présents dans le noyau cométaire. Nous avons donc développé un sous-système chromatographique qui fera partie intégrante de l'expérience COSAC.<br />La principale tâche de ce travail a été de concevoir la partie séparative de ce système, constituée de colonnes chromatographiques connectées en parallèle. Cette partie a été développée en vue de la séparation et de l'identification d'une large gamme de composés d'intérêt cométaire initialement identifiés, allant des composés les plus légers (gaz nobles) jusqu'à des espèces organiques de poids moléculaire élevé (HAP). A cette fin, un travail expérimental a été mené pour comparer les propriétés analytiques (sélectivité, efficacité) des nombreuses colonnes chromatographiques candidates, dans les conditions de température in situ (isotherme comprise entre 30°C et 60°C). Cette étude, associée à la prise en compte de contraintes opératoires (présence d'eau, faible consommation de gaz vecteur, robustesse des colonnes...), a permis d'aboutir à la sélection et à l'optimisation des caractéristiques de 5 colonnes chromatographiques différentes. Cette combinaison correspond au nombre minimal de colonnes permettant de répondre aux objectifs du système chromatographique.<br />Une fois les colonnes de l'expérience sélectionnées, elles ont été soumises aux différentes contraintes liées à l'instrumentation spatiale (vibrations, cycles de température) et à l'environnement spatial (pression réduite, radiations) pour tester leur robustesse. Les résultats montrent que les performances de ces colonnes ne sont affectées ni par ces tests, ni par la présence d'eau dans l'échantillon, prouvant ainsi leur capacité à être utilisées dans le système chromatographique.<br />Ensuite, les performances réelles de ce système ont été évaluées à l'aide d'un outil de laboratoire reproduisant l'expérience COSAC (colonnes, détecteurs) et les conditions opératoires in situ (température, pression externe). Cette étude a permis de montrer que les propriétés analytiques du système ne sont pas significativement altérées comparativement à celles observées à pression atmosphérique en sortie de colonne, et que le gain de vitesse entraîné par la présence d'une pression réduite était bénéfique par la réduction du temps d'analyse. De plus, la pression en tête de colonne optimale de l'expérience a pu être fixée (150 kPa). Nous avons également montré que l'expérience devrait permettre d'identifier environ 75% des composés initialement ciblés.<br />Enfin, la sensibilité du système (colonne+détecteur) a été évaluée en mesurant la quantité minimale détectable d'un composé présent dans un mélange analysé. Elle est comprise entre 10-11 mol et 10-12 mol, ce qui correspond à un rapport de volume de 1 ppm dans le cas le plus favorable où il y a suffisamment d'échantillon gazeux pour remplir complètement la boucle d'échantillonnage. Ce dernier résultat permet de conclure que le système développé permet l'analyse de composés traces présents dans le noyau cométaire et que sa sensibilité est plus importante que celle des observations spectroscopiques de la coma (environ 0,1%).<br />Au delà du travail expérimental de mise en œuvre de ce système chromatographique, nous avons pu également montrer que le couplage d'une des colonnes avec les techniques préparatives des échantillons de COSAC devrait permettre d'analyser des espèces chimiques qui ne pouvaient pas l'être par CPG directe (acides aminés), ou de mettre en évidence des composés réfractaires à partir de leurs produits de dégradation thermique (poly-HCN). Enfin, nous présentons les premiers travaux expérimentaux et théoriques développés en vue de l'interprétation des futures données collectées par l'instrument de vol.

Le bloc opératoire constitue l'un des secteurs les plus coûteux et les plus importants dans un établissement hospitalier. Afin, d'utiliser de manière efficace et rationnelle les ressources (humaines et matérielles) disponibles tout en assurant une bonne qualité de service vis-à-vis des patients, la planification du bloc opératoire est devenue l'une des premières préoccupations des établissements hospitaliers. Le problème de planification du bloc opératoire consiste à déterminer pour un horizon de plusieurs jours, l'ensemble d'interventions qui seront réalisées dans chaque salle opératoire. Ce problème a été traité dans la littérature et plusieurs approches de planification ont été proposées. Toutefois, les approches existantes sont essentiellement basées sur des modèles déterministes qui font abstraction de toutes sortes d'aléas. Or, le bloc opératoire est sujet à nombreuses formes d'aléas qui concernent essentiellement la chirurgie d'urgence et les durées d'interventions. À ce titre, l'objectif de notre travail de recherche est de développer des modèles et méthodes pour la planification des activités chirurgicales dans le bloc opératoire tout en tenant compte des aléas importants. Dans le cadre de cette thèse, nous avons proposé des modèles stochastiques qui (i) capturent les éléments essentiels à considérer lors de la planification des activités chirurgicales, (ii) permettent de modéliser de manière explicite différentes formes d'aléas tels que les incertitudes relatives aux durées des interventions et à la chirurgie d'urgence, et (iii) peuvent être facilement étendus pour modéliser d'autres contraintes dues aux pratiques du terrain. Nous avons aussi développé plusieurs approches et méthodes d'optimisation complètes et complémentaires pour la planification stochastique du bloc opératoire. Moyennant des expérimentations numériques, nous avons évalué les performances de ces différentes approches et nous avons montré leurs efficacités. En particulier, nous avons montré que des gains considérables peuvent être réalisés moyennant une modélisation stochastique du problème de planification du bloc opératoire.

Ce travail a pour objet la résolution d'un problème combinatoire posé dans le cadre de la régulation court terme (ou dynamique) du trafic aérien. On cherche à déterminer pour chaque vol régulable une trajectoire en 4 dimensions réalisable de manière à respecter les contraintes de capacité des secteurs tout en minimisant la somme des coûts des trajectoires choisies. Le problème est modélisé par un programme linéaire mixte. Une représentation ad hoc du système aérien sert de support à la modélisation fine des trajectoires. Un processus global de résolution basé sur la génération de colonnes couplée à la technique de branch-and-bound est détaillé. Les colonnes du problème représentant des trajectoires, la génération de colonnes par le sous problème de tarification se traduit par la recherche de chemins quadridimensionnels sur un réseau continu et dynamique. Un algorithme spécifique basé sur les algorithmes de plus court chemin par marquage et sur la programmation dynamique est développé et testé. Toute la méthode est évaluée sur des instances réelles représentant l'espace aérien géré par la CFMU, l'organisme européen de gestion des flux de trafic aérien. Les résultats obtenus en un temps de calcul compatible avec le contexte opérationnel valident finalement la méthode développée.

La thèse comprend 8 chapitres, 3 annexes, 191 figures, 43 tableaux, 13 photos et 181 références bibliographiques. Le corps du texte totalise 135 pages et les annexes 120 pages. Le chapitre 1 constitue lintroduction dans laquelle le contexte et les objectifs de la recherche sont définis. Le chapitre 2 présente létat de la question concernant les colonnes faites de tubes en acier remplis de béton (CFSHS columns - concrete filled steel hollow section columns). Leur comportement à température ordinaire et sous conditions dincendie est analysé ainsi que les paramètres significatifs qui guident leur comportement. Les propriétés du béton auto-plaçant sont aussi examinées dans ce chapitre. Le chapitre 3 est consacré à la présentation du code de calcul SAFIR développé à lUniversité de Liège pour la simulation du comportement structural à température ordinaire et sous conditions dincendie. Le logiciel a été utilisé pour simuler des résultats dessais expérimentaux présentés dans la littérature, et quelques calibrations sont proposées. En utilisant le modèle décrit au chapitre 3, la charge ultime à température ordinaire des colonnes CFSHS est calculée en considérant différents paramètres. On considère essentiellement des tubes de petites dimensions avec un pourcentage élevé darmatures ou contenant un autre profilé métallique. Ce type délément nest pas couvert par les Eurocodes. Des simulations ont été réalisées en vue dexaminer si les méthodes classiques de lEurocode 4 (EN1994-1-1) sont applicables à ce type de section et de voir quelle courbe de flambement est la plus appropriée. Le chapitre 5 décrit la recherche expérimentale réalisée à lUniversité de Liège relative au comportement au feu des colonnes CFSHS. Les essais expérimentaux ont été simulés par SAFIR, tant en ce qui concerne la répartition de la température à lintérieur des éléments que le comportement structural. Un des objectifs de ces calculs était de vérifier si les propriétés thermiques et mécaniques du béton auto-plaçant sont proches de celles du béton ordinaire. En vue de fournir aux bureaux détudes des outils pratiques de dimensionnement, une formule permettant dévaluer la résistance au feu des colonnes CFSHS est proposée dans le chapitre 6. Le domaine dapplicabilité a été étendu par rapport aux études précédentes. Une formule pour colonnes courtes de section carrée a dabord été établie sur base de simulations effectuées à laide de SAFIR en considérant linfluence des paramètres principaux. On examine ensuite si cette formule est aussi applicable à dautres types de profilés. La formule a été étendue en cas des colonnes élancées et à celui des colonnes chargées excentriquement. Létude expérimentale du chapitre 5 est limitée à des sections dassez petites dimensions (< 300 mm), essentiellement pour des problèmes de capacité de mise en charge des laboratoires. En vue de recueillir des informations pratiques pour des profilés de plus grandes dimensions pour lesquels on peut atteindre des résistances au feu de 2 heures et plus, des simulations numériques additionnelles sont présentées dans le chapitre 7, avec des résultats utilisables en bureau détudes. Le chapitre 8 donne les conclusions de létude et présente des suggestions pour des recherches futures.

Nos travaux portent sur la modelisation et la resolution de problemes d'optimisation combinatoire emergeant dans le cadre de la planification de missions spatiales. Ces problemes de grande taille presentent des caracteristiques communes en termes de types de donnees, de contraintes et de criteres a optimiser. Nous nous focalisons sur l'apport de la programmation lineaire pour ces problemes, associee a des methodes de simplification de l'espace de recherche, par decomposition ou grace a des techniques de propagation de contraintes. Nous avons plus particulierement etudie deux problemes. Le premier concerne la planification de communications sonde/satellite et d'experiences dans un projet d'exploration martienne. Une decomposition de ce probleme permet de le formuler comme deux problemes independants : un probleme de planification des communications que nous modelisons et resolvons par programmation lineaire en nombres entiers, et un probleme d'aide a la decision pour la planification des experiences, pour lequel nous etablissons des courbes d'evaluation de la charge des ressources deduites de l'application de techniques de propagation de contraintes basees sur un raisonnement energetique. Le second probleme etudie est celui de la planification de prises de vue d'un satellite d'observation de la Terre. Nous proposons un modele lineaire en variables mixtes et nous developpons une approche de resolution par generation de colonnes, qui est une adaptation de la programmation lineaire au traitement de problemes de grande taille, faisant appel a certaines techniques de decomposition des modeles.

La survie des réseaux est un domaine d'étude technique très intéressant ainsi qu'une préoccupation critique dans la conception des réseaux. Compte tenu du fait que de plus en plus de données sont transportées à travers des réseaux de communication, une simple panne peut interrompre des millions d'utilisateurs et engendrer des millions de dollars de pertes de revenu. Les techniques de protection des réseaux consistent à fournir une capacité supplémentaire dans un réseau et à réacheminer les flux automatiquement autour de la panne en utilisant cette disponibilité de capacité. Cette thèse porte sur la conception de réseaux optiques intégrant des techniques de survie qui utilisent des schémas de protection basés sur les p-cycles. Plus précisément, les p-cycles de protection par chemin sont exploités dans le contexte de pannes sur les liens. Notre étude se concentre sur la mise en place de structures de protection par p-cycles, et ce, en supposant que les chemins d'opération pour l'ensemble des requêtes sont définis a priori. La majorité des travaux existants utilisent des heuristiques ou des méthodes de résolution ayant de la difficulté à résoudre des instances de grande taille. L'objectif de cette thèse est double. D'une part, nous proposons des modèles et des méthodes de résolution capables d'aborder des problèmes de plus grande taille que ceux déjà présentés dans la littérature. D'autre part, grâce aux nouveaux algorithmes, nous sommes en mesure de produire des solutions optimales ou quasi-optimales. Pour ce faire, nous nous appuyons sur la technique de génération de colonnes, celle-ci étant adéquate pour résoudre des problèmes de programmation linéaire de grande taille. Dans ce projet, la génération de colonnes est utilisée comme une façon intelligente d'énumérer implicitement des cycles prometteurs. Nous proposons d'abord des formulations pour le problème maître et le problème auxiliaire ainsi qu'un premier algorithme de génération de colonnes pour la conception de réseaux protegées par des p-cycles de la protection par chemin. L'algorithme obtient de meilleures solutions, dans un temps raisonnable, que celles obtenues par les méthodes existantes. Par la suite, une formulation plus compacte est proposée pour le problème auxiliaire. De plus, nous présentons une nouvelle méthode de décomposition hiérarchique qui apporte une grande amélioration de l'efficacité globale de l'algorithme. En ce qui concerne les solutions en nombres entiers, nous proposons deux méthodes heurisiques qui arrivent à trouver des bonnes solutions. Nous nous attardons aussi à une comparaison systématique entre les p-cycles et les schémas classiques de protection partagée. Nous effectuons donc une comparaison précise en utilisant des formulations unifiées et basées sur la génération de colonnes pour obtenir des résultats de bonne qualité. Par la suite, nous évaluons empiriquement les versions orientée et non-orientée des p-cycles pour la protection par lien ainsi que pour la protection par chemin, dans des scénarios de trafic asymétrique. Nous montrons quel est le coût de protection additionnel engendré lorsque des systèmes bidirectionnels sont employés dans de tels scénarios. Finalement, nous étudions une formulation de génération de colonnes pour la conception de réseaux avec des p-cycles en présence d'exigences de disponibilité et nous obtenons des premières bornes inférieures pour ce problème. / Network survivability is a very interesting area of technical study and a critical concern in network design. As more and more data are carried over communication networks, a single outage can disrupt millions of users and result in millions of dollars of lost revenue. Survivability techniques involve providing some redundant capacity within the network and automatically rerouting traffic around the failure using this redundant capacity. This thesis concerns the design of survivable optical networks using p-cycle based schemes, more particularly, path-protecting p-cycles, in link failure scenarios. Our study focuses on the placement of p-cycle protection structures assuming that the working routes for the set of connection requests are defined a priori. Most existing work carried out on p-cycles concerns heuristic algorithms or methods suffering from critical lack of scalability. Thus, the objective of this thesis is twofold: on the one hand, to propose scalable models and solution methods enabling to approach larger problem instances and on the other hand, to produce optimal or near optimal solutions with mathematically proven optimality gaps. For this, we rely on the column generation technique which is suitable to solve large scale linear programming problems. Here, column generation is used as an intelligent way of implicitly enumerating promising cycles to be part of p-cycle designs. At first, we propose mathematical formulations for the master and the pricing problems as well as the first column generation algorithm for the design of survivable networks based on path-protecting p-cycles. The resulting algorithm obtains better solutions within reasonable running time in comparison with existing methods. Then, a much more compact formulation of the pricing problem is obtained. In addition, we also propose a new hierarchical decomposition method which greatly improves the efficiency of the whole algorithm and allows us to solve larger problem instances. As for integer solutions, two heuristic approaches are proposed to obtain good solutions. Next, we dedicate our attention to a systematic comparison of p-cycles and classical shared protection schemes. We perform an accurate comparison by using a unified column generation framework to find provably good results. Afterwards, our study concerns an empirical evaluation of directed and undirected link- and path-protecting p-cycles under asymmetric traffic scenarios. We show how much additional protection cost results from employing bidirectional systems in such scenarios. Finally, we investigate a column generation formulation for the design of p-cycle networks under availability requirements and obtain the first lower bounds for the problem.

Le problème de localisation-routage avec capacités (PLRC) apparaît comme un problème clé dans la conception de réseaux de distribution de marchandises. Il généralisele problème de localisation avec capacités (PLC) ainsi que le problème de tournées de véhicules à multiples dépôts (PTVMD), le premier en ajoutant des décisions liées au routage et le deuxième en ajoutant des décisions liées à la localisation des dépôts. Dans cette thèse on dévelope des outils pour résoudre le PLRC à l’aide de la programmation mathématique. Dans le chapitre 3, on introduit trois nouveaux modèles pour le PLRC basés sur des flots de véhicules et des flots de commodités, et on montre comment ceux-ci dominent, en termes de la qualité de la borne inférieure, la formulation originale à deux indices [19]. Des nouvelles inégalités valides ont été dévelopées et ajoutées aux modèles, de même que des inégalités connues. De nouveaux algorithmes de séparation ont aussi été dévelopés qui dans la plupart de cas généralisent ceux trouvés dans la litterature. Les résultats numériques montrent que ces modèles de flot sont en fait utiles pour résoudre des instances de petite à moyenne taille. Dans le chapitre 4, on présente une nouvelle méthode de génération de colonnes basée sur une formulation de partition d’ensemble. Le sous-problème consiste en un problème de plus court chemin avec capacités (PCCC). En particulier, on utilise une relaxation de ce problème dans laquelle il est possible de produire des routes avec des cycles de longueur trois ou plus. Ceci est complété par des nouvelles coupes qui permettent de réduire encore davantage le saut d’intégralité en même temps que de défavoriser l’apparition de cycles dans les routes. Ces résultats suggèrent que cette méthode fournit la meilleure méthode exacte pour le PLRC. Dans le chapitre 5, on introduit une nouvelle méthode heuristique pour le PLRC. Premièrement, on démarre une méthode randomisée de type GRASP pour trouver un premier ensemble de solutions de bonne qualité. Les solutions de cet ensemble sont alors combinées de façon à les améliorer. Finalement, on démarre une méthode de type détruir et réparer basée sur la résolution d’un nouveau modèle de localisation et réaffectation qui généralise le problème de réaffectaction [48]. / The capacitated location-routing problem (CLRP) arises as a key problem in the design of distribution networks. It generalizes both the capacitated facility location problem (CFLP) and the multiple depot vehicle routing problem (MDVRP), the first by considering additional routing decisions and the second by adding the location decision variables. In this thesis we use different mathematical programming tools to develop and specialize new models and algorithms for solving the CLRP. In Chapter 3, three new models are presented for the CLRP based on vehicle-flow and commodity-flow formulations, all of which are shown to dominate, in terms of the linear relaxation lower bound, the original two-index vehicle-flow formulation [19]. Known valid inequalities are complemented with some new ones and included using separation algorithms that in many cases generalize extisting ones found in the literature. Computational experiments suggest that flow models can be efficient for dealing with small or medium size instances of the CLRP (50 customers or less). In Chapter 4, a new branch-and-cut-and-price exact algorithm is introduced for the CLRP based on a set-partitioning formulation. The pricing problem is a shortest path problem with resource constraints (SPPRC). In particular, we consider a relaxation of such problem in which routes are allowed to contain cycles of length three or more. This is complemented with the development of new valid inequalities that are shown to be effective for closing the optimality gap as well as to restrict the appearance of cycles. Computational experience supports the fact that this method is now the best exact method for the CLRP. In Chapter 5, we introduce a new metaheuristic with the aim of finding good quality solutions in short or moderate computing times. First, a bundle of good solutions is generated with the help of a greedy randomized adaptive search procedure (GRASP). Following this, a blending procedure is applied with the aim of producing a better upper bound as a combination of all the others in the bundle. An iterative destroy-and-repair method is then applied using a location-reallocation model that generalizes the reallocation model due to de Franceschi et al. [48].

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

L'optimisation multi-objectif concerne la résolution de problèmes pour lesquels plusieurs objectifs (ou critères) contradictoires sont pris en compte. Contrairement aux problèmes d'optimisation ayant un seul objectif, un problème multi-objectif ne possède pas une valeur optimale unique mais plutôt un ensemble de points appelés "ensemble non dominé". Les bornes inférieures et supérieures d'un problème multi-objectif peuvent être également décrites par des ensembles. Dans la pratique, les variables utilisées en optimisation multiobjectif représentent souvent des objets non fractionnables et on parle alors de problèmes multi-objectif en nombres entiers. Afin d'obtenir de meilleures bornes qui peuvent être utilisées dans la conception de méthodes exactes, certains problèmes sont formulés avec un nombre exponentiel de variables de décision et ces problèmes sont résolus par la méthode de génération de colonnes. Les travaux de cette thèse visent à contribuer à l'étude de l'utilisation de la génération de colonnes en programmation linéaires en nombres entiers multi-objectif. Pour cela nous étudions un problème de tournées de véhicules bi-objectif qui peut être considéré comme une généralisation de plusieurs autres problèmes de tournées de véhicules. Nous proposons des formulations mathématiques pour ce problème et des techniques pour accélérer le calcul des bornes inférieures par génération de colonnes. Les sous-problèmes qui doivent être résolus pour le calcul des bornes inférieures ont une structure similaire. Nous exploitons cette caractéristique pour traiter simultanément certains sous-problèmes plutôt qu'indépendamment.

Le renforcement des sols en zone sismique par des colonnes ballastées et/ou des inclusions rigides représente une alternative prometteuse et de plus en plus répandue par rapport aux solutions lourdes de fondations sur pieux. On sait que les pieux subissent, du fait de leur rigidité, des moments très importants au niveau de la liaison chevêtre-pieu. Les inclusions rigides surmontées d'un matelas granulaire permettent de mieux dissiper les efforts inertiels transmis par la superstructure, mais peuvent nécessiter des armatures si ce matelas n'est pas suffisamment épais. On peut penser que la colonne à module mixte (CMM) offre une solution combinant l'effet " matelas " à travers sa partie supérieure en colonne ballastée plus flexible et l'effet stabilisateur de la colonne inférieure. Cette thèse présente dans une première partie l'étude expérimentale réalisée au Laboratoire 3S-R (Grenoble) sur des modèles réduits à l'échelle 1/10 afin d'analyser la réponse de ces systèmes sous différentes charges statiques et dynamiques. Le modèle physique se compose d'une semelle carrée reposant directement sur l'argile renforcée. Le chargement vertical et horizontal, statique et dynamique est appliqué par l'intermédiaire de la fondation. Une instrumentation a été placée au niveau de la semelle pour obtenir la réponse globale du système, ainsi que dans la partie rigide inférieure du modèle pour évaluer la répartition des efforts entre inclusion et partie flexible supérieure. Une attention toute particulière a été donnée à la simulation de l'effet inertiel d'un séisme. Les profils de moments, d'efforts tranchants et de déplacements en fonction de la profondeur déterminés à partir de 20 extensomètres répartis régulièrement sur toute la hauteur de la partie rigide ont permis d'étudier l'influence de la hauteur de la colonne ou du matelas. La comparaison entre les déplacements dynamiques de la semelle et les courbes P-y (pression latérale P fonction du déplacement latéral y de la tête de pieu), permet de quantifier la dissipation de l'énergie dans les différentes parties du système. Les résultats expérimentaux montrent que la partie supérieure souple absorbe l'essentiel de l'énergie inertielle sismique. Une modélisation numérique 3D confirme les tendances observées expérimentalement et souligne l'importance du rôle de la zone de transition entre partie souple et partie rigide.