Résumé : / Abstract :

Cette thèse est une illustration de problèmes de Recherche Opérationnelle abordés dans le contexte hospitalier du CHRU de Tours. La problématique considérée relève des transports et plus exactement de tournées de véhicules. Cette thèse s'articule autour de l'étude de deux principaux problèmes : le transport de flux de produits et le transport de flux de patients. Le premier problème de tournées de véhicules concerne toute la gestion des différents types de flux logistiques (logistique hôtelière, pharmacie, lingerie,plateaux repas, etc.) à livrer ou à collecter dans les services de soins de chaque hôpital du CHRU de Tours. Le deuxième problème concerne les transports de patients aussi bien urgents (SAMU) que planifiés (Centrale des ambulanciers). Pour résoudre ces problèmes, plusieurs méthodes s'inspirant des techniques de la RO sont proposées : des méthodesexactes (programmation linéaire en nombres entiers), des heuristiques (algorithme glouton, recherche tabou avec et sans mémoire adaptative, algorithme génétique, algorithme mémétique) et des moteurs de simulation à événements discrets ont été développés. Des expérimentations numériques valident l'intérêt et la qualité des méthodes développées. / This thesis illustrates the OR problems found in a general hospital context like the hospital complex of Tours. The problem is addressed in this thesis is a vehicle routing problem. This work focuses on the study of two main problems : the transportation of patient and the transportation of commodities. The first problem of vehicle routing deals with the logistics flows in an hospital complex (clean linen, meals carts, medicines, sterile equipments, etc.) which are to be delivered or picked up in the hospital units, locatedat different places in the city. The second problem deals with the emergency patient transport (Emergency Medical Assistance Service) as well as with the planned transports (ambulance central station). To solve these problems, several methods based on techniques of OR are proposed: exact methods (integer linear programming), heuristics (greedyalgorithm, tabu search with and without adaptive memory, genetic algorithm, memetic algorithm), and discrete event simulations.

Automatiser la conduite peut réduire le risque d'accidents et fluidifier le trafic en s’appuyant sur des communications entre véhicules et avec une infrastructure dédiée. Maintenir les services lorsque l’infrastructure faillit nécessite un protocole de routage adapté aux communications véhicule-à-véhicule (V2V). Cette thèse pose l’hypothèse de l’absence d’infrastructure et de service global de localisation, chaque véhicule connaissant sa seule position. Un modèle d’organisation des communications V2V, CBL, est proposé pour créer et maintenir une structure supportant les échanges proches, entre véhicules voisins, et lointains à travers le trafic. Il crée une hiérarchie où des groupes dissociés de véhicules voisins (feuilles) sont connectés via un véhicule leader (branche) à une colonne vertébrale (chaîne) formée le long de la route par interconnexion des branches. CBL requière la seule connaissance du voisinage à un saut et peut s’intégrer à tout protocole de routage. Les évaluations sur des scénarios routiers montrent que CBL exploite mieux les contraintes spatiales dues à la route, obtenant une structure plus adaptée à l’optimisation du trafic broadcast comparativement à la technique des multipoints relais dans OLSR, mais aussi face aux protocoles DSR, AODV et GRP, pour un trafic basé sur les préconisations IEEE de taille et fréquence de messages en milieu routier. Des évaluations sur des trafics d’applications coopératives telles que l’égo-localisation et la perception élargie montrent que CBL offre un service de communication à latence et taux de pertes faibles selon un compromis voulu entre fréquence de messages et performances. / Automated driving can reduce accidents and improve the traffic flow by using communications between vehicles and dedicated infrastructures. Maintaining services when an infrastructure failed requires a routing protocol adapted to vehicle-to-vehicle (V2V) communications. This dissertation assumes the absence of dedicated infrastructure and global location service, each vehicle knowing its only own position. A V2V communication organization model, CBL, is proposed to create and maintain a structure that supports close exchanges between neighbouring vehicles and remote exchanges through the traffic. CBL creates a hierarchy where disjoint groups of neighbouring vehicles (leaves) are connected via a leader vehicle (branch) to a backbone (chain) formed along the road by the interconnection of the branches. CBL requires only the knowledge of the one-hop neighborhood and can be integrated into any routing protocol. The evaluations on road scenarios using IEEE-based traffic recommended on road environments in terms of size and message frequency show that CBL makes a better use of the spatial constraints due to the road. A structure is obtained that suits better in the optimisation of the broadcast traffic than the technique of multipoint relays in OLSR, but also compared to DSR, AODV and GRP protocols. Evaluations of cooperative application traffic such as ego-localization and extended perception show that CBL offers a communication service with low latency, low packet loss, according to a wanted trade-off between message frequency and performance.

