De nombreux problèmes d'optimisation propres à différents secteurs industriels et académiques (énergie, chimie, transport, etc.) nécessitent de concevoir des méthodes de plus en plus efficaces pour les résoudre. Afin de répondre à ces besoins, l'objectif de cette thèse est de développer une bibliothèque composée de plusieurs métaheuristiques hybrides distribuées et massivement parallèles. Dans un premier temps, nous avons étudié le problème du voyageur de commerce et sa résolution par la méthode colonie de fourmis afin de mettre en place les techniques d'hybridation et de parallélisation. Ensuite, deux autres problèmes d'optimisation ont été traités, à savoir, le problème d'affectation quadratique (QAP) et le problème de la résolution structurale des zéolithes (ZSP). Pour le QAP, plusieurs variantes basées sur une recherche taboue itérative avec des diversifications adaptatives ont été proposées. Le but de ces propositions est d'étudier l'impact de : l'échange des données, des stratégies de diversification et des méthodes de coopération. Notre meilleure variante est comparée à six des meilleurs travaux de la littérature. En ce qui concerne le ZSP, deux nouvelles formulations de la fonction objective sont proposées pour évaluer le potentiel des structures zéolitiques trouvées. Ces formulations sont basées sur le principe de pénalisation et de récompense. Deux algorithmes génétiques hybrides et parallèles sont proposés pour générer des structures zéolitiques stables. Nos algorithmes ont généré actuellement six topologies stables, parmi lesquelles trois ne sont pas répertoriées sur le site Web du SC-IZA ou dans l'Atlas of Prospective Zeolite Structures. / Many optimization problems specific to different industrial and academic sectors (energy, chemicals, transportation, etc.) require the development of more effective methods in resolving. To meet these needs, the aim of this thesis is to develop a library of several hybrid metaheuristics distributed and massively parallel. First, we studied the traveling salesman problem and its resolution by the ant colony method to establish hybridization and parallelization techniques. Two other optimization problems have been dealt, which are, the quadratic assignment problem (QAP) and the zeolite structure problem (ZSP). For the QAP, several variants based on an iterative tabu search with adaptive diversification have been proposed. The aim of these proposals is to study the impact of: the data exchange, the diversification strategies and the methods of cooperation. Our best variant is compared with six from the leading works of the literature. For the ZSP two new formulations of the objective function are proposed to evaluate the potential of the zeolites structures founded. These formulations are based on reward and penalty evaluation. Two hybrid and parallel genetic algorithms are proposed to generate stable zeolites structures. Our algorithms have now generated six stable topologies, three of them are not listed in the SC-JZA website or in the Atlas of Prospective Zeolite Structures.

<p>An introduction to bacterial polysaccharides and the methods for structural determination are described in the first two parts of the thesis.</p><p>In a structural elucidation of bacterial polysaccharides NMR experiments are important as is component analysis. A short description of immunochemical methods such as enzyme immunoassays is included. Two NMR techniques used for interaction studies, trNOE and STD NMR, are also discussed. </p><p>The third part of the thesis discusses and summarizes the results from the included papers. The structures of the exopolysaccharides produced by two lactic acid bacteria are determined by one- and two dimensional NMR experiments. One is a heteropolysaccharide produced by <i>Streptococcus thermophilus</i> and the other a homopolysaccharide produced by <i>Propionibacterium freudenreichii</i>. The structure of an acidic polysaccharide from a marine bacterium with two serine residues in the repeating unit is also investigated. The structural and immunological relationship between two O-antigenic polysaccharides from <i>Escherichia coli</i> strain 180/C3 and O5 is discussed and investigated. Finally, interaction studies of an octasaccharide derived from the <i>Salmonella enteritidis</i> O-antigen and a bacteriophage are described which were performed with NMR experiments.</p>

An introduction to bacterial polysaccharides and the methods for structural determination are described in the first two parts of the thesis. In a structural elucidation of bacterial polysaccharides NMR experiments are important as is component analysis. A short description of immunochemical methods such as enzyme immunoassays is included. Two NMR techniques used for interaction studies, trNOE and STD NMR, are also discussed. The third part of the thesis discusses and summarizes the results from the included papers. The structures of the exopolysaccharides produced by two lactic acid bacteria are determined by one- and two dimensional NMR experiments. One is a heteropolysaccharide produced by Streptococcus thermophilus and the other a homopolysaccharide produced by Propionibacterium freudenreichii. The structure of an acidic polysaccharide from a marine bacterium with two serine residues in the repeating unit is also investigated. The structural and immunological relationship between two O-antigenic polysaccharides from Escherichia coli strain 180/C3 and O5 is discussed and investigated. Finally, interaction studies of an octasaccharide derived from the Salmonella enteritidis O-antigen and a bacteriophage are described which were performed with NMR experiments.

