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.

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.

Titre de l'écran-titre (visionné le 2 octobre 2023) / Dans l'environnement commercial mondial concurrentiel d'aujourd'hui, les chaînes d'approvisionnement sont devenues plus complexes et plus sensibles en raison de leur dépendance vis-à-vis des demandes des clients en constante évolution. La création de valeur pour les clients ne réfère pas toujours à la qualité ou à la quantité du produit, elle réfère également à la disponibilité du produit à temps à l'endroit demandé. Tirer parti d'une chaîne d'approvisionnement pour fournir une valeur élevée aux clients ne peut être possible sans un transport organisé de manière efficace. Les professionnels considèrent qu'un service de livraison amélioré est crucial pour répondre à la demande des clients et augmenter la disponibilité des produits. En effet, un tel service est considéré comme un facteur clé dans la création de valeur pour les clients dans le monde des affaires. Le transport est l'un des éléments clés de la chaîne d'approvisionnement, car il joue un rôle essentiel dans le maintien d'une chaîne d'approvisionnement robuste et résiliente. De plus, un réseau de transport efficace aide les entreprises à réduire leurs coûts d'exploitation, à augmenter les niveaux de service et à obtenir un avantage sur la concurrence. Cela augmente l'intérêt de la recherche axée sur la gestion des opérations de transport et de la distribution. Tout au long de cette recherche, nous nous intéressons aux problèmes de cueillettes et de livraisons (ou Pickup and Delivery problems (PDPs)) qui sont une généralisation du problème classique de tournées de véhicules (Vehicle Routing Problem). En général, les PDPs impliquent la conception d'itinéraires à coût minimum pour un ensemble de véhicules afin de satisfaire toutes les requêtes de cueillettes et de livraisons. Les relations d'appariement et de précédence entre les lieux de cueillette et de livraison doivent être respectées. Plusieurs variantes de PDPs sont créées en ajoutant différents types de contraintes telles que les fenêtres de temps, la capacité des véhicules, etc. Cette classe de problèmes d'optimisation trouve des applications dans plusieurs contextes réels, tels que le transport de passagers porte-à-porte, les services de courrier urbain, le transport maritime et le transport de marchandises. Les PDPs ont été largement abordés dans la littérature. Cependant, les réseaux de distribution modernes avec des opérations de plus en plus complexes et des caractéristiques spéciales rendent les méthodes conventionnelles limitées et/ou inefficaces. Par conséquent, il est essentiel de développer de nouvelles méthodes et des solutions innovantes pour relever les nouveaux défis de l'industrie des transports. Dans ce projet de recherche, nous aborderons des PDPs réels issus de différents contextes tels que la livraison du dernier kilomètre et les services de santé. Tout d'abord, nous étudions un nouveau PDP dans le contexte de la livraison du dernier kilomètre connu sous le nom multi-pickup and delivery problem with time windows (MPDPTW), c'est un problème de cueillettes multiples et de livraison avec fenêtres de temps. Ce problème trouve de nombreuses applications concrètes, comme dans le domaine de l'économie du partage avec les services UBER EAT, où un client est autorisé à commander de la nourriture de différents restaurants; l'entreprise doit ensuite effectuer des cueillettes à différents endroits, avant de livrer tous les repas au client. Nous avons conçu de nouveaux algorithmes exacts pour le MPDPTW, fournissant les premières bornes inférieures et obtenant des solutions optimales pour les grandes instances. Dans ce travail, deux nouvelles formulations pour le problème sont introduites, une formulation à deux indices et la formulation des représentants asymétriques (asymmetric representatives formulation). Une transformation du MPDPTW en PDPTW est également proposée et testée. Les formulations mathématiques sont ensuite comparées pour trouver le meilleur algorithme pour le problème. Le deuxième problème abordé dans ce projet de recherche est une application liée au PDP dans le contexte de la logistique des soins de santé. Les activités de transport dans les hôpitaux sont de plus en plus complexes en raison de la grande variété de fournitures et d'équipements utilisés, tels que les articles jetables qui sont utilisés plus fréquemment. Cela se traduit par une augmentation du volume de transport dans les hôpitaux. Ces facteurs justifient le besoin de plus d'efficacité et de productivité des systèmes de transport dans les hôpitaux afin de répondre au niveau de service attendu par les patients sans augmenter les coûts. Un moyen efficace pour atteindre ces objectifs est l'automatisation des processus logistiques à l'aide de véhicules autoguidés (automated guided vehicles). Nous étudions le fleet sizing and routing problem with synchronization of automated guided vehicles with dynamic demands (FSRPS-AGV), c'est un problème de dimensionnement de flotte de véhicules autoguidés dans un environnement dynamique avec des contraintes de synchronization. Ce problème est dans le cadre d'une application réelle avec un partenaire de l'industrie de la santé à la ville de Québec. Nous décrivons le problème, nous introduisons une formulation mathématique et proposons une matheuristique pour le résoudre. Les tests sont menés sur des instances petites et grandes générées à partir de données réelles fournies par notre partenaire industriel. La troisième problématique étudiée dans ce projet est une application dans le contexte de la livraison de béton prêt à l'emploi (BPE). De nombreux problèmes opérationnels difficiles sont rencontrés par les fournisseurs du BPE, tels que la planification des opérations de production dans les usines de production, la planification des horaires quotidiens et hebdomadaires des chauffeurs, la planification des opérations de chargement, et la livraison du béton sur les chantiers de construction. Dans un environnement commercial caractérisé par une concurrence féroce, des solutions innovantes sont nécessaires pour résoudre ces problèmes afin d'atteindre l'exellence opérationnelle et de garantir un avantage concurrentiel. Bien que l'optimisation des opérations de livraison de béton soit essentielle pour les entreprises de béton, la satisfaction des chauffeurs et des clients ne doit pas être négligée. Nous étudions le personnel scheduling problem for ready-mixed concrete delivery (PSP-RMC) dans le contexte d'une application réelle avec une entreprise de béton au Québec, Canada. L'objectif est d'aider les fournisseurs de BPE à planifier des horaires de chauffeurs rentables et consistents (heures de début de travail similaires au cours de la semaine) sur un large horizon de planification sous des contraintes opérationnelles et réglementaires strictes. Des problèmes de PDPs sont résolus à l'intérieur même du PSP-RMC pour obtenir des routes pour les chauffeurs. Nous décrivons le problème et proposons un algorithme métaheuristique en deux étapes pour le résoudre. Les tests sont menées sur des instances artificielles et sur des instances générées à partir de données réelles fournies par notre partenaire industriel. Cette thèse est structurée comme suit. Une revue de la littérature sur les problèmes de cueillettes et de livraisons est présentée après un chapitre d'introduction. Le chapitre 2 est consacré au multi-pickup and delivery problem with time windows, et le chapitre 3 présente le fleet sizing and routing problem with synchronization of automated guided vehicles with dynamic demands. Le chapitre 4 présente le personnel scheduling problem for ready-mixed concrete delivery. La conclusion suit et résume les principales contributions de cette thèse dans le dernier chapitre. / In today's challenging and competitive global business environment, supply chains have become more complex and sensitive due to their dependence on constantly changing customer demands. Creating value for customers does not always refer to the quality or quantity of the product, it also refers to the availability of the product on time at the requested location. Leveraging a supply chain to provide high value to customers cannot be possible without effectively organized transportation. A better delivery service increases the availability of products to fulfill the demand of customers. Therefore, business practitioners consider it a very important factor in creating value for customers. Transportation is one of the key components in the entire supply chain, it has a critical role in maintaining a robust and resilient supply chain. Moreover, an efficient transportation network helps businesses to reduce operating costs, increase service levels, and gain a clear advantage over the competition. This increases research interest focused on transportation operations management. Throughout this research, we are interested in pickup and delivery problems (PDPs) which are a generalization of the classical vehicle routing problem (VRP). In general, the PDPs involve designing minimum-cost routes for a set of vehicles to satisfy all the pickup-delivery requests. Pairing and precedence relations of pickup and delivery locations must be respected. Variants of PDPs are found by adding side constraints such as time windows, vehicle capacity, etc. This class of optimization problems has applications in several real-life contexts, such as door-to-door passenger transportation, urban courier services, maritime shipping and freight transportation. PDPs have been widely addressed in the literature. However, modern delivery networks with more and more complex operations and special characteristics make conventional methods limited and/or inefficient. Hence, developing new innovative solution methods to tackle the new challenges of the transportation industry is crucial. In this research project, we tackle real-life PDPs arising from different contexts, such as last mile delivery and healthcare services. First, we study a new rich PDP in the context of last mile delivery known as the multi-pickup and delivery problem with time windows (MPDPTW). This problem finds many real-life applications, some of them are in the context of shared economy such as UBER EAT services, where a client is allowed to order food from different restaurants; the company must then perform all pickups at different places, before delivering all meals to the client location. We designed a new branch-and-cut algorithm for the MPDPTW providing the first dual bounds for the problem and obtaining tight solutions for large instances. In this work, two new formulations for the problem are introduced, a two-index formulation and the asymmetric representatives formulation (ARF). A transformation of the MPDPTW into a PDPTW is also proposed and tested. The mathematical formulations are then compared to define the best one for the problem. The second problem tackled in this research project is a PDP-related application in the context of healthcare logistics. Transportation activities in hospitals are now becoming more complex due to the wide variety of supplies and equipment used such as disposable items which are being used more frequently. This results in the expansion of the volume of transportation in hospitals. These factors justify the need for more efficiency and productivity of transportation systems in hospitals in order to meet the service level expected by patients without increasing costs. One of the most powerful ways of achieving these goals is the automation of logistics processes by using automated guided vehicles. We study the fleet sizing and routing problem with synchronization of automated guided vehicles with dynamic demands in the context of a real-life application with an industrial partner from the healthcare industry in Quebec City, Canada. We describe the problem, introduce a mathematical formulation for it, and propose a powerful matheuristic to solve it. Computational experiments are conducted on large and small instances generated based on real-data provided by our industrial partner. The third problem studied in this project is another application, this time in the context of ready-mixed concrete (RMC) delivery. Many challenging operational problems are faced by RMC suppliers such as scheduling production operations at production plants, creating daily and weekly drivers' schedules, loading operations scheduling, and delivering concrete to construction sites. In a business environment characterized by a fierce competition, innovative solutions are needed to tackle these problems in order to achieve operational efficiency and guarantee a competitive advantage. Although optimizing concrete delivery operations is essential for concrete companies, drivers' and customers' satisfaction should not be neglected. We study the personnel scheduling problem for RMC delivery in the context of a real-life application with a concrete company in Quebec, Canada. The goal is to help RMC suppliers build cost-effective and consistent (similar starting times over the week) drivers' schedules over a large planning horizon, under tight operational and regulatory constraints. The PSP-RMC embeds a PDP which is solved to create routes for drivers. We describe the problem and propose a two-stage metaheuristic algorithm to solve it. Computational experiments are conducted on artificial instances, and on instances generated based on real-data provided by our industrial partner. This thesis is structured as follows. A literature review on the pickup and delivery problems is presented after an introductory chapter. Chapter 2 is devoted to the multi-pickup and delivery problem with time windows, and Chapter 3 presents the fleet sizing and routing problem with synchronization of automated guided vehicles with dynamic demands. Chapter 4 presents the personnel scheduling problem for ready-mixed concrete delivery. The conclusion follows and summarizes the main contributions of this thesis in the last Chapter.

