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].

Modélisation procédurale par composants

Le réalisme des images en infographie exige de créer des objets (ou des scènes) de plus en plus complexes, ce qui entraîne des coûts considérables. La modélisation procédurale peut aider à automatiser le processus de création, à simplifier le processus de modification ou à générer de multiples variantes d'une instance d'objet. Cependant même si plusieurs méthodes procédurales existent, aucune méthode unique permet de créer tous les types d'objets complexes, dont en particulier un édifice complet. Les travaux réalisés dans le cadre de cette thèse proposent deux solutions au problème de la modélisation procédurale: une solution au niveau de la géométrie de base, et l’autre sous forme d'un système général adapté à la modélisation des objets complexes. Premièrement, nous présentons le bloc, une nouvelle primitive de modélisation simple et générale, basée sur une forme cubique généralisée. Les blocs sont disposés et connectés entre eux pour constituer la forme de base des objets, à partir de laquelle est extrait un maillage de contrôle pouvant produire des arêtes lisses et vives. La nature volumétrique des blocs permet une spécification simple de la topologie, ainsi que le support des opérations de CSG entre les blocs. La paramétrisation de la surface, héritée des faces des blocs, fournit un soutien pour les textures et les fonctions de déplacements afin d'appliquer des détails de surface. Une variété d'exemples illustrent la généralité des blocs dans des contextes de modélisation à la fois interactive et procédurale. Deuxièmement, nous présentons un nouveau système de modélisation procédurale qui unifie diverses techniques dans un cadre commun. Notre système repose sur le concept de composants pour définir spatialement et sémantiquement divers éléments. À travers une série de déclarations successives exécutées sur un sous-ensemble de composants obtenus à l'aide de requêtes, nous créons un arbre de composants définissant ultimement un objet dont la géométrie est générée à l'aide des blocs. Nous avons appliqué notre concept de modélisation par composants à la génération d'édifices complets, avec intérieurs et extérieurs cohérents. Ce nouveau système s'avère général et bien adapté pour le partionnement des espaces, l'insertion d'ouvertures (portes et fenêtres), l'intégration d'escaliers, la décoration de façades et de murs, l'agencement de meubles, et diverses autres opérations nécessaires lors de la construction d'un édifice complet.

Patrons de distribution des crustacés planctoniques dans le fleuve Saint-Laurent

La recherche porte sur les patrons de distribution longitudinale (amont-aval) et transversale (rive nord - rive sud) des communautés de crustacés planctoniques qui ont été analysés le long du fleuve Saint-Laurent entre le lac Saint-François et la zone de transition estuarienne, à deux hydropériodes en mai (crue) et en août (étiage). Les données zooplanctoniques et environnementales ont été récoltées à 52 stations réparties sur 16 transects transversaux en 2006. Au chapitre 1, nous présentons les principaux modèles écosystémiques en rivière, une synthèse des facteurs influençant le zooplancton en rivières et les objectifs et hypothèses de recherche. Au chapitre 2, nous décrivons la structure des communautés de zooplancton dans trois zones biogéographiques du fleuve et 6 habitats longitudinaux, ainsi que les relations entre la structure du zooplancton et la distribution spatiale des masses d’eau et les variables environnementales. Au chapitre 3, nous réalisons une partition de la variation des variables spatiales AEM (basées sur la distribution des masses d’eau) et des variables environnementales pour évaluer quelle part de la variation du zooplancton est expliquée par les processus hydrologiques (variables AEM) et les conditions locales (facteurs environnementaux). Le gradient salinité-conductivité relié à la discontinuité fleuve-estuaire a déterminé la distribution à grande échelle du zooplancton. Dans les zones fluviales, la distribution du zooplancton est davantage influencée par la distribution des masses d’eau que par les facteurs environnementaux locaux. La distribution des masses d’eau explique une plus grande partie de la variation dans la distribution du zooplancton en août qu’en mai.

Heuristiques efficaces pour l'optimisation de la performance des systèmes séries-parallèles

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

Impact des perturbations anthropiques sur la végétation du complexe de milieux humides des Tourbières-de-Lanoraie

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

Investigation of the structure and dynamics of the centromeric epigenetic mark