Intitulée « Economie de l’innovation – le cas du véhicule intelligent », cette thèse analyse la montée en puissance de l’innovation dans le transport à travers la croissance de l’intelligence artificielle dans les véhicules, les infrastructures et les postes centralisés de régulation et de surveillance. Elle introduit de nouveaux instruments théoriques en économie de l’innovation, définissant le cadre d’une économie comportementale de l’innovation. Ces nouveaux instruments théoriques sont appliqués au cas des concepteurs et des consommateurs-conducteurs du véhicule intelligent. Les apports novateurs portent sur : - l’impact sur la sécurité routière des systèmes intelligents ; - les conditions de l’acceptabilité et de la diffusion des systèmes intelligents ;- l’évolution de l’industrie automobile vers le véhicule intelligent ; - la conception générale du véhicule intelligent : l’intelligence artificielle intégrée dans le véhicule comme un outil ou le véhicule comme accessoire de l’intelligence du mouvement. / Titled “Economy of innovation – The case of the intelligent (smart ?) vehicle”, this thesis deals with the growing innovation in the transportation means through the growing importance of artificial intelligence in vehicles, in infrastructures, and in centralized regulation and monitoring centers. It presents new theoretical instruments applicable for the economy of innovation by defining the framework of its behavioral aspects. These new theoretical instruments are applied to the case of designers and to the case of consumers-drivers of the intelligent vehicle. Innovative topics are the following: - the impact of intelligent systems on road safety, - the conditions for accepting and spreading intelligent systems, - the evolution of the car industry towards the intelligent vehicle, - the global design of the intelligent vehicle: the artificial intelligence embedded in the vehicle as an assistant tool or the vehicle as secondary to the intelligence of the movement.

Les tournées de service concernent l’organisation de déplacement de personnels vers des clients. Lors de la planification et de l’exécution de tournées de service mono-période, les entreprises sont confrontées aux aléas des temps de service et de parcours. C’est pourquoi, dans cette thèse, nous nous intéressons à une variante du problème de tournées de service, dans laquelle les temps de parcours et de service sont stochastiques. Il s’agit du problème de tournées de service multi-dépôt, incluant fenêtres de temps, temps de service et de parcours stochastiques avec priorité entre les clients (distinction clients obligatoires / clients optionnels). Pour résoudre cette problématique, nous proposons trois méthodes différentes. Dans la première méthode, nous construisons des routes contenant uniquement des clients obligatoires puis nous procédons à l’insertion des clients optionnels. La deuxième méthode est une méthode approchée basée sur la génération de colonnes consistant à générer un ensemble de routes de bonne qualité pour chaque véhicule puis à en sélectionner une par véhicule. La dernière méthode est un algorithme de branch and price dans lequel le sous-problème consiste à générer des routes réalisables pour un véhicule donné, tandis que le problème maître permet de sélectionner des routes en s’assurant que la priorité des clients est respectée. Après chacune de ces méthodes, afin d’évaluer la qualité de ces solutions face aux aléas, nous utilisons un algorithme de programmation dynamique et procédons à un ensemble de simulations du déroulement des tournées en temps réel. Nous avons testé ces méthodes sur des problèmes dont les données sont issues du milieu industriel. / The field service routing problem consists in assigning the visits of technicians to clients in order to satisfy their requests for service activities such as maintenance. When planning service routes, companies have to face hazardous travel and service times. Therefore, in this thesis, we deal with a variant of the single-period field service routing problem in which travel and service times are stochastic. It is the field service routing problem with multiple depots, time windows, stochastic travel and service times and priority within customers (distinguishing mandatory and optional customers). To solve this problem, we propose three different methods. In the first one, we first build routes containing only mandatory customers and then, we insert optional customers in these routes. The second one is a heuristic method based on column generation consisting in generating a set of valuable routes for each vehicle and then in selecting one route per vehicle. The last method is a branch and price algorithm, based on the second method, in which the subproblem consists in finding feasible routes for a given vehicle, whereas the master problem consists in selecting routes while ensuring that customer’s priority is respected. After each of these methods, in order to evaluate the quality of these solutions regarding stochasticity, we use a dynamic programming algorithm and we proceed to a set of simulations of the real-time execution of the service activities over the period. All our experimentations have been made on problems coming from realistic data.

