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.

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.

De nos jours, l’optimisation des opérations de distribution au sein d’une chaîne logistique passe par la prise de décisions impliquant plusieurs activités simultanément. Cette thèse se concentre sur la résolution de problèmes complexes de distribution. Nous étudions premièrement le cas où un transporteur externe est disponible pour pallier au manque de capacité de la flotte interne. Par la suite nous abordons l’optimisation des tournées en tenant compte du calendrier de production de l’usine et des calendriers de demandes des clients. Ces problématiques se positionnent dans le cadre d’un réseau manufacturier composé d’une usine adjacente à un centre de distribution et d’un ensemble de clients. Les clients, tout dépendamment des contextes, peuvent être des utilisateurs finaux ou des détaillants. Cette problématique comporte de nombreuses particularités dont, entre autres, la détermination des quantités à livrer, le choix des véhicules à utiliser, la création des tournées, la gestion des stocks du centre de distribution qui est alimenté en fonction du calendrier de production de l’usine et la détermination des dates de livraison en respectant les calendriers de demandes. En regard avec les nombreuses décisions à prendre, la problématique a été divisée en trois grands axes de recherche, chacun se concentrant sur une partie du problème pour ainsi développer des méthodes pouvant être réutilisées par la suite. Ces axes de recherches sont 1) le transport multi-périodes dans un réseau production/distribution, 2) le problème de tournées de véhicules avec flotte limitée hétérogène et transporteur externe et 3) le problème de tournées de véhicules avec livraisons fractionnées et calendriers de production et de demandes. Le premier axe de recherche se concentre sur la planification des transports lorsque le calendrier de production détermine la disponibilité des divers produits et où les calendriers de demandes des clients imposent les dates de livraison au plus tard. La planification est complexifiée par la présence d’une flotte privée de véhicules hétérogènes et par l’éloignement de certains clients ce qui implique des déplacements multi-périodes. Des heuristiques de transport en aller-retour ainsi que des heuristiques impliquant des tournées avec plusieurs clients ont été développées. Le deuxième axe de recherche étudie un problème de tournées de véhicules mono-période et mono-produit où la capacité totale de la flotte privée limitée est insuffisante pour répondre à la demande des clients. Dans un tel contexte, le recours à un transporteur externe est nécessaire afin de combler les besoins manquants de transport. Pour desservir chacun des clients, une décision doit premièrement être prise quant au choix du type de transport utilisé : flotte privée ou transporteur externe. Deuxièmement, pour les clients desservis par la flotte privée limitée, le type de véhicule à utiliser doit être déterminé conjointement avec la planification des tournées. Pour solutionner ce problème, une heuristique rapide et une métaheuristique ont été développées. Le dernier axe de recherche se concentre sur un problème de tournées de véhicules avec calendriers de production et de demandes. Dans un tel contexte, la disponibilité des divers produits dépend du calendrier de production. De leur côté, les clients, par le biais de leurs calendriers de demandes, fixent les quantités et les dates de livraison au plus tard des produits qu’ils désirent. Les tournées doivent être planifiées en fonction d’une flotte privée homogène et limitée de véhicules et de la présence d’un transporteur externe. Le problème consiste à déterminer pour chaque produit les dates de livraison et les quantités à livrer, en plus de choisir le type de véhicules et de confectionner les tournées de la flotte privée. Une métaheuristique sophistiquée, utilisant une méthode de recherche avec tabous, a été conçue. Ces axes de recherche font l’objet de quatre articles scientifiques qui composent cette thèse par insertion d’articles. Trois de ces articles sont déjà acceptés pour publication et le quatrième est actuellement en arbitrage. / Nowadays, optimizing transportation activities implies making decisions about many activities at the same time. This doctoral dissertation focuses on complex distribution problems, specifically tour optimization taking the factory's production calendar and the customers' demand calendars into account. The manufacturing network studied is composed of a factory, a distribution center (DC) and a set of customers. Depending on the context, the customers may be final users or retailers. The deliveries are made with a private limited fleet of homogenous vehicles owned by the network, supplemented, when it is necessary, by common carriers. To solve this problem many decisions must be made, such as determining the quantities to deliver; choosing the type of vehicles to use and their routing; deciding how to manage the DC inventory, which is supplied according to the production calendar; and establishing the delivery dates with respect to the demand calendars. Given the number of decisions that need to be made, this complex problem was divided into three main research themes, each one devoted to a part of the problem. These main themes are 1) multi-period routing in a production/distribution network, 2) vehicle routing with a private heterogeneous limited fleet and a common carrier, and 3) vehicle routing with split deliveries and production and demand calendars. The idea was to develop methods that could be reused in future projects. The first main theme concentrates on route planning and scheduling given a production calendar that governs inventory availability and demand calendars that impose delivery of the requested quantities of each product at the latest dates possible. These planning and scheduling decisions are made more complex by the availability of only a limited private fleet of heterogeneous vehicles for deliveries and by the distance of some customers which necessitates the use of multi-period routes. Heuristics for round trip transportation and routing with few customers were developed. The second theme focuses on a mono-period, mono-product vehicle routing problem in which the total capacity of the private limited fleet is insufficient to allow deliveries to all the customers. In this context, a common carrier is needed to supplement the transportation capacity. For each customer, a decision first has to be made as to whether the delivery will be made by the private vehicles or the common carrier. Then, for the deliveries by the private fleet, the type of vehicle and the routing must be determined. To solve this problem, a fast heuristic and a more complicated metaheuristic were developed. The third theme examines a split vehicle routing problem with production and demand calendars. In this context, inventory availability depends on the production calendar, and the customers impose the product quantities and the latest possible delivery dates via their demand calendars. For deliveries, both a limited private fleet of homogeneous vehicles and a common carrier are available. To solve this problem, first the delivery dates and the product quantities must be determined, and then the type of vehicle and the routes must be determined. To this end, a complex metaheuristic, using a tabu search algorithm, was conceived. The research for this dissertation led to four scientific papers. Three of these papers have been published, and the fourth is currently submitted for publication.

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

