Afin de supporter les différentes activités au sein d’un centre hospitalier, le département de logistique est primordial pour offrir un service de qualité. Plus particulièrement, un service de brancarderie est nécessaire afin d’acheminer les patients non autonomes ou du matériel aux différentes unités de soins. La planification de ces activités de transport présente d’importants défis, car elle s’opère dans un environnement dynamique et imprévisible. En plus, l’aspect humain des transports apporte son lot de complication. Ce document traitera de la problématique du transport intrahospitalier au Centre Hospitalier Universitaire de Sherbrooke (CHUS). Cet établissement de santé coordonne ses activités de transports par le biais d’un système centralisé affectant des requêtes de transports aux différents brancardiers. L’outil de simulation va permettre de reproduire les flux à l’intérieur d’un établissement cible. Ensuite, le comportement du modèle de simulation sera mesuré et analysé lorsque des modifications au niveau des différents paramètres sont apportées.

Le problème de tournée de véhicules (VRP) est un problème classique d'optimisation en recherche opérationnelle et logistique. Il consiste à concevoir des itinéraires efficaces pour une flotte de véhicules afin de desservir plusieurs clients tout en minimisant les coûts de transport et en respectant la capacité des véhicules. Dans le monde réel, les entreprises font face à des problèmes plus complexes qui nécessitent la résolution de problèmes de tournée de véhicules riches. Ces problèmes sont des variantes du VRP qui intègrent des modèles et des approches de solution adaptés aux contraintes et caractéristiques spécifiques à chaque entreprise. Cependant, la complexité de ces variantes riches augmente significativement par rapport aux VRP traditionnels, ce qui peut entraîner des coûts élevés en termes de puissance de calcul et de temps d'exécution. Il est donc crucial pour les entreprises de logistique d'optimiser efficacement leurs opérations de livraison, de ramassage ou de transport, tout en tenant compte de leurs contraintes spécifiques. Cela nécessite des investissements dans des méthodes avancées d'optimisation pour trouver un compromis acceptable entre l'efficacité opérationnelle, les économies de coûts, la satisfaction client et la réduction de l'impact environnemental. Cette thèse s'intéresse à trois variantes distinctes du problème de tournée de véhicules et propose des modèles mathématiques et des approches de solution utilisant des techniques de recherche opérationnelle. La motivation de cette recherche découle d'une collaboration avec des partenaires industriels et de l'identification de certains aspects à explorer dans la littérature existante. Le premier chapitre de la thèse traite de la résolution d'un problème rencontré par les entreprises de distribution de meubles et d'électronique qui offrent des services d'installation à leurs clients. Ce problème est un problème de tournée de véhicules avec des fenêtres de temps et des contraintes de synchronisation entre deux flottes distinctes de livreurs et d'installateurs. Pour le résoudre, nous avons développé un modèle de programmation linéaire en nombres entiers mixtes et utilisé un algorithme de branch-and-bound ainsi qu'une heuristique de recherche à grand voisinage pour trouver des solutions quasi-optimales. Des expérimentations numériques ont fourni des informations précieuses sur la manière dont une entreprise peut réduire ses coûts liés à son offre de service d'installation tout en minimisant la distance parcourue. De plus, nous avons généralisé deux problèmes existants dans la littérature sur le VRP avec la nouvelle variante étudiée. Cela nous a permis d'utiliser nos algorithmes développés pour résoudre ces problèmes et d'établir de nouvelles bornes inférieures et supérieures pour leurs solutions. Le second chapitre aborde la planification efficace de bétonnières livrant du béton prêt à l'emploi sur des chantiers de construction. Le problème implique de concilier des objectifs contradictoires tels que la minimisation des coûts de transport, la maximisation de la satisfaction du client et le respect des horaires des conducteurs. Il faut également prendre en compte des contraintes réalistes telles que les quarts de travail des conducteurs, les heures minimales de travail et les pénalités pour heures supplémentaires. De plus, la planification devient plus complexe lorsque les clients demandent la livraison de plusieurs types de béton dans la même fenêtre de temps. Pour résoudre ce problème rencontré par un partenaire industriel au Québec, nous proposons une formulation mathématique et une approche de solution heuristique. Nous évaluons notre heuristique en utilisant des données spécifiquement générées pour le problème ainsi que des données de référence d'une autre variante connexe. Le dernier chapitre de la thèse aborde un problème de conception de réseaux de distribution en se concentrant sur le problème de localisation et de tournée de véhicules à deux échelons, en tenant compte de l'incertitude de la demande. Nous concevons un réseau de distribution à deux échelons avec des dépôts et des satellites capables d'accommoder des demandes incertaines des clients. Simultanément, nous nous assurons que les itinéraires planifiés restent réalisables pour toutes les valeurs futures de la demande qui seront à l'intérieur d'un ensemble d'incertitude en utilisant des techniques d'optimisation robuste. Pour résoudre ce problème, nous introduisons une formulation robuste pour un modèle mathématique intégré, et utilisons une heuristique de recherche à grand voisinage ainsi qu'un algorithme de branch-and-cut. De plus, nous proposons quatre approches de solution non intégrées basées sur des formulations robustes des problèmes de tournée de véhicules, de localisation de sites, de localisation et de routage, et de localisation de site à deux échelons. Nous comparons l'approche intégrée aux méthodes non intégrées et évaluons le coût de la robustesse ainsi que le compromis entre des solutions robustes plus conservatrices et plus risquées en effectuant des simulations Monte Carlo. En résumé, cette étude enrichit la littérature sur les problèmes de tournées de véhicules, de livraison de béton, de localisation et de tournées de véhicules à deux échelons, ainsi que sur l'optimisation robuste, en proposant des algorithmes efficaces pour résoudre des problèmes ayant des applications pratiques dans les secteurs de la logistique et de la construction. / The Vehicle Routing Problem (VRP) is a classic optimization problem in operations research and logistics. It involves designing efficient routes for a fleet of vehicles to serve multiple customers while minimizing transportation costs and respecting vehicle capacities. In the real world, companies face more complex issues that require solving rich VRPs. These problems are variants of the VRP that incorporate models and solution approaches tailored to the constraints and specific characteristics of each company. However, the complexity of these rich variants increases significantly compared to traditional VRPs, resulting in high computational cost and execution time. Therefore, it is critical for logistics companies to optimize their delivery, pickup, or transportation operations while taking into account their specific constraints. This requires investing in advanced optimization methods to find an acceptable trade-off between operational efficiency, cost savings, customer satisfaction, and reduced environmental impact. In this thesis, we focus on addressing three distinct variants of the Rich VRP and providing models and solutions using operations research techniques. Our research was motivated by our collaboration with industrial companies and the identification of gaps in the existing literature. We first study a real-world problem faced by companies that provide installation services when distributing furniture and electronics. This problem is a VRP with time windows and synchronization constraints between two distinct delivery and installation fleets. To solve this problem, we develop a mixed-integer linear programming model and employ a branch-and-bound algorithm and adaptive large neighborhood search metaheuristic to find near-optimal solutions. Extensive computational experiments provide valuable insights into how a company can reduce its costs related to its installation service while minimizing the total distance traveled. The variant we studied is a generalization of two existing problems in the VRP literature, so we applied our developed algorithms to solve these problems and provided new lower and upper bounds for their solutions. Next, we address the problem of efficiently scheduling concrete mixers to deliver ready-mixed concrete to construction sites. The problem involves balancing conflicting objectives: minimizing transportation costs, maximizing customer satisfaction, while respecting driver schedules. Realistic constraints must be considered, including driver work shifts, minimum working hours, and overtime penalties. Additionally, scheduling becomes more complex when customers request multiple types of concrete to be delivered within the same time window. To solve this concrete delivery problem faced ivby an industrial partner in Quebec, we propose a mathematical formulation and a heuristic solution approach. We evaluate our proposed heuristic using instances specifically generated for the problem, as well as benchmark instances from another related variant. Finally, we study a problem in the design of distribution networks: the two-echelon capacitated location routing problem under demand uncertainty. We design a distribution network with open depots and satellites capable of accommodating uncertain customer demands at the second echelon. Simultaneously, we ensure that planned routes remain feasible for all values within an uncertainty set using the robust optimization methodology. To solve this uncertain problem, we introduce a robust counterpart for an integrated model and employ an adaptive large neighborhood search and branch-and-cut algorithms to find near-optimal solutions. Additionally, we propose four non-integrated solution approaches based on robust counterparts for the VRP, facility location problem, location routing problem, and two-echelon facility location problem. We compare the integrated approach to non-integrated methods and evaluate the cost of robustness and the trade-off between conservative and riskier robust solutions using Monte Carlo simulations. Overall, this thesis provides valuable contributions to the fields of VRP, Concrete Delivery Problem, Two-Echelon Location Routing Problem, and Robust Optimization by developing efficient algorithms for solving real-world problems with practical applications in the logistics and construction industries.

