identifier: Chidambaram, S. (2019). PoET-BiN: Power Efficient Tiny Binary Neurons  [Mémoire de maîtrise, Polytechnique Montréal].

abstract: RÉSUMÉ: Le succès des réseaux de neurones dans la classification des images a inspiré diverses implémentations matérielles sur des systèmes embarqués telles que des FPGAs, des processeurs embarqués et des unités de traitement graphiques. Ces systèmes sont souvent limités en termes de puissance. Toutefois, les réseaux de neurones consomment énormément à travers les opérations de multiplication/accumulation et des accès mémoire pour la récupération des poids. La quantification et l'élagage ont été proposés pour résoudre ce problème. Bien que efficaces, ces techniques ne prennent pas en compte l'architecture sous-jacente du matériel utilisé. Dans ce travail, nous proposons une implémentation économe en énergie, basée sur une table de vérité, d'un neurone binaire sur des systèmes embarqués à ressources limitées. Une approche d'arbre de décision modifiée constitue le fondement de la mise en œuvre proposée dans le domaine binaire. Un accès de LUT consomme beaucoup moins d'énergie que l'opération équivalente de multiplication/accumulation qu'il remplace. De plus, l'algorithme modifié de l'arbre de décision élimine le besoin d'accéder à la mémoire. Nous avons utilisé les neurones binaires proposés pour mettre en œuvre la couche de classification de réseaux utilisés pour la résolution des jeux de données MNIST, SVHN et CIFAR-10, avec des résultats presque à la pointe de la technologie. La réduction de puissance pour la couche de classification atteint trois ordres de grandeur pour l'ensemble de données MNIST et cinq ordres de grandeur pour les ensembles de données SVHN et CIFAR-10.  ABSTRACT: The success of neural networks in image classification has inspired various hardware implementations on embedded platforms such as Field Programmable Gate Arrays, embedded processors and Graphical Processing Units. These embedded platforms are constrained in terms of power, which is mainly consumed by the Multiply Accumulate operations and the memory accesses for weight fetching. Quantization and pruning have been proposed to ad-dress this issue. Though effective, these techniques do not take into account the underlying architecture of the embedded hardware. In this work, we propose PoET-BiN, a Look-Up Table based power efficient implementation on resource constrained embedded devices. A modified Decision Tree approach forms the backbone of the proposed implementation in the binary domain. A LUT access consumes far less power than the equivalent Multiply Accumulate operation it replaces, and the modified Decision Tree algorithm eliminates the need for memory accesses. We applied the PoET-BiN architecture to implement the classification layers of networks trained on MNIST, SVHN and CIFAR-10 datasets, with near state-of-the art results. The energy reduction for the classifier portion reaches up to six orders of magnitude compared to a floating point implementations and up to three orders of magnitude when compared to recent binary quantized neural networks.


identifier: Nolet-Gravel, É. (2019). Changements projetés des précipitations extrêmes au Québec  [Mémoire de maîtrise, Polytechnique Montréal].

type:
Mémoire ou thèse
NonPeerReviewed

abstract: RÉSUMÉ: Le Québec fait partie des régions dans le monde dont les événements de précipitations intenses sont susceptibles d'augmenter considérablement si le réchauffement climatique passe de 1.5°C à 2°C. Les impacts d'événements de pluies intenses sont nombreux et peuvent affecter gravement la santé et l'économie d'une population. Il est donc très important d'estimer adéquatement les précipitations extrêmes dans le futur. Les courbes Intensité-Durée-Fréquence (IDF) permettent d'analyser le risque associé aux événements de pluies intenses. Elles servent notamment pour le dimensionnement des infrastructures exposées aux aléas du climat et à la définition des zones inondables. Pour l'instant, Environnement et Changement climatique Canada (ECCC) fourni les courbes IDF les plus utilisées au pays et suppose que les événements de pluies intenses sont stationnaires dans le temps. Cela signifie qu'ECCC considère que le comportement d'une série de précipitations extrêmes demeure inchangé à travers le temps. Par conséquent, l'objectif du projet est d'introduire les effets des changements climatiques dans les courbes IDF au Québec en incorporant la non-stationnarité due au climat dans la modélisation des séries de précipitations extrêmes. Pour modéliser les extrêmes climatiques de manière non stationnaire, il faut se tourner vers les modèles numériques de climat afin d'estimer les effets des changements climatiques. Ces modèles permettent de faire des projections quantitatives du climat futur. En particulier, les modèles climatiques régionaux permettent de simuler le climat à petite résolution spatiale, puisqu'ils sont limités à un région du globe seulement. Pour ce mémoire, l'ensemble de simulations ClimEx a été utilisé. Ce dernier exploite la cinquième version du Modèle Régional Canadien du Climat ainsi que le scénario RCP8.5 pour les émissions de gaz à effet de serre et d'aérosols. Pour atteindre notre objectif, un modèle hiérarchique bayésien a été développé afin de synthétiser la nonstationnarité contenue dans les séries de précipitations extrêmes de ClimEx. La concentration annuelle des gaz à effet de serre pondérés selon leur pouvoir de réchauffement planétaire a servi de variable explicative dans le modèle pour incorporer les effets des changements climatiques. Un facteur de correction, à appliquer ultérieurement sur les courbes IDF, a été calculé pour une cellule en particulier et permet de voir l'augmentation des niveaux de retour.  ABSTRACT: Extreme precipitations events are expected to increase substantially in the province of Quebec if the global warming goes from 1.5°C to 2°C. Intense rainfall can have big consequences on the health and the economy of a population. Therefore, it is important to obtain accurate estimates of the extreme precipitations to expect in the future. Intensity-Duration-Frequency (IDF) curves represent the main tool to analyse the risk associated to intense rainfall events. They are used for the design of infrastructures exposed to climate hazards and to define flood plains. In Canada, the most used IDF curves are the one provided by Environment and Climate Change Canada (ECCC), which considers extreme precipitations events as stationary processes, meaning their behavior remains unchanged over the years. This project has the goal of introducing the effects of climate change into the estimation of IDF curves in Quebec by adding non-stationarity into extreme precipitations series. Numerical climate models will be very useful to model climate extremes by non-stationary processes. Climate models make quantitative projections of the climate to come. More precisely, regional climate models are restricted to a region of the world and can therefore simulate the climate for a small domain. For this research, the set of simulations ClimEx was utilized. It uses the 5th version of the Canadian Regional Climate Model and the scenario RCP8.5 for the greenhouse gases and aerosols emissions. A bayesian hierarchical model was developed to synthesize the nonstationarity contained in the ClimEx dataset. To incorporate the effects of climate change, the greenhouse gases concentration weighted by their global warming potential was used as a covariate in the model. A correction factor was calculated for a cell to update IDF curves and it shows that the return levels are increasing over the period.


identifier: Lajoie, P.-Y. (2019). Simultaneous Localization and Mapping Systems Robust to Perceptual Aliasing  [Mémoire de maîtrise, Polytechnique Montréal].