Le centromère est le site chromosomal où le kinetochore se forme, afin d’assurer une ségrégation fidèles des chromosomes et ainsi maintenir la ploïdie appropriée lors de la mitose. L’identité du centromere est héritée par un mécanisme épigénétique impliquant une variante de l’histone H3 nommée centromere protein-A (CENP-A), qui remplace l’histone H3 au niveau de la chromatine du centromère. Des erreurs de propagation de la chromatine du centromère peuvent mener à des problèmes de ségrégation des chromosomes, pouvant entraîner l’aneuploïdie, un phénomène fréquemment observé dans le cancer. De plus, une expression non-régulée de CENP-A a aussi été rapportée dans différentes tumeurs humaines. Ainsi, plusieurs études ont cherchées à élucider la structure et le rôle de la chromatine contenant CENP-A dans des cellules en prolifération. Toutefois, la nature moléculaire de CENP-A en tant que marqueur épigénétique ainsi que ces dynamiques à l'extérieur du cycle cellulaire demeurent des sujets débat. Dans cette thèse, une nouvelle méthode de comptage de molécules uniques à l'aide de la microscopie à réflexion totale interne de la fluorescence (TIRF) sera décrite, puis exploitée afin d'élucider la composition moléculaire des nucléosomes contenant CENP-A, extraits de cellules en prolifération. Nous démontrons que les nucléosomes contenant CENP-A marquent les centromères humains de façon épigénétique à travers le cycle cellulaire. De plus, nos données démontrent que la forme prénucléosomale de CENP-A, en association avec la protéine chaperon HJURP existe sous forme de monomère et de dimère, ce qui reflète une étape intermédiaire de l'assemblage de nucléosomes contenant CENP-A. Ensuite, des analyses quantitatives de centromères lors de différenciation myogénique, et dans différents tissus adultes révèlent des changements globaux qui maintiennent la marque épigénétique dans une forme inactive suite à la différentiation terminale. Ces changements incluent une réduction du nombre de points focaux de CENP-A, un réarrangement des points dans le noyau, ainsi qu'une réduction importante de la quantité de CENP-A. De plus, nous démontrons que lorsqu'une dédifférenciation cellulaire est induite puis le cycle cellulaire ré-entamé, le phénotype "différencié" décrit ci-haut est récupéré, et les centromères reprennent leur phénotype "prolifératif". En somme, cet oeuvre décrit la composition structurale sous-jacente à l'identité épigénétique des centromères de cellules humaines lors du cycle cellulaire, et met en lumière le rôle de CENP-A à l'extérieur du cycle cellulaire.

Dynamique des communautés végétales et impacts des perturbations humaines sur la végétation des tourbières.

Ce mémoire visait à comprendre la dynamique temporelle et les patrons floristiques actuels de deux tourbières du sud-ouest du Québec (Small et Large Tea Field) et à identifier les facteurs anthropiques, environnementaux et spatiaux sous-jacents. Pour répondre aux objectifs, des inventaires floristiques anciens (1985) ont d’abord été comparés à des inventaires récents (2012) puis les patrons actuels et les facteurs sous-jacents ont été identifiés à l’aide d’analyses multi-variables. Mes résultats montrent d’abord qu’un boisement important s’est produit au cours des 30 dernières années dans les tourbières à l’étude, probablement en lien avec le drainage des terres agricoles avoisinantes, diminuant la hauteur de la nappe phréatique. Simultanément, les sphaignes ont proliférées dans le centre des sites s’expliquant par une recolonisation des secteurs ayant brûlés en 1983. D’autre part, mes analyses ont montré que les patrons floristiques actuels étaient surtout liés aux variables environnementales (pH et conductivité de l’eau, épaisseur des dépôts), bien que la variance associée aux activités humaines était aussi significative, notamment dans la tourbière Large (18.6%). Les patrons floristiques ainsi que les variables environnementales et anthropiques explicatives étaient aussi fortement structurés dans l’espace, notamment selon un gradient bordure-centre. Enfin, la diversité béta actuelle était surtout liée à la présence d’espèces non-tourbicoles ou exotiques. Globalement, cette étude a montré que les perturbations humaines passées et actuelles avaient un impact important sur la dynamique et la distribution de la végétation des tourbières Small et Large Tea Field.

Features of neighbourhood environments associated with obesity and related health behaviours in children: using multiple statistical approaches to identify obesogenic environments