L’agriculture de précision est un mode de culture qui consiste à prendre en compte la variabilité intra-parcellaire afin d'appliquer le bon traitement au bon endroit. Depuis les années 80, l’agriculture de précision s’est développée grâce à l’arrivée d’outils de géolocalisation (GPS), de matériels permettant une gestion modulée des cultures et surtout d'une multitude de données issues de prélèvements sur le terrain, d'images et de capteurs. Dans ce contexte, l’agriculture de précision a fait émerger de nouveaux problèmes à la fois combinatoires et complexes afin de répondre à des enjeux de performance économique, technique et environnementale.Cette thèse porte sur l'utilisation de la programmation par contraintes pour résoudre des problèmes de tournées dans le contexte de l’agriculture de précision et, plus précisément, en viticulture de précision.Un problème de tournées de véhicule consiste à déterminer une flotte de véhicules afin de visiter une liste de clients ou de réaliser des tournées d’interventions. Le but est de minimiser le coût total des tournées tout en respectant différentes contraintes. Ce problème est une extension classique du problème du voyageur de commerce et fait partie des problèmes NP-difficiles.La programmation par contraintes est un outil très puissant capable de résoudre des problèmes combinatoires comme les problèmes de tournées. Elle fournit des algorithmes de filtrage dédiés à des contraintes de circuits qui permettent de résoudre de façon efficace des problèmes associant ces contraintes de circuit à d'autres contraintes plus spécifiques.La première contribution de cette thèse est la formalisation du problème de la vendange sélective et sa modélisation sous la forme d’un problème d’optimisation sous contraintes. Le problème de la vendange sélective consiste à trouver la trajectoire optimale d’une machine à vendanger qui récolte et sépare deux qualités de raisins. En plus d’être un problème de tournées peu commun, la gestion du remplissage simultané des deux bacs augmente la combinatoire du problème. Plusieurs modèles sont présentés et testés sur des données réelles provenant de vignobles situés dans le sud de la France.La deuxième contribution est l’établissement d’une nouvelle contrainte globale de tournées nommée WeightedSubCircuits. Elle permet d'aborder le problème plus général de tournées multiples dans lequel on cherche à couvrir une partie du graphe par un ensemble de circuits disjoints de coût minimal. Un algorithme de filtrage partiel de cette contrainte est également présenté. Des expérimentations ont été réalisées, notamment sur un problème de planning de techniciens intervenant sur des vignobles en Californie qui a été modélisé dans le cadre de cette thèse. Ces résultats préliminaires ont montré l'intérêt du filtrage apporté par cette nouvelle contrainte. / L’agriculture de précision est un mode de culture qui consiste à prendre en compte la variabilité intra-parcellaire afin d'appliquer le bon traitement au bon endroit. Depuis les années 80, l’agriculture de précision s’est développée grâce à l’arrivée d’outils de géolocalisation (GPS), de matériels permettant une gestion modulée des cultures et surtout d'une multitude de données issues de prélèvements sur le terrain, d'images et de capteurs. Dans ce contexte, l’agriculture de précision a fait émerger de nouveaux problèmes à la fois combinatoires et complexes afin de répondre à des enjeux de performance économique, technique et environnementale.Cette thèse porte sur l'utilisation de la programmation par contraintes pour résoudre des problèmes de tournées dans le contexte de l’agriculture de précision et, plus précisément, en viticulture de précision.Un problème de tournées de véhicule consiste à déterminer une flotte de véhicules afin de visiter une liste de clients ou de réaliser des tournées d’interventions. Le but est de minimiser le coût total des tournées tout en respectant différentes contraintes. Ce problème est une extension classique du problème du voyageur de commerce et fait partie des problèmes NP-difficiles.La programmation par contraintes est un outil très puissant capable de résoudre des problèmes combinatoires comme les problèmes de tournées. Elle fournit des algorithmes de filtrage dédiés à des contraintes de circuits qui permettent de résoudre de façon efficace des problèmes associant ces contraintes de circuit à d'autres contraintes plus spécifiques.La première contribution de cette thèse est la formalisation du problème de la vendange sélective et sa modélisation sous la forme d’un problème d’optimisation sous contraintes. Le problème de la vendange sélective consiste à trouver la trajectoire optimale d’une machine à vendanger qui récolte et sépare deux qualités de raisins. En plus d’être un problème de tournées peu commun, la gestion du remplissage simultané des deux bacs augmente la combinatoire du problème. Plusieurs modèles sont présentés et testés sur des données réelles provenant de vignobles situés dans le sud de la France.La deuxième contribution est l’établissement d’une nouvelle contrainte globale de tournées nommée WeightedSubCircuits. Elle permet d'aborder le problème plus général de tournées multiples dans lequel on cherche à couvrir une partie du graphe par un ensemble de circuits disjoints de coût minimal. Un algorithme de filtrage partiel de cette contrainte est également présenté. Des expérimentations ont été réalisées, notamment sur un problème de planning de techniciens intervenant sur des vignobles en Californie qui a été modélisé dans le cadre de cette thèse. Ces résultats préliminaires ont montré l'intérêt du filtrage apporté par cette nouvelle contrainte.