abstract: RÉSUMÉ: De nos jours, la robotique gagne rapidement en popularité et promet un large éventail de nouvelles applications. Bien que le marché actuel soit dominé par les robots téléguidés, plusieurs compagnies cherchent à révolutionner notre quotidien avec des robots pleinement autonomes comme les voitures sans conducteur. En effet, les géants des technologies de partout dans le monde nous promettent régulièrement de nouvelles percées extraordinaires au niveau de l'autonomie des robots et multiplient des démonstrations plus impressionnantes les unes que les autres. Toutefois, ces systèmes autonomes devront se prouver extrêmement fiables et sécuritaires afin d'obtenir l'acceptabilité sociale nécessaire à leur succès. Malheureusement, les techniques présentement offertes par la littérature scientifique n'ont pas un niveau de robustesse à la hauteur des attentes de la population. C'est pourquoi les chercheurs universitaires et industriels doivent redoubler d'efforts afin de trouver de meilleures solutions qui sauront inspirer la confiance du public envers les systèmes robotiques autonomes. En particulier, une des composantes cruciales de tels systèmes est la localisation du robot dans son environnement. Cette composante est essentielle pour le déploiement de robots dans des environnements sans GPS (ex. à l'intérieur, sous terre, sous l'eau, etc.), puisque dans ces situations un robot doit estimer précisément sa position sur la seule base des mesures extraites à partir de ses propres senseurs. Pour y parvenir, une des techniques les plus populaires est la cartographie et localisation simultanée (SLAM) lors de laquelle un robot construit une carte de son environnement afin de suivre et estimer son propre mouvement et sa position. Cette technique est efficace, mais elle est tout de même vulnérable aux erreurs d'association et à la présence de mesures aberrantes. Les ingénieurs contournent généralement ce problème en performant une calibration très précise. Une telle calibration spécifique à l'environnement d'opération est appropriée pour des environnements très contrôlés comme ceux qu'on retrouve dans les laboratoires de recherche. Par contre, cette solution n'est pas viable pour des systèmes robotiques vendus au grand public et opérés par des utilisateurs sans formation. Une des principales causes d'erreurs en cartographie et localisation simultanée est l'aliasing perceptuel. Ce phénomène engendre des mesures aberrantes lorsqu'un robot confond deux endroits différents comme étant le même. L'addition de mesures aberrantes dans l'estimateur mène généralement à l'échec complet du système et donc possiblement à des conséquences dramatiques en termes de sécurité. Afin d'offrir des solutions à ces enjeux de robustesse, ce mémoire propose deux contributions à la littérature scientifique. La première introduit une nouvelle formulation pour le problème d'optimisation au coeur de la cartographie et localisation simultanée. Cette nouvelle formulation inclut un modèle explicite du phénomène d'aliasing perceptuel de façon à rejeter efficacement les mesures aberrantes. La seconde présente une nouvelle méthode de cartographie et localisation simultanée pour systèmes multi-robot qui est distribuée et robuste aux mesures aberrantes. Cette contribution est particulièrement importante puisque les systèmes multi-robots sont davantage vulnérables à l'aliasing perceptuel que les systèmes avec un seul robot. Plusieurs résultats expérimentaux obtenus lors de simulations, avec des jeux de données réelles et sur le terrain montrent que les techniques proposées produisent des estimés précis de localisation en présence de mesures aberrantes.  ABSTRACT: Autonomous robotics is growing fast in popularity and has a large range of potential new applications. While the current market is dominated by human-controlled robots, many companies aim to revolutionize our daily lives by focusing on autonomous robotic platforms such as self-driving cars. Indeed, companies around the world regularly promise ground-breaking innovations and show very impressive demontrations of autonomous robots. However, to get the public acceptance they need to prosper, those autonomous systems have to be as safe and as reliable as possible. Unfortunately, the current implementations are not yet sufficiently robust, so academic and industrial researchers need to investigate better and more trustworthy solutions to the many challenges of autonomous navigation and behaviors. In particular, one of the most crucial components of most autonomous systems is the self-localization mechanism. This component is essential for the deployment of robots in GPS-denied environments (e.g. indoors, underground, submarine, etc.) since a robot would need to estimate is own position in its environment based on the measurements acquired by its own onboard sensors. In that regard, one of the most popular techniques is the simultaneous localization and mapping (SLAM) approach in which the robot builds a map of its surrounding environment to track and estimate its own movements and position. This technique has been proven to be very efficient, but it is also known as quite vulnerable to data association errors and the presence of spurious measurements. Engineers often circumvent those problems by doing a very precise, yet cumbersome, parameter tuning. Such environment-specific parameter tuning is appropriate for the controlled environment found in research laboratories, but it is by no means a sufficient solution for consumer robots deployed in the wild and sold to untrained customers. One of the main causes of errors in SLAM is the perceptual aliasing phenomenon in which two different places are confused as the same by the robot. This phenomenon leads to the addition of spurious measurements in the estimation mechanism which in turn leads to the failure of the whole system. In regard to the robustness challenges in SLAM systems, this thesis proposes two contributions to the scientific literature. The first introduces a new robust formulation of the core optimization problem in SLAM that models explicitly the perceptual aliasing phenomenon to efficiently reject spurious measurements. The second presents a distributed, online and robust solution for multi-robot SLAM in robotic teams. This contribution is particularly important since multi-robot systems are more vulnerable to perceptual aliasing than single-robot systems. Extensive experimental results in simulation, on datasets and on the field show that the proposed techniques can produce accurate localization estimates in the presence of spurious measurements.


identifier: Abdou Amadou, I. (2019). Approche heuristique pour la planification à court terme dans les mines à ciel ouvert  [Thèse de doctorat, Polytechnique Montréal].

abstract: RÉSUMÉ: Le présent projet de thèse vise à résoudre le problème de l'optimisation de la planification minière à court terme des mines à ciel avec une prise en compte de la réalité de l'exploitation minière. Cette planification est fortement contrainte car elle est l'avant dernière étape de la mise oeuvre de l'exploitation minière. À ce titre, elle regroupe à la fois des contraintes de production et des contraintes opérationnelles relatives aux équipements et aux techniques de l'exploitation minière. Malgré une production littéraire un peu soutenue sur l'optimisation de la planification à court terme des mines à ciel ouvert, très peu d'études se sont intéressées aux suivis des opérations de forage, dynamitage et d'extraction et aux équipements qui doivent les réaliser. La première étape de ce projet consiste à proposer un programme linéaire dont l'objectif est de minimiser le coût du déplacement des équipements de production et de favoriser l'accessibilité des blocs pour la réalisation des opérations minières. Cette modélisation permettra d'ordonnancer la production suivant les périodes de l'horizon de la planification (3 à 6 mois avec la semaine comme unité de période) sous la contrainte des cibles de production et des exigences de qualité. Le modèle prendra aussi en compte les contraintes opérationnelles qui sont l'accessibilité horizontale des blocs, la précédence verticale des bloc et la mise en oeuvre des opérations de forage, de dynamitage et d'extraction. La réalisation des opérations se fera par des équipements dont il faut suivre les déplacements tout en s'assurant de la disponibilité des ressources suffisantes (capacité, vitesse, disponibilité). La modélisation permettra aussi une amélioration de la précision et de l'exactitude de la précédence des tâches, ce qui facilitera la mise en oeuvre ultérieure du dispatching. Une méthode de décomposition du problème initial en 2 étapes est proposée pour la résolution du problème. La première étape de la démarche consiste à ordonnancer les blocs sous la contrainte des cibles de production et de qualité pour déterminer les blocs qui feront partie de contour d'exploitation et les périodes d'extraction de chaque bloc. L'ordonnancement se fait par la résolution de 2 nouveaux MIP développés à cet effet. La seconde étape se base sur les résultats de l'ordonnancement des bloc pour déterminer les tournées des équipements de production avec pour objectif de minimiser le coût des déplacements et de favoriser l'accessibilité horizontale des blocs. La détermination des tournées des équipements se fera en 2 phases avec des résolutions de nouveaux MIP adaptés à la problématique. La première phase consistera à déterminer les tournées des pelles par la résolution d'un MIP approprié qui intègre des estimations de la durée des opérations de forage et de dynamitage. La seconde phase s'occupera de la détermination des tournées des équipements de forage et de dynamitage sur la base des résultats de l'affectation de pelles. Une autre approche de résolution des problèmes des tournées des équipements par la méthode de la programmation par contraintes est testée et une comparaison est réalisée avec les résultats de la résolution des MIP d'affectation des équipements. Les résolutions des MIP ont été réalisées par la méthode itérative des fenêtre mobiles et les tests ont été réalisés avec des données artificielles. La démarche a permis de résoudre des instances de moins 400 blocs en 4h et de moins de 500 blocs en 10h. L'étape de l'ordonnancement des blocs a permis une réduction d'au moins 96% de la taille des graphes des déplacements possibles des équipements. La programmation par contraintes a donné de très bons résultats lors de tests de la détermination des tournées des pelles, les résultats sont par contre moins intéressants pour la détermination des tournées des foreuses et équipements de dynamitage.  ABSTRACT: This thesis project aims to solve the problem of optimizing the short-term mining planning of open-pit mines by taking into account the reality of mining. This planning is strongly constrained as it is the last step before the dispatching. As such, it combines both production constraints and operational constraints on equipment and mining techniques. Despite a literature production on optimizing the short-term planning of open-pit mines, very few studies have focused on the monitoring of drilling, blasting and extraction operations and their equipment. The first step of this project consists in proposing a linear program whose objective is to minimize the cost of moving the production equipment and to promote the horizontal accessibility of the blocks for carrying out the mining operations. This modeling will make it possible to schedule the production according to the periods of the horizon of the planning (3 to 6 months with the week as unit of period) under the constraint of the targets of production and the requirements of quality. The model will also take into account the operational constraints that are the horizontal accessibility of the blocks, the vertical precedence of the blocks and the implementation of drilling, blasting and extraction operations. The implementation of operations will be done by equipment that must be tracked while ensuring the availability of sufficient resources (capacity, speed, availability). The modeling will also improve the precision and accuracy of the task precedence, which will facilitate the subsequent implementation of dispatching. An initial 2-step problem decomposition method is proposed for solving the problem. The first step of the process consists of scheduling the blocks under the constraint of the production and quality targets to determine the blocks that will be extract and their extraction periods. The scheduling is done by the resolution of 2 new MIP developed for this purpose. The second step is based on the results of block scheduling to determine the production equipment tours with the objective of minimizing the cost of moving of the equipment and promoting horizontal accessibility of the blocks. The determination of equipment routing will be in two phases with resolutions of new MIP adapted to the problem. The first phase will consist of determining shovel tours by the resolution of an appropriate MIP that incorporates estimates of the duration of drilling and blasting operations. The second phase will deal with the determination of the rounds of drilling and blasting equipment based on the results of the assignment of shovels. Another approach to solving the problems of equipment runs by the constraint programming method is tested and a comparison is made with the results of the resolution of the equipment assignment MIPs.The resolutions of the MIPs were realized by the iterative method of the mobile windows and the tests were performed with artificial data. With this approach, it has be possible to resolved instances of less than 400 blocks in 4 hours and less than 500 blocks in 10 hours.The stage of block scheduling allowed a reduction of more than 96% in the size of the possible displacement graphs of the equipment. The constraint programming has given very good results during tests of the determination of the routing of the shovels, the results are on the other hand less interesting for the determination of the rounds of the drills and equipment of blasting.


identifier: Wu, A. (2019). Apprentissage machine pour l'accélération de l'optimisation des blocs mensuels d'équipages aériens  [Mémoire de maîtrise, Polytechnique Montréal].