Contexte: L'obésité chez les jeunes représente aujourd’hui un problème de santé publique à l’échelle mondiale. Afin d’identifier des cibles potentielles pour des stratégies populationnelles de prévention, les liens entre les caractéristiques du voisinage, l’obésité chez les jeunes et les habitudes de vie font de plus en plus l’objet d’études. Cependant, la recherche à ce jour comporte plusieurs incohérences. But: L’objectif général de cette thèse est d’étudier la contribution de différentes caractéristiques du voisinage relativement à l’obésité chez les jeunes et les habitudes de vie qui y sont associées. Les objectifs spécifiques consistent à: 1) Examiner les associations entre la présence de différents commerces d’alimentation dans les voisinages résidentiels et scolaires des enfants et leurs habitudes alimentaires; 2) Examiner comment l’exposition à certaines caractéristiques du voisinage résidentiel détermine l’obésité au niveau familial (chez le jeune, la mère et le père), ainsi que l’obésité individuelle pour chaque membre de la famille; 3) Identifier des combinaisons de facteurs de risque individuels, familiaux et du voisinage résidentiel qui prédisent le mieux l’obésité chez les jeunes, et déterminer si ces profils de facteurs de risque prédisent aussi un changement dans l’obésité après un suivi de deux ans. Méthodes: Les données proviennent de l’étude QUALITY, une cohorte québécoise de 630 jeunes, âgés de 8-10 ans au temps 1, avec une histoire d’obésité parentale. Les voisinages de 512 participants habitant la Région métropolitaine de Montréal ont été caractérisés à l’aide de : 1) données spatiales provenant du recensement et de bases de données administratives, calculées pour des zones tampons à partir du réseau routier et centrées sur le lieu de la résidence et de l’école; et 2) des observations menées par des évaluateurs dans le voisinage résidentiel. Les mesures du voisinage étudiées se rapportent aux caractéristiques de l’environnement bâti, social et alimentaire. L’obésité a été estimée aux temps 1 et 2 à l’aide de l’indice de masse corporelle (IMC) calculé à partir du poids et de la taille mesurés. Les habitudes alimentaires ont été mesurées au temps 1 à l'aide de trois rappels alimentaires. Les analyses effectuées comprennent, entres autres, des équations d'estimation généralisées, des régressions multiniveaux et des analyses prédictives basées sur des arbres de décision. Résultats: Les résultats démontrent la présence d’associations avec l’obésité chez les jeunes et les habitudes alimentaires pour certaines caractéristiques du voisinage. En particulier, la présence de dépanneurs et de restaurants-minutes dans le voisinage résidentiel et scolaire est associée avec de moins bonnes habitudes alimentaires. La présence accrue de trafic routier, ainsi qu’un faible niveau de prestige et d’urbanisation dans le voisinage résidentiel sont associés à l’obésité familiale. Enfin, les résultats montrent qu’habiter un voisinage obésogène, caractérisé par une défavorisation socioéconomique, la présence de moins de parcs et de plus de dépanneurs, prédit l'obésité chez les jeunes lorsque combiné à la présence de facteurs de risque individuels et familiaux. Conclusion: Cette thèse contribue aux écrits sur les voisinages et l’obésité chez les jeunes en considérant à la fois l'influence potentielle du voisinage résidentiel et scolaire ainsi que l’influence de l’environnement familial, en utilisant des méthodes objectives pour caractériser le voisinage et en utilisant des méthodes statistiques novatrices. Les résultats appuient en outre la notion que les efforts de prévention de l'obésité doivent cibler les multiples facteurs de risque de l'obésité chez les jeunes dans les environnements bâtis, sociaux et familiaux de ces jeunes.

Distributed conditional computation

