Models and algorithms for the capacitated location-routing 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].

Caractérisation du motif acidique de la sous-unité p28 de l’IL-27 et étude des propriétés partagées entre cette protéine, le CNTF, CLC/CLF et l’interleukine-6

L’interleukine 6 (IL-6) est une cytokine qui joue un rôle essentiel dans l’inflammation. Son récepteur (IL-6R) est composé de la chaîne non signalétique IL-6Rα et de la chaîne transductrice du signal gp130, commune aux cytokines de la famille IL-6. La liaison de l’IL-6 à son récepteur permet l’activation de plusieurs voies de signalisation, notamment des voies Jak/STAT1 et préférentiellement Jak/STAT3. De façon complémentaire, nous avons démontré que l’IL-6 est capable d’activer la voie Jak/STAT5 dans les lymphocytes T CD4. L’activation de cette voie de signalisation pourrait être impliquée dans le rétrocontrôle des effets pro-inflammatoires de l’IL-6 sur les cellules T CD4. Le facteur neurotrophique ciliaire (CNTF) et la « cardiotrophin-like cytokine/cytokine-like factor 1 » (CLC/CLF) sont deux cytokines de la famille de l’IL-6 qui signalent à travers un récepteur commun, le récepteur au CNTF (CNTFR), composé du CNTFRα, « leukaemia inhibitory factor receptor β » (LIFRβ) et gp130. Toutes deux exercent des actions au niveau du système immunitaire, or la chaîne CNTFRα de leur récepteur n’y est pas exprimée. Il a été montré que le CNTFR humain peut également activer un récepteur formé des sous-unités IL-6Rα, LIFRβ et gp130. Nous avons comparé les effets du CNTF et du CLC/CLF de souris sur des transfectants exprimant LIFRβ et gp130 et les chaines α connues de la famille IL-6 (IL-6Rα, IL-11Rβ et CNTFRα). Nos résultats indiquent que le CNTF de souris, comme le CNTF humain est capable d’activer un récepteur formé de l’IL-6Rα, LIFRβ et gp130. Toutefois cette propriété n’est pas partagée par CLC/CLF et le récepteur impliqué dans les effets de cette cytokine sur le système immunitaire reste donc à identifier. L’IL-27 appartient à la famille de l’IL-6 composée d’une sous-unité cytokinique, p28, associée à un récepteur soluble « l’Epstein-Barr virus-induced gene 3» (EBI3). La sous-unité p28 peut s’associer avec le récepteur soluble CLF pour former une cytokine capable d’activer les lymphocytes T. Dans le but de caractériser cette cytokine, nous avons montré que p28/CLF agit aussi sur les lymphocytes B et permet leur différenciation en plasmocytes. Le partage de l’IL-6R par l’IL-6 et p28/CLF semble être à l’origine de la similarité des effets de ces deux cytokines. De plus, nous avons observé des effets semblables à ceux de l’IL-6 suite à l’association de la sous-unité p28 seule avec la chaîne IL-6Rα. En effet, afin de mieux caractériser la cytokine p28/CLF, nous avons étudié les effets dus au recrutement de la chaîne IL-6Rα par la sous-unité p28. Les cytokines de la famille de l’IL-6 sont composées de quatre hélices α disposées de façon anti-parallèle deux à deux. La sous-unité p28 possède, au niveau d’une boucle reliant deux hélices α, un motif de plusieurs acides glutamiques consécutifs (motif polyE) qui n’est retrouvé dans aucune autre cytokine de cette famille. Nous avons démontré que ce motif est impliqué dans la liaison de cette sous-unité avec l’hydroxyapatite et l’os. Cette caractéristique de p28 pourrait permettre un ciblage de l’IL-27 (p28/EBI3) et de p28/CLF préférentiellement vers la niche endostéale des cellules souches et des cellules immunitaires.

Introduction à quelques aspects de quantification géométrique.

