Cette thèse porte sur la résolution de problèmes de transport qui intègrent des contraintes temporelles considérant les fenêtres de temps, la synchronisation des visites et l’équilibrage des services. Ces problèmes trouvent plusieurs applications dans le monde réel.L’objectif de nos recherches est l’élaboration de nouvelles méthodes de résolution pour les problèmes considérés en examinant leur performance avec une étude comparative par rapport aux différentes approches de la littérature. Deux variantes sont traitées. Le premier cas étudie le Problème de Tournées de Véhicules avec Fenêtres de Temps (VRPTW). Nous proposons de nouveaux prétraitements et bornes inférieures pour déterminer le nombre de véhicules nécessaires en s’inspirant de travaux menés en ordonnancement (raisonnement énergétique) et d’autres problèmes combinatoires comme la clique maximum et les problèmes de bin-packing. Nous présentons également un algorithme d’optimisation par essaim particulaire qui traite de la minimisation du nombre de véhicules puis de celle du temps de trajet total. Le deuxième cas étudie le Problème de Tournées de Véhicules avec des Fenêtres de Temps et des Visites Synchronisées (VRPTWSyn). Nous proposons plusieurs méthodes basées sur des approches heuristiques et des formulations linéaires avec l’incorporation d’inégalités valides pour tenir compte de la contrainte de synchronisation. / This dissertation focuses on vehicle routing problems, one of the major academic problems in logistics. We address NP-Hard problems that model some realworld situations particularly those with different temporal constraints including time windows, visit synchronization and service balance.The aim of this research is to develop new algorithms for the considered problems,investigate their performance and compare them with the literature approaches.Two cases are carried out. The first case studies the Vehicle Routing Problem with Time Windows (VRPTW). We propose new lower bound methods for the number of vehicles. Then we present a Particle Swarm Optimization algorithm dealing with the Solomon objective. The second case studies the VehicleRouting Problem with Time Windows and Synchronized Visits (VRPTWsyn).Both exact methods and heuristics are proposed and compared to the literature approaches.