L'objectif de cette thèse est de présenter différentes applications du programme de recherche de calcul conditionnel distribué. On espère que ces applications, ainsi que la théorie présentée ici, mènera à une solution générale du problème d'intelligence artificielle, en particulier en ce qui a trait à la nécessité d'efficience. La vision du calcul conditionnel distribué consiste à accélérer l'évaluation et l'entraînement de modèles profonds, ce qui est très différent de l'objectif usuel d'améliorer sa capacité de généralisation et d'optimisation. Le travail présenté ici a des liens étroits avec les modèles de type mélange d'experts. Dans le chapitre 2, nous présentons un nouvel algorithme d'apprentissage profond qui utilise une forme simple d'apprentissage par renforcement sur un modèle d'arbre de décisions à base de réseau de neurones. Nous démontrons la nécessité d'une contrainte d'équilibre pour maintenir la distribution d'exemples aux experts uniforme et empêcher les monopoles. Pour rendre le calcul efficient, l'entrainement et l'évaluation sont contraints à être éparse en utilisant un routeur échantillonnant des experts d'une distribution multinomiale étant donné un exemple. Dans le chapitre 3, nous présentons un nouveau modèle profond constitué d'une représentation éparse divisée en segments d'experts. Un modèle de langue à base de réseau de neurones est construit à partir des transformations éparses entre ces segments. L'opération éparse par bloc est implémentée pour utilisation sur des cartes graphiques. Sa vitesse est comparée à deux opérations denses du même calibre pour démontrer le gain réel de calcul qui peut être obtenu. Un modèle profond utilisant des opérations éparses contrôlées par un routeur distinct des experts est entraîné sur un ensemble de données d'un milliard de mots. Un nouvel algorithme de partitionnement de données est appliqué sur un ensemble de mots pour hiérarchiser la couche de sortie d'un modèle de langage, la rendant ainsi beaucoup plus efficiente. Le travail présenté dans cette thèse est au centre de la vision de calcul conditionnel distribué émis par Yoshua Bengio. Elle tente d'appliquer la recherche dans le domaine des mélanges d'experts aux modèles profonds pour améliorer leur vitesse ainsi que leur capacité d'optimisation. Nous croyons que la théorie et les expériences de cette thèse sont une étape importante sur la voie du calcul conditionnel distribué car elle cadre bien le problème, surtout en ce qui concerne la compétitivité des systèmes d'experts.

Lier la spéciation chimique du cérium à sa biodisponibilité sous différentes conditions environnementales

L’étude qui suit porte sur l’évaluation du risque écotoxicologique du cérium, l’élément le plus exploité de la famille des lanthanides. La présence grandissante de ce métal dans notre quotidien rend possible son relargage dans l’environnement. Il est donc primordial de comprendre l’impact qu’il aura sur les organismes vivant dans un système aquatique. Une approche centrée sur le modèle du ligand biotique a été utilisée pour évaluer adéquatement l’interaction entre le cérium et un ligand biotique à la surface de l’algue unicellulaire Chlamydomonas reinhardtii. Pour mener une étude sur le risque écotoxicologique d’un élément métallique il faut, avant tout, comprendre la spéciation (répartition sous ses différentes formes chimiques) de l’élément en question. Les premières sections du mémoire vont donc traiter des expériences qui ont été menées pour évaluer la spéciation du cérium dans les conditions expérimentales d’exposition à C. reinhardtii. Il sera question de faire la distinction entre la forme particulaire du métal et sa forme dissoute, de caractériser ces changements par spectroscopie ainsi que d’évaluer le pouvoir complexant de la matière organique naturelle. Les résultats montrent une importante déplétion du métal dissout en solution à pH neutre et basique et une forte interaction avec la matière organique naturelle, peu importe le pH de la solution. Ensuite, les expériences de bioaccumulation seront expliquéesen comparant l’effet du pH, de la présence d’un ion compétiteur et de la présence de matière organique naturelle sur les paramètres d’internalisation du cérium. Les résultats indiquent qu’à pH acide, le comportement du cérium est plus prévisible qu’à pH neutre. Néanmoins, en tenant compte de la complexité des milieux naturels, l’interaction du métal avec les molécules complexantes va diminuer son risque d’interaction avec un organisme vivant.

The berth allocation problem at port terminals : a column generation framework

Le problème d'allocation de postes d'amarrage (PAPA) est l'un des principaux problèmes de décision aux terminaux portuaires qui a été largement étudié. Dans des recherches antérieures, le PAPA a été reformulé comme étant un problème de partitionnement généralisé (PPG) et résolu en utilisant un solveur standard. Les affectations (colonnes) ont été générées a priori de manière statique et fournies comme entrée au modèle %d'optimisation. Cette méthode est capable de fournir une solution optimale au problème pour des instances de tailles moyennes. Cependant, son inconvénient principal est l'explosion du nombre d'affectations avec l'augmentation de la taille du problème, qui fait en sorte que le solveur d'optimisation se trouve à court de mémoire. Dans ce mémoire, nous nous intéressons aux limites de la reformulation PPG. Nous présentons un cadre de génération de colonnes où les affectations sont générées de manière dynamique pour résoudre les grandes instances du PAPA. Nous proposons un algorithme de génération de colonnes qui peut être facilement adapté pour résoudre toutes les variantes du PAPA en se basant sur différents attributs spatiaux et temporels. Nous avons testé notre méthode sur un modèle d'allocation dans lequel les postes d'amarrage sont considérés discrets, l'arrivée des navires est dynamique et finalement les temps de manutention dépendent des postes d'amarrage où les bateaux vont être amarrés. Les résultats expérimentaux des tests sur un ensemble d'instances artificielles indiquent que la méthode proposée permet de fournir une solution optimale ou proche de l'optimalité même pour des problème de très grandes tailles en seulement quelques minutes.