Le concept de réserve voie a été présenté comme une stratégie de gestion du trafic et a de nombreuses applications dans la vie réelle. Des études antérieures dans la littérature se concentrent principalement sur l'impact de la réservation de la voie dans une région locale du réseau de transport. Dans cette thèse, les problèmes de réservation de voies sont étudiés dans le but de minimiser l'impact sur le trafic total par la réservation optimale des voies dans un réseau de transport. Nous avons d’abord se concentrer sur le problème de réservation de voie (LRP) pour le transport automatisé pour les poids lourds avec temps de déplacement statique. Ce travail est généralisé au problème de réservation voies avec une capacité limitée de la voie (CLRP) pour les grands événements spéciaux. Enfin, le problème de réservation de voies avec le temps de déplacement dépendant du temps (LRP-TT), et le problème de réservation voies avec la vitesse de déplacement dépendant du temps (LRP-TS) sont étudiés. Pour chacun des problèmes étudiés, les modèles mathématiques appropriés sont formulés, leurs complexités sont démontrées. Différentes méthodes de résolution sont explorées, y compris exacte cut-and-solve méthode, cut-and-solve et méthod de coupe combinée, et la méthode de recherche tabou. Les performances des algorithmes proposés sont évaluées par des instances générées au hasard. Les résultats numériques ont montré que les algorithmes proposés sont plus efficaces pour résoudre les problèmes étudiés que le logiciel commercial référence CPLEX / The concept of lane reservation has been introduced as a traffic management strategy and has many applications in real life. Previous studies in the literature mainly focus on the impact of lane reservation in a local region of transportation network. In this thesis optimal lane reservation problems are studied with the objective to minimize impact on total traffic by optimally setting reserved lanes in a transportation network. We firstly focus on the lane reservation problem (LRP) for automated truck freight transportation with static link travel time. This primary work has been extended to the capacitated lane reservation problem (CLRP) for large-scale special events. Finally, lane reservation problem with time-dependent travel time (TTLRP), and lane reservation problem with time-dependent travel speed (TSLRP) are studied. For each of the considered problems, appropriate mathematical models are formulated, their complexities are demonstrated. Different resolution methods are explored including exact cut-and-solve method, cut-and-solve and cutting plane combined method, and Tabu-search method. The performance of the proposed algorithms is evaluated by randomly generated instances. Numerical results have shown that the proposed algorithms are more effective to solve the considered problems than the reference commercial package CPLEX

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