Cette thèse cherche à analyser les trois tournées de l’actrice française Sarah Bernhardt (1844-1923) au Brésil, précisément dans les villes de Rio de Janeiro et Sao Paulo. Les voyages datant de 1886, 1893, 1905. Cette étude a comme arrière-plan les réflexions autour de la circulation culturelle et de la mondialisation de la culture au XIXe siècle. On considère les voyages Sarah Bernhardt comme un exemple précieux du processus de diffusion du théâtre français et d’internationalisation des publics. Coté brésilien, on percevra que cette même période, marquée par une forte présence artistique étrangère, est aussi le moment où les Brésiliens (ou du moins l’élite lettrée du pays) cherchent à penser l’identité du pays, tout en édifiant l’art dramatique national. L’enjeu de cette thèse est alors de comprendre comment la présence théâtrale étrangère se place dans ce contexte. Plus qu’une étude sur une « influence théâtrale » française au Brésil, l’objectif des pages qui suivent est de réfléchir à la formation de la pratique artistique brésilienne dans le cadre d’un processus plus large de mondialisation de la culture au XIXe siècle – où le théâtre occupe une place majeure. En ce qui concerne précisément Sarah Bernhardt, cette thèse cherche à démontrer l’importance de l’actrice dans ce phénomène. Grande étoile médiatique de la période, Sarah est, dans le même temps, liée au grand théâtre français de répertoire. La question est alors de comprendre comment ce « grand théâtre » se diffuse internationalement, tout en s’imprégnant des stratégies commerciales de l’industrie théâtrale de l’époque. Dans ce sens, on se demandera comment l’actrice construit son image à l’étranger, plus particulièrement au Brésil, et quelle partie du « marché » culturelle cherche-t-elle à dominer, soutenue par ses imprésarios. En un mot comment la « Sarah Barnum* » se veut-elle également ambassadrice du génie français ? Référence à l’entrepreneur de spectacles américain Phineas Taylor Barnum (1810-1891). Il était connu pour ses affaires très prospères dans le domaine culturel. Le Cirque Barnum, fondé en 1871 est devenu l’un des plus connus de l’époque et a rassemblé des artistes provenant de divers pays. Dans le monumental ouvrage édité par Noel Daniel sur le cirque aux Etats-Unis entre 1850 et 1950, Linda Granfield remarque l’importance de Barnum : « Aujourd’hui encore, les hommes d’affaires du monde entier étudient la conférence donnée par Barnum en 1858 et intitulée The Art of Money Getting («L’Art de faire de l’argent »). Il y exposait sa vision de la réussite financière et déclarait : « Aux Etats-Unis où nous avons plus de terres que d’habitants, il n’est pas difficile pour une personne en bonne santé de prospérer ». (Granfield, Linda. « Un vent de folie souffle sur la ville » In Noel Daniel (ed.), The circus 1850-1950. New York : Éditions Taschen, 2008. p.53) Les titres des différentes parties de son discours comme « Quoique que vous entrepreniez, mettez-y toute votre énergie », « Lisez la presse » et, une des  clefs de sa réussite, « Faites de la publicité », continuent d’inspirer les entrepreneurs à ce jour. Le surnom « Sarah Barnum » a été employé par l’actrice Marie Colombier, dans un livre qui proposait de témoigner de la tournée de Sarah Bernhardt en Amérique. L’ouvrage paru en 1883, qui a fait scandale : « Les Mémoires de Sarah Barnum » cherchait clairement à donner l’image d’une Sarah Bernhardt cabotine et intéressée par le profit, tout comme le grand imprésario américain Taylor Barnum. Voir Marie Colombier, Voyages de Sarah Bernhardt en Amérique. Paris : C. Marpon et E. Flammarion Éditeurs, 1887. / This work proposes an analysis of the french actress Sarah Bernhardt's (1844-1923) three tours in Brazil, precisely in the cities of Rio de Janeiro and São Paulo in 1886, 1893, 1905. Taking the thoughts about the flow of artists and the cultural globalization of the 19th century as a background, the present study considers Sarah Bernhardt tours as a precious example of the French theater diffusion process and of the internalization of audiences. In what regards Brazil, it is noticeable that the referred period, marked by a strong foreign artistic presence, is also the moment in which the country’s literate elite reflected about a project of a nation and about the construction of a national dramatic art. The focus of this thesis is, therefore, to locate Sarah Bernhardt’s tours in this panorama. More than a study about French “theatrical influence” in Brazil, our main goal is to ponder about the construction of the Brazilian artistic practice in a context of a broader process of cultural globalization in the 19th century, in which theater played a fundamental role. In what concerns Sarah Bernhardt specifically, this thesis intends to demonstrate the actress’s relevance in this phenomenon. Sarah was a great media star and, at the same time, associated to the french theater erudite repertoire. It attempts, therefore, to understand in what way this “repertory theater” is internationally broadcasted, also impregnating itself with commercial strategies common to the period’s theater industry. In that sense, the construction of the actress’s image abroad, specially in Brazil, is questioned. Also, what part of the cultural “market” Sarah Bernhardt and her managers tried to dominate is evaluated. In other words, how did the actress became Sarah Barnum, with a flair of ambassador of the génie français ?

Le présent mémoire traite du problème de distribution de l’aide humanitaire en région sinistrée. L’objectif est de distribuer l’aide humanitaire à des zones sinistrées à partir d’un ensemble de centres de distribution via une flotte de véhicules hétérogène. Étant donné le contexte particulier d’urgence, la distribution est planifiée pour satisfaire la demande des zones touchées pour chaque type d’aide humanitaire dans les plus brefs délais, tout en tenant compte à la fois de la durée de déplacement et de la durée de chargement et de déchargement. Dans ce mémoire, nous proposons une approche itérative à deux phases afin d’améliorer la qualité de la solution obtenue par une approche heuristique déjà proposée par Berkoune et al. (2011). Des séries d’expérimentations basées sur des problèmes tests ont été effectuées pour évaluer la qualité de la solution obtenue avec l’algorithme développé. La synthèse des résultats obtenus a démontré que l’approche développée permet de résoudre à l’optimalité des problèmes de taille réduite en évitant d’énumérer de façon exhaustive toutes les combinaisons possibles. Une évaluation du choix de la condition d’arrêt ainsi que trois variantes de l’algorithme développé ont été également proposées. Les résultats obtenus nous ont menés à conclure que lorsque la taille du problème devient importante, les améliorations proposées présenteraient une bonne alternative pour réduire le temps total de calcul et raffiner la qualité de la solution obtenue. Mots clés : Logistique humanitaire, tournées de véhicules, livraison partagée, modélisation mathématique et heuristiques. / This thesis addresses the problem of distribution of humanitarian aid in disaster areas. The objective is to deliver humanitarian aid to the affected areas from a set of distribution centers, by using a fleet of heterogeneous vehicles. Given the particular emergency situation, the distribution is planned to meet the demand of affected areas for each type of humanitarian aid in the shortest possible time, taking into account both the travel and products loading and unloading times. In this thesis, we propose a two-phase solution approach in order to improve the quality of the solution obtained using the heuristic approach previously proposed by Berkoune et al. (2011). A series of experiments are run to assess the quality of the solutions obtained with the developed algorithm. The obtained results showed that the developed approach can solve the problem to optimality for the majority of the instances, avoiding an exhaustive enumeration of all possible combinations. An evaluation of the choice of stopping condition and three Variants of the developed algorithm are also proposed. The obtained results show that when the problem size becomes large, the proposed improvements provide a good alternative to reduce the total computation time and improve the quality of the obtained solution. Keywords: Emergency logistics, vehicle routing, split delivery, mathematical modeling and heuristics.