abstract: RÉSUMÉ: Les compagnies aériennes sont soumises à une forte pression pour diminuer leurs coûts, c'est pourquoi elles consacrent beaucoup d'efforts dans l'optimisation de la planification aérienne, et notamment dans l'optimisation des horaires d'équipages, car le personnel de bord est leur deuxième poste de dépense après le carburant. Ce mémoire se situe dans le cadre de l'optimisation des blocs mensuels d'équipages aériens, qui consiste à construire les emplois du temps des membres d'équipage sur un mois, en affectant à tous les employés des rotations déjà construites, et ce de manière personnalisée. Une rotation est une séquence de vols commençant et terminant au même aéroport de base. Une méthode connue et efficace pour résoudre ces problèmes est la génération de colonnes, utilisée par l'entreprise AD OPT qui a collaboré sur ce projet. Dans cette méthode, un problème maître restreint optimise les coûts sur un sous-ensemble de blocs mensuels possibles en s'assurant de la couverture de toutes les rotations. D'autre part, des sous-problèmes se chargent de générer des nouveaux blocs mensuels qui vont améliorer la solution du problème maître restreint. La génération de colonnes est un algorithme itératif exact qui considère implicitement tous les blocs possibles sans les énumérer. Dans notre cas, un sous-problème est un problème de plus court chemin dans un réseau contenant toutes les rotations possibles, un chemin représentant un bloc. Il y a un sous-problème par employé. Les données fournies par AD OPT concernent une compagnie aérienne réelle, ayant environ 2000 employés et 5000 rotations par mois. On a donc ici 2000 réseaux de 5000 rotations chacun. En outre, il faut résoudre les problèmes de plus courts chemins dans ces réseaux des centaines de fois. Or, un bloc ne contient jamais plus de 10 rotations. L'objectif de cette maîtrise est alors d'accélérer les temps de calcul en réduisant la taille de ces réseaux d'un facteur 10 avec des techniques d'apprentissage machine. Grâce aux données historiques, la machine peut estimer la probabilité qu'une rotation soit dans le bloc d'un employé dans un mois futur. À partir de ces informations, on pourra extraire, pour chaque employé, les 500 rotations les plus probables et donner seulement celles-ci aux réseaux correspondants. Les réseaux réduits ainsi obtenus seront ensuite étendus progressivement, au fur et à mesure des itérations de la génération de colonnes, pour finalement considérer les réseaux entiers, garantissant ainsi l'optimalité. Le rôle de l'apprentissage machine est donc de fournir des informations pertinentes à un optimiseur exact de blocs mensuels. Les caractéristiques d'apprentissage sont les suivantes : les préférences et qualifications des employés, ainsi que les vols et les qualifications requises des rotations. Quelques améliorations du modèle classique d'apprentissage profond en classification sont présentées : une méthode de pondération de l'entropie croisée qui favorise la minimisation du rappel, ainsi que deux méthodes de sur-échantillonnage qui visent à rééquilibrer l'ensemble de données. L'une répète les échantillons de la classe minoritaire, et l'autre en génère des nouveaux par interpolation. À chaque fois, trois architectures de perceptron multicouche ont été testées, deux optimiseurs ont été envisagés, et plusieurs valeurs d'hyper-paramètres ont été explorées. La mesure de performance utilisée est calculée par rapport à la solution dont nous disposons, alors qu'il en existe de nombreuses autres tout aussi bonnes quoique très différentes. Ainsi, la performance est sous-évaluée par rapport à celle qui considérerait plusieurs de ces solutions équivalentes. Idéalement, la performance serait en fait calculée par rapport à une nouvelle solution, donnée par la génération de colonnes qui intégrerait les résultats de l'apprentissage. Ce n'était pas envisageable pour des raisons pratiques, mais c'est assurément un prolongement possible de ces travaux. Après avoir sélectionné les cas où l'ensemble des rotations apparaissaient au moins une fois dans les réseaux réduits des employés, les expériences effectuées donnent une performance de 37% dans le meilleur cas. Pour des raisons pratiques, l'intégration des résultats d'apprentissage dans la génération de colonnes n'a pas pu être réalisée dans le cadre de cette maîtrise. Ceci fera l'objet d'un projet futur, et on espère obtenir des meilleurs résultats en utilisant une mesure de performance plus adéquate à l'optimisation.  ABSTRACT: Airline companies are under a heavy pressure to lower their costs. Therefore, they put a lot of effort into their airline planning optimization, and especially into the crew scheduling optimization, since the onboard staff is their second biggest expense after fuel. The framework of this project is the aircrew rostering problem, which consists of building the monthly schedules of all the crew members by assigning pairings in a personalized way. A pairing is a sequence of flights, starting and ending at the same airport. A well-known and efficient way to solve this problem is the column generation algorithm, used by the AD OPT company, which collaborated on this project. In this method, a restricted master problem minimizes the total cost on a subset of possible blocks, while ensuring the coverage of all the pairings. On the other hand, sub-problems generate new monthly blocks, which will improve the solution of the restricted master problem. Column generation is an iterative and exact algorithm that implicitly considers all the possible blocks without enumerating them. In this case, a sub-problem is a shortest path problem in a network that contains all the possible pairings (a path represents a block). There is one sub-problem by employee. The data provided by AD OPT relates to a real-world airline company, that has around 2000 employees and 5000 pairings each month. Therefore, there are 2000 networks containing 5000 pairings each. However, a block never has more than 10 pairings. Therefore, the purpose of this thesis is to accelerate the computational time by reducing the network sizes by a factor of 10 with machine learning techniques. Based on historical data, one can estimate the probability of a pairing being in the block of an employee in the future. From this information, one will be able to extract the 500 most likely pairings for each employee, and give only these to the corresponding networks. The resulting reduced networks will be progressively extended when the columns generated with the current reduced networks seem to be insufficient, and in the end, the whole networks will be considered to guarantee optimality. Thus, the role of machine learning is to provide relevant information to an exact optimizer of the crew rostering problem. The learning features are: the employees' wishes and qualifications, together with the pairings' flights and required qualifications. We present a few improvements to the standard deep learning model used in classification: a method that weighs the cross-entropy loss function in a way that favors recall minimization, as well as two sampling methods, that aim to rebalance the dataset. The first one repeats minority samples, and the other one artificially generates new ones by interpolation. In each of these methods, three perceptron architectures are tested, two optimizers are considered and several values of hyper-parameters are explored. The selected performance measure is computed with respect to the solution at disposal, whereas many very different, but just as good solutions exist. Consequently, the performance will always be under-evaluated in comparison to a performance that would consider many of these solutions. In fact, ideally, the performance would be computed with respect to a new solution provided by the column generation algorithm, that integrates the information provided by machine learning. For practical reasons, that wasn't realistic in this case, but it would definitely be part of the future work. Once we selected the cases in which all the pairings appear at least once in the reduced networks, the best performance among the experiences carried out in this project is 37%. For practical reasons, the integration of the learnt results within the column generation algorithm couldn't be completed in this masters' thesis. This will be implemented in the future, and we hope to deliver better results by using a performance measure that is more relevant to the optimization point of view.


identifier: Tahir, A. (2019). Génération de colonnes en nombres entiers pour les problèmes de type partitionnement d'ensemble  [Thèse de doctorat, Polytechnique Montréal].