On révise les prérequis de géométrie différentielle nécessaires à une première approche de la théorie de la quantification géométrique, c'est-à-dire des notions de base en géométrie symplectique, des notions de groupes et d'algèbres de Lie, d'action d'un groupe de Lie, de G-fibré principal, de connexion, de fibré associé et de structure presque-complexe. Ceci mène à une étude plus approfondie des fibrés en droites hermitiens, dont une condition d'existence de fibré préquantique sur une variété symplectique. Avec ces outils en main, nous commençons ensuite l'étude de la quantification géométrique, étape par étape. Nous introduisons la théorie de la préquantification, i.e. la construction des opérateurs associés à des observables classiques et la construction d'un espace de Hilbert. Des problèmes majeurs font surface lors de l'application concrète de la préquantification : les opérateurs ne sont pas ceux attendus par la première quantification et l'espace de Hilbert formé est trop gros. Une première correction, la polarisation, élimine quelques problèmes, mais limite grandement l'ensemble des observables classiques que l'on peut quantifier. Ce mémoire n'est pas un survol complet de la quantification géométrique, et cela n'est pas son but. Il ne couvre ni la correction métaplectique, ni le noyau BKS. Il est un à-côté de lecture pour ceux qui s'introduisent à la quantification géométrique. D'une part, il introduit des concepts de géométrie différentielle pris pour acquis dans (Woodhouse [21]) et (Sniatycki [18]), i.e. G-fibrés principaux et fibrés associés. Enfin, il rajoute des détails à quelques preuves rapides données dans ces deux dernières références.

Dynamic Facility Location with Modular Capacities : Models, Algorithms and Applications in Forestry

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.

L’optimisation de la performance des services infirmiers : miser sur des pratiques de gestion utilisées par les organisations hautement performantes

Travail dirigé présenté à la Faculté des Sciences Infirmières en vue de l’obtention du grade de Maître ès Sciences (M. Sc.) en sciences infirmière option administration des sciences infirmières

On Vessiot's Theory of Partial Differential Equations

The object of research presented here is Vessiot's theory of partial differential equations: for a given differential equation one constructs a distribution both tangential to the differential equation and contained within the contact distribution of the jet bundle. Then within it, one seeks n-dimensional subdistributions which are transversal to the base manifold, the integral distributions. These consist of integral elements, and these again shall be adapted so that they make a subdistribution which closes under the Lie-bracket. This then is called a flat Vessiot connection. Solutions to the differential equation may be regarded as integral manifolds of these distributions. In the first part of the thesis, I give a survey of the present state of the formal theory of partial differential equations: one regards differential equations as fibred submanifolds in a suitable jet bundle and considers formal integrability and the stronger notion of involutivity of differential equations for analyzing their solvability. An arbitrary system may (locally) be represented in reduced Cartan normal form. This leads to a natural description of its geometric symbol. The Vessiot distribution now can be split into the direct sum of the symbol and a horizontal complement (which is not unique). The n-dimensional subdistributions which close under the Lie bracket and are transversal to the base manifold are the sought tangential approximations for the solutions of the differential equation. It is now possible to show their existence by analyzing the structure equations. Vessiot's theory is now based on a rigorous foundation. Furthermore, the relation between Vessiot's approach and the crucial notions of the formal theory (like formal integrability and involutivity of differential equations) is clarified. The possible obstructions to involution of a differential equation are deduced explicitly. In the second part of the thesis it is shown that Vessiot's approach for the construction of the wanted distributions step by step succeeds if, and only if, the given system is involutive. Firstly, an existence theorem for integral distributions is proven. Then an existence theorem for flat Vessiot connections is shown. The differential-geometric structure of the basic systems is analyzed and simplified, as compared to those of other approaches, in particular the structure equations which are considered for the proofs of the existence theorems: here, they are a set of linear equations and an involutive system of differential equations. The definition of integral elements given here links Vessiot theory and the dual Cartan-Kähler theory of exterior systems. The analysis of the structure equations not only yields theoretical insight but also produces an algorithm which can be used to derive the coefficients of the vector fields, which span the integral distributions, explicitly. Therefore implementing the algorithm in the computer algebra system MuPAD now is possible.

Generating Communications Systems Through Shared Context

In a distributed model of intelligence, peer components need to communicate with one another. I present a system which enables two agents connected by a thick twisted bundle of wires to bootstrap a simple communication system from observations of a shared environment. The agents learn a large vocabulary of symbols, as well as inflections on those symbols which allow thematic role-frames to be transmitted. Language acquisition time is rapid and linear in the number of symbols and inflections. The final communication system is robust and performance degrades gradually in the face of problems.

Recovering Euclidean deformable models from stereo-motion