Le problème du commis voyageur, aussi connu sous le nom de problème du voyageur de commerce ou traveling salesman problem (TSP) en anglais, est un problème classique de l'optimisation combinatoire et de la recherche opérationnelle. Il consiste, étant donné un certain nombre de villes et la distance entre chacune d'entre elles, à trouver un chemin de longueur minimale visitant chaque ville une seule fois et retournant à son point de départ. Le problème apparaît naturellement dans une multitude de problématiques de transport et industrielles, en plus de trouver des applications dans un important nombre de domaines en apparence non liés, allant de la logistique au séquençage de l'ADN. Toutefois, sa complexité informatique le rend difficile à résoudre. Le solveur Concorde permet actuellement de résoudre de manière exacte des instances du TSP comportant des milliers de villes en seulement quelques secondes. Cependant, une limitation importante est qu'il ne permet pas de considérer des contraintes additionnelles telles que des fenêtres de temps pour chaque visite. La programmation par contraintes est une approche permettant facilement d'ajouter ces contraintes au problème. Dans ce mémoire, nous revisitons l'approche CP-based Lagrangian relaxation (CP-LR) utilisée notamment pour les algorithmes de filtrage de l'état de l'art de la contrainte WeightedCircuit encodant le TSP en programmation par contraintes. Nous proposons deux nouveaux algorithmes basés sur notre approche CP-LR améliorée. Ceux-ci permettent d'obtenir un gain significatif sur le temps de résolution du TSP comparativement à l'implémentation de l'état de l'art. / The traveling salesman problem (TSP) is a classic problem in combinatorial optimization and operations research. It consists, given a number of cities and the distance between each of them, to find a path of minimal distance visiting each city exactly once and returning to its starting point. The problem naturally appears in various transportation and industrial problems, in addition to having applications in several domains apparently unrelated, going from logistics to DNA sequencing. Its computational complexity makes it nonetheless difficult to solve. The Concorde solver currently allows to exactly solve TSP instances having thousands of cities in only a few seconds. However, an important limitation is that it cannot consider additional constraints such as time windows for each visit. Constraint programming is an approach that easily allows these constraints to be added to the problem. In this Master's thesis, we revisit the CP-based Lagrangian relaxation (CP-LR) approach used in particular for the state-of-the-art filtering algorithms of the WeightedCircuit constraint that encodes the TSP in constraint programming. We propose two new algorithms based on our improved CP-LR approach. These allow to obtain a significant gain on the TSP solving time when compared to the state-of-the-art implementation.

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