abstract: RÉSUMÉ: Le problème de partitionnement d'ensemble (SPP : Set Partitioning Problem) est un problème d'optimisation combinatoire, se formulant comme un modèle de programmation linéaire en nombres entiers. L'objectif du SPP est de trouver une partition d'un ensemble de tâches (e.g., vols, clients, ...) à coût minimum. Le modèle du SPP est composé de deux types de contraintes : les contraintes de partitionnement qui assurent que chaque tâche soit couverte exactement une fois, et des contraintes supplémentaires qui permettent de modéliser d'autres aspects du problème traité comme les disponibilités du personnel. Le SPP permet de modéliser plusieurs problèmes rencontrés dans l'industrie comme les problèmes de tournées de véhicules et de rotations d'équipages dans le domaine aérien (CPP : crew pairing problem). Les problèmes mentionnés ci-dessus sont généralement résolus à l'aide de la méthode Branchand- Price. C'est une méthode duale fractionnaire dont l'objectif est de trouver des solutions entières en ignorant, dans un premier temps, les contraintes d'intégralité sur les variables du modèle de SPP. Pour ce faire, Branch-and-Price explore un arbre de branchement où chaque noeud de branchement est résolu à l'aide de la méthode de génération de colonnes. Malgré sa popularité, Branch-and-Price peut être lente dans le cas de problèmes difficiles de très grande taille. Par conséquent, les solutions entières recherchées ne sont obtenues que vers la fin de la résolution. D'autres méthodes, dites primales, sont également utilisées pour résoudre le SPP. Elles cherchent une solution optimale en améliorant à chaque itération la solution entière courante. À l'itération 0, ces méthodes partent d'une solution entière initiale qui est généralement disponible pour les problèmes industriels. Parmi les méthodes primales efficaces, on trouve l'algorithme du simplexe en nombres entiers avec décomposition (ISUD) et ses deux variantes améliorées nommées ZOOM et I2SUD. Cet algorithme primal trouve une séquence de solutions entières avec des coûts décroissants, menant à une solution optimale ou quasioptimale. ISUD est l'un des algorithmes primaux potentiels qui a pu résoudre efficacement des problèmes SPP de grande taille. Ceci a vivifié l'intérêt que l'on commence à porter aux approches primales. Malgré ses deux variantes améliorées, ISUD a cependant deux limitations majeures : i) il suppose que les colonnes sont générées a priori, ii) il ne gère pas les contraintes supplémentaires, souvent rencontrées en milieux pratiques. Ceci dit, et à l'instar de ces constats, nous proposons dans le cadre de cette thèse trois sujets pour remédier aux limitations précédemment soulevées. Dans le premier sujet, nous proposons une méthode de génération de colonnes en nombres entiers (ICG) qui combine ISUD et la génération de colonnes pour résoudre des problèmes de partitionnement avec un très grand nombre de variables. ICG génère une séquence de solutions entières avec des coûts décroissants, menant à une solution optimale ou quasi-optimale. Des expérimentations numériques sur des instances du CPP et du problème d'horaires de chauffeurs et d'autobus (VCSP : vehicle and crew scheduling problem), impliquant jusqu'à 2000 contraintes montrent que ICG surpasse nettement deux heuristiques populaires de génération de colonnes. ICG trouve des solutions optimales ou quasi-optimales en moins d'une heure de temps de résolution, en générant jusqu'à 300 solutions entières pendant le processus de résolution. Cependant, ICG ne permet pas de résoudre les SPPs avec des contraintes supplémentaires, d'où le deuxième sujet de cette thèse. Dans le deuxième sujet, nous proposons une version améliorée d'ICG, notée I2CG, qui peut résoudre efficacement des problèmes de partitionnement d'ensembles de grande taille avec des contraintes supplémentaires. Ces dernières sont difficiles à gérer dans le contexte des méthodes primales car elles peuvent créer des minimums locaux en coupant tous les points extrêmes entiers adjacents à la solution courante. Les expérimentations numériques sur des instances du CPP impliquant jusqu'à 1761 contraintes montrent que I2CG est efficace et surpasse largement deux heuristiques populaires de génération de colonnes. Pour la plus grande instance testée, I2CG a pu produire en moins d'une heure de temps de calcul plus que 500 solutions entières menant à une solution optimale ou quasi-optimale. Le troisième sujet porte sur l'amélioration de la méthode I2CG à l'aide des techniques d'apprentissage machine. En effet, nous utilisons un modèle de prédiction pour prédire avec une certaine probabilité les connexions entre les vols dans le CPP. Ces probabilités sont incorporées dans la méthode I2CG pour favoriser la génération des colonnes ayant une plus grande probabilité d'appartenir à des solutions optimales ou quasi-optimales. Les tests effectués sur 49 instances de CPP, impliquant jusqu'à 1740 vols, montrent clairement que la nouvelle version d'I2CG est plus rapide que I2CG. En effet, la nouvelle version génère et trouve aussi une séquence de solutions entières avec des coûts décroissants jusqu'à atteindre une solution optimale ou quasi-optimale en réduisant le temps de résolution total de 50% en moyenne.  ABSTRACT: The Set Partitioning Problem (SPP) is a combinatorial optimization problem, formulated as an integer linear programming model. The SPP aims to find a minimum cost partition of a set of tasks (e.g., flights, customers, ...). The SPP model has two types of constraints: partitioning constraints ensuring that each task is covered exactly once; and side constraints for modeling other aspects of the problem, such as staff availability. The SPP can be used to model several real-world problems such as vehicle routing and crew pairing problems (CPP). The problems mentioned above are usually solved using Branch-and-Price based approaches. Branch-and-Price is a fractional dual method that aims to find integer solutions by ignoring the integrality constraints in the SPP model. Branch-and-Price explores a search tree where each branch node is solved using the column generation method (CG). Despite its wide popularity, Branch-and-Price becomes increasingly slow on very large and difficult problems. Therefore, the expected integer solutions are only obtained in the end of the resolution. Other methods, known as primal methods, are also used to solve the SPP. They look for optimality by improving the current integer solution. These methods start from an initial integer solution which is generally available in industrial contexts. One of the most efficient primal methods is the integral simplex using decomposition (ISUD) algorithm and its two improved variants called ZOOM and I2SUD. This primal algorithm finds a sequence of integer solutions with decreasing costs, leading to an optimal or near-optimal solution. ISUD is one of the potential primal algorithms that has been able to efficiently solve large SPPs, and so giving a boost of interest towards primal approaches. Even with its two improved variants, ISUD still has two main limitations: i) it assumes that the columns are generated a priori, ii) it does not handle the side constraints commonly encountered in practice. In the first subject of this thesis, we develop an integral column generation (ICG) heuristic that combines ISUD and column generation to solve SPPs with a very large number of variables. Computational experiments on instances of the public transit vehicle and crew scheduling problem (VCSP) and of CPP involving up to 2000 constraints show that ICG clearly outperforms two popular column generation heuristics (RMH : restricted master heuristic and DH : diving heuristic). ICG can yield optimal or near-optimal solutions in less than one hour of computational time, generating up to 300 integer solutions during the solution process. However, ICG cannot solve SPPs with side constraints. In the second subject, we develop a generalized version of ICG, denoted I2CG, that can solve efficiently large-scale set partitioning problems with side constraints (SPPSC). The latter are difficult to handle in the context of primal methods because it can create local minima by cutting all integer extreme points adjacent to the current solution. Computational experiments on instances of the airline crew pairing problem involving up to 1761 constraints show that I2CG is efficient and significantly outperforms DH and RMH. For the largest tested instance, I2CG can produce more than 500 integer solutions leading to an optimal or quasi-optimal (i.e., near-optimal) solution. The third subject proposes a machine learning based improvement process for the I2CG algorithm. Indeed, we use a prediction model to predict with some probability the connections between flights. These probabilities are embedded in the I2CG algorithm to favour the generation of columns with a higher probability of being in the optimal or near-optimal solutions. Computational experiments on 49 instances of the CPP involving up to 1740 flights show that the new version of I2CG is faster than I2CG. It generates a sequence of integer solutions with decreasing costs until reaching an optimal or quasi-optimal solution and the computational time is reduced by 50% on average.


identifier: Pereira de Lima, L. A. (2019). Second-Order Modeling for the Oxygen Uptake Kinetics in Humans  [Thèse de doctorat, Polytechnique Montréal].