In this paper we present a novel structure from motion (SfM) approach able to infer 3D deformable models from uncalibrated stereo images. Using a stereo setup dramatically improves the 3D model estimation when the observed 3D shape is mostly deforming without undergoing strong rigid motion. Our approach first calibrates the stereo system automatically and then computes a single metric rigid structure for each frame. Afterwards, these 3D shapes are aligned to a reference view using a RANSAC method in order to compute the mean shape of the object and to select the subset of points on the object which have remained rigid throughout the sequence without deforming. The selected rigid points are then used to compute frame-wise shape registration and to extract the motion parameters robustly from frame to frame. Finally, all this information is used in a global optimization stage with bundle adjustment which allows to refine the frame-wise initial solution and also to recover the non-rigid 3D model. We show results on synthetic and real data that prove the performance of the proposed method even when there is no rigid motion in the original sequence

Monocular-based 3-D seafloor reconstruction and ortho-mosaicing by piecewise planar representation

Photo-mosaicing techniques have become popular for seafloor mapping in various marine science applications. However, the common methods cannot accurately map regions with high relief and topographical variations. Ortho-mosaicing borrowed from photogrammetry is an alternative technique that enables taking into account the 3-D shape of the terrain. A serious bottleneck is the volume of elevation information that needs to be estimated from the video data, fused, and processed for the generation of a composite ortho-photo that covers a relatively large seafloor area. We present a framework that combines the advantages of dense depth-map and 3-D feature estimation techniques based on visual motion cues. The main goal is to identify and reconstruct certain key terrain feature points that adequately represent the surface with minimal complexity in the form of piecewise planar patches. The proposed implementation utilizes local depth maps for feature selection, while tracking over several views enables 3-D reconstruction by bundle adjustment. Experimental results with synthetic and real data validate the effectiveness of the proposed approach

Desenlaces de las infecciones respiratorias en la unidad de cuidado intensivo de la fundación neumologica colombiana

Las infecciones asociadas a ventilación mecánica (VM) son frecuentes en la unidad de cuidado intensivo (UCI). Existen dos infecciones: neumonía (NAV) y traqueobronquitis (TAV). NAV genera impacto negativo en los desenlaces de los pacientes al aumentar la morbilidad, mortalidad y los tiempos en UCI y VM, pero no se conoce el impacto de TAV. El objetivo de este estudio fue identificar si hay diferencias entre NAV y TAV. Materiales y métodos: Se realizó un estudio de cohortes entre 2009 y 2013 en la UCI de la Fundación Neumológica Colombiana. De los pacientes con NAV y TAV se obtuvieron datos demográficos, epidemiológicos, microbiológicos y desenlaces como tiempos de estancia en UCI, VM y de hospitalización y mortalidad. Se compararon estadísticamente mediante t de Student y Chi2 para datos normales y prueba de Mann-Whitney para datos no normales. Resultados: Los pacientes con NAV y TAV fueron similares en la condición de ingreso a UCI. Al diagnóstico de la infección hubo diferencias significativas entre grupos en la oxigenación y tiempo de estancia hospitalaria, en UCI y VM. La microbiología fue con predominio de gérmenes Gram negativos y presencia de multirresistencia en el 52.5% de casos, sin diferencias significativas entre grupos. En los desenlaces, se observó diferencias en los tiempos totales de estancia en UCI, hospitalización y VM, pero sin diferencia en ellos después del diagnóstico. No hubo diferencias significativas en mortalidad. Conclusiones: NAV y TAV son similares en el impacto sobre la evolución de los pacientes en cuanto a morbilidad, estancias y mortalidad.

Efficient topology estimation for large scale optical mapping

