Nous étudions dans cette thèse un problème de construction de tournées de véhicules pour le transport de personnes à la demande (TAD) qui, combinant la souplesse des taxis à la capacité de regroupement des transports en commun, est une voie pour repenser nos pratiques en terme de mobilité. Après avoir défini puis classé plusieurs critères de qualité de service, nous en sélectionnons trois pour leur représentativité : la minimisation de la distance totale parcourue, la maximisation du taux de remplissage des véhicules et la minimisation du temps perdu en transport. La méthode d'optimisation utilisée est basée sur une approche par décomposition appelée génération de colonnes. Nous nous plaçons dans le cas statique où toutes les demandes sont connues par avance. L'adaptation de cette méthode exacte aux trois critères choisis induit des développements originaux, comme la modélisation du réseau par un p-graphe ou l'optimisation d'une fonction objectif fractionnaire. Cette étude est intégrée à un projet pluridisciplinaire piloté par des géographes qui a pour sujet d'expérimentation la mise en place d'un TAD opérationnel dans le Pays du Doubs Central (France). Un algorithme de résolution heuristique spécifique a été développé pour cette application. L'intégration des résultats des deux algorithmes à un Système d'Information Géographique permet une analyse des critères de qualité de service et de leurs interactions avec le territoire d'un point de vue géomatique. Il en découle une étude sur la forme des tournées et plus particulièrement sur différentes mesures de leur sinuosité.

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éthodes exactes (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'interêt et la qualité des méthodes développées.

Le management de la chaîne logistique concerne un large éventail d'activités. Nombreuses ceux qui ont un caractère incertain apportant souvent des conséquences inattendues. Malgré cela, l'incertitude est fréquemment non considérée dans la gestion de la chaîne logistique traditionnelle. En plus de l'incertitude, l'indisponibilité des ressources augmentera la complexité du problème. En prenons en compte les contraintes d'incertitude et de disponibilité nous étudions le management de la chaîne logistique selon différents aspects. Cette thèse représente une tentative de recherche afin d'aborder ce problème d'une façon systématique et complète et nous espérons que notre travail contribuera aux futurs travaux de recherche et sera utile aux gestionnaires de la chaîne logistique. Nous nous concentrons sur trois sources classiques de l'incertitude ; celle de la demande, celle la fabrication et celle liée à la distribution. Pour chaque source d'incertitude, nous analysons ses causes et ses impacts sur les performances de la chaîne logistique. L'incertitude est spécifiée dans des problèmes classiques concrets et des approches sont proposées pour les résoudre. Nous nous sommes également focalisés sur le problème bi-niveau de vendeur de journaux qui représente une chaîne logistique miniature, concerné par une double incertitude. Les méthodes utilisées offrent une bonne démonstration du traitement des variables incertaines dans les problèmes de décision.

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

Les entreprises de transport font face à des problèmes de taille grandissante où l'utilisation de transbordement peut avoir un impact significatif sur les coûts. ILOG TPO est un logiciel capable de résoudre de tels problèmes, mais il lui est difficile de prendre de bonnes décisions concernant le transbordement. De plus, le processus de résolution d'ILOG TPO est basé sur la recherche locale, et il peut être aidé pour certaines décisions globales comme le transbordement. Cette thèse se place dans ce contexte, et son objectif est d'aider ILOG TPO à trouver de meilleures solutions. Pour cela, une formulation complète est d'abord proposée pour résoudre les plus petites instances, et avec une technique de plans coupants, les solutions optimales sont généralement trouvées en un temps raisonnable. Ensuite, un algorithme à deux phases qui inclut un programme en variables mixtes (MIP) sur une relaxation de type réseau du problème est donné pour de plus grandes instances. Cet algorithme est une coopération entre le MIP et ILOG TPO, où le MIP donne à ILOG TPO, pour chaque ordre de transport, le chemin de hubs par lequel il devrait être acheminé. Cette heuristique trouve des solutions similaires à ILOG TPO seul, mais le temps de calcul est réduit de façon significative.

Dans cette thèse, nous proposons d'aborder l'ordonnancement des transports par une approche interdisciplinaire. L'idée est d'intégrer les facteurs humains dans le système d'aide à la décision réalisé, de façon à ce que l'homme puisse agir sur la modélisation et la résolution du problème. Le système proposé doit offrir de la flexibilité, afin d'être capable de s'adapter aux nouvelles situations et aux changements, même si ceux-ci n'ont pas été prévus initialement par le concepteur du système. Pour atteindre l'objectif fixé, nous nous sommes notamment appuyé sur une analyse du domaine de travail (" Work Domain Analysis ") basée sur une hiérarchie d'abstraction des entités (physiques ou plus abstraites) manipulées dans ce type de problèmes. Nous avons proposé une architecture pour le système d'aide à la décision basée sur cette analyse du domaine et la programmation par contraintes. Nous avons également conçu, et intégré dans le système, des algorithmes dédiés et des méthodes de résolution basés sur le principe d'inversion de modèle. Enfin, nous avons proposé une architecture d'interfaces avec l'objectif d'assister efficacement l'opérateur humain dans la réalisation des différentes sous-tâches nécessaires à la résolution globale du problème. L'étude du sujet interdisciplinaire a été précédée d'une analyse focalisée sur la résolution de problèmes théoriques d'ordonnancement à machines parallèles avec contraintes de précédence et temps de préparation des machines entre opérations, utilisant des méthodes de recherche arborescente basée sur les divergences.

La distribution de liquide cryogénique en « vrac », ou par camions citernes, est un cas particulier des problèmes d’optimisation logistique. Ces problèmes d’optimisation de chaines logistiques et/ou de transport sont habituellement traités sous l’hypothèse que les données sont connues à l’avance et certaines. Or, la majorité des problèmes d’optimisation industriels se placent dans un contexte incertain. Mes travaux de recherche s’intéressent aussi bien aux méthodes d’optimisation robuste que stochastiques.Mes travaux portent sur deux problèmes distincts. Le premier est un problème de tournées de véhicules avec gestion des stocks. Je propose une méthodologie basée sur les méthodes d’optimisation robuste, représentant les pannes par des scénarios. Je montre qu’il est possible de trouver des solutions qui réduisent de manière significative l’impact des pannes d’usine sur la distribution. Je montre aussi comment la méthode proposée peut aussi être appliquée à la version déterministe du problème en utilisant la méthode GRASP, et ainsi améliorer significativement les résultats obtenu par l’algorithme en place. Le deuxième problème étudié concerne la planification de la production et d’affectation les clients. Je modélise ce problème à l’aide de la technique d’optimisation stochastique avec recours. Le problème maître prend les décisions avant qu’une panne ce produise, tandis que les problèmes esclaves optimisent le retour à la normale après la panne. Le but est de minimiser le coût de la chaîne logistique. Les résultats présentés contiennent non seulement la solution optimale au problème stochastique, mais aussi des indicateurs clés de performance. Je montre qu’il est possible de trouver des solutions ou les pannes n’ont qu’un impact mineur. / The distribution of liquid gazes (or cryogenic liquids) using bulks and tractors is a particular aspect of a fret distribution supply chain. Traditionally, these optimisation problems are treated under certainty assumptions. However, a large part of real world optimisation problems are subject to significant uncertainties due to noisy, approximated or unknown objective functions, data and/or environment parameters. In this research we investigate both robust and stochastic solutions. We study both an inventory routing problem (IRP) and a production planning and customer allocation problem. Thus, we present a robust methodology with an advanced scenario generation methodology. We show that with minimal cost increase, we can significantly reduce the impact of the outage on the supply chain. We also show how the solution generation used in this method can also be applied to the deterministic version of the problem to create an efficient GRASP and significantly improve the results of the existing algorithm. The production planning and customer allocation problem aims at making tactical decisions over a longer time horizon. We propose a single-period, two-stage stochastic model, where the first stage decisions represent the initial decisions taken for the entire period, and the second stage representing the recovery decision taken after an outage. We aim at making a tool that can be used both for decision making and supply chain analysis. Therefore, we not only present the optimized solution, but also key performance indicators. We show on multiple real-life test cases that it isoften possible to find solutions where a plant outage has only a minimal impact.

Nous nous sommes intéressés à la problématique d’organisation des tournées de soins à domicile dans le cadre de structures de maintien à domicile comme par exemple les service d’Hospitalisation À Domicile ou les Services de Soins Infirmiers À Domicile. Les soins sont prodigués au domicile des patients par un ou deux soignants d’un type défini, comme médecin ou infirmier par exemple pendant une période de disponibilité du patient. Le patient est caractérisé par un niveau de dépendance et peut exprimer une préférence pour être soigné par un soignant plutôt qu’un autre. L’objectif est de construire les tournées des soignants en rendant visite à tous les patients tout en minimisant la longueur (ou durée) des tournées, en équilibrant les tournées suivant le niveau de dépendance des patients et en favorisant la préférence des patients. Après avoir réalisé un état de l’art des problèmes d’organisation de tournées de soins à domicile, nous proposons deux modélisations mathématiques de notre problème sous la forme d’un multiple Traveling Salesman Problem avec fenêtres de temps (m-TSPTW) auquel s’ajoute des contraintes spécifiques comme la synchronisation d’activités ou la prise en compte de types de ressource et des critères de performance propres au problème (équilibrage et préférence). Nous avons ensuite proposé des méthodes approchées basées sur des couplages métaheuristique - modèle de simulation testées sur des instances de la littérature d’un problème proche du nôtre et des instances adaptées à notre problème. Pour terminer, nous abordons trois perspectives de recherche :- la réorganisation des tournées suite à l’absence d’un soignant,- la prise en compte de temps de transport stochastique,- la localisation de structures de maintien à domicile et l’impact sur la construction des tournées. / We are interested in a routing problem within the context of home health care. The cares are provided by one or two caregivers with the required type at the patient’s home during the patients’ availability. A type is doctor or nurse for instance. Each patient is characterized by a dependency level and may give a preference for a caregiver. The goal is to construct the tour for each caregiver visiting all patients, minimizing the length of the tours, balancing the workload of the caregivers and maximizing the satisfaction of the patients. We present a state of the art of the home health care problem. Then we propose two mathematical models of our problem based on the multiple Traveling Salesman Problem with Time Windows (m-TSPTW) with specific constraints like the activities’s synchronization or ressources’ type. The performance criteria are specific of our problem : workload balancing and patients’ satisfaction. We then propose approached methods based on combination between Metaheuristics and simulation model. This méthods have been tested on dataset from the literature and dataset adapted to our problem. We conclude with three research perspectives :- the reorganization of the tours when a caregiver is not available,- the integration of stochastic transport time,- the location of home support structure and its impact on the routes’ construction.

En réponse aux contraintes économiques, au problème du vieillissement de la population et aussi à la volonté des patients de se faire soigner dans le milieu familial, l’Hospitalisation À Domicile (HAD) prend de plus en plus d’ampleur. Dans ce travail de recherche, nous nous intéressons aux établissements d’hospitalisation à domicile, parmi les différentes problématiques qui existent dans ce domaine, nous étudions le problème de routage et de planification des personnels.Nous développons tout d’abord un modèle de programmation linéaire en nombres entiers qui permet de formuler clairement les contraintes du problème.Nous présentons par la suite, une matheuristique permettant de résoudre le problème défini sur une journée de planification. Nous développons également une variante de notre matheuristique sur un horizon de 14 jours. Cette dernière prend en considération plusieurs contraintes en plus de celles considérées pour la planification sur une journée. Enfin, nous introduisons un problème de réoptimisation de routage et de la planification des personnels pour l’hospitalisation à domicile et présentons quelques approches de résolutions. Ces différentes méthodes combinent des heuristiques, la programmation dynamique et la programmation mathématique. / Home health care (HHC), i.e., visiting and nursing patients athome, is a growing sector in the medical care system. There fore, the optimal scheduling of the health care staffs arises. The objective of this problem consists in constructing routes and rosters for the staffs while optimizing costs. We propose an integer linear programming formulation (ILP) that clearly formulate the constraints of the problem. We present a matheuristic to solve the daily routing and rostering problem. We also develop a variant of our matheuristic defined for a period of 14 days. It takes into account several constraints in addition to those considered in the daily planning. Finally, we introduce the problem of reoptimizing the routing and rostering staffs and we give some ideas to solve this problem. These methods combine heuristic algorithms, dynamic programming and mathematical programming.

Ce mémoire vise à définir et quantifier les émissions de gaz à effet de serre (GES) émises par le réseau de transport logistique de notre partenaire industriel. En parallèle, nous détaillons plusieurs scénarios d'optimisation possibles afin de réduire son empreinte carbone. Cela se fait par optimisation mathématique, par laquelle les déplacements entre l'entreprise et ses différents partenaires, de l'approvisionnement à la livraison au client final, pour différents types de produits et différents transporteurs avec différents types de véhicules sont considérés. Plus précisément, notre objectif est de décrire et de représenter la différence entre la situation actuelle et la solution obtenue en optimisant le réseau en termes de distance parcourue, de GES émis, de consolidation des livraisons ainsi que de production et de stocks nécessaires. Suite à l'analyse quantitative et qualitative des résultats, nous sommes en mesure de fournir de nombreuses suggestions d'amélioration à l'entreprise en ce qui concerne la gestion de son transport interne et externe. Un certain nombre d'indicateurs de performance clés sont également évalués, les plus importants étant l'inventaire et le nombre de voyages effectués. Ceux-ci sont considérablement réduits dans notre scénario optimisé. Pour garantir des résultats commerciaux optimaux, nous proposons un modèle de résolution en deux étapes comprenant une modélisation mathématique du problème suivie d'une amélioration manuelle de la solution. De plus, les méthodes de calcul utilisées pour mesurer les émissions de GES sont basées sur la distance parcourue ainsi que sur la capacité utilisée de chaque véhicule, attribuant ainsi l’utilisation du véhicule à l’entreprise (tandis que la capacité restante est utilisée par d’autres compagnies lorsque le transporteur consolide ses opérations). Cela nous permet d'estimer les émissions générées même lorsque la construction des routes de différents transporteurs n'est pas exactement connue. La coordination, la consolidation et la synchronisation des différents voyages liés aux activités de l’entreprise nous ont permis de réduire les émissions de GES jusqu’à 23%, soit 3,438.64 tonnes de CO2e économisées sur une base annuelle, soit 2,733,354 km. De plus, nos observations des résultats ont mis en évidence une multitude de recommandations concernant l’utilisation des transporteurs, la réduction des stocks et le contrôle des flux de transport au sein de l’entreprise. / This thesis aims to define and quantify the greenhouse gas (GHG) emission emitted by our industrial partner’s logistics transportation network. Next to that, we detail several possible optimization scenarios in order to reduce its carbon footprint. This is done via mathematical optimization, in which the trips between the company and its various partners, from supply to delivery to the end customer, for different types of products and different carriers with different types of vehicles are considered. More specifically, our purpose is to describe and represent the difference between the current situation and the solution obtained by optimizing the network in terms of distance traveled, GHG emitted, consolidation of deliveries as well as production and stock needed. Following the quantitative and qualitative analysis of the results, we are able to provide numerous suggestions for improvements to the company with regard to the management of its internal and external transport. A number of key performance indicators are also evaluated, most importantly inventory and the number of trips. These are drastically reduced in our optimized scenario. To ensure optimal business results, we propose a two-step resolution model that includes mathematical modeling of the problem followed by manual improvement of the solution. In addition, the calculation methods used to measure GHGs emitted are based on the distance traveled as well as the capacity used of each vehicle, thus assigning vehicle usage to the company (while the remaining vehicle space is to be used by other companies when the carrier consolidates its operation). This allows us to estimate the emissions generated even when the construction of routes of different carriers is not exactly known. The coordination, consolidation and synchronization of the various trips related to the company’s activities allowed us to reduce the GHGs emitted by up to 23%, which translates into 3,438.64 tons of CO2e saved on a yearly basis, or 2,733,354 km. In addition, our observations of the results highlighted a multitude of recommendations regarding the use of carriers, the reduction of inventory and the control of transport flows within the company.