Many companies have traveling salesmen that market and sell their products.This results in much traveling by car due to the daily customer visits. Thiscauses costs for the company, in form of travel expenses compensation, and environmentaleffects, in form of carbon dioxide pollution. As many companies arecertified according to environmental management systems, such as ISO 14001,the environmental work becomes more and more important as the environmentalconsciousness increases every day for companies, authorities and public.The main task of this thesis is to compute reasonable limits on the mileage ofthe salesmen; these limits are based on specific conditions for each salesman’sdistrict. The objective is to implement a heuristic algorithm that optimizes thecustomer tours for an arbitrary chosen month, which will represent a “standard”month. The output of the algorithm, the computed distances, will constitute amileage limit for the salesman.The algorithm consists of a constructive heuristic that builds an initial solution,which is modified if infeasible. This solution is then improved by a local searchalgorithm preceding a genetic algorithm, which task is to improve the toursseparately.This method for computing mileage limits for traveling salesmen generates goodsolutions in form of realistic tours. The mileage limits could be improved if theinput data were more accurate and adjusted to each district, but the suggestedmethod does what it is supposed to do.

This Thesis Work will concentrate on a very interesting problem, the Vehicle Routing Problem (VRP). In this problem, customers or cities have to be visited and packages have to be transported to each of them, starting from a basis point on the map. The goal is to solve the transportation problem, to be able to deliver the packages-on time for the customers,-enough package for each Customer,-using the available resources- and – of course - to be so effective as it is possible.Although this problem seems to be very easy to solve with a small number of cities or customers, it is not. In this problem the algorithm have to face with several constraints, for example opening hours, package delivery times, truck capacities, etc. This makes this problem a so called Multi Constraint Optimization Problem (MCOP). What’s more, this problem is intractable with current amount of computational power which is available for most of us. As the number of customers grow, the calculations to be done grows exponential fast, because all constraints have to be solved for each customers and it should not be forgotten that the goal is to find a solution, what is best enough, before the time for the calculation is up. This problem is introduced in the first chapter: form its basics, the Traveling Salesman Problem, using some theoretical and mathematical background it is shown, why is it so hard to optimize this problem, and although it is so hard, and there is no best algorithm known for huge number of customers, why is it a worth to deal with it. Just think about a huge transportation company with ten thousands of trucks, millions of customers: how much money could be saved if we would know the optimal path for all our packages.Although there is no best algorithm is known for this kind of optimization problems, we are trying to give an acceptable solution for it in the second and third chapter, where two algorithms are described: the Genetic Algorithm and the Simulated Annealing. Both of them are based on obtaining the processes of nature and material science. These algorithms will hardly ever be able to find the best solution for the problem, but they are able to give a very good solution in special cases within acceptable calculation time.In these chapters (2nd and 3rd) the Genetic Algorithm and Simulated Annealing is described in details, from their basis in the “real world” through their terminology and finally the basic implementation of them. The work will put a stress on the limits of these algorithms, their advantages and disadvantages, and also the comparison of them to each other.Finally, after all of these theories are shown, a simulation will be executed on an artificial environment of the VRP, with both Simulated Annealing and Genetic Algorithm. They will both solve the same problem in the same environment and are going to be compared to each other. The environment and the implementation are also described here, so as the test results obtained.Finally the possible improvements of these algorithms are discussed, and the work will try to answer the “big” question, “Which algorithm is better?”, if this question even exists.

<p>Many companies have traveling salesmen that market and sell their products.This results in much traveling by car due to the daily customer visits. Thiscauses costs for the company, in form of travel expenses compensation, and environmentaleffects, in form of carbon dioxide pollution. As many companies arecertified according to environmental management systems, such as ISO 14001,the environmental work becomes more and more important as the environmentalconsciousness increases every day for companies, authorities and public.The main task of this thesis is to compute reasonable limits on the mileage ofthe salesmen; these limits are based on specific conditions for each salesman’sdistrict. The objective is to implement a heuristic algorithm that optimizes thecustomer tours for an arbitrary chosen month, which will represent a “standard”month. The output of the algorithm, the computed distances, will constitute amileage limit for the salesman.The algorithm consists of a constructive heuristic that builds an initial solution,which is modified if infeasible. This solution is then improved by a local searchalgorithm preceding a genetic algorithm, which task is to improve the toursseparately.This method for computing mileage limits for traveling salesmen generates goodsolutions in form of realistic tours. The mileage limits could be improved if theinput data were more accurate and adjusted to each district, but the suggestedmethod does what it is supposed to do.</p>