De nos jours, les services de livraison à domicile deviennent de plus en plus sollicités an de répondre aux besoins des clients qui cherchent à recevoir leurs produits dans les plus brefs délais et avec des coûts raisonnables. Les entreprises œuvrant dans le domaine de la livraison à domicile ont différentes manières de proposer des fenêtres de temps à leurs clients. Certains, comme les bannières à rabais, ont comme objectif d'offrir des solutions de transport au coût minimal. Ces entreprises offrent très peu de flexibilité à leurs clients quant aux modalités de livraison. Ainsi, certains clients pourraient faire leurs achats chez d'autres détaillants qui offrent un meilleur service. D'autres entreprises offrent plus de flexibilité aux clients en mettant à leur disposition un large éventail de fenêtres de temps où pourrait avoir lieu leur livraison. Cette manière de procéder engendre forcément des coûts additionnels, car les conducteurs feront des livraisons dans leurs secteurs plusieurs fois par semaine. Ces coûts seront alors transférés dans les prix de vente de l'entreprise. Ces deux exemples constituent deux méthodes extrêmes pour planifier les livraisons. L'un priorise davantage les coûts au détriment de la satisfaction des clients. Le deuxième effectue le contraire en misant davantage sur la satisfaction des clients au prix d'avoir des coûts de transport plus élevés. Ce mémoire a pour objectif de proposer de nouvelles techniques pour offrir un compromis entre ces deux extrémités. Ces techniques auront pour but d'offrir plusieurs de choix aux clients tout en essayant de maintenir des coûts de livraison qui sont bas. Notre schéma de résolution s'effectue en deux temps : 1. Nous utiliserons des heuristiques pour générer des calendriers de livraison, 2. Nous simulerons des arrivées de clients desquels nous calculerons différentes valeurs pour mesurer la satisfaction du client avec les coûts de transport. Les résultats seront interprétés de manière à regarder tous les aspects techniques et comparer la satisfaction avec les coûts de transport. Mots clés : Livraison à domicile, satisfaction client, tournée de véhicules, offre de fenêtres de temps. / Nowadays, home delivery services have become more and more requested in order to respond to the needs of customers seeking to receive their products as quickly as possible and at a reasonable cost. Home delivery companies have di erent ways of offering time windows to their customers. Some, such as discount banners, aim to provide transportation solutions at minimal cost. These companies offer very little exibility to their customers regarding delivery terms. That's why, some customers could shop at other retailers who offer better service. Other companies offer customers more exibility by providing a wide range of time windows where their delivery could take place. This way of doing things inevitably entails additional costs, since drivers will make deliveries to their zones several times a week. These costs will then be transferred to the sales prices of the company. These two examples are two extreme methods for scheduling deliveries. One prioritizes costs at the expense of customer satisfaction. The second is doing the opposite by focusing more on customer satisfaction at the cost of higher transportation costs. This thesis has as objective to propose new techniques to offer a compromise between these two ends. These techniques will aim to offer many choices to customers while trying to keep shipping costs low. Our resolution scheme is done in two stages: 1. We will use heuristics to generate delivery schedules, 2. We will simulate customer arrivals from which we will calculate different values to measure customer satisfaction with transportation costs. The results will be interpreted in a way that looks at all technical aspects and compares satisfaction with transportation costs. Keywords: Home delivery, customer satisfaction, vehicle routing problem, time windows offer.