De nos jours, le transport de marchandises est devenu un défi majeur puisque les entreprises doivent savoir gérer les flux en minimisant les coûts. Dans ce contexte, ce mémoire traite un problème logistique ayant pour but de satisfaire des ordres de transport qui sont des remorques à déplacer d’un terminal à un autre dans un réseau de terminaux de transport en maximisant le profit. Notons que la littérature scientifique n’offre presque pas de publications qui traitent ce problème de planification des opérations dans un réseau de terminaux de transport ou dans un réseau collaboratif d’entreprises de transport. Nous disposons d’un nombre de terminaux, de chauffeurs situés à différents terminaux et d’un nombre d’ordres à satisfaire. Nous devons choisir les ordres à compléter et les chauffeurs à affecter en respectant certaines contraintes de temps (temps dûs, temps de travail des chauffeurs, heures supplémentaires, temps nécessaire pour satisfaire les ordres et retourner au terminal de résidence...) et en considérant les coûts (salaires des chauffeurs, coût des heures supplémentaires, coût du carburant, pénalités de retard …) afin de maximiser le profit. Dans ce travail nous allons étudier et analyser ce problème. Deux méthodes pour le résoudre seront développées. La première méthode de résolution est une heuristique de décomposition composée d’une heuristique constructive suivie par la résolution d’un modèle mathématique. La deuxième méthode est constituée d’une heuristique constructive suivie de trois phases d’amélioration. Plusieurs instances numériques seront créées afin de valider les méthodes proposées et pour analyser la qualité des solutions que ces méthodes peuvent produire. / Nowadays, the transportation of goods has become a major challenge since companies must know how to manage flows while minimizing costs. In this context, this thesis deals with a logistical problem aimed at satisfying transport orders which are trailers to be moved from one terminal to another in a network of transportation terminals by maximizing profit. Note that the scientific literature offers almost no publications that deal with this problem of planning operations in a network of terminals or in a collaborative network of transportation companies. We have several terminals, several drivers located at different terminals and several orders to fulfill. We must choose the orders to be selected and the drivers to be assigned while respecting certain time constraints (duetime, working time of the drivers, overtime, time necessary to fulfill the orders and return to drivers’ residence terminal...) and considering costs (driver salaries, overtime cost, fuel cost, late penalties…) in order to maximize profit.In this work we will study and analyze this problem. Two methods to solve it will be developed. The first resolution method is a decomposition heuristic composed of a constructive heuristic followed by solving a mathematical model. The second method consists of a constructive heuristic followed by three improvement methods. Several numerical instances will be created in order to validate the proposed methods and to analyze the quality of the solutions that these methods can produce.