Impacts de l'urbanisation sur la diversité spécifique et fonctionnelle dans les forêts riveraines

L'urbanisation représente une menace majeure pour la biodiversité. Ce mémoire de maîtrise vise à comprendre ses effets sur la composition fonctionnelle et l'homogénéisation biotique dans les forêts riveraines. Des inventaires floristiques ont été réalisés dans 57 forêts riveraines de la région de Montréal. Afin d'étudier la variation de la composition fonctionnelle avec l'urbanisation, des moyennes pondérées de traits par communauté ont été calculées pour les arbres, arbustes et herbacées. Chaque forêt a été caractérisée par des variables relatives au paysage urbain environnant, aux conditions locales des forêts et aux processus spatiaux. Les conditions locales, notamment les inondations, exerçaient une pression de sélection dominante sur les traits. L'effet du paysage était indirect, agissant via l'altération des régimes hydrologiques. La dispersion le long des rivières était aussi un processus important dans la structuration des forêts riveraines. Les changements dans la diversité β taxonomique et fonctionnelle des herbacées ont été étudiés entre trois niveaux d'urbanisation et d'inondation. Alors que l'urbanisation a favorisé une différenciation taxonomique, les inondations ont favorisé une homogénéisation taxonomique, sans influencer la diversité β fonctionnelle. L'urbanisation était l'élément déclencheur des changements de la diversité β, directement, en causant un gain en espèces exotiques et une diminution de la richesse totale dans les forêts très urbanisées, et, indirectement, en entraînant un important turnover d'espèces par l'altération des régimes hydrologiques. Globalement, ces résultats suggèrent que la modification des processus naturels par les activités anthropiques est le principal moteur de changements dans les communautés riveraines urbaines.

Quantum suppression of shot noise in field emitters

We have analyzed the shot noise of electron emission under strong applied electric fields within the Landauer-Bttiker scheme. In contrast to the previous studies of vacuum-tube emitters, we show that in new generation electron emitters, scaled down to the nanometer dimensions, shot noise much smaller than the Schottky noise is observable. Carbon nanotube field emitters are among possible candidates to observe the effect of shot-noise suppression caused by quantum partitioning.

Decimation Filter Design Toolbox for Multi-Standard Wireless Transceivers using MATLAB.

The demand for new telecommunication services requiring higher capacities, data rates and different operating modes have motivated the development of new generation multi-standard wireless transceivers. A multi-standard design often involves extensive system level analysis and architectural partitioning, typically requiring extensive calculations. In this research, a decimation filter design tool for wireless communication standards consisting of GSM, WCDMA, WLANa, WLANb, WLANg and WiMAX is developed in MATLAB® using GUIDE environment for visual analysis. The user can select a required wireless communication standard, and obtain the corresponding multistage decimation filter implementation using this toolbox. The toolbox helps the user or design engineer to perform a quick design and analysis of decimation filter for multiple standards without doing extensive calculation of the underlying methods.

Channel Adaptive MAC Protocol with Traffic-Aware Distributed Power Management in Wireless Sensor Networks-Some Performance Issues

In Wireless Sensor Networks (WSN), neglecting the effects of varying channel quality can lead to an unnecessary wastage of precious battery resources and in turn can result in the rapid depletion of sensor energy and the partitioning of the network. Fairness is a critical issue when accessing a shared wireless channel and fair scheduling must be employed to provide the proper flow of information in a WSN. In this paper, we develop a channel adaptive MAC protocol with a traffic-aware dynamic power management algorithm for efficient packet scheduling and queuing in a sensor network, with time varying characteristics of the wireless channel also taken into consideration. The proposed protocol calculates a combined weight value based on the channel state and link quality. Then transmission is allowed only for those nodes with weights greater than a minimum quality threshold and nodes attempting to access the wireless medium with a low weight will be allowed to transmit only when their weight becomes high. This results in many poor quality nodes being deprived of transmission for a considerable amount of time. To avoid the buffer overflow and to achieve fairness for the poor quality nodes, we design a Load prediction algorithm. We also design a traffic aware dynamic power management scheme to minimize the energy consumption by continuously turning off the radio interface of all the unnecessary nodes that are not included in the routing path. By Simulation results, we show that our proposed protocol achieves a higher throughput and fairness besides reducing the delay