Le problème d'approvisionnement de stations d'essence consiste à livrer des carburants à l'aide d'une flotte de camions-citernes compartimentés en maximisant une fonction de revenu du transporteur. Il convient essentiellement de déterminer les quantités à livrer de chaque produit, de les affecter aux compartiments des véhicules et de construire les routes permettant leur livraison. Cette thèse comporte trois articles présentant chacun une version différente de ce problème d'approvisionnement. / Nous proposons, dans le premier article, une méthode exacte de résolution applicable au cas où la flotte est illimitée et le nombre de stations par route limité à deux. Le problème y est décomposé en un sous-problème d'affectation des produits aux compartiments des véhicules et un sous-problème de routage. L'affectation des produits aux compartiments repose sur un algorithme classique d'affectation dans un graphe bipartite suivi d'un test d'optimalité, et recourt éventuellement à la résolution d'un programme linéaire en nombres entiers. Puisqu'un voyage ne peut desservir plus de deux stations, le problème de routage est réduit à un problème de couplage de coût minimal clans un graphe non bipartite. Deux stratégies sont alors proposées : rechercher un chargement admissible des produits dans les compartiments pour tous les couples possibles de stations, puis résoudre le problème de couplage correspondant, ou générer les routes en résolvant le problème de couplage a priori pour ensuite tester l'existence d'un chargement admissible pour chacune, cette procédure étant répétée aussi longtemps qu'une route non admissible est générée. / Nous présentons dans le second article une heuristique appliquée au problème d'approvisionnement sur plusieurs périodes avec cette fois un nombre limité de camions-citernes. Dans cette version du problème d'approvisionnement, l'objectif est de déterminer pour chacjue période, les stations, les produits et les quantités à livrer, d'affecter les pioduits aux compartiments des camions-citernes et de construire les routes. L'affectation des stations aux différentes périodes est déterminée par un algorithme récursif incluant une procédure d'anticipation des livraisons. Nous proposons par ailleurs une procédure d'affectation des routes aux véhicules (route packing) par laquelle les routes sont affectées aux véhicules. / Dans le troisième article, nous nous intéressons à nouveau au problème monopé¬riode en intégrant cette fois la gestion des fenêtres de temps en dehors desquelles les livraisons ne peuvent avoir lieu. Nous y considérons par ailleurs le cas d'une flotte limitée et relaxons l'hypothèse de limitation des routes à deux stations. Une formulation différente de celle proposée dans le premier article est présentée. Elle repose sur une sélection de routes respectant les contraintes horaires à partir d'un ensemble de routes admissibles générées a priori et éventuellement présélectionnées. De cette formulation, deux heuristiques sont développées reposant sur une présélection des arcs du graphe c

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.

Ce document a pour but de décrire les processus de prise d’appels et de formation des routes de la compagnie Med Express. L’étude commence par effectuer la cartographie des flux des opérations ainsi qu’une analyse sur la construction des routes. L’analyse des routes construites par Med Express a démontré qu’il y avait un haut taux de retard. En utilisant un algorithme, la moyenne d’appels par route est restée semblable, mais sans aucun retard. En traitant les appels comme préprogrammés, le nombre moyen d’appels par route a augmenté tout en diminuant la distance totale parcourue. Ces résultats nous ont permis d’affirmer que la séparation myope des appels entre les répartiteurs diminue l’efficacité globale de la flotte. De plus, le fait de connaitre la demande à l’avance est un avantage. Finalement, un léger changement dans les heures de cueillettes permet de grandes améliorations globales quant à la distance parcourue et au nombre d’appels par route.

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.