Dans cette thèse, nous nous sommes intéressés à la résolution approchée de problèmes de tournées de véhicules. Nous avons exploité des travaux menés sur les graphes d'intervalles et des propriétés de dominance relatives aux tournées saturées pour traiter les problèmes de tournées sélectives plus efficacement. Des approches basées sur un algorithme d'optimisation par essaim particulaire et un algorithme mémétique ont été proposées. Les métaheuristiques développées font appel à un ensemble de techniques particulièrement efficaces telles que le découpage optimal, les opérateurs de croisement génétiques ainsi que des méthodes de recherches locales. Nous nous sommes intéressés également aux problèmes de tournées classiques avec fenêtres de temps. Différents prétraitements ont été introduits pour obtenir des bornes inférieures sur le nombre de véhicules. Ces prétraitements s'inspirent de méthodes issues de modèles de graphes, de problème d'ordonnancement et de problèmes de bin packing avec conflits. Nous avons montré également l'utilité des méthodes développées dans un contexte industriel à travers la réalisation d'un portail de services mobilité.

Les problèmes de tournées de véhicules (VRPs) ont fait l’objet de plusieurs travaux de recherche depuis maintenant plus de 50 ans. La plupart des approches trouvées dans la littérature s’appuient sur un graphe complet ou un nœud est introduit pour tout point d’intérêt du réseau routier (typiquement les clients et le dépôt). Cette modélisation est, implicitement, basée sur l’hypothèse que le meilleur chemin entre toute paire de points du réseau routier est bien défini. Cependant, cette hypothèse n’est pas toujours valide dans de nombreuses situations. Souvent, plus d’informations sont nécessaires pour modéliser et résoudre correctement le problème. Nous commençons par examiner ces situations et définir les limites de la modélisation basée sur un graphe complet. Nous proposons un état de l’art des travaux qui examinent ces limites et qui traitent des VRPs en considérant plus d’informations issues du réseau routier. Nous décrivons les approches alternatives proposées, à savoir la modélisation utilisant un multi-graphe et celle utilisant la résolution directe sur un graph représentant le réseau routier. Dans une seconde étude, nous nous intéressons à l’approche basée sur la construction d’un multi-graphe. Nous proposons, d’abord, un algorithme qui permet de calculer d’une manière efficace la représentation par multi-graph du réseau routier. Puis, nous présentons une analyse empirique sur l’impact de cette modélisation sur la qualité de la solution. Pour ce faire, nous considérons le problème classique VRPTW comme un problème de pilote. Par la suite, nous développons une méthode heuristique efficace afin de résoudre le VRPTW basée sur une représentation par un multi-graphe.Dans une troisième étape, nous nous concentrons sur l’approche basée sur la résolution directe du problème sur un graphe représentant le réseau routier. Nous développons un algorithme de type branch-and-price pour la résolution de cette variante du problème. Une étude expérimentale est, ensuite, menée afin d’évaluer l’efficacité relative des deux approches. Enfin, nous étudions les problèmes de tournées de véhicules dans lesquels les temps de parcours varient au cours de la journée. Nous proposons un algorithme de type branch-and-price afin de résoudre le problème avec des fenêtres de temps directement sur le graphe représentant le réseau routier. Une analyse empirique sur l’impact de l’approche proposée sur la qualité de la solution est proposée. / Vehicle routing problems (VRPs) have drawn many researchers’ attention for more than fifty years. Most approaches found in the literature are, implicitly, based on the key assumption that the best path between each two points of interest in the road network (customers, depot, etc.) can be easily defined. Thus, the problem is tackled using the so-called customer-based graph, a complete graph representation of the road network. In many situations, such a graph may fail to accurately represent the original road network and more information are needed to address correctly the routing problem.We first examine these situations and point out the limits of the traditional customer-based graph. We propose a survey on works investigating vehicle routing problems by considering more information from the road network. We outline the proposed alternative approaches, namely the multigraph representation and the road network approach.Then, we are interested in the multigraph approach. We propose an algorithm that efficiently compute the multigraph representation for large sized road networks. We present an empirical analysis on the impact of the multigraph representation on the solution quality for the VPR with time windows (VRPTW) when several attributes are defined on road segments. Then, we develop an efficient heuristic method for the multigraph-based VRPTW.Next, we investigate the road network approach. We develop a complete branch-and-price algorithm that can solve the VRPTW directly on the original road network. We evaluate the relative efficiency of the two approaches through an extensive computational study.Finally, we are interested in problems where travel times vary over the time of the day, called time dependent vehicle routing problems (TDVRPs). We develop a branch-and-price algorithm that solves the TDVRP with time windows directly on the road network and we analyze the impact of the proposed approach on the solution quality.