In this work, the Traveling Salesman Problem (TSP) is discussed. The Hybrid Genetic Algorithm for solving the TSP is presented. The traveling salesman problem is formulated as follows: given matrix D=(dij)nxn of distances between n objects and the set P of permutations of the integers from 1 to n, find a permutation p=(p(1), p(2), ..., p(n)) P that minimizes. Many heuristic algorithms can be applied for the TSP. Recently, genetic algorithms (GAs) are among the advanced heuristic techniques for the combinatorial problems, like the TSP. genetic algorithms are based on the biological process of natural selection. The original concepts of GAs were developed in 1970s. Many simulations have demonstrated the efficiency of GAs on different optimization problems, among them, bin–packing, generalized assignment problem, graph partitioning, job–shop scheduling problem, set covering problem, vehicle routing. One of the main operators in GAs is the crossover (i.e. solution recombination). This operator plays a very important role by constructing competitive GAs. In this work, we investigate several crossover operators for the TSP, among them, CX (cycle crossover), PMX (partialy mapped crossover), POS (position based crossover), ER (edge recombination crossover), edge-NN (edge recombination crossover, nearest neighbour) and AP (alternating-positions crossover). Comparison of these crossover operators was performed. The results show high efficiency of the edge-NN, ER and PMX crossovers.

Parallèlement au rôle central du récepteur aux androgènes, l'environnement tumoral immédiat exerce aussi une action majeure sur la progression du cancer de la prostate. L'hypoxie locale, par le biais de régulations multiples, serait impliquée dans la migration cellulaire et la dissémination tumorale. L'objectif de ma thèse a été d'identifier de nouvelles cibles thérapeutiques et de nouveaux marqueurs pronostiques pour ces cancers. J'ai tout d'abord participé à l'identification d'un partenaire du récepteur aux androgènes, la protéine CAD, enzyme clé de la synthèse des pyrimidines. Parallèlement, nous nous sommes intéressés au rôle d'un anti-angiogénique endogène dans la progression du cancer de la prostate, la thrombospondine-1 (TSP-1). Bien que l'activité anti angiogénique soit souvent considérée comme anti-tumorale, nous avons mis en évidence le caractère protumoral de la TSP-1, par son action promigratoire sur les cellules tumorales. Ces travaux m'ont conduits à étudier l'axe CXCR4/SDF-1, régulé en partie par l'hypoxie et stimulant la migration cellulaire. Nous avons montré sur tissu humain que CXCR4 était exprimé principalement au niveau du front tumoral des cancers localisés et localement avancés, et que son expression était associée à une transition épithélio-mésenchymateuse. SDF-1 était surexprimée selon un gradient croissant allant du centre des tumeurs vers le tissu péritumoral distant, exerçant possiblement un chimiotactisme sur les cellules du front tumoral. La surexpression de CXCR4 au front tumoral ainsi que le gradient de SDF1 étaient associés au pronostic.

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

The tree-width and branch-width of a graph are two well-studied examples of parameters that measure how well a given graph can be decomposed into a tree structure. In this thesis we give several results and applications concerning these concepts, in particular if the graph is embedded on a surface. In the first part of this thesis we develop a geometric description of tangles in graphs embedded on a fixed surface (tangles are the obstructions for low branch-width), generalizing a result of Robertson and Seymour. We use this result to establish a relationship between the branch-width of an embedded graph and the carving-width of an associated graph, generalizing a result for the plane of Seymour and Thomas. We also discuss how these results relate to the polynomial-time algorithm to determine the branch-width of planar graphs of Seymour and Thomas, and explain why their method does not generalize to surfaces other than the sphere. We also prove a result concerning the class C_2k of minor-minimal graphs of branch-width 2k in the plane, for an integer k at least 2. We show that applying a certain construction to a class of graphs in the projective plane yields a subclass of C_2k, but also show that not all members of C_2k arise in this way if k is at least 3. The last part of the thesis is concerned with applications of graphs of bounded tree-width to the Traveling Salesman Problem (TSP). We first show how one can solve the separation problem for comb inequalities (with an arbitrary number of teeth) in linear time if the tree-width is bounded. In the second part, we modify an algorithm of Letchford et al. using tree-decompositions to obtain a practical method for separating a different class of TSP inequalities, called simple DP constraints, and study their effectiveness for solving TSP instances.