Tableau d’honneur de la Faculté des études supérieures et postdoctorales, 2018-2019. / Les activités de distribution et d’entreposage sont des piliers importants de la chaîne d’approvisionnement. Ils assurent la stabilité du flux de matières et la synchronisation de toutes les parties prenantes du réseau. Un centre de distribution (CD) agit comme un point de découplage entre l’approvisionnement, la production et les ventes. La distribution comprend un large éventail d’activités visant à assurer la satisfaction de la demande. Ces activités passent de la réception au stockage des produits finis ou semi-finis, à la préparation des commandes et à la livraison. Les opérations d’un CD sont maintenant perçues comme des facteurs critiques d’amélioration. Elles sont responsables de la satisfaction d’un marché en évolution, exigeant des délais de livraison toujours plus rapides et plus fiables, des commandes exactes et des produits hautement personnalisés. C’est pourquoi la recherche en gestion des opérations met beaucoup d’efforts sur le problème de gestion des CDs. Depuis plusieurs années, nous avons connu de fortes avancées en matière d’entreposage et de préparation de commandes. L’activité de préparation de commandes est le processus consistant à récupérer les articles à leur emplacement de stockage afin d’assembler des commandes. Ce problème a souvent été résolu comme une variante du problème du voyageur de commerce, où l’opérateur se déplace à travers les allées de l’entrepôt. Cependant, les entrepôts modernes comportent de plus en plus de familles de produits ayant des caractéristiques très particulières rendant les méthodes conventionnelles moins adéquates. Le premier volet de cette thèse par articles présente deux importants et complexes problèmes de manutention des produits lors de la préparation des commandes. Le problème de préparation des commandes a été largement étudié dans la littérature au cours des dernières décennies. Notre recherche élargit le spectre de ce problème en incluant un ensemble de caractéristiques associées aux installations physiques de la zone de prélèvement, comme les allées étroites, et aux caractéristiques des produits (poids, volume, catégorie, fragilité, etc.). Une perspective plus appliquée à la réalité des opérations est utilisée dans notre développement d’algorithmes. Les déplacements liés à la préparation des commandes sont fortement influencés par le positionnement des produits. La position des produits dans la zone de prélèvement est déterminée par une stratégie d’affectation de stockage (storage assignment strategy). Beaucoup de ces stratégies utilisent de l’information sur les ventes des produits afin de faciliter l’accès aux plus populaires. Dans l’environnement concurrentiel d’aujourd’hui, la durée de vie rentable d’un produit peut être relativement courte. Des promotions peuvent également être faites pour pousser différents produits sur le marché. Le positionnement fourni par la stratégie d’hier ne sera probablement plus optimal aujourd’hui. Il existe plusieurs études mesurant l’impact d’une bonne réaffectation de produits sur les opérations de prélèvement. Cependant, ils étudient la différence des performances avec les positionnements passés et actuels. La littérature démontre clairement que cela apporte des avantages en termes d’efficacité. Toutefois, les déplacements nécessaires pour passer d’une position à une autre peuvent constituer une activité très exigeante. Ceci constitue le second volet de cette thèse qui présente des avancées intéressantes sur le problème de repositionnement des produits dans la zone de prélèvement. Nous présentons le problème de repositionnement des produits sous une forme encore peu étudiée aux meilleurs de nos connaissances : le problème de repositionnement. Plus précisément, nous étudions la charge de travail requise pour passer d’une configuration à l’autre. Cette thèse est structuré comme suit. L’introduction présente les caractéristiques et les missions d’un système de distribution. Le chapitre 1 fournit un survol de la littérature sur les principales fonctions d’un centre de distribution et met l’accent sur la préparation des commandes et les décisions qui affectent cette opération. Le chapitre 2 est consacré à l’étude d’un problème de préparation de commandes en allées étroites avec des équipements de manutention contraignants. Dans le chapitre 3, nous étudions un problème de préparation des commandes où les caractéristiques des produits limitent fortement les routes de prélèvement. Le chapitre 4 présente une variante du problème de repositionnement (reassignment) avec une formulation originale pour le résoudre. La conclusion suit et résume les principales contributions de cette thèse. Mots clés : Préparation des commandes, entreposage, problèmes de routage, algorithmes exacts et heuristiques, réaffectation des produits, manutention. / Distribution and warehousing activities are important pillars to an effective supply chain. They ensure the regulation of the operational flow and the synchronization of all actors in the network. Hence, distribution centers (DCs) act as crossover points between the supply, the production and the demand. The distribution includes a wide range of activities to ensure the integrity of the demand satisfaction. These activities range from the reception and storage of finished or semi-finished products to the preparation of orders and delivery. Distribution has been long seen as an operation with no or low added value; this has changed, and nowadays it is perceived as one of the critical areas for improvement. These activities are responsible for the satisfaction of an evolving market, requiring ever faster and more reliable delivery times, exact orders and highly customized products. This leads to an increased research interest on operations management focused on warehousing. For several years, we have witnessed strong advances in warehousing and order picking operations. The order picking activity is the process of retrieving items within the storage locations for the purpose of fulfilling orders. This problem has long been solved as a variant of the travelling salesman problem, where the order picker moves through aisles. However, modern warehouses with more and more product families may have special characteristics that make conventional methods irrelevant or inefficient. The first part of this thesis presents two practical and challenging material handling problems for the order picking within DCs. Since there are many research axes in the field of warehousing operations, we concentrated our efforts on the order picking problem and the repositioning of the products within the picking area. The order picking problem has been intensively studied in the literature. Our research widens the spectrum of this problem by including a set of characteristics associated with the physical facilities of the picking area and characteristics of the product, such as its weight, volume, category, fragility, etc. This means that a more applied perspective on the reality of operations is used in our algorithms development. The order picking workload is strongly influenced by the positioning of the products. The position of products within the picking area is determined by a storage assignment strategy. Many of these strategies use product sales information in order to facilitate access to the most popular items. In today’s competitive environment, the profitable lifetime of a product can be relatively short. The positioning provided by yesterday’s assignment is likely not the optimal one in the near future. There are several studies measuring the impact of a good reassignment of products on the picking operations. However, they study the difference between the two states of systems on the picking time. It is clear that this brings benefits. However, moving from one position to another is a very workload demanding activity. This constitutes the second part of this thesis which presents interesting advances on the repositioning of products within the picking area. We introduce the repositioning problem as an innovative way of improving performance, in what we call the reassignment problem. More specifically, we study the workload required to move from one setup to the next. This thesis is structured as follows. The introduction presents the characteristics and missions of a distribution system. Chapter 1 presents an overview of the literature on the main functions of a DC and emphasizes on order picking and decisions affecting this operation. Chapter 2 is devoted to the study of a picking problem with narrow aisles facilities and binding material handling equipment. In Chapter 3, we study the picking problem with a set of product features that strongly constrain the picking sequence. Chapter 4 presents a variant of the reassignment problem with a strong and new formulation to solve it. The conclusion follows and summarizes the main contributions of this thesis. Key words: Order-picking, warehousing, routing problems, exact and heuristic algorithms, products reassignment, material handling.