De nos jours, le transport de marchandises est devenu un défi majeur puisque les entreprises doivent savoir gérer les flux en minimisant les coûts. Dans ce contexte, ce mémoire traite un problème logistique ayant pour but de satisfaire des ordres de transport qui sont des remorques à déplacer d'un terminal à un autre dans un réseau de terminaux de transport en maximisant le profit. Notons que la littérature scientifique n'offre presque pas de publications qui traitent ce problème de planification des opérations dans un réseau de terminaux de transport ou dans un réseau collaboratif d'entreprises de transport. Nous disposons d'un nombre de terminaux, de chauffeurs situés à différents terminaux et d'un nombre d'ordres à satisfaire. Nous devons choisir les ordres à compléter et les chauffeurs à affecter en respectant certaines contraintes de temps (temps dûs, temps de travail des chauffeurs, heures supplémentaires, temps nécessaire pour satisfaire les ordres et retourner au terminal de résidence...) et en considérant les coûts (salaires des chauffeurs, coût des heures supplémentaires, coût du carburant, pénalités de retard ...) afin de maximiser le profit. Dans ce travail nous allons étudier et analyser ce problème. Deux méthodes pour le résoudre seront développées. La première méthode de résolution est une heuristique de décomposition composée d'une heuristique constructive suivie par la résolution d'un modèle mathématique. La deuxième méthode est constituée d'une heuristique constructive suivie de trois phases d'amélioration. Plusieurs instances numériques seront créées afin de valider les méthodes proposées et pour analyser la qualité des solutions que ces méthodes peuvent produire. / Nowadays, the transportation of goods has become a major challenge since companies must know how to manage flows while minimizing costs. In this context, this thesis deals with a logistical problem aimed at satisfying transport orders which are trailers to be moved from one terminal to another in a network of transportation terminals by maximizing profit. Note that the scientific literature offers almost no publications that deal with this problem of planning operations in a network of terminals or in a collaborative network of transportation companies. We have several terminals, several drivers located at different terminals and several orders to fulfill. We must choose the orders to be selected and the drivers to be assigned while respecting certain time constraints (due time, working time of the drivers, overtime, time necessary to fulfill the orders and return to drivers' residence terminal...) and considering costs (driver salaries, overtime cost, fuel cost, late penalties...) in order to maximize profit. In this work we will study and analyze this problem. Two methods to solve it will be developed. The first resolution method is a decomposition heuristic composed of a constructive heuristic followed by solving a mathematical model. The second method consists of a constructive heuristic followed by three improvement methods. Several numerical instances will be created in order to validate the proposed methods and to analyze the quality of the solutions that these methods can produce.

De nos jours, le transport joue un rôle clé dans la vie des pays modernes, en particulier pour les flux de marchandises. La logistique des flux entre régions, pays et continents a bénéficié d’innovations technologiques et organisationnelles assurant efficacité et efficience. Il n’en a pas été de même à l’échelle urbaine, plus particulièrement dans les centres-villes : la gestion des flux dans un environnement caractérisé par une forte densité démographique n’a pas encore véritablement trouvé son modèle d’organisation. Aujourd’hui, la logistique urbaine ou encore la gestion "du dernier kilomètre" constitue donc un enjeu de premier plan, tant socio politique et environnemental qu’économique. La logistique urbaine est caractérisée par la présence de plusieurs acteurs (chargeurs ou propriétaires de marchandises, clients, transporteurs, autorités publiques, …) ayant chacun des priorités différentes (réduction de la pollution, amélioration de la qualité de service, minimisation de la distance totale parcourue, …). Pour relever ces défis, un des leviers possibles consiste à optimiser les tournées de distribution et/ou collecte de marchandises, dans le contexte et sous les contraintes de la ville.Le but de ce travail de thèse réside alors dans la planification de la distribution des marchandises dans un réseau logistique, abordée sous un angle de collaboration entre les chargeurs. Cette collaboration consiste à regrouper les demandes de divers chargeurs pour optimiser le taux de chargement des camions et obtenir de meilleurs prix de transport. Ici, la gestion du « dernier kilomètre » s’apparente à ce que l’on identifie dans la littérature comme le Pickup and Delivery Problem (PDP). Dans le cadre de cette thèse, nous nous intéressons à des variantes de ce problème plus adaptées au contexte urbain. Après avoir réalisé un état de l’art sur les problèmes d’optimisation combinatoire autour du transport et les méthodes utilisées pour leur résolution, nous étudions deux nouvelles variantes du problème de collecte et de livraison : le Selective PDP with Time Windows and Paired Demands et le Multi-periods PDP with Time Windows and Paired Demands. La première permet aux transporteurs de livrer le maximum de clients dans une journée par exemple ; avec la seconde, et en cas d’impossibilité de livraison dans cette période, on détermine la meilleure date de livraison en minimisant la distance parcourue. Chacune d’elles fait l’objet d’une description formelle, d’une modélisation mathématique sous forme de programme linéaire, puis d’une résolution par des méthodes exacte, heuristiques et métaheuristiques, dans des cas mono-objectif et multi-objectifs. La performance de chaque approche a été évaluée par un nombre substantiel de tests sur des instances de différentes tailles issues de la littérature et/ou que nous avons générées. Les avantages et les inconvénients de chaque approche sont analysés, notamment dans le cadre de la collaboration entre chargeurs. / Nowadays, transportation plays a key role in our modern countries’life, in particular for the goods flows. The logistics of flows between regions, countries and continents have benefited from technological and organizational innovations ensuring efficiency and effectiveness. It has not been the same at the urban scale, especially in city centers: the management of flows in a high population density environment has not yet found its organizational model. Today, urban logistics or "last mile" management is therefore a major issue, both socio-political and environmental as well as economic. Urban logistics is characterized by several actors (shippers or owners of goods, customers, carriers, public authorities, ...) each with different priorities (reduction of pollution, improvement of service quality, minimization of total distance traveled, ...). To overcome these challenges, one possible lever is to optimize the distribution and/or collection of goods in the context and under the constraints of the city.The goal of this PhD work is then to plan the distribution of goods in a logistics network, approached from a collaboration angle between shippers. This collaboration consists in grouping the demands of several shippers to optimize the loading rate of the trucks and to obtain better transport prices. Here, managing the "last mile" is similar to what is known in the literature as the Pickup and Delivery Problem (PDP). In this thesis, we are interested in variants of this problem more adapted to the urban context. After having realized a state of the art on the combinatorial optimization problems around the transport and the methods used for their resolution, we study two new variants of the problem of collection and delivery: the Selective PDP with Windows and Paired Demands and the Multi-period PDP with Windows and Paired Demands. The first allows carriers to deliver the maximum number of customers in a day for example; with the second, and in case of impossibility of delivery in this period, we determine the best delivery date by minimizing the distance traveled. Each of them is the subject of a formal description, of a mathematical modeling in the form of a linear program, then of a resolution by exact methods, heuristics and metaheuristics, in single-objective and multi-objective cases. The performance of each approach was evaluated by a substantial number of tests on instances of different sizes from the literature and / or that we generated. The advantages and drawbacks of each approach are analyzed, in particular in the context of collaboration between shippers.

Nous présentons dans cette thèse, un outil d'aide à la décision pour la régulation du trafic ferroviaire dans une usine sidérurgique. La particularité de ce système est qu'il repose sur une utilisation en temps réel, et qu'il est soumis à des contraintes spécifiques liées au processus de fabrication de l'acier. Nous décrivons ses spécificités et son rapprochement avec le problème de tournées de véhicules avec fenêtres de temps. La méthode de résolution que nous avons mise en oeuvre repose sur la coopération d'une heuristique de construction parallèle des tournées avec une heuristique d'amélioration des tournées. Les applications aux cas réels que nous avons menées montrent une amélioration de la satisfaction client en terme de nombre de retards et de durée totale des retards. La mise en oeuvre dans un site industriel est également présentée dans ce mémoire.

Le soin à domicile est un secteur en plein essor ces dernières années. Cela est dû au vieillissement de la population, à la volonté de réduire les coûts hospitaliers et d’assurer le bien-être du patient en le gardant dans son cadre familial tout en maintenant la qualité des soins. L’organisation de ces soins nécessite une prise de décisions aux niveaux stratégique, tactique et opérationnel. Cette thèse s’articule autour de l’étude de problèmes apparaissant uniquement au niveau opérationnel. Ces problèmes traitent de la planification des tournées du personnel de soins à domicile. La première étape de cette étude a consisté à faire une revue de la littérature. De nombreux modèles mathématiques ont été formulés dans la littérature. Cependant, ces modèles étaient dédiés à une structure de soins à domicile spécifique et pouvaient être difficilement transposés. Nous proposons ici une approche générique tant du point de vue de la modélisation que des méthodes de résolutions. À cet effet, nous avons identifié les caractéristiques fréquemment rencontrées dans la littérature à travers cette revue de la littérature. Un modèle générique a été proposé prenant en compte la plupart des caractéristiques. Ce modèle générique constitue un socle pour la construction de méthodes de résolution. Deux méthodes de résolution ont été conçues. La première méthode est une méthode par décomposition et la deuxième méthode est un algorithme hybride génétique avec gestion de la population. Ces deux méthodes utilisent des représentations d’une solution issues de la littérature et adaptées aux caractéristiques du problème. Des expérimentations numériques ont été réalisées dans le but d’évaluer les méthodes proposées et de se comparer à la littérature. / The home care is a growing sector. Many questions research problems exist. We can identify at strategic level the districting problem ; at tactical level, the resource dimensioning problem ; and operational level, the operation assignment and the home care routing and scheduling problem. This thesis focuses on the last one. For this purpose, we propose a state of the art, a generic model and two solutions methods hybrid genetic algorithm and a decomposition.