abstract: RÉSUMÉ: La consommation d'oxygène (V̇ O2) est une mesure physiologique qui représente le taux avec lequel un individu extrait, transporte et utilise l'oxygène de l'environnement. L'étude de la cinétique du V̇ O2 en réponse aux variations de l'intensité de travail physique (WR) peut fournir des informations précieuses sur la fonction métabolique d'un individu, dans la mesure où elle reflète la fonctionnalité et l'interaction de différents systèmes de l'organisme, tels que les systèmes cardiovasculaire, respiratoire et neuromusculaire. Outre son utilité dans la compréhension de la physiologie du corps humain, l'analyse de la cinétique du V̇ O2 représente un levier important dans l'évaluation de la condition physique et la détection des pathologies. La pertinence des résultats de cette analyse dépend fortement du modèle adopté. Datant du début des années 1970, le modèle Multi-Exponentiel du Premier Ordre (FOME) reste l'état de l'art pour la modélisation de la réponse du V̇ O2 à l'entrée échelon positive de la WR.  Bien que les deux ou trois exponentielles du premier ordre du modèle FOME décrivent bien les trois phases typiques de la réponse du V̇ O2 à l'entrée échelon, elles restent incapables de modéliser l'oscillation connue comme le dépassement (ou l'overshoot) dans la cinétique du V̇ O2 (OV̇ O2K) au cours de la phase II dans certains cas. Ce patron de dépassement, très commun aux courbes du second ordre, peut être utilisé par le modèle FOME seulement en ajoutant un terme additionnel de dépassement à sa composante fondamentale. Néanmoins, cette approche est dépourvue de l'aspect physiologique et augmente le nombre de paramètres de courbe du modèle. De plus, la modélisation du premier ordre du OV̇ O2K pourrait mener à des évaluations erronées pour des indicateurs physiologiques importants comme le déficit en O2, la constante de temps et l'amplitude de la composante fondamentale.  Un autre phénomène, « la composante lente du V̇ O2 », appelée dans ce travail de recherche l'augmentation lente de la cinétique du V̇ O2 (V̇ O2SA), nécessite aussi l'ajout d'un terme additionnel au modèle FOME pendant la phase III de la réponse du V̇ O2. Dans ce cas, le terme ajouté présume la théorie d'un délai de recrutement additionnel des fibres musculaires de type II. Grace à ce délai, le recrutement survient seulement au « début » du V̇ O2SA, même avec une WR constant. De plus, l'ajout de la composante lente du premier ordre est limité aux transitions des intensités supra-modérées, où la V̇ O2SA est présente. Pour cela, le concept d'un modèle unique de cinétique du V̇ O2 pour l'ensemble du spectre de WR n'est pas pris en charge par le modèle FOME.  Avec l'objectif de développer et implémenter un modèle de la cinétique du V̇ O2 pour les humains qui serait capable de représenter les réponses à l'entrée échelon positive de l'exercice pour n'importe quelle WR et indépendamment de la présence du OV̇ O2K ou de la V̇ O2SA, deux modèles basés sur les courbes du second ordre sont proposés. Outre les résultats de la littérature scientifique, les données collectées pour cette étude à partir de tests de cyclergométrie avec 14 cyclistes et triathlètes bien entraînés sont utilisées pour l'appui mathématique et conceptuel des modèles proposés.  Dans le premier modèle, le Mixed Multi-Exponentiel (MiME), la composante fondamentale du modèle FOME, responsable de la forme de la phase II de la réponse du V̇ O2 à l'échelon, est remplacée par une courbe du second ordre. Ainsi, au lieu de « corriger » la courbe du premier ordre dans le cas d'un OV̇ O2K, le modèle MiME présente sa réponse de dépassement comme une possibilité parmi d'autres — les courbes de non-dépassement habituelles comprises — représentées à partir d'une simple adaptation des paramètres de courbe du second ordre.    Pour le deuxième modèle proposé, le terme additionnel avec un délai — utilisé pour représenter la  ̇ O2SA dans les modèles FOME et MiME — sera supprimé. Ce modèle, construit à partir de deux composantes simultanées du second ordre (SOSC), va représenter la réponse du V̇ O2 indépendamment de la présence du OV̇ O2K ou de la V̇ O2SA. Contrairement au modèle MiME, ces différentes formes de courbe peuvent être réalisables dans la dynamique SOSC tout simplement au moyen de la modification des paramètres internes du modèle. Ainsi, l'ajout d'un terme complémentaire n'est pas nécessaire et la structure du modèle reste qualitativement inchangée pour toutes les transitions échelon de WR. La dépendance continue entre les amplitudes des composantes du modèle SOSC et la WR permet non seulement d'éliminer le problème de discontinuité présenté par le FOME et le MiME dans la transition des intensités modérées à supra-modérées, mais aussi de réinterpréter d'importants concepts physiologiques, tels que le seuil d'accumulation de lactate, la puissance critique et l'état stable maximal de lactatémie. De plus, la dynamique du SOSC permet des notions alternatives concernant les patrons du recrutement des fibres musculaires supplémentaires pendant l'exercice. Ce recrutement supplémentaire des fibres, bien que non nécessairement refusé, n'est plus obligatoire dans le modèle SOSC.  Enfin, les résultats issus de la comparaison entre la racine des erreurs quadratiques moyennes des courbes du modèle démontrent une performance d'ajustement globale nettement meilleure du SOSC par rapport au MiME et de ces deux derniers modèles par rapport au modèle FOME. Ainsi, compte tenu des résultats des analyses statistiques et conceptuelles issus de ce travail de recherche, le modèle MiME et, surtout, le modèle SOSC représentent des alternatives cohérentes et complètes pour l'amélioration de la modélisation de la cinétique du V̇ O2 chez les humains.  ABSTRACT: The oxygen uptake (V̇ O2) is a physiological measure that represents the rate at which an individual extracts, transports, and uses oxygen from the environment. The study of the V̇ O2 kinetics in response to variations in exercise work rate (WR) may provide valuable information on an individual's metabolic function, as it reflects the functionality and interaction of different body systems, such as the cardiovascular, respiratory, and neuromuscular ones. Thus, in addition to enhancing the understanding of human physiology itself, the V̇ O2 kinetics analysis represents an important tool for fitness level assessment and detection of disease conditions. Moreover, the utility and pertinence of this analysis' results are highly dependent on the appropriateness of its adopted modeling. Dating from the early 1970s, the First-Order Multi-Exponential (FOME) model remains the state-of-the-art choice for modeling the V̇ O2 response to the WR step on-transient.  However, while the FOME's two or three first-order exponentials sufficiently describe the three phases of a typical V̇ O2 step response, they fail to model the oscillation known as the overshoot in the V̇ O2 kinetics (OV̇ O2K) observed during phase II in some cases. Such an overshoot pattern, very common to second-order curves, may only be represented by the FOME model by means of the application of an overshoot add-on term to its fundamental component, an approach that lacks physiological support and increases the amount of curve parameters. Moreover, the first-order representation of OV̇ O2K cases may yield spurious evaluations of important physiological indicators such as the O2 deficit and the fundamental component's time constant and amplitude.   Another phenomenon, widely know as the V̇ O2 “slow component,” and referred to in this work as the slow augmentation in the V̇ O2 kinetics (V̇ O2SA), also requires the incorporation of an add-on term by the FOME model, this time to phase III of the V̇ O2 step response. In this case, this add-on term necessarily assumes the theory of a delayed additional recruitment of type II muscle fibers occurring only at the “onset” of the V̇ O2SA, despite the constant WR condition. Additionally, because the incorporation of this first-order slow component add-on term is restricted to transitions to supra-moderate intensities, where the V̇ O2SA is considered to manifest, the concept of a single VO2 kinetics model for the whole WR spectrum is not supported by the FOME model. With the objective of developing and implementing a comprehensive model for the V̇ O2 kinetics in humans capable of comprising exercise step on-transient responses to any WR, regardless of the manifestation of none, either, or both of the OV̇ O2K and/or V̇ O2SA phenomena, two models using second-order exponential curves are proposed in this work. In addition to results from the literature, original data collected for this study by means of cycle ergometry testing of 14 well trained cyclists and triathletes is used for the mathematical and conceptual support of these proposed models.  In the first of them, the Mixed Multi-Exponential (MiME) model, the FOME model's fundamental component is replaced by a second-order curve. Thus, instead of “fixing” the first-order curve in the OV̇ O2K cases, the MiME presents its overshooting curve as one of the multiple shape possibilities—including the usual nonovershooting curves—achievable by a mere adaptation of the values of the two second-order solution's shape parameters. Additionally, because the OV̇ O2K is incorporated in the second-order representation of the fundamental component, the objective detection and quantification of this phenomenon are facilitated. However, in the supra-moderate cases, the MiME will still represent the V̇ O2SA with a first-order slow component add-on term.  In the second model proposed, the concept of a delayed add-on term to represent the V̇ O2SA is also abandoned, and a model composed of two Second-Order Simultaneous Components (SOSC) is applied to represent V̇ O2 step responses containing none, either, or both of the OV̇ O2K and/or ̇ O2SA phenomena. However, unlike in the MiME model, these shape possibilities are achievable in the SOSC dynamics exclusively by means of the numerical adaptation of the model's internal parameters, so that the conditional incorporation of add-on terms is not required and the model's structure remains qualitatively constant for step on-transients to any WR. The continuous dependence between the amplitudes of SOSC components and the WR eliminates the issue of the FOME and MiME's continuity disruption in the transition from moderate to supra-moderate intensities, allowing important physiological concepts such as the lactate threshold, the critical power, and the maximal lactate steady-state to be revisited. Moreover, alternative insights into the patterns of muscle fiber recruitment during exercise are also provided by the SOSC dynamics, and the theory of additional fiber recruitment, although not necessarily denied, is no longer mandatory.  Finally, results from the comparison between the root mean squared errors of the models' curves, demonstrate a significantly better overall fitting performance of the SOSC over the MiME, and of these two over the FOME model. Thus, considering both statistical and conceptual analyses performed in this thesis, the MiME model and, above all, the SOSC model are coherent, comprehensive alternatives for the improvement of the V̇ O2 kinetics modeling in humans.


identifier: Niang, N. A. (2019). Simulation multi-agent des opérations sur un réseau d'autopartage en libre-service intégral  [Mémoire de maîtrise, Polytechnique Montréal].