Ce mémoire traite un problème de transport de personnes dans un contexte hospitalier, connu sous le nom du problème de brancardier. L'objectif est de construire des itinéraires qui répondent aux demandes de transports émergentes entre les différents services d'un grand centre hospitalier en temps réel, en minimisant le temps total de retard pondéré. Ce problème est traité comme un problème de cueillettes et de livraisons multitrajets qui considère des fenêtres de temps souples, une flotte hétérogène de véhicules et des contraintes liées à la capacité. Les requêtes de transport de patients sont imprévisibles et dynamiques. Elles sont révélées lorsqu'un patient nécessite un service de transport pour des raisons médicales. Ce travail présente trois approches de résolution du problème de transport de patients, à noter une première approche statique, une deuxième dynamique et une troisième stochastique. De plus, une stratégie d'attente et deux stratégies de relocalisation de véhicules ont été développées. Les approches sont évaluées sur des données réelles d'un grand hôpital, le Policlinico Sant'Orsola-Malpighi de la mairie de Bologne en Italie. / The following study presents the problem of transportation of patients in the medical field. Demand in this context is unpredictable and revealed dynamically. The objective is to develop an algorithm capable of constructing efficient and effective routes in real time while minimizing the total weighted lateness. This problem is considered as a multitrip pickup and delivery problem with soft time windows, heterogeneous fleet, and capacity constraints. This work presents a detailed description of the discussed problem and proposes three approaches to solve it: a static approach, a dynamic approach and a stochastic one. Moreover, it presents a waiting and two relocalisation strategies. These approaches have all been tested and evaluated using real data collected from the medical campus of Policlinico Sant'Orsola-Malpighi of the town Hall of Bologne in Italy.