Pour les systèmes de commande sous la forme de dx/dt = f (x, u), dans la littérature, les chercheurs s'intéressaient à la stabilisation de ce système de différentes manières : asymptotique, uniformément asymptotique, partielle, en temps fini, etc. Pour aboutir à ces résultats, les méthodes utilisées font appel aux techniques suivantes : Lyapunov, Lasalle, Barbalat, surface glissante, etc. Dans cette thèse, nous nous sommes intéressés à une autre fonctionnalité de la commande, dite commande répulsive stabilisante. Les résultats ont été généralisés au cas d'un système avec dérive et sans dérive. Comme résultat, l'approche de commande qu'on propose assure la stabilité du système autour d'une position désirée et la répulsion de celui-ci par rapport à un ensemble indésirable, construit dans l'espace de navigation. Toute forme d'application sera concernée par nos résultats théoriques, on peut citer, la navigation terrestre et aérienne dans un environnement peu ou pas connu. De même, la commande qu'on propose préserve la communication inter-agent, une fois planifiées. En terme d'application, on a considéré le modèle d'un véhicule à roues type unicycle, sans tenir compte de l'orientation (cas non holonôme) et dans le cas où l'environnement contient un ou plusieurs obstacle(s). Contrairement aux résultats de la littérature, qui sont basés sur une commande à structure variable pour l'évitement d'un obstacle, la commande répulsive-stabilisante trouvée est une commande continue sur l'espace de navigation. La deuxième partie de cette thèse traite le problème de stabilité d'une formation d'agents (système multi-véhicules) qui évolue dans un environnement hostile tout en préservant la communication entre les agents. Pour réussir la formation, la décentralisation de la commande par rapport aux agents est rendue robuste à travers des graphes de communication. Ces graphes relèvent de la stratégie et objectifs de la formation. Nos résultats de stabilité ont fait l'objet d'une implémentation rigoureuse sur un simulateur réalisé sous Matlab. / For control systems in the form dx/dt = f (x, u), in the literature, researchers were interested in stabilizing the system in different ways : asymptotic, uniformly asymptotic, partial, in #nite time, etc. To achieve these results, the methods involve the following techniques : Lyapunov, LaSalle, Barbalat, sliding surface, etc. In this thesis, we became interested in another feature form of the controller, called repulsive stabilizing controller. The results were generalized to the case of a system with drift and without drift. As a result, the proposed control approach ensures the system stability around a desired position and the repulsion of the latter over a set junk, built in the navigation space. Any form of application will be concerned by our theoretical results including, terrestrial and aerial navigations in a little known or not known environment. Similarly, the proposed control law, once planned, preserves the inter-agent communication. In terms of application, we considered the model of a unicycle-type wheeled vehicle, regardless of orientation (non-holonomic case) and where the environment contains one or more obstacle(s). Contrary to the results of the literature, which are based on a switching control structure for avoidance of an obstacle, the stabilizing repulsive found is a smooth and continuous controller on the navigation space. The second part of this thesis addresses the stability problem of a formation of agents (multi-vehicle) operating in a hostile environment while maintaining the communication between agents. To successfully the strategy of the formation, the decentralized controller over agents is made robust through communication graphs. These graphs are performed according to the formation strategy and objectives. Our stability results have been implemented in a simulator made in Matlab.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Les technologies de navigation autonome ont grandement progressé dans les deux dernières décennies. La majorité de ces avancées ont été validées en environnements intérieurs et contrôlés, comme les entrepôts et les pistes de course. Toutefois, les industries qui bénéficieraient le plus de l'automatisation des véhicules tendent à opérer en environnements hors route éloignés. Ces industries incluent l'agriculture, la construction, la défense et la foresterie. De plus, le déploiement sécuritaire de ces technologies en environnements nordiques requiert leur robustesse aux conditions hivernales. La précipitation et l'accumulation de neige entraînent des problèmes significatifs et non réglés pour les systèmes de navigation autonome, incluant le bruit de mesure de capteurs, le faible contraste de repères visuels et la variabilité de traction. La météo hivernale peut également causer un sol glacé, qui est caractérisé par une friction faible entre le pneu et le sol. La méthode la plus répandue pour localiser des véhicules est système de positionnement par satellites (GNSS), qui offre un positionnement global d'une exactitude centimétrique, si le signal de suffisamment de satellites est reçu. L'accès à un signal GNSS exacte et fiable pour la localisation en environnements éloignés est limité, ce qui bloque l'utilisation sécuritaire des technologies de navigation autonome dans ces industries. Cette thèse s'attaque au problème de la robustesse de la navigation autonome en régions nordiques en déployant des véhicules autonomes en conditions hivernales et en forêts subarctiques. Comme cette technologie inclut plusieurs composantes, l'emphase est mise sur les sous-problèmes du suivi de chemin, de la localisation et de la cartographie. Les modèles de mouvements sont une composante fondamentale pour les algorithmes de suivi de chemin. L'exactitude de la prédiction de ces modèles est corrélée avec la performance de suivi de chemin. Par conséquent, améliorer l'exactitude de prédiction des modèles de mouvement en conditions hivernales permettra aux véhicules sans pilote (UGVs) d'opérer en conditions nordiques, tout au long de l'année. Dans le Chapitre 2, une évaluation expérimentale de modèles cinématiques pour véhicules à direction par glissement (SSMRs) sur l'asphalte et les terrains enneigés est proposée. Le mouvement des SSMRs est significativement différent sur les deux terrains, et la récolte d'un jeu de données d'entraînement pour n'importe quel modèle de mouvement est long et sujet à un biais en stimulation des commandes du véhicule. Aussi, la plus grande d'erreur de prédiction pour les SSMRs est le glissement angulaire, ce qui motive le développement de modèles et contrôleurs qui raisonnent avec ce phénomène. Ce travail motive les contributions présentées au Chapitre 3. Un protocole de récolte de jeu de données d'entraînement de modèle automatisé permet de minimiser le biais de récolte du jeu de données et de générer un modèle exact avec 46 sec de temps de conduite, le temps le plus court observé dans les travaux connexes. Celui-ci est couplé avec un modèle d'apprentissage du glissement, qui résonne avec la dynamique des SSMRs tout en requérant peu de connaissances sur les propriétés du véhicule et du terrain. La combinaison de ce protocole et ce modèle est particulièrement utile pour générer rapidement un modèle exact pour un UGV opérant dans un nouvel environnement, en minimisant les coûts énergétiques. Dans le Chapitre 4, les modèles évalués dans le Chapitre 2 sont utilisés pour déployer un UGV et compléter 18.8 km de navigation dans une forêt boréale, durant l'hiver. Les données enregistrées lors de ce déploiement sont utilisées pour produire un rapport de terrain qui décrit l'impact de ce biome et cette météo sur la navigation par lidar. Les impacts les plus importants sont le manque de fiabilité du signal GNSS en raison de la végétation dense et la faible quantité de repères géométriques dans les pistes forestières, ce qui mène à une grande incertitude de localisation dans la direction longitudinale du UGV. Ce rapport montre que c'est l'accumulation de neige, et non la précipitation, qui a un impact significatif sur l'exactitude de la localisation, menant potentiellement à l'échec du système. Une liste de leçons apprises et de défis futurs menant à l'autonomie tout au long de l'année en forêt boréale est aussi présentée. Enfin, une conclusion fournit une liste de défis ouverts en modélisation, suivi de chemin, localisation et cartographie. Ces défis sont fournis avec l'objectif de guider et de motiver des pairs à continuer à repousser les limites des technologies de navigation autonome en régions nordiques. / Autonomous navigation technologies have made great advances in the last two decades. The vast majority of these are proven in indoors or controlled environments, such as warehouses or racetracks. However, industries that stand to benefit the most from vehicle automation tend to operate in remote, off-road environments. These include agriculture, construction, mining, defense and forestry. Additionally, safe deployment of such technologies in northern environments will require robustness to harsh winter weather. Snow precipitation and accumulation cause significant unresolved challenges for autonomous navigation systems, such as sensor noise, low visual feature contrast and traction variability. Winter weather can also lead to icy terrain, characterized by low tire-terrain friction and high vehicle slip. The most widespread method for localizing vehicles is Global Navigation Satellite System (GNSS), providing centimeter-accurate global positioning, if signal from enough satellites is available. Access to accurate and reliable GNSS signal for localization in remote environments is limited, which prevents the safe usage of autonomous vehicles within these industries. This thesis tackles the problem of improving autonomous navigation robustness in northern regions by deploying vehicles in winter conditions and subarctic forests. Since this technology includes many components, the emphasis is placed on the path following, localization and mapping sub-problems. Motion models are a fundamental component of path following algorithms, and increasing their accuracy and robustness is correlated with path following performance. Thus, improving model prediction accuracy in winter weather will enable uncrewed ground vehicles (UGVs) to operate in northern regions, throughout the year. In Chapter 2, an experimental evaluation of kinematic motion models for skid-steer mobile robots (SSMRs) on concrete and snow-covered terrain is proposed. SSMR motion is significantly different on both terrains and gathering a training dataset for any motion model is time-consuming and subject to bias in input sampling. Also, the largest error source for motion prediction of SSMRs is angular slip, motivating novel models and controllers accounting for this phenomenon. This leads to the contributions presented in Chapter 3. An automated training dataset gathering protocol is proposed, minimizing input sampling bias and generate accurate motion models with 46 sec, the shortest training driving time from similar work. This protocol is coupled with a novel slip learning model, that accounts for SSMR dynamics while requiring minimal knowledge about the vehicle and terrain properties. The combination of the protocol and model is especially useful to quickly generate an accurate motion model for any UGV operating in a novel environment, while minimizing energy costs. In Chapter 4, we use the models evaluated in Chapter 2 to deploy a UGV and successfully conduct 18.8 km of autonomous navigation in a boreal forest during wintertime. The data recorded during this deployment is then used to produce a field report describing the impact of this biome and weather on lidar-based navigation. The most important ones are the unreliability of GNSS signal due to dense vegetation and low geometrical features of forest trails, which lead to localization uncertainty in the UGV's longitudinal direction. Furthermore, it is not snow precipitation, but snow accumulation that has a significant impact on localization accuracy, potentially leading to localization failure. A list of lessons learned and upcoming challenges to year-long autonomy in boreal forests is presented. Lastly, a conclusion provides a list of open challenges related to motion modeling, path following, localization and mapping. These are given with the aim to guide and motivate fellow researchers to continue pushing the robustness of autonomous navigation technologies in northern regions.