abstract: RÉSUMÉ: Avec l'accroissement constant de la population, les grandes agglomérations sont à la recherche de solutions durables afin de relever les défis de mobilité actuels. D'ailleurs, un objectif principal du gouvernement québécois est l'intégration des modes de transport alternatifs à l'offre de trans-port urbain actuelle (Transports Québec, 2019). Face à un besoin en mobilité temporellement et spatialement variable, l'autopartage en libre-service intégral se démarque par la flexibilité qu'elle offre à ses usagers. En effet, les compagnies d'autopartage proposant cette variante de service innovent en permettant à leur client de stationner leur véhicule dans n'importe quel stationnement public autorisé. Toutefois, une augmentation de la flexibilité pour l'utilisateur rime très souvent à une augmentation de la complexité organisationnelle pour les opérateurs. L'efficacité opérationnelle est ainsi obtenue en résolvant efficacement les problématiques liées par exemple au choix de la couverture de réseau optimale sur un territoire donné. Dans ce contexte, la simulation devient un outil d'analyse de prédilection.Le sujet de cette étude est le service d'autopartage en libre-service intégral de Communauto à Montréal. Plutôt que d'estimer sa demande, cette étude vise à analyser sa performance opérationnelle relativement à différentes stratégies de configurations de réseau. Historiquement, lorsqu'il s'agit de systèmes hétérogènes tels que l'objet de cette étude, le mélange de paradigmes de simulation est privilégié pour modéliser les différentes composantes du système (Shaheen, 2009). Ainsi, il a été choisi d'adopter aussi bien une approche à base d'agent, pour représenter les entités évoluant sur le réseau, qu'une approche à évènements discrets pour représenter les procédures récurrentes, à l'image du processus de recharge d'un véhicule.Le modèle a été développé et implémenté sur Anylogic (The Anylogic Company, 2019c). Principalement, trois expérimentations visant à comprendre l'interaction dynamique entre la demande, le taux de service et les politiques d'utilisation du service ont été menées. Chaque expérimentation a été évaluée quand les clients sont restreints à terminer leur voyage dans la zone de service définie par l'opérateur (scénario 1) ou non (scénario 2). Globalement, l'utilisation moyenne du service est légèrement supérieure au scénario 2 qu'au scénario 1, ce dernier permettant néanmoins d'avoir une fréquence d'utilisation journalière des véhicules de la flotte plus uniforme. Afin d'analyser la sensibilité du système aux variations de la demande et de la flotte, l'élasticité de la demande latente a été évaluée par rapport à ces changements stratégiques. Cet indice de sensibilité mesure à quel point la demande latente change lorsque l'une de ces variables stratégiques change. Ainsi, en faisant varier le nombre de véhicules disponibles, les coefficients d'élasticité obtenus ont permis de conclure qu'une augmentation de la taille de la flotte entraîne une baisse de la demande latente, quel que soit le scénario étudié. L'inverse est vrai dans le cas où l'intensité de la demande est sujette à variation.  ABSTRACT: With human population constantly growing, sustainable ways to meet current mobility challenges is quickly becoming a concern for highly urbanized cities. Indeed, one main objective of the Quebec government is to integrate alternative modes of transportation into the current urban trans-portation offer (Transports Québec, 2019). With a mobility demand that is both spatially and tem-porally variable, free-floating carsharing stands out for the flexibility it offers to its users. Indeed, carsharing companies offering this variant of service innovate by allowing their customers to park their vehicles in any authorized public parking space. However, an increase in flexibility for the user very often means an increase in organisational complexity for the carsharing company. Operational efficiency is thus achieved by effectively solving problems related, for instance, to the choice of optimal network coverage in a given territory. In this context, simulation becomes a preferred analytical tool.The subject of this study is Communauto's free-floating carsharing service in Montreal. Rather than estimating its demand, this study aims to analyze its operational performance with respect to different network configuration strategies. Historically, when it comes to heterogeneous systems such as the subject of this study, the mixture of simulation paradigms is preferred to model the different components of the system (Shaheen, 2009). Thus, it was chosen to adopt both an agent-based approach to represent entities operating on the network, and a discrete event approach to represent recurrent and entity-specific procedures such as the charging process of a vehicle.The model was developed and implemented on Anylogic (Anylogic, 2019). Mainly, three experi-ments were conducted directly aimed at understanding the dynamic interaction between demand, service rate and clients' usage policies. Each experimentation was evaluated when a policy re-straining customers' trips ends in a service area defined by the operator was applied strictly (Sce-nario 1) and when customers were allowed to complete their travel outside that same area (sce-nario 2). Experimentation shows an overall increase in the vehicle utilization rate in scenario 2 compared to scenario 1, the latter making it possible to have more uniform daily vehicle utiliza-tion frequency. In order to analyze the sensitivity of the system to variations in fleet demand and sizing, the latent demand's elasticity was assessed in relation to these strategic changes. This sensitivity index measures to which degree latent demand changes when one of those strategic variables changes. By varying the number of vehicles available, the coefficients of elasticity obtained made it possible to conclude that an increase in the size of the fleet causes a fall in latent demand whatever the scenario under study is. The opposite is true when the intensity of demand is subject to variation.


identifier: Mohammed, I. (2019). Comparison of the Renishaw Ball Bar and Samba Method in 3-Axis and 5-Axis Machine Calibration, Including Reversal Error Estimation with the Tango Method  [Mémoire de maîtrise, Polytechnique Montréal].

abstract: RÉSUMÉ: Cette étude porte sur la comparaison des erreurs géométriques de la fraiseuse 5 axes obtenues par l'analyse d'une barre à billes Renishaw avec celles de la méthode SAMBA/TANGO. Les vingt paramètres de l'erreur recueillis par le logiciel de la barre à billes Renishaw dans les plans XY, YZ, et ZX sont le jeu d'inversion, le jeu latéral, la rectitude, l'erreur d'échelle, et la perpendicularité selon X, Y et Z. Une stratégie composée développée pour la méthode TANGO/SAMBA utilise 21 indexations, une échelle et quatre sphères calibrées, et une face. La face est mesurée plusieurs fois avec différents pré-mouvements selon X, Y et Z pour identifier l'erreur de retournement et l'erreur de jeu d'inversion. Les résultats montrent que les paramètres de l'erreur sont comparables en utilisant les deux méthodes. Le paramètre associé à l'erreur d'échelle EXX montre des valeurs d'erreur cohérentes. L'erreur d'échelle vaut -4.65 µm et -4.67 µm pour la méthode barre à billes et la méthode SAMBA/TANGO respectivement. Cette nouvelle technique qui a été développée pour estimer l'erreur de retournement et aussi utilisée dans ce projet pour déterminer l'erreur de six retournement. L'erreur de quatre retournement était en accord avec la méthode de Renishaw barre à billes et celle de SAMBA/TANGO. Globalement, les données acquises montrent que la comparaison des méthodes BB et SAMBA/TANGO est possible pour 9 des 20 paramètres d'erreur.  ABSTRACT: This research work is related to the comparison of the geometric error of the HU40T five-axis machine tool obtained with a Renishaw ball bar with those from the SAMBA/ TANGO method. The twenty-error parameter gathered from the Renishaw ball bar software in the XY, YZ, and ZX plane are backlash error, lateral play, straightness, scaling error, and squareness error in the X, Y, and Z direction. A compound strategy developed for the SAMBA/ TANGO method uses 21-indexations, one scale and four master balls, and one facet. The reversal and backlash error measured by repeatedly probing the facet with different pre-motion in X, Y, and Z-axis. Finally, the result of the present work shows that the error parameter are not always in good agreement between these two methods. The scaling error parameter in the x-direction EXX was in close agreement. Scaling error values found at -4.65 µm and -4.67 µm in Ball bar and SAMBA/TANGO, respectively. The new technique developed for the estimation of reversal error was useful to obtain the six-reversal error. The four-reversal error was in agreement for the Renishaw ball bar and SAMBA/ TANGO method. The overall obtained measured data shows that the comparison of the Renishaw ball bar and SAMBA/TANGO method is possible for the 9-error parameter out of the 20-selected parameter.


identifier: Gaudet, S. (2019). Vérification de code pour le modèle k-ϵ standard de OpenFOAM  [Mémoire de maîtrise, Polytechnique Montréal].

abstract: RÉSUMÉ: Dans un contexte industriel toujours plus compétitif, les industries sont constamment comparées les unes aux autres. Elles ont donc intérêt à se moderniser et investir dans des outils de pointe afin d'améliorer la qualité de leur procédé et de diminuer leurs coûts d'opération. Les outils de CFD répondent précisément à ce besoin, ce qui explique la demande grandissante pour ces outils dans l'industrie. Toutefois, la crédibilité des résultats obtenus reste un obstacle majeur pour l'application plus répandue des outils de CFD. Nous avons donc comme but de contribuer à la crédibilité des résultats en confirmant que les méthodes numériques, telles qu'implémentées dans le code, se comportent conformément à la théorie. Dans le cadre de ce travail, nous avons choisi d'employer le code OpenFOAM, un logiciel à code source libre fréquemment employé dans l'industrie. Il offre une impressionnante collection d'outils entièrement gratuits, répondant en grande partie aux besoins industriels actuels. Cependant, ce logiciel est nettement plus complexe à employer qu'un logiciel de CFD commercial. De plus, on retrouve peu d'informations détaillant la vérification rigoureuse du code. Il nous semble donc approprié de porter plus d'attention à la vérification du code OpenFOAM pour les multiples solveurs, modèles et conditions limites disponibles. Dans ce mémoire nous effectuerons la vérification du code OpenFOAM pour un écoulement turbulent et incompressible. En effet, ce type d'écoulement est représentatif de la majorité des situations rencontrées dans un contexte industriel. On modélise la turbulence avec le modèle k-ϵ standard à cause de sa simplicité d'utilisation et son faible coût de calcul. Ce modèle est un compromis intéressant pour sa précision et son coût de calcul. Nous commencerons par vérifier le code pour un écoulement très simple, soit celui de Poiseuille. Nous appliquerons ensuite la méthode de solutions manufacturées imitant un écoulement laminaire 1D de type couche limite, un écoulement libre 2D laminaire, un écoulement libre 2D turbulent, et finalement un écoulement de type couche cisaillée. Afin de mieux comprendre les écarts entre le taux de convergence théorique et le taux de convergence observé, nous poursuivrons la vérification en y ajoutant l'étape de vérification de simulation à l'aide de l'extrapolation de Richardson. Ces cas nous permettront de confirmer si le taux de convergence théorique des schémas numériques est respecté ou non.  ABSTRACT: In an ever more competitive industrial context, factories are regularly compared with each other. Hence, they have every reason to modernize themselves and invest in state-of-the-art tools to improve the quality of their process and reduce their operating costs. CFD tools are tailored for this need. This explains the growing demand for such services in this industry. However, the credibility of predictions remains a major obstacle of a more widespread use of CFD tools. We therefore aim to contribute to the credibility of the results by confirming that numerical methods, as implemented in the code, behave as predicted by theory. As part of this work, we chose to use the OpenFOAM code, an open-source software widely used in the industry. It offers an impressive collection of tools that meets most of the industry's needs. However, this software is significantly more complex to use than commercial CFD software. Also, there is little information detailing the rigorous verification of its code. Therefore, it seems appropriate for us to pay more attention to the verification of OpenFOAM's code for the numerous solvers, models and boundary conditions that are available. In this thesis we will perform code verification of a turbulent incompressible flow solver. This flow is quite representative of most flows encountered in the industry. We use the standard k-ϵ model since it is easy to use and for its cheap computational cost. These two qualities make this model the ideal compromise between accuracy and computational costs. We will start by verifying the code for a very simple Poiseuille flow. We will then apply the method of manufactured solutions to mimic a boundary layer 1D laminar flow, a laminar 2D free flow, a turbulent 2D free flow, and then finally a sheared layered flow. In order to better understand the disagreements between the theoretical and observed convergence rates, we will add a step of verification of simulations to this study, using Richardson's extrapolation. These cases will allow us to confirm whether the theoretical convergence rate of the numerical schemes is achieved or not.