Ce mémoire vise à justifier la pertinence de la mutualisation des besoins de transport en charges partielles par les entreprises expéditrices. En effet, les avantages de la mutualisation dans un contexte de transport ont déjà été démontrés, mais plus précisément du point de vue des transporteurs. Voulant ainsi justifier un tel concept, mais du point de vue des entreprises expéditrices, une Plate-forme virtuelle d’optimisation et de mutualisation des opérations de transport en charges partielles est simulée dans ce mémoire. Pour démontrer cette pertinence, le but premier a été de s’intéresser à la réduction des émissions de gaz à effet de serre (GES) découlant d’un tel effort de mutualisation, la prémisse de ce mémoire étant de réduire l’empreinte écologique de l’industrie du transport routier et de diminuer l’achalandage sur le réseau routier à Québec. Ainsi, le deuxième but a été de s’intéresser à la réduction du nombre de camions en circulation. Enfin, le troisième et dernier but a été de s’intéresser aux gains financiers d’une telle plate-forme, soit l’incitatif presque toujours premier des entreprises. À l’aide d’entreprises situées à Québec, il a été possible de simuler un contexte réel de commerce entre des entreprises partenaires et des transporteurs. Les résultats obtenus permettent de constater qu’un effort de mutualisation aide à réduire significativement les émissions de GES dès qu’une dizaine d’entreprises participent (réductions de 35% et plus pour les trois tests effectués). Finalement, il est démontré que les résultats économiques d’une telle plate-forme sont également très attirants pour les entreprises qui acceptent d’être des partenaires d’affaires. Enfin, l’idée présentée dans ce mémoire a été poussée encore plus loin et est l’objet de l’article scientifique intitulé Service level, financial and environmental optimization of collaborative transportation auquel j’ai participé en tant coauteure.