L'automobile est un moyen de transport de prédilection puisqu'elle confère beaucoup de liberté aux utilisateurs. Cependant, les coûts sociaux et économiques reliés aux accidents de la route, ainsi que les émissions polluantes produites par la combustion des hydrocarbures, représentent une problématique à laquelle le Réseau de centres d'excellence AUTO21 s'intéresse. Notamment, AUTO21 finance ce projet qui porte sur les architectures décisionnelles appliquées aux trains de véhicules. Un train de véhicule est un système de transport intelligent regroupant un ensemble de véhicules qui se suivent les uns derrière les autres, conservant une faible distance entre eux.L'architecture DCD est une architecture décisionnelle complète avec communication bidirectionnelle responsable de la prise de décision distribuée d'un groupe de véhicules opérant au sein d'un train de véhicules.L'architecture réalise la plupart des manoeuvres réalisables dans les trains de véhicules tels l'insertion ou le retrait d'un véhicule dans le train, ainsi que la gestion des situations d'urgences telles les collisions et la défaillance de certains capteurs. La validation de l'architecture est effectuée avec un groupe de quatre robots mobiles équipés d'un système de positionnement relatif qui permet de localiser les véhicules les uns par rapport aux autres. Un ensemble de 18 scénarios de tests, couvrant un large éventail des situations susceptibles de survenir dans les trains de véhicules, est réalisé. Les résultats obtenus indiquent que la prise de décision des véhicules, ainsi que la coordination des véhicules via la communication sont robustes et permettent l'exécution des manoeuvres attendues.