Large scale image mosaicing methods are in great demand among scientists who study different aspects of the seabed, and have been fostered by impressive advances in the capabilities of underwater robots in gathering optical data from the seafloor. Cost and weight constraints mean that lowcost Remotely operated vehicles (ROVs) usually have a very limited number of sensors. When a low-cost robot carries out a seafloor survey using a down-looking camera, it usually follows a predetermined trajectory that provides several non time-consecutive overlapping image pairs. Finding these pairs (a process known as topology estimation) is indispensable to obtaining globally consistent mosaics and accurate trajectory estimates, which are necessary for a global view of the surveyed area, especially when optical sensors are the only data source. This thesis presents a set of consistent methods aimed at creating large area image mosaics from optical data obtained during surveys with low-cost underwater vehicles. First, a global alignment method developed within a Feature-based image mosaicing (FIM) framework, where nonlinear minimisation is substituted by two linear steps, is discussed. Then, a simple four-point mosaic rectifying method is proposed to reduce distortions that might occur due to lens distortions, error accumulation and the difficulties of optical imaging in an underwater medium. The topology estimation problem is addressed by means of an augmented state and extended Kalman filter combined framework, aimed at minimising the total number of matching attempts and simultaneously obtaining the best possible trajectory. Potential image pairs are predicted by taking into account the uncertainty in the trajectory. The contribution of matching an image pair is investigated using information theory principles. Lastly, a different solution to the topology estimation problem is proposed in a bundle adjustment framework. Innovative aspects include the use of fast image similarity criterion combined with a Minimum spanning tree (MST) solution, to obtain a tentative topology. This topology is improved by attempting image matching with the pairs for which there is the most overlap evidence. Unlike previous approaches for large-area mosaicing, our framework is able to deal naturally with cases where time-consecutive images cannot be matched successfully, such as completely unordered sets. Finally, the efficiency of the proposed methods is discussed and a comparison made with other state-of-the-art approaches, using a series of challenging datasets in underwater scenarios

Consumer willingness to pay for in-flight service and comfort levels: A choice experiment

In the competitive aviation market as a result of the emergence of low cost carriers, charter airlines have had to reconsider their approach to service provision. Specifically, the reduction in service and comfort levels offered by the low cost airlines provides charter carriers with an opportunity to differentiate their product based on the quality of the offering. To consider this strategic option we employ an on-line choice experiment to examine consumer choices with respect to the bundle of services on offer when deciding to purchase a flight, With these data we use the Bayesian methods to estimate a mixed logit specification. Our results reveal that in principle passengers are willing to pay a relatively large amount for enhanced service quality. (C) 2008 Elsevier Ltd. All rights reserved.

Use of a novel Hill-climbing genetic algorithm in protein folding simulations

We have developed a novel Hill-climbing genetic algorithm (GA) for simulation of protein folding. The program (written in C) builds a set of Cartesian points to represent an unfolded polypeptide's backbone. The dihedral angles determining the chain's configuration are stored in an array of chromosome structures that is copied and then mutated. The fitness of the mutated chain's configuration is determined by its radius of gyration. A four-helix bundle was used to optimise simulation conditions, and the program was compared with other, larger, genetic algorithms on a variety of structures. The program ran 50% faster than other GA programs. Overall, tests on 100 non-redundant structures gave comparable results to other genetic algorithms, with the Hill-climbing program running from between 20 and 50% faster. Examples including crambin, cytochrome c, cytochrome B and hemerythrin gave good secondary structure fits with overall alpha carbon atom rms deviations of between 5 and 5.6 Angstrom with an optimised hydrophobic term in the fitness function. (C) 2003 Elsevier Ltd. All rights reserved.

The geometry of optimal control solutions on some six dimensional lie groups

This paper examines optimal solutions of control systems with drift defined on the orthonormal frame bundle of particular Riemannian manifolds of constant curvature. The manifolds considered here are the space forms Euclidean space E-3, the spheres S-3 and the hyperboloids H-3 with the corresponding frame bundles equal to the Euclidean group of motions SE(3), the rotation group SO(4) and the Lorentz group SO(1,3). The optimal controls of these systems are solved explicitly in terms of elliptic functions. In this paper, a geometric interpretation of the extremal solutions is given with particular emphasis to a singularity in the explicit solutions. Using a reduced form of the Casimir functions the geometry of these solutions are illustrated.

Integrating Hamiltonian systems defined on the Lie groups SO(4) and SO(1,3)

This paper examines optimal solutions of control systems with drift defined on the orthonormal frame bundle of particular Riemannian manifolds of constant curvature. The manifolds considered here are the space forms Euclidean space E³, the spheres S³ and the hyperboloids H³ with the corresponding frame bundles equal to the Euclidean group of motions SE(3), the rotation group SO(4) and the Lorentz group SO(1,3). The optimal controls of these systems are solved explicitly in terms of elliptic functions. In this paper, a geometric interpretation of the extremal solutions is given with particular emphasis to a singularity in the explicit solutions. Using a reduced form of the Casimir functions the geometry of these solutions is illustrated.