Cette recherche vise à améliorer l'efficacité et la qualité des systèmes de santé en optimisant le *transport des patients intra-hôpital* - une activité opérationnelle critique mais souvent négligée au sein des hôpitaux. L'étude se concentre sur plusieurs processus de prise de décision qui jouent des rôles pivots aux niveaux stratégique, tactique et opérationnel. Elle met en lumière la nature dynamique des demandes de transport, des besoins en équipement et de la charge physique sur les porteurs, offrant une exploration détaillée des lacunes existantes et proposant des solutions innovantes, se concentrant sur la minimisation des temps d'attente des patients et l'optimisation de l'utilisation des ressources pour améliorer la qualité globale du service. La première partie de cette thèse explore la prise de décision en temps réel, s'adaptant à l'arrivée imprévisible des demandes de transport. Considérant que les décideurs doivent mettre à jour les horaires actuels en raison de l'arrivée dynamique des demandes, des politiques de réaffectation sont proposées et évaluées. Pour l'attribution des demandes de transport aux porteurs, la mise en œuvre de différentes méthodes de résolution telles que des formulations mathématiques et des heuristiques est proposée. Cette partie vise à évaluer la combinaison de politiques de réaffectation et de méthodes de résolution pour améliorer les systèmes de transport *intra-hôpital*. Les sections suivantes de la thèse se concentrent sur l'incorporation d'autres hypothèses actuelles et réalités du système de transport des patients *intra-hôpital*. Ces aspects incluent plusieurs modes de transport et les efforts ergonomiques des porteurs, aspects souvent négligés dans la littérature. En intégrant ces facteurs, les approches d'optimisation prendront en compte les besoins de changement d'équipement et assureront l'équité dans la charge de travail des porteurs. La recherche utilise des modèles d'optimisation et de modèle simulation d'événements discrets pour souligner l'applicabilité pratique des solutions proposées. En conclusion, la thèse intègre les stratégies d'optimisation recherchées dans un modèle de Simulation d'Événements Discrets. Ce cadre est présenté pour simuler l'arrivée dynamique des demandes, mais sert également d'outil d'aide à la décision permettant aux gestionnaires d'évaluer stratégiquement et d'optimiser un système de transport de patients *intra-hospitalier*. En mettant l'accent sur un équilibre entre les objectifs managériaux, la satisfaction des patients et le fardeau ergonomique des porteurs, le modèle de Simulation d'Événements Discrets offre une approche complète visant à améliorer l'efficacité globale des institutions de santé. Ce thèse est structuré comme suit : Le chapitre introductif est suivi du Chapitre 1, qui présente une revue de littérature sur le problème de transport des patients *intra-hôpital*. Dans le Chapitre 2, l'accent est mis sur l'introduction du problème, spécifiquement l'évaluation de l'arrivée dynamique des demandes et la combinaison des politiques de reprogrammation et des méthodes de résolution. Le Chapitre 3 intègre la nécessité pour les porteurs de changer d'équipement dans les modèles d'optimisation. Enfin, le Chapitre 4 se concentre sur le fardeau ergonomique des porteurs, en évaluant différentes fonctions objectives et une *Bi-Objective Optimization* pour maintenir l'efficacité opérationnelle du système de transport tout en assurant une répartition équitable de la charge de travail parmi les porteurs. / This research aims to enhance the efficiency and quality of healthcare systems by optimizing *intra-hospital patient transportation* -- a critical yet often overlooked operational activity within hospitals. The study focuses on multiple decision-making processes that play pivotal roles at strategic, tactical, and operational levels. It highlights the dynamic nature of transportation requests, equipment needs, and the physical burden on porters, offering a detailed exploration of existing gaps and proposing innovative solutions, focusing on minimizing patient waiting times and optimizing resource utilization to improve overall service quality. The first part of this thesis explores real-time decision-making, adapting to the unpredictable arrival of transport requests. Considering that decision-makers must update current schedules due to the dynamic arrival of requests, rescheduling policies are proposed and evaluated. For the assignment of transport requests to porters, the implementation of various solving methods such as mathematical formulations and heuristics is proposed. This part aims to evaluate the combination of rescheduling policies and solving methods to improve the *intra-hospital* transportation systems. The subsequent sections of the thesis focus on incorporating current assumptions and realities of the *intra-hospital* patient transportation system. These include multiple modes of transportation and the ergonomic efforts of porters, aspects often neglected in the literature. By incorporating these factors, the optimization approaches will account for equipment switching requirements and ensure the fairness in the workload of porters. The research utilizes optimization models and Discret-Event Simulation model to emphasize the practical applicability of the proposed solutions. In conclusion, the thesis integrates the researched optimization strategies into an Discret-Event Simulation model. This model is presented to simulate the dynamic arrival of the request, but also is as decision-making tool that enables managers to strategically evaluate, and optimize an *intra-hospital* patient transportation system. Emphasizing a balanced focus on managerial objectives, patient satisfaction, and porter ergonomic burden, our research provides a comprehensive approach towards improving the overall efficiency of healthcare institutions. This thesis is structured as follows: The introductory chapter is followed by Chapter 1, which presents a literature review on the *intra-hospital* patient transportation problem. In Chapter 2, the focus is on introducing the problem, specifically evaluating the dynamic arrival of requests and the combination of rescheduling policies and solving methods. Chapter 3 integrates the necessity of porters switching equipment into the optimization models. Lastly, Chapter 4 focuses on the ergonomic burden of porters, evaluating different objective functions and a Bi-Objective Optimization to maintain the operational efficiency of the transportation system while ensuring a fair workload distribution among porters.