identifier: Robitaille, B. (2019). Analyse des propriétés mécaniques de joints à recouvrement en aluminium 2024-T3 AlClad soudés par friction-malaxage et impact de la préparation de surface  [Mémoire de maîtrise, Polytechnique Montréal].

abstract: RÉSUMÉ: Dans ce mémoire, les propriétés mécaniques de joints à recouvrement en aluminium 2024-T3 AlClad soudés par friction-malaxage sont étudiées. Le soudage par friction-malaxage est un procédé récent qui est de plus en plus utilisé dans les domaines de l'aérospatiale et des transports. Cette technique est appelée à remplacer les méthodes de soudage conventionnel et de rivetage puisqu'elle possède plusieurs avantages, permettant généralement de réduire le poids total de l'assemblage et de joindre des alliages difficilement soudables par fusion. Plusieurs paramètres de soudage régissent la qualité du joint, comme les vitesses d'avance et de rotation. Il est par contre intéressant de s'attarder à des paramètres moins étudiés actuellement, mais qui peuvent affecter les propriétés mécaniques et potentiellement rendre plus efficaces les procédures de soudage. C'est le cas des étapes de préparation de surface des pièces avant la réalisation de la soudure. L'objectif principal du projet est de déterminer si l'état de surface des pièces avant le soudage par friction-malaxage peut influencer les propriétés mécaniques lors de sollicitations monotones et cycliques pour des joints à recouvrement en alliage d'aluminium 2024-T3 AlClad. Des recommandations adéquates quant à la préparation de surface pour les soudures étudiées sont ensuite être émises et permettent de guider les industriels dans le développement de leurs procédures de soudage. Le deuxième chapitre présente une revue de littérature. La composition chimique et les propriétés mécaniques du matériau utilisé pour les joints, l'aluminium 2024-T3 AlClad, y sont d'abord examinées. Le procédé du soudage par friction-malaxage est ensuite présenté. Le fonctionnement général, les types de joints qu'il est possible de produire ainsi que la préparation de surface des pièces sont abordés. Une section de ce chapitre est dédiée à l'état de contrainte et à la rupture lors d'une sollicitation monotone uniaxiale d'un joint à recouvrement. Le phénomène de la flexion secondaire est expliqué et les types de rupture sont présentés. Les facteurs pouvant affecter cette rupture, comme les discontinuités géométriques, la microstructure du joint et la présence d'oxydes ou de revêtement AlClad sont détaillés. Ces facteurs sont repris dans la section sur l'état de contrainte et la rupture lors d'une sollicitation cyclique uniaxiale d'un joint à recouvrement. Il ressort principalement de cette revue de littérature que les oxydes sont difficiles à disperser pendant le soudage par frictionmalaxage de joints à recouvrement et qu'ils peuvent diminuer la résistance mécanique lors d'une sollicitation monotone.  ABSTRACT: This dissertation studies the mechanical properties of aluminum 2024-T3 AlClad overlap friction-stir-welded joints. Friction stir welding is a recent joining process that is being increasingly used in the aerospace and the transportation industries. Conventional welding and riveting may be gradually replaced by this technique as it presents many advantages, like the weight saving possibilities and the ability to weld "unweldable" alloys. Many parameters affect the quality of the joint, like the tool rotation and advance speeds. These are two of the main parameters, but it is important to address other variables that might also affect the mechanical properties of the resulting welded assembly and potentially result in better welding procedures. That is the case of surface preparation steps done prior to welding. The main goal of this research project is to establish if the surface state of the workpieces prior to friction stir welding can influence the mechanical properties of the 2024-T3 AlClad aluminum overlap joints during monotonous and cyclic solicitations. Appropriate recommendations regarding the surface preparation for the studied welds will be formulated and companies using friction stir welding as a joining method will be able to adapt their welding procedures if needed. The second chapter is a literature review. The chemical composition and the mechanical properties of 2024-T3 AlClad aluminum are first addressed. The friction stir welding process is then presented. The generalities of the process, the type of joints that can be made and the surface preparation of the pieces are presented. A section of this chapter is dedicated to the stress state and the types of failure for lap joints during a monotonous uniaxial solicitation. The secondary bending phenomenon is explained and the failure types are presented. The factors that can affect this failure, like geometrical discontinuities, the microstructure of the joint and the presence of surface oxide or cladding material are detailed. These factors are also addressed in the section on stress state and failure during a cyclic uniaxial solicitation. The oxides were reported as hard to break during friction stir welding and can reduce the ultimate strength of the welds during static testing. Some authors also conclude that the cladding fragments in the nugget offered a preferred failure zone during monotonous solicitation and that they were weak spots in the metallurgical bond of the welded zone. The third chapter presents the organization of the project and the methodology. The production of the welded joints and their mechanical testing was addressed. Two types of welded assemblies were produced.


identifier: Musongela, M. (2019). Généralisation du modèle TIBÈRE pour la simulation des fuites B1 hétérogènes à la méthode des caractéristiques  [Thèse de doctorat, Polytechnique Montréal].

abstract: RÉSUMÉ: Ce travail de recherche s'intéresse à généraliser le modèle de fuites hétérogènes TIBÈRE à la méthode des caractéristiques (MoC) dans le code DRAGON-5. Les fuites de neutrons sont prises en compte au sein du calcul de réseau afin d'obtenir des coefficients de diffusion plus précis qui serviront au calcul de coeur. Le calcul de réseau résoud l'équation de transport des neutrons dans des contextes bien distincts. Pendant longtemps, la méthode des probabilités de collision (CP) a été l'outil principal de résolution de cette équation. Toutefois, depuis quelques années la méthode MoC lui est préférée notamment de par sa capacité à résoudre des configurations comportant un plus grand nombre de régions et de plus grande complexité. L'objectif de cette thèse est de modifier DRAGON-5 de façon à lui permettre de traiter les deux variantes de TIBÈRE (TIBÈRE1 avec réflexion spéculaire et TIBÈRE2 avec réflexion quasi-isotrope) avec la méthode MoC en 2-D. De plus, afin de tirer profit des avantages qu'offre cette méthode de résolution, une implantation en 3-D est possible et a été réalisée pour le modèle TIBÈRE2. Les deux modèles ont été implantés avec succès moyennant le stockage supplémentaire de termes provenant de la source de fuites. La vérification dans DRAGON-5 a été réalisée en comparant avec les modèles TIBÈRE2-CP et ECCO-MoC disponibles dans le code. Un calcul à 2 groupes a été réalisé sur une petite cellule où on a simulé un vide croissant puis des calculs multigroupes ont été réalisées sur les géométries suivantes : cellule CANDU6 (2-D), cellule REP (2-D et 3-D), 2 cellules et 6 cellules REP (3-D) avec et sans réflecteurs. Finalement, des cellules d'un réacteur refroidi au sodium en géométrie cartésienne (TIBÈRE-1 et 2) et hexagonale (TIBÈRE-2) et pour lesquels les effets de streaming sont plus importants sont aussi analysées. Les résultats obtenus démontrent notamment que le modèle TIBÈRE-MoC permet le traitement de zones vidangées en 2-D et en 3-D. Dans l'ensemble une bonne cohérence des résultats est observée avec TIBÈRE2-CP ainsi que ECCO-MoC. Dans les zones vidangées, on constate des différences un peu plus élevées entre CP et MoC qui sont dues au traitement analytique de la variable polaire pour CP vs le traitement numérique pour MoC. Afin d'accélérer les itérations internes pour MoC, il est suggéré d'effectuer une étude plus approfondie avec les différentes méthodes disponibles dans DRAGON.  ABSTRACT: This research focuses on the generalization of the TIBÈRE heterogeneous leakage model to the MoC method in the lattice code DRAGON-5. Neutron leakage is taken into account in lattice calculations in order to obtain more precise diffusion coefficients which will be used for the core calculation. The lattice calculation requires the solution of the neutron transport equation at different stages. For a long time, the CP method has been the main tool for solving this equation. However, nowadays the MoC method tends to supplant the CP approaches thanks to its ability to treat configurations with a greater number of regions and greater complexity. The aim of this thesis is to modify DRAGON-5 so as to allow it to treat the two variants of TIBÈRE (TIBÈRE1 with specular reflection and TIBÈRE2 with quasi-isotropic reflection) with the MoC method in 2-D. Furthermore, in order to take advantage of this method of resolution, a 3-D implementation is possible and has been realized for the TIBÈRE2 model. Both models have been successfully implemented at the cost of additional storage of terms from the source of leakage. Verification in DRAGON-5 was performed by comparing with TIBÈRE2-CP and ECCO-MoC models both available in the code. A 2-group calculation was carried out on a small cell where a progressive voiding was simulated and then multigroup computations were performed on the following geometries: CANDU6 cell (2-D), PWR cell (2-D and 3-D) , 2 PWR cells and 6 cells (3-D) with and without reflectors. Finally, LMFBR pin cells in cartesian (TIBÈRE-1 and 2) and hexagonal (TIBERE-2 only) geometry, where the effect of streaming is more important, are also analyzed. The results obtained demonstrate in particular that the TIBÈRE-MoC model allows the treatment of voided regions in 2-D and 3-D. Globally, the results show a good consistency with TIBERE2-CP as well as ECCO-MoC. In the voided regions, there are slightly higher differences between CP and MoC due to the analytical treatment of the polar variable for CP vs the numerical treatment for MoC. In order to speed up the internal iterations for MoC, it is suggested to carry out a more in-depth study with the different methods available in DRAGON.


identifier: Kordjazi, Z. (2019). Development of Oxygen Scavenging Polymeric Systems for Food Packaging Applications  [Thèse de doctorat, Polytechnique Montréal].

abstract: RÉSUMÉ: La protection des aliments sensibles à la dégradation par oxydation est un aspect crucial afin d'augmenter la durée de vie des aliments. Elle permet également de satisfaire les clients et d'assurer leur sécurité. Pour ce faire, les petits sachets sont les absorbeurs d'oxygène les plus couramment utilisés mais ils présentent plusieurs inconvénients comme être absorbés accidentellement par le consommateur ou se déchirer à l'intérieur de l'emballage. L'incorporation d'une molécule active dans la matrice polymère du film d'emballage est une approche de plus en plus courante dans le domaine des emballages actifs ; cependant ces absorbeurs d'oxygène ne sont pas aussi efficaces que les sachets.  ABSTRACT: The protection of oxygen-sensitive food products against oxidative degradation is a crucial aspect to increase the food shelf life as well as the security of packaged food and fulfill customer needs. Oxygen absorbers in the form of small sachets are the most common available oxygen scavengers that are used, but there are some drawbacks associated with these types of scavengers such as being eaten unintentionally by consumers or being ruptured inside the package. Incorporation of active molecules into a polymeric matrix is a current approach in active packaging; however, available oxygen scavengers in active packaging films are not as efficient as sachets.


identifier: Abdali, H. (2019). Development of Amino Functionalized Graphene Based Polymer Nanofibers for Gas Sensors  [Thèse de doctorat, Polytechnique Montréal].

abstract: RÉSUMÉ: Ces dernières années, la préparation d'architectures nanostructurées a été une stratégie importante pour améliorer les performances de détection de gaz. Ces matériaux ont un rapport surface / volume extrêmement élevé et ont des structures avec une nanoporosité élevée, ce qui augmente l'adsorption des gaz. Parmi ces nanomatériaux, le graphène fonctionnalisé a suscité un intérêt considérable pour l'application en détection du fait de sa conductivité variable, ce qui le rend disponible pour les phénomènes de transport d'électrons à très grande mobilité électrique en présence de gaz oxydants et réducteurs. De plus, la polyaniline (PANI) est facilement synthétisée et la structure de sa chaîne moléculaire peut être modifiée de manière pratique par copolymérisation ou dérivations structurelles. Grace à ses propriétés électriques, électrochimiques et optiques uniques, elle peut également être utilisée comme détecteur efficace pour la surveillance de composés organiques et inorganiques.  ABSTRACT: In recent years, the preparation of nanostructured architectures has been an important strategy for improving gas sensing performance. These materials have an extremely high surface-to-volume ratio and high nanoporous structures, which increases the adsorption of gases. Among these nanomaterials, functionalized graphene has generated considerable interest in sensing applications owing to its variable conductivity, which makes it available for electron transport phenomena with very high electrical mobility in the presence of oxidizing and reducing gases. Additionally, polyaniline (PANI) is easily synthesized and its molecular chain structure can be modified conveniently by copolymerization or structural derivations. Due to its unique electrical, electrochemical, and optical properties, it can also be utilized as efficient sensors for monitoring organic and inorganic compounds.


identifier: Zago, P. (2019). Ré-optimisation de plans d'expédition de marchandises par cargos aériens  [Mémoire de maîtrise, Polytechnique Montréal].

abstract: RÉSUMÉ: Lorsque des clients veulent transporter des marchandises d'un endroit à un autre par cargos aériens, il est très commun que les clients soient facturées seulement pour la capacité qu'ils ont utilisée et non pour la capacité réservée. À cause de cette politique de réservation, les clients réservent plus de capacité qu'il leur est réellement nécessaire. Il est aussi courant que les clients ne se présentent pas à l'aéroport le jour du décollage. Pour compenser cela, les compagnies ont recours à la surréservation, c'est-à-dire qu'elles vendent plus de capacité qu'elles n'en disposent réellement. Un mauvais seuil de surréservation peut occasionner deux situations : soit il est trop faible et on aurait pu accepter plus de demandes, soit trop de demandes ont été acceptées et toutes les demandes ne peuvent être chargées dans l'avion. Une certaine partie de ces demandes devra être ré-assignée à d'autres vols. Cette étape a généralement lieu quelques heures avant le départ. Ce mémoire présente, sous la forme d'un article, une méthode de ré-optimisation qui est appliquée à un plan d'expédition et dont l'objectif est de minimiser l'espérance de débordement sur un réseau aérien. Pour réduire cette dernière, les marchandises des avions plus à même de déborder sont ré-assignées à des avions moins remplis. Afin de décrire le comportement des clients, nous avons introduit une distribution qui combine une distribution de Bernoulli à une distribution normale. L'originalité de cette distribution est qu'elle permet de bien capturer le cas où les clients ne se présentent pas à l'aéroport et qu'elle traduit la différence entre la marchandise réelle et la marchandise réservée. Par la suite, nous avons développé deux modèles mathématiques en nombres entiers dont la fonction objectif est l'espérance du débordement sur le réseau. Ces modèles mathématiques, utilisés en ré-optimisation, ont permis de produire des plans d'expédition plus robustes avec moins de débordements tout en permettant une utilisation plus homogène des avions sur l'ensemble du réseau, créant ainsi de l'espace pour accepter plus de demandes sur les vols les plus saturés. Dans le premier modèle, la fonction objectif est approximée à l'aide de scénarios. Dans le second modèle, la fonction objectif est calculée analytiquement en utilisant la distribution introduite. La fonction objectif obtenue étant non-linéaire, nous l'avons approximé afin d'avoir un modèle résolvable à l'aide de solveurs commerciaux. Pour tester la précision et la rapidité de notre modèle, nous avons simulé un plan d'expédition en se basant sur un fichier de données contenant l'ensemble des vols pour le mois de mai 2017. Lors de la phase expérimentale, nous avons comparé les résultats obtenus à l'aide du modèle analytique à ceux obtenus avec le modèle par scénarios. Nous avons obtenu des solutions de qualité similaire mais le modèle analytique permet d'obtenir des solutions en des temps de calculs relativement inférieurs. De plus, un autre avantage de ce modèle est qu'il nécessite seulement de connaître la probabilité de non-présentation d'un client, la moyenne et la variance de la distribution décrivant la quantité de marchandises qu'un client souhaite transporter. Il n'est pas nécessaire de connaitre la distribution dans sa totalité, ce qui réduit considérablement le travail de préparation des données. Finalement, les résultats prometteurs, obtenus au cours de ce projet, ont permis d'évaluer la précision et le temps de résolution sur un vrai réseau de grande taille et encouragent à tester notre méthode sur des données industrielles pour voir son efficacité réelle.  ABSTRACT: When customers want to transport goods from one place to another by air cargo, it is very common for customers to be billed only for the capacity they have used and not for the reserved capacity. As a result of this reservation policy, customers are booking more capacity than they really need. It is also common for customers not to show up at the airport on the day of departure. In order to compensate for this potential waste of capacity, airfreight carriers resort to overbooking, i.e., they sell more capacity than is actually available. Nevertheless, a wrong overbooking threshold can lead to two cases: either it is too low and more requests could have been accepted, or too many requests have been accepted and not all of them can be loaded on the aircraft. Some of these requests will have to be reassigned to other flights. This stage usually takes place a few hours before departure. This thesis presents, in the form of an article, a reoptimization method that is applied to a shipping plan, and whose objective is minimize the expectation of overflow on the whole network. To reduce this expectation, the commodities from aircrafts that are more likely to overflow are reassigned to aircrafts that are less filled. In order to describe customer behaviour, we introduced a distribution that combines a Bernoulli distribution with a normal distribution. The originality of this distribution is that it makes it possible to capture the case where customers do not show up at the airport and that it reflects the difference between the actual commodities and the booked commodities. Subsequently, we developed two integer mathematical models whose objective function is the expectation of overflow on the network. These mathematical models, used in reoptimization, have made it possible to produce more robust shipping plans with fewer overflows but also to have a more homogeneous use of aircraft throughout the network, thus creating space to accept more requests on the most saturated flights. In the first model, the objective function is approximated using scenarios. In the second model, the objective function is calculated analytically using the introduced distribution. The objective function obtained being nonlinear, we approximated it in order to have a model that can be solved using commercial solvers. To test the accuracy and quality of our model, we simulated a shipping plan based on a data file containing all the flights for May 2017. In the experiments, we compared the results obtained using the analytical model with those obtained using the scenario-based model. We have obtained solutions of similar quality, but the analytical model allows us to obtain solutions in relatively shorter computation times. In addition, another advantage of this model is that it only requires knowing the probability of no-show of a client, as well as the average and the variance of the distribution describing the quantity of goods that a client wishes to transport. It is not necessary to know the entire distribution, which considerably reduces the work of data preparation. Finally, the promising results obtained during this project made it possible to evaluate the accuracy and solution time on a real large network and encourage us to test our method on industrial data to see its real effectiveness.