Ce mémoire présente les résultats de projets d'optimisation de réseaux de transport de l'entreprise Produit Forestier Résolu (PFR). Ces réseaux traitent, dans un cas, du transport de bois brut inter-usine et dans l'autre, de l'approvisionnement et du transport de copeaux vers les papetières. Le projet du transport de bois brut inter-usine cherche à développer un outil d'optimisation pour effectuer la planification du transport du bois brut entre les différentes étapes de production, soit le sciage, le séchage et le planage. Ce projet s'avère nécessaire en raison du contexte opérationnel de PFR, qui possède plusieurs petites usines avec des capacités différentes à chaque étape, demandant donc le transport de produits à différents moments. Le projet se restreint au territoire du Lac Saint-Jean, au Québec. Ce projet est complexe notamment en raison de la gestion des chargements; comme il s'agit de paquets de bois de toutes longueurs et dimensions, il n'est pas possible de simplement considérer une caractéristique physique pour remplir le camion. Les résultats sont prometteurs et proposent, outre une réduction significative du temps de planification, des gains allant de 1200 à 3000$ pour une période de deux semaines. Du côté du transport de copeaux, l'objectif est également de créer un outil d'optimisation, cette fois pour gérer l'approvisionnement en copeaux des papetières de PFR à travers la province de Québec. Ici, le défi est de considérer les recettes de productions aux papetières et d'assurer l'approvisionnement en tenant compte des différents mélanges d'essences aux scieries et les contraintes d'entreposage aux papetières. En raison de l'ampleur du réseau, les résultats sont significatifs, proposant des gains allant de 180 000 à 475 000$ pour une période de 4 semaines, en plus de faciliter la production de différents scénarios étudiant diverses hypothèses.