Ce projet de recherche présente les résultats d'une étude qualitative explorant la possible relation entre la distance temporelle perçue et l'intention d'adoption du camion à l'hydrogène, du camion électrique et du camion autonome par les parties prenantes de l'industrie du camionnage canadienne. Le camion à l'hydrogène et le camion électrique se présentent comme alternative aux carburants fossiles pour l'industrie du camionnage tandis que le camion autonome pourrait être une solution à la pénurie de main-d'œuvre. Les facteurs explorés furent la distance temporelle, la résistance aux changements du PDG ou de l'équipe de direction, l'attitude envers les solutions de remplacement proposées et le type de transport effectué ou consommé. Afin de collecter les données, une entrevue individuelle semi-dirigée d'environ une heure fut réalisée auprès de 31 experts de l'industrie du camionnage. La perception de la distance temporelle (élevée vs faible) a semblé être positivement liée à l'intention d'adoption pour le camion électrique ainsi que le camion autonome. Dans le cas du camion à l'hydrogène, la possible relation ne put être explorée dû à un manque de connaissance de la part des répondants. / This research project presents the results of a qualitative study exploring the possible relationship between perceived temporal distance and the intention to adopt the hydrogen truck, the electric truck and autonomous truck by stakeholders of the Canadian trucking industry. The hydrogen truck and the electric truck are presented as an alternative to fossil fuels for the trucking industry while the autonomous truck could be a solution to the labour shortage. Factors explored were temporal distance, CEO or management team resistance to change, attitude toward the proposed alternatives and the type of transport performed or consumed. In order to collect the data, an individual semi-structured interview lasting approximately one hour was conducted with 31 trucking industry experts. The perception of temporal distance (high vs. low) seemed to be positively related to the intention to adopt for the electric truck as well as the autonomous truck. In the case of the hydrogen truck, the possible relationship could not be explored due to a lack of knowledge on the part of the respondents.