Aujourd’hui, les manipulateurs robotiques sont appelés à effectuer une gamme de plus en plus large de tâches allant au-delà des applications traditionnelles. Un tel type d’application est l’interaction physique humain-robot. Pour que ces systèmes soient sécuritaires, il peut être souhaitable de réduire leur poids et leur force en réduisant la taille de leurs actionneurs. En effet, réduire la taille des actionneurs augmente la sécurité de deux manières, l’inertie du manipulateur diminue et les couples générés par les moteurs sont fortement réduits. Cependant, le principal inconvénient de ces manipulateurs est la réduction de leur capacité de charge utile. C’est pourquoi une meilleure utilisation des capacités articulaires est nécessaire pour leur permettre d’accomplir des tâches qu’elles ne pourraient normalement pas accomplir. Ainsi, cette thèse présente une étude de deux types principaux de tâches pour lesquelles une stratégie d’optimisation de trajectoire efficace peut être particulièrement utile. La première tâche consiste à soulever des objets lourds, c’est-à-dire, qui dépassent la capacité de charge utile d’un manipulateur. L’étude de cette tâche pourrait mener à la conception de manipulateurs plus légers et plus capables. Ce travail se concentre sur l’étude des méthodes de génération de trajectoires permettant aux manipulateurs ayant des actionneurs relativement faibles de soulever des charges lourdes en exploitant pleinement leur dynamique. La deuxième tâche étudiée dans cette thèse est la tâche de lancer des objets. Plus précisément, la portée des manipulateurs est étudiée, c’est-à-dire, la distance maximale à laquelle un objet peut être lancé avec un manipulateur donné est recherchée. Cette tâche est étudiée à trois niveaux de complexité : la recherche de la distance maximale possible avec des contraintes de vitesse, la recherche de la capacité maximale de lancement en considérant une trajectoire complète avec des contraintes cinématiques et la recherche de la capacité maximale de lancement en considérant une trajectoire complète avec des contraintes dynamiques. Enfin, des critères de performance sont établis à partir de ces deux types de tâches afin d’aider au processus de conception d’un nouveau manipulateur. Ainsi, une simulation d’optimisation de la conception est effectuée à titre de preuve de concept. / Today, robotic manipulators are being called upon to perform an increasingly wide range of tasks that extend beyond the conventional ones required in traditional applications. One such type of application is physical human-robot interaction. In order for such systems to be safe, it can be desirable to decrease their weight and strength by reducing the size of their actuators.Indeed, reducing the size of the actuators increases safety in two manners, the inertia of the manipulator decreases and the torques generated by the motors are greatly reduced. However, the main drawback of such manipulators is the reduction of their payload capacity.Therefore, better usage of the limited joint efforts is required to enable them to perform tasks that they would normally not be able to accomplish. Thus, this thesis presents a study of two main types of tasks where an effective trajectory optimisation strategy can be particularly valuable. The first task is that of lifting heavy objects, i.e., objects that exceed the conservative estimate of the payload capacity of a manipulator. Studying this task could lead to the design of lighter,more capable manipulators. This work focuses on studying trajectory generation methods to enable manipulators with relatively weak actuators to lift heavy payloads by fully utilizing their dynamics. The second task studied in this thesis is the task of throwing objects. Specifically, the distance throwing capabilities of manipulators is studied where the maximum distance that an object can be thrown with a given manipulator is sought. This task is studied at three levels of complexity: finding the maximum possible throwing capacity of manipulators with velocity constraints, finding the maximum throwing capacity considering a full trajectory with kinematic constraints, and finding the maximum throwing capacity considering a full trajectory with dynamic constraints. Finally, performance criteria are established from these two types of tasks in order help in the process of designing a new manipulator. Thus, a simple design optimisation simulation is performed as a proof of concept.

Tableau d’honneur de la Faculté des études supérieures et postdoctorales, 2018-2019. / Les activités de distribution et d’entreposage sont des piliers importants de la chaîne d’approvisionnement. Ils assurent la stabilité du flux de matières et la synchronisation de toutes les parties prenantes du réseau. Un centre de distribution (CD) agit comme un point de découplage entre l’approvisionnement, la production et les ventes. La distribution comprend un large éventail d’activités visant à assurer la satisfaction de la demande. Ces activités passent de la réception au stockage des produits finis ou semi-finis, à la préparation des commandes et à la livraison. Les opérations d’un CD sont maintenant perçues comme des facteurs critiques d’amélioration. Elles sont responsables de la satisfaction d’un marché en évolution, exigeant des délais de livraison toujours plus rapides et plus fiables, des commandes exactes et des produits hautement personnalisés. C’est pourquoi la recherche en gestion des opérations met beaucoup d’efforts sur le problème de gestion des CDs. Depuis plusieurs années, nous avons connu de fortes avancées en matière d’entreposage et de préparation de commandes. L’activité de préparation de commandes est le processus consistant à récupérer les articles à leur emplacement de stockage afin d’assembler des commandes. Ce problème a souvent été résolu comme une variante du problème du voyageur de commerce, où l’opérateur se déplace à travers les allées de l’entrepôt. Cependant, les entrepôts modernes comportent de plus en plus de familles de produits ayant des caractéristiques très particulières rendant les méthodes conventionnelles moins adéquates. Le premier volet de cette thèse par articles présente deux importants et complexes problèmes de manutention des produits lors de la préparation des commandes. Le problème de préparation des commandes a été largement étudié dans la littérature au cours des dernières décennies. Notre recherche élargit le spectre de ce problème en incluant un ensemble de caractéristiques associées aux installations physiques de la zone de prélèvement, comme les allées étroites, et aux caractéristiques des produits (poids, volume, catégorie, fragilité, etc.). Une perspective plus appliquée à la réalité des opérations est utilisée dans notre développement d’algorithmes. Les déplacements liés à la préparation des commandes sont fortement influencés par le positionnement des produits. La position des produits dans la zone de prélèvement est déterminée par une stratégie d’affectation de stockage (storage assignment strategy). Beaucoup de ces stratégies utilisent de l’information sur les ventes des produits afin de faciliter l’accès aux plus populaires. Dans l’environnement concurrentiel d’aujourd’hui, la durée de vie rentable d’un produit peut être relativement courte. Des promotions peuvent également être faites pour pousser différents produits sur le marché. Le positionnement fourni par la stratégie d’hier ne sera probablement plus optimal aujourd’hui. Il existe plusieurs études mesurant l’impact d’une bonne réaffectation de produits sur les opérations de prélèvement. Cependant, ils étudient la différence des performances avec les positionnements passés et actuels. La littérature démontre clairement que cela apporte des avantages en termes d’efficacité. Toutefois, les déplacements nécessaires pour passer d’une position à une autre peuvent constituer une activité très exigeante. Ceci constitue le second volet de cette thèse qui présente des avancées intéressantes sur le problème de repositionnement des produits dans la zone de prélèvement. Nous présentons le problème de repositionnement des produits sous une forme encore peu étudiée aux meilleurs de nos connaissances : le problème de repositionnement. Plus précisément, nous étudions la charge de travail requise pour passer d’une configuration à l’autre. Cette thèse est structuré comme suit. L’introduction présente les caractéristiques et les missions d’un système de distribution. Le chapitre 1 fournit un survol de la littérature sur les principales fonctions d’un centre de distribution et met l’accent sur la préparation des commandes et les décisions qui affectent cette opération. Le chapitre 2 est consacré à l’étude d’un problème de préparation de commandes en allées étroites avec des équipements de manutention contraignants. Dans le chapitre 3, nous étudions un problème de préparation des commandes où les caractéristiques des produits limitent fortement les routes de prélèvement. Le chapitre 4 présente une variante du problème de repositionnement (reassignment) avec une formulation originale pour le résoudre. La conclusion suit et résume les principales contributions de cette thèse. Mots clés : Préparation des commandes, entreposage, problèmes de routage, algorithmes exacts et heuristiques, réaffectation des produits, manutention. / Distribution and warehousing activities are important pillars to an effective supply chain. They ensure the regulation of the operational flow and the synchronization of all actors in the network. Hence, distribution centers (DCs) act as crossover points between the supply, the production and the demand. The distribution includes a wide range of activities to ensure the integrity of the demand satisfaction. These activities range from the reception and storage of finished or semi-finished products to the preparation of orders and delivery. Distribution has been long seen as an operation with no or low added value; this has changed, and nowadays it is perceived as one of the critical areas for improvement. These activities are responsible for the satisfaction of an evolving market, requiring ever faster and more reliable delivery times, exact orders and highly customized products. This leads to an increased research interest on operations management focused on warehousing. For several years, we have witnessed strong advances in warehousing and order picking operations. The order picking activity is the process of retrieving items within the storage locations for the purpose of fulfilling orders. This problem has long been solved as a variant of the travelling salesman problem, where the order picker moves through aisles. However, modern warehouses with more and more product families may have special characteristics that make conventional methods irrelevant or inefficient. The first part of this thesis presents two practical and challenging material handling problems for the order picking within DCs. Since there are many research axes in the field of warehousing operations, we concentrated our efforts on the order picking problem and the repositioning of the products within the picking area. The order picking problem has been intensively studied in the literature. Our research widens the spectrum of this problem by including a set of characteristics associated with the physical facilities of the picking area and characteristics of the product, such as its weight, volume, category, fragility, etc. This means that a more applied perspective on the reality of operations is used in our algorithms development. The order picking workload is strongly influenced by the positioning of the products. The position of products within the picking area is determined by a storage assignment strategy. Many of these strategies use product sales information in order to facilitate access to the most popular items. In today’s competitive environment, the profitable lifetime of a product can be relatively short. The positioning provided by yesterday’s assignment is likely not the optimal one in the near future. There are several studies measuring the impact of a good reassignment of products on the picking operations. However, they study the difference between the two states of systems on the picking time. It is clear that this brings benefits. However, moving from one position to another is a very workload demanding activity. This constitutes the second part of this thesis which presents interesting advances on the repositioning of products within the picking area. We introduce the repositioning problem as an innovative way of improving performance, in what we call the reassignment problem. More specifically, we study the workload required to move from one setup to the next. This thesis is structured as follows. The introduction presents the characteristics and missions of a distribution system. Chapter 1 presents an overview of the literature on the main functions of a DC and emphasizes on order picking and decisions affecting this operation. Chapter 2 is devoted to the study of a picking problem with narrow aisles facilities and binding material handling equipment. In Chapter 3, we study the picking problem with a set of product features that strongly constrain the picking sequence. Chapter 4 presents a variant of the reassignment problem with a strong and new formulation to solve it. The conclusion follows and summarizes the main contributions of this thesis. Key words: Order-picking, warehousing, routing problems, exact and heuristic algorithms, products reassignment, material handling.

Le projet d’optimisation de la régularité du service de transport en commun a pour but de trouver des solutions au problème de groupage d’autobus au Réseau de Transport de la Capitale. Le phénomène est caractérisé par des intervalles irréguliers entre les passages d’autobus aux arrêts. Ce sont les retards encourus par certains autobus qui sont à l’origine du problème. Les retards relèvent d’événements sporadiques qui sont influencés par les caractéristiques physiques et temporelles d’un parcours. Cette recherche se penche plus particulièrement sur le Métrobus 807, parcours très achalandé et parcourant l’axe entre les pôles ouest et est de la Ville de Québec. L’objectif est de proposer des solutions au problème et de les comparer entre elles afin de faire les recommandations adéquates quant à une potentielle implantation. Actuellement, des intervalles irréguliers, conséquences du phénomène de groupage d’autobus, sont notés à plusieurs endroits sur le réseau entre autres sur le parcours 807. Cela nuit à l’efficacité du réseau dans son ensemble et cause des frustrations chez les utilisateurs de transport en commun dans la Ville de Québec. L’éventail L’éventail des solutions proposées dans le cadre de cette recherche se compose de solutions à la fois appliquées individuellement et de manière combinée. Les solutions proposées agissent sur les sources potentielles de retard et visent à rétablir rapidement les intervalles suite à la détection d’un événement de groupage. Les solutions sont ensuite testées en contexte de simulation à événements discrets afin de prédire leur performance en situation réelle. Le simulateur permet de tester les solutions dans un environnement dynamique où l’on peut préalablement à l’implantation quantifier et qualifier les effets escomptés de chaque solution. Les recommandations formulées permettent d’améliorer la régularité du service de transport en commun, de maximiser l’utilisation des ressources et d’offrir à l’utilisateur de transport commun un confort et une expérience améliorée. / The regularity optimization project of the public transit service aims at finding solutions to the bus bunching problem at the Réseau de Transport de la Capitale. The phenomenon is characterized by irregular intervals between the transits of buses at stops. The delays incurred by certain buses are at the origin of the problem. Delays are caused by sporadic events that are influenced by the physical and temporal characteristics of a bus line. This research focuses on the Métrobus 807, a crowded bus route that travels the axis between the West and East poles of Quebec City. The goal is to suggest solutions to the problem and to compare them with each other in order to make the proper recommendations for a potential implementation. Currently, irregular intervals, consequences of the bus bunching phenomenon, are noted in several places on the network as well as on the 807 bus route. The efficiency of the network as well as the public transit user experience in Quebec City is negatively affected. The suggested solutions in the present research include solutions applied individually as well as combined with others. The suggested solutions act on the potential sources of delays and are meant to quickly restore the intervals following the detection of a bus bunching event. The solutions are then tested under a discrete event simulation to predict their performance under real circumstances. The simulation allows to test the solutions in a dynamic environment in which it is possible to quantify and qualify the expected results prior to an implementation. The recommendations made in this research allow to improve the regularity of the public transit service, to maximize the use of resources and to offer to the public transit user a comfortable and enhanced experience.

Cette thèse explore des pistes d'amélioration du système de trafic aérien dans l'espace océanique de l'Atlantique Nord (NAT). D'abord, on considère le système actuel, où les avions suivent les rails prédefinis. On favorise les re-routages entre rails, diminuant la congestion dans l'espace continental. On applique des méthodes stochastiques d'optimisation pour trouver une configuration de vols sans conflits avec la séparation reduite entre aéronefs. Ensuite, on simule la planification des trajectoires avec le Wind Networking (WN). La source prinicipale des erreurs dans la prédiction de trajectoires étant l'incertitude dans la prévision du vent, le WN permet aux avions d'échanger leurs vents mesurés afin d'ajuster leurs prédictions. Enfin, on introduit le concept de free-flight dans NAT. Etant donné des trajectoires vent-optimales, on applique une méthode stochastique d'optimisation pour réduire le nombre de conflits au niveau stratégique, tout en conservant les trajectoires proches de leur optimum. Nos résultats numériques mettent en évidence plusieurs pistes pour améliorer le système de trafic aérien dans NAT, en considérant de nouvelles technologies et de nouveaux concepts. / This thesis investigates the ways to improve the air traffic system in the highly congested North Atlantic oceanic airspace (NAT). First, we consider the current system, where aircraft follow predefined NAT tracks. We favor the re-routings between tracks, decreasing congestion in pre-oceanic airspace, and apply stochastic methods of optimization to find a conflict-free flight configuration with reduced separation between aircraft. Second, we simulate trajectory prediction by Wind Networking (WN). While the main source of time prediction errors is the uncertainty in wind forecast, WN permits aircraft to exchange measured winds and adjust their predictions using this recent and accurate information. Third, we study the impact of introducing the free flight concept in NAT. We apply a stochastic method of optimization on data provided by NASA consisting of NAT flights with wind optimal trajectories. The aim is to reduce the number of conflicts on the strategic level, while keeping the trajectories close to the optimal routes. Our computational experiments show that the air traffic situation in NAT can be improved in several different ways, considering new technologies and new trajectory planning concepts.

Cette thèse porte sur l'utilisation de données de vols pour l'optimisation de trajectoires de montée vis-à-vis de la consommation de carburant.Dans un premier temps nous nous sommes intéressé au problème d'identification de modèles de la dynamique de l'avion dans le but de les utiliser pour poser le problème d'optimisation de trajectoire à résoudre. Nous commençont par proposer une formulation statique du problème d'identification de la dynamique. Nous l'interpretons comme un problème de régression multi-tâche à structure latente, pour lequel nous proposons un modèle paramétrique. L'estimation des paramètres est faite par l'application de quelques variations de la méthode du maximum de vraisemblance.Nous suggérons également dans ce contexte d'employer des méthodes de sélection de variable pour construire une structure de modèle de régression polynomiale dépendant des données. L'approche proposée est une extension à un contexte multi-tâche structuré du bootstrap Lasso. Elle nous permet en effet de sélectionner les variables du modèle dans un contexte à fortes corrélations, tout en conservant la structure du problème inhérente à nos connaissances métier.Dans un deuxième temps, nous traitons la caractérisation des solutions du problème d'optimisation de trajectoire relativement au domaine de validité des modèles identifiés. Dans cette optique, nous proposons un critère probabiliste pour quantifier la proximité entre une courbe arbitraire et un ensemble de trajectoires échantillonnées à partir d'un même processus stochastique. Nous proposons une classe d'estimateurs de cette quantitée et nous étudions de façon plus pratique une implémentation nonparamétrique basé sur des estimateurs à noyau, et une implémentation paramétrique faisant intervenir des mélanges Gaussiens. Ce dernier est introduit comme pénalité dans le critère d'optimisation de trajectoire dans l'objectif l'intention d'obtenir directement des trajectoires consommant peu sans trop s'éloigner des régions de validité. / This thesis deals with the use of flight data for the optimization of climb trajectories with relation to fuel consumption.We first focus on methods for identifying the aircraft dynamics, in order to plug it in the trajectory optimization problem. We suggest a static formulation of the identification problem, which we interpret as a structured multi-task regression problem. In this framework, we propose parametric models and use different maximum likelihood approaches to learn the unknown parameters.Furthermore, polynomial models are considered and an extension to the structured multi-task setting of the bootstrap Lasso is used to make a consistent selection of the monomials despite the high correlations among them.Next, we consider the problem of assessing the optimized trajectories relatively to the validity region of the identified models. For this, we propose a probabilistic criterion for quantifying the closeness between an arbitrary curve and a set of trajectories sampled from the same stochastic process. We propose a class of estimators of this quantity and prove their consistency in some sense. A nonparemetric implementation based on kernel density estimators, as well as a parametric implementation based on Gaussian mixtures are presented. We introduce the later as a penalty term in the trajectory optimization problem, which allows us to control the trade-off between trajectory acceptability and consumption reduction.

Cette thèse s'inscrit dans l'amélioration de la gestion du trafic aérien. Le vent et la température sont deux paramètres omniprésents, subis, et à l'origine de nombreux biais de prédiction qui altèrent le suivi des trajectoires. Nous proposons une méthode pour limiter ces biais. Le concept "Wind and Température Networking" améliore la prédiction de trajectoire en utilisant le vent et la température mesurés par les avions voisins. Nous détaillons les effets de la température sur l'avion, permettant sa prise en compte. L'évaluation du concept est faite sur 8000 vols. Nous traitons du calcul de trajectoires optimales en présence de vent prédit, pour remplacer les actuelles routes de l'Atlantique Nord, et aboutir à des groupes de trajectoires optimisées et robustes. Dans la conclusion, nous présentons d'autres champs d'applications du partage de vents, et abordons les besoins en nouvelles infrastructures et protocoles de communication, nécessaires à la prise en compte de ce nouveau concept. / This thesis is related to air traffic management systems current changes. On the ground and in flight, trajectory calculation methods and available data differ. Wind and temperature are two ubiquitous parameters that are subject to and cause prediction bias. We propose a concept to limit this bias. Our "Wind and Temperature Networking" concept improves trajectory prediction, using wind and temperature information from neighboring aircraft. We detail the effects of temperature on the aircraft performances, allowing for temperature to be taken into account. The concept evaluation is done on 8000 flights. We discuss the calculation of optimal trajectories in the presence of predicted winds, to replace the current North Atlantic Tracks, and to provide optimized and robust groups of trajectories. The conclusion of this thesis presents other fields of wind sharing applications, and addresses the need for new telecommunications infrastructures and protocols.