La planification tactique des opérations forêt-usines est centrée sur trois éléments principaux : la récolte, le transport et la transformation du bois. La planification de cette chaine d’approvisionnement est très complexe. Il existe déjà des outils pour faciliter la décision de décideur tels que FPInterface et Optitek, tous deux développés par FPInnovations. Cette mémoire vise à développer un module d’optimisation qui est connecté aux utiles de simulation. LogiOpt est constituée d'un modèle mathématique. Le modèle développé vise l’optimisation de la chaîne d’approvisionnement entre la forêt et l’usine en concentrant les efforts sur les activités que l’entreprise planifie conjointement avec son entrepreneur d’opérations forestières principal. Grâce à ces solutions de logiciels de simulation et de notre modèle mathématique, nous combinons à la fois dans notre cadre récolte, le transport, l'allocation des bois et des opérations de production. Pour tester notre model mathématique, nous avons utilisé les données d’une année d’exploitation à une entreprise québécoise œuvrant dans le milieu forestier. Nous avons comparé nos résultats avec un plan tactique manuel « simulé ». De ce fait, nous avons constaté que LogiOpt effectue une meilleure allocation de la matière première en allant récolter dans moins de blocs de récolte tout en utilisant des bois ayant un meilleur rendement en usine. Conséquemment, on produit plus de produits finis en usine tout en utilisant la même quantité de bois qu’un plan tactique plus traditionnel. / Forest and sawmills tactical planning is based on three main elements: wood harvesting, wood transportation and wood transformation. Planning the whole supply chain, is quite complex. Tools have been built to help manager in his decision process, for example FPInterface and Optitek, which were developed by FPInnovations. The aim of this thesis is to develop an optimization module, LogiOpt, which will be integrated to simulation tools. LogiOpt is made of a mathematical model. The developed model aims at optimizing the supply chain between the forest and the mills. Using simulation software solutions and our mathematical model, we combine at the same time in our framework harvesting, transportation, wood allocation and production operations. To test our mathematical model, we used data obtained from one business year of a Quebec based wood manufacturer. We compared our results with a manual simulated tactical plan. In this regard, we observed that LogiOpt performs better in wood allocation between sawmills, harvesting in less harvesting while using wood with better output. We then end up producing more finished products at sawmills using the same wood quantity as a traditional tactical plan.

Reproduction de : Thèse de doctorat : Informatique : Lille 1 : 2004. / N° d'ordre (Lille 1) : 3514. Résumé en français et en anglais. Titre provenant de la page de titre du document numérisé. Bibliogr. p. [149]-160.

Face à une concurrence féroce par suite de la modélisation économique, les entreprises doivent bien gérer leurs chaînes logistiques afin de réduire leurs coûts d’exploitation tout en améliorant leurs services au client. Un enjeu majeur de cette gestion et la gestion efficace des stocks multi-échelons. Dans cette thèse, nous étudions des systèmes de stocks multi-échelons avec des coûts de passation de commande à chaque stock. En raison de l’existence des coûts de passation de commande, l’optimisation d’un tel système devient très compliquée. Récemment, l’approche de service garanti (GSA) a été utilisée pour déterminer les stocks de sécurité pour les systèmes de stocks multi-échelons, mais sans coûts fixes de passation de commande. Nous généralisons la GSA pour optimiser la politique de stockage (R, Q) d’un système de stocks multi-échelons avec la demande suivant un processus de Poisson et coûts fixes de passation de commande à chaque stock. Nous considérons trois types de systèmes de stocks multi-échelons, et pour chaque type, nous d'abord établissons un modèle mathématique pour le problème d’optimisation. Ensuite, le modèle est résolu par une procédure itérative fondée sur deux algorithmes de programmation dynamique (DP). Un algorithme DP est utilisé pour résoudre le sous-problème de détermination de quantités de commande et l'autre est utilisé pour résoudre le sous-problème de détermination de points de recommande du modèle. Les résultats numériques démontrent l'efficacité des algorithmes et de la procédure / With the increasing complexity of supply chains led by economic globalization, integrated supply chain management has become an important strategy utilized by the firms to reduce the overall cost while meeting the customer service. This change has made academic researchers and industrial practitioners pay more and more attention to multi-echelon inventory management over the last two decades. In this thesis, we study multi-echelon inventory systems with fixed order costs at each stock. Because of the existence of fixed order costs, the optimization of such system becomes very complicated. Recently, Guaranteed Service Approach (GSA) was used to set safety stock for multi-echelon inventory systems, but without fixed order costs. We extend the GSA to optimize (R, Q) inventory policies for multi-echelon inventory systems with Poisson demand and fixed order costs. Our objective is to find optimal (R, Q) policy for such a system so that its total cost is minimized while achieving a service level to customer. Three types of multi-echelon inventory systems, serial systems, assembly systems and two-level distribution systems are considered. For each type, we first establish a mathematical model for the optimization problem. Then, the model is solved by an iterative procedure based on two dynamic programming (DP) algorithms. One DP algorithm is used to solve the order size decision subproblem and the other is used to solve the reorder point decision subproblem of the model. Numerical experiments demonstrate the efficiency of the algorithms and the procedure

Ce projet de recherche s’inscrit dans un partenariat entre l’ANDRA (Agence Nationale pour la gestion des Déchets Radioactifs) et le LOSI de l’Institut Charles Delaunay (STMR UMR CNRS), UTT.La thèse vise à dimensionner les ouvrages de stockage vis-à-vis des divers flux industriels. Les flux concernés sont de nature variée et cela constitue l’une des caractéristiques du stockage. Les ouvrages doivent en effet être conçus pour permettre un développement progressif, à l’origine d’une coexistence de flux nucléaires (les colis de déchets nucléaires et les flux associés, telle la ventilation nucléaire) et de flux de chantiers conventionnels. Le dimensionnement des flux et la conception des ouvrages pour autoriser ces flux se trouvent donc au cœur du processus de conception du stockage.La problématique de notre partenaire industriel porte sur la conception de réseau (appelé flow path design). Notre contribution est dédiée au développement de modèles de flow path design avec de nouvelles contraintes ainsi qu’au développement de méthodes. Les extensions au modèle de base prennent en compte une flotte hétérogène, des segments interdits d’accès à certains véhicules et des coûts de construction. Différentes méthodes d'optimisation approchées ont aussi été développées et testées. Il s’agit de métaheuristiques basées sur les recherches locales, l’algorithme de colonies de fourmis ainsi que l’algorithme des abeilles. L’efficacité des méthodes est prouvée grâce à des tests sur des instances de la littérature et l’application au cas réel est faite par simulation / This research project is part of a partnership between ANDRA (National Agency for Radioactive Waste Management) and the LOSI, Institut Charles Delaunay (TSR UMR CNRS), UTT.The thesis aims to design the storage structures for various industrial flows. Flows involved are varied in nature and it is one of the characteristics of the storage. The works must be designed to effect a gradual development, from a "coactivity", that is to say, a coexistence of nuclear flux (the nuclear waste packages and the associated flow, such nuclear ventilation) and conventional flow sites. The design flow and the design of structures to allow these flows are therefore at the heart of the design process of storage.The problem of our industrial partner focuses on flow path design. Our contribution is dedicated to the development of models of flow path design with new constraints and the development of methods. Extensions to the basic model takes into account different type of vehicle, not allowed some segments and taking into account construction costs. Different optimization methods have also been developed and tested. Metaheuristics are based on local search, the ant colony algorithm and the algorithm of bees. Efficiency of methods is demonstrated through tests on literature benchmarks and application to the real case is done by simulation

Cette thèse considère le problème consistant à intégrer les décisions de routage et stockage lors de la conception de la chaîne logistique. Le but est de sélectionner des dépôts parmi un ensemble de candidats pour desservir un ensemble de détaillants à l’aide d’une flotte de véhicules de capacité permettant visiter plus d’un détaillant par route. On cherche à déterminer la localisation de ces dépôts et les tournées des véhicules afin de maintenir leurs niveaux optimaux de stocks. La demande chez les détaillants est connue à l’avance. Des applications dans les domaines de la logistique humanitaire et militaire sont envisageables. Pour résoudre le problème, deux matheuristiques sont proposées. Dans la première partie, une méthode coopérative qui combine des méthodes exactes pour le problème de conception de la chaîne logistique et des méthodes heuristiques de routage est présentée. Dans la deuxième partie, une méthode de décomposition utilisant une réformulation de Dantzig-Wolf sur les variables de routage est proposée. L’algorithme intègre les concepts de génération de colonnes, relaxation lagrangienne et recherche locale. Les résultats montrent la capacité des algorithmes à trouver des solutions de bonne qualité et nous estimons de façon empirique l’impact de considérer un modèle intégré au lieu d’utiliser une méthode d’optimisation séquentielle. De plus, les résultats des méthodes présentées sur des sous-problèmes sont aussi étudiés. Ces sont: le problème de localisation-routage, le problème de tournées avec gestion de stocks, et le problème de plus court chemin généralisé / The problem of designing a supply chain including simultaneously routing and inventory management decisions is studied in this thesis. The objective is to select a subset of depots to open, the inventory policies for a 2-echelon system, and the set of routes to perform distribution from the upper echelon to the next using a homogeneous fleet of vehicles over a finite planning horizon. Demand is considered to be known. Applications are found in humanitarian logistics and military logistics. To solve the problem, two matheuristic procedures are developed. On the first part a cooperative algorithm combining exact methods for the supply chain design problem and routing heuristics is presented. On the second part, a partition is proposed using a Dantzig-Wolf reformulation on the routing variables. An hybridization between column generation, Lagrangian relaxation and local search is proposed in this part, put together as a heuristic method. Furthermore, results demonstrate the capability of the algorithms to compute high quality solutions and empirically estimate the improvement in the cost function of the proposed model when compared to a sequential optimization approach. Furthermore, results of the proposed methodologies on benchmark instances for subproblems are studied as well. Those are the capacitated location-routing problem, the inventory-routing problem, and the generalized elementary shortest path problem

Les travaux de cette thèse concernent la résolution d'un problème de planification dans un réseau de distribution à deux échelons intégrant la gestion de stocks de produits périssables, le dimensionnement de lots, des alternatives d'approvisionnement. La livraison s'effectue directement entre un fournisseur et son client, sans tournée avec une flotte homogène de véhicules. Nous proposons un programme linéaire mixte, une heuristique constructive (déterministe) et une heuristique réactive randomisée. Pour certaines instances, le solveur de programme linéaire mixte ne fournit pas une bonne solution réalisable dans la limite de temps définie ou prend beaucoup de temps. Les heuristiques proposées sont rapides mais ne donnent pas de bonnes solutions pour certaines instances. Pour améliorer la qualité des solutions des heuristiques, la descente à voisinage variable (VND), la recherche locale itérative (ILS) et la recherche locale itérative à démarrages multiples (MS-ILS) sont développées.Toutes ces méthodes ont été incluses dans un APS (Advanced Planning System) et sont comparées avec CPLEX sur des instances extraites de bases de données réelles. Un générateur aléatoire d'instances est conçu pour plus de diversité pour les tests. Une relaxation lagrangienne est implémentée pour comparer les solutions des instances, pour lesquelles CPLEX ne fournit pas une bonne solution réalisable dans le temps imparti, avec les autres méthodes. Une heuristique lagrangienne, utilisant la relaxation lagrangienne et une heuristique de réparation, est également développée / This work presents a planning problem in a distribution network incorporating two levels inventory management of perishable products, lot-sizing, multi-sourcing and transport capacity with a homogeneous fleet of vehicles. A mixed integer linear programming (MILP) a greedy heuristic and a reactive randomized heuristic are developed to solve this real planning problem. There are some instances for which the solver CPLEX cannot give a good upper bound within the limited time and for other instances it takes a lot of time to solve MILP. The heuristics are alternatives to the mixed integer linear program to quickly solve some large instances taking into account original and difficult constraints. For some instances the gap between the solutions of the solver (MILP) and the heuristics becomes quite significant. The variable neighborhood descent (VND), the iterated local search (ILS) and the multi-start iterated local search (MS-ILS) are implemented. These methods are included in an APS (Advanced Planning System) and compared with a MILP solver. The instances are derived from actual data or built using a random generator of instances to have wider diversity for computational evaluation. A lagrangian relaxation is developed to compare the solutions of the instances, for which CPLEX cannot give a good upper bound within the limited time, with the other methods (greedy heuristic, VND, ILS and MS-ILS). A lagrangian heuristic is proposed; the solution of lagrangian relaxation is used to build a feasible solution with a repair heuristic

Ce mémoire traite un problème de sélection des transporteurs à un niveau opérationnel de la hiérarchie de décision, d'un système de trafic constitué de trois flottes de transporteurs (interne, externe et spot), plusieurs entrepôts, plusieurs centres de distributions et plusieurs produits. Les demandes de produits sont considérées aléatoires et les transporteurs des flottes, interne et externe, sont sujets à des périodes de non-disponibilités. Pour permettre de suivre l'évolution du système dans le temps, la politique de sélection devrait inclure une stratégie d'affectation des quantités transférées en fonction de l'état du système. Les transporteurs externes proviennent d'un processus de sélection au niveau stratégique. Les transporteurs spots sont appelés du marché au comptant. Dans la première partie de ce mémoire, un cadre conceptuel est proposé permettant de raccorder les décisions de sélection prises au niveau stratégique et opérationnel. La sélection stratégique utilise un mécanisme d'enchères combinatoires dans lequel les transporteurs se mettent en concurrence en soumettant des mises en paquet sur les offres proposées par les expéditeurs. Un modèle mathématique mixte en nombres entiers est exposé pour déterminer les transporteurs gagnants de l'enchère avec lesquels l'expéditeur va s'engager sur une longue période. Les transporteurs gagnants de cette phase seront regroupés dans une seule flotte, appelée flotte externe. Dans la deuxième partie du projet, le problème de sélection des transporteurs, qui traite le cas d'une chaîne logistique simple, constituée d'un seul entrepôt, un seul centre de distribution, un seul produit et les trois flottes des transporteurs, est abordé. De ce fait, une formulation en programmation dynamique stochastique du problème est développée. Une résolution numérique est menée par la suite pour résoudre les équations d'optimalité obtenues. Pour illustrer l'utilité pratique et le comportement robuste de la politique développée, plusieurs analyses de sensibilité sont effectuées. Cette politique combine les deux aspects : la sélection des transporteurs et le contrôle des inventaires dans les centres de distribution. Par la suite, une approche expérimentale basée sur la simulation et des techniques d'optimisation statistiques est adoptée, en vue de valider, quantifier et optimiser la structure de la politique obtenue par modélisation mathématique. Une comparaison statistique est par la suite menée permettant de montrer la supériorité de la politique paramétrée développée par rapport à une autre politique basée principalement sur les coûts du transport comme critères de sélection. Finalement, une politique générale est proposée permettant de résoudre le problème de sélection des transporteurs à la phase opérationnelle de la hiérarchie. Cette politique est basée sur la structure globale de la politique développée du cas simple dans la deuxième partie du projet. Elle est appliquée dans un cadre plus représentatif de la réalité. Une comparaison statistique est par la suite menée montrant les gains que la politique générale proposée occasionnent par rapport à une autre politique générale visant un minimum de stock dans les centres de distribution et un coût de transport réduit. Plusieurs interprétations ont été dégagées à travers cette étude.

La planification de l'approvisionnement de matière ligneuse en forêt publique québécoise représente un cas complexe de chaîne d'approvisionnement divergente (Alayet et al., 2015). Les clients de cette chaîne peuvent être nombreux. Ils participent à la planification en interagissant avec le ministère des Forêts, de la Faune et des Parcs (MFFP) qui est le fournisseur des plans de récolte. Les clients interagissent aussi entre eux afin de coordonner les activités menant à la livraison des différents produits d'un peuplement ou d'un arbre à différentes usines. De manière générale et plus particulièrement dans le contexte à l'étude, l'alignement des objectifs et capacités des parties prenantes de la planification est un des principaux facteurs de succès de la chaîne d'approvisionnement (Lee, 2004; Gunn, 2005; Simatupang et Sridharan, 2005; Fawcett et al., 2008; Cao et Zhang, 2013, Wong et al., 2012). L'alignement représente l'adéquation, en termes d'objectifs, de structures et de processus à l'interne et entre les différentes fonctions et parties prenantes d'une chaîne d'approvisionnement (Wong et al., 2012). Au Québec, on observe une inadéquation historique entre l'offre et la demande, 30 % ou plus de la possibilité forestière annuelle totale de la forêt publique n'étant pas récoltée. De plus, les stratégies d'aménagement menant aux calculs des possibilités forestières ne prennent peu ou pas en compte les aspects économiques, ce qui se traduit par une insatisfaction des clients industriels quant à la valeur générée par les plans d'approvisionnement. Enfin, des parties prenantes à la planification manifestent de l'insatisfaction à l'égard du processus de planification et de la valeur des plans (Gharbi, 2014). La première partie de cette recherche, qui consiste en une étude de cas descriptive, a pour objectif de vérifier s'il y a un manque d'alignement en étudiant le processus de planification actuel et ses mécanismes d'alignement. Le processus est comparé à un cadre conceptuel de référence développé à partir des concepts théoriques recueillis dans la littérature et des principales composantes du modèle SCOR (Supply Chain Organizational Reference) du Supply Chain Council. Des sondages et entrevues auprès de planificateurs forestiers ont permis de cartographier, de décrire et d'interpréter le processus, et d'établir des concordances et discordances avec le cadre conceptuel. Bien que plusieurs sous-processus soient définis de manière exhaustive par le MFFP, l'étude démontre que l'organisation du processus de planification n'est pas clairement définie. Les rôles, responsabilités et tâches sont fractionnés et exécutés en silos, ce qui limite l'intégration des capacités des parties prenantes. La décomposition hiérarchique de la planification n'est pas conforme avec les conventions scientifiques, entraînant des incohérences entre les niveaux de planification et des difficultés de compréhension et de communication entre les parties prenantes. Les objectifs de production et d'approvisionnement ne sont pas suffisamment clairs et définis. Enfin, l'utilisation d'indicateurs et des tableaux de bord n'est pas généralisée, ce qui ne facilite pas la collaboration, l'adaptation et l'ajustement. Ainsi, les mécanismes de rétroaction et de mesure de la performance sont déficients. La démarche a permis de vérifier qu'il existe un manque d'alignement. Elle a également permis d'identifier les principaux facteurs qui contribuent au manque d'alignement. La seconde partie de cette recherche a pour objectif de proposer et de tester un processus de planification de niveau stratégique axé sur l'alignement des objectifs et des capacités de planification des approvisionnements de matière ligneuse à partir des principes du cadre conceptuel retenu. Un projet a été mené en mode de recherche-action. Les parties prenantes de la planification ont été invitées à participer à l'élaboration d'une stratégie régionale de production de bois (SRPB). Un processus mettant de l'avant les principes d'alignement des objectifs et capacités leur a été proposé. Cette démarche démontre qu'il est possible d'accroître la satisfaction des parties prenantes à l'égard du processus de planification en favorisant l'alignement des objectifs et capacités, ce qui répond à la question de recherche. Bien que le projet (SRPB) n'aborde que le niveau stratégique de la planification des approvisionnements de matière ligneuse en forêt publique québécoise, nous croyons que les résultats de cette recherche, notamment le cadre conceptuel supportant la configuration d'un processus, sont transférables aux échelles de planification tactique et opérationnelle ainsi qu'à d'autres contextes régionaux du Québec et d'ailleurs. Nous croyons également que ces résultats peuvent inspirer des démarches de configuration de systèmes et de processus de planification dans d'autres domaines où la planification des approvisionnements fait intervenir plusieurs parties prenantes. Ce projet de recherche contribue à combler le vide constaté dans la littérature concernant le domaine de l'alignement des objectifs et capacités en matière de processus de planification de l'approvisionnement de matière ligneuse. / Planning for timber supply in Quebec's public forests represents a complex case of a divergent supply chain (Alayet and al., 2015). The customers of this chain can be numerous. They participate in planning by interacting with the Ministry of Forests, Wildlife and Parks (MFFP) which is the supplier of the plans. Customers also interact with each other to coordinate activities leading to the delivery of different products from a stand or tree to different factories. In general and more particularly in the context under study, alignment of objectives and capacities of stakeholders participating in planning is one of the main factors of success in the supply chain (Lee, 2004; Gunn, 2005; Simatupang and Sridharan, 2005; Fawcett and al., 2008; Cao and Zhang, 2013, Wong and al., 2012). Alignment represents the fit, in terms of objectives, structures and processes internally and between the different functions and stakeholders of a supply chain (Wong and al., 2012). In Quebec, potential timber supply and harvested timber show a historical inadequacy, with 30 % or more of the total annual allowable cut of the public forest not being harvested. In addition, the management strategies leading to the allowable cut calculations take little or no account of the economic aspects, which results in dissatisfaction of industrial customers with the value generated by the supply plans. Finally, planning stakeholders express dissatisfaction with the planning process and the value of plans (Gharbi, 2014). The first part of this research, which consists of a descriptive case study, aims to verify if there is a lack of alignment by studying the current planning process and its alignment mechanisms. The process is compared to a conceptual reference framework developed from theoretical concepts collected in the literature and from the main components of the Supply Chain Council's Supply Chain Organizational Reference model (SCOR). Surveys and interviews with forest planners helped to map, describe and interpret the process, and establish concordances and disagreements with the conceptual framework. Although several sub-processes are comprehensively defined by the MFFP, the study shows that the organization of the planning process is not clearly defined. Roles, responsibilities and tasks are broken down and executed in silos rather than fostering the integration of stakeholder capacities. The hierarchical breakdown of planning does not conform to scientific conventions, leading to inconsistencies between planning levels and difficulties in understanding and communicating among stakeholders. The production and supply objectives are not sufficiently clear and defined. Finally, the use of indicators and dashboards is not widespread, which does not facilitate collaboration, adaptation and adjustment. Thus, the feedback and performance measurement mechanisms are deficient. This research allowed us to verify that there is a lack of alignment and identify the main factors involved. The second part of this research aims to propose and test a strategic level planning process focused on the alignment of objectives and planning capacities for woody material supplies from the principles of the conceptual framework adopted. A project was carried out in action research mode. Planning stakeholders were invited to participate in the development of a Regional Timber Production Strategy (SRPB). They were offered a process that put forward principles for aligning objectives and capacities. This approach demonstrates that it is possible to increase stakeholder satisfaction with the planning process by promoting alignment of goals and capabilities, which answers the research question. Although the project (SRPB) only addresses the strategic level of planning woody material supplies in Quebec public forests, we believe that the results of this research, specifically the conceptual framework supporting the configuration of a process, are transferable at the tactical and operational planning scales as well as in other regional contexts in Quebec and elsewhere. We also believe that these findings may inspire approaches to configuring systems and planning processes in other areas where supply planning involves multiple stakeholders. This research project contributes to filling the gap noted in the literature concerning the field of alignment of objectives and capacities in the planning process of the woody material supply.

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

Le problème de tournées de véhicules (Vehicle routing problem - VRP), introduit il y a plus de 60 ans, demeure au cœur des systèmes de transport. Après des décennies de développement, le VRP, par son ensemble très riche de variantes, représente l'un des problèmes les plus étudiés dans la littérature. Pourtant, en raison du manque de données, deux hypothèses importantes font que le VRP ne s'adapte pas efficacement au trafic et à la congestion, deux éléments importants pour modéliser de façon réelle des problèmes pratiques. Une première hypothèse considère que la vitesse de déplacement est constante dans le temps. La seconde, considère que chaque paire de nœuds (clients) n'est reliée que par un arc, ignorant le réseau routier implicite (sous-jacent). La congestion de la circulation est l'un des plus grands défis des systèmes de transport. Ces systèmes étant directement affectés par la congestion, l'ensemble de la chaîne d'approvisionnement doit s'adapter à ce facteur, ce qui n'est pas simple. La croissance continue du fret au cours des dernières années aggrave encore la situation et une attention renouvelée à la mobilité, à l'environnement et à la logistique urbaine a mis en lumière ces questions. Récemment, les avancées technologiques en communication et en acquisition de données en temps réel ont permis de collecter plusieurs informations sur les véhicules telles que leur localisation, leur accélération, leur vitesse, leur décélération, etc. Ainsi, nous pouvons remettre en question la façon dont nous définissons, modélisons et résolvons les problèmes de transport. Ceci nous permet de surmonter les deux hypothèses mentionnées en intégrant non seulement les informations relatives à la congestion, mais aussi en considérant l'ensemble du réseau routier. Dans cette thèse nous considérons l'ensemble du réseau routier sous-jacent, ce qui signifie que nous avons les nœuds clients mais également tous les nœuds intermédiaires qui constituent ce réseau. Ensuite, nous modélisons le temps de trajet de chaque route individuellement au cours de la journée. En divisant une journée en petits intervalles, jusqu'à une précision de l'ordre de la seconde, nous prenons en considération des informations précises sur le trafic. Il en résulte un nouveau problème appelé le problème de tournées de véhicules à plus court chemin avec dépendance du temps (Time-dependant shortest path vehicle routing problem - TD-SPVRP), dans lequel nous combinons le problème du plus court chemin avec dépendance du temps et le VRP avec dépendance du temps, créant ainsi un problème plus général et très complexe. Le TD-SPVRP est plus proche des conditions réelles et il constitue le sujet du chapitre 2 où nous le formulons comme un modèle de programmation linéaire en nombres entiers mixtes et concevons une heuristique rapide et efficace pour le résoudre. Nous testons le modèle ainsi que l'heuristique sur des instances générées à partir de données réelles de circulation sur le réseau routier de la ville de Québec, Canada. Les résultats montrent que l'heuristique fournit des solutions de haute qualité avec un écart moyen de 5,66% par rapport aux bornes inférieures déterminées par le modèle. Cependant, le modèle mathématique ne parvient pas à trouver aucune solution pour les instances de données réelles. Pour pouvoir résoudre ce problème complexe, une grande attention a été portée à la performance de l'implantation des algorithmes proposés afin d'améliorer leur rapidité en termes de temps d'exécution. Le problème reste très compliqué, surtout lorsque nous considérons une grande partie du réseau routier sous-jacent avec des données de trafic très précises. Pour cela, nous avons utilisé différentes techniques pour optimiser l'effort de calcul afin de résoudre le problème en évaluant l'impact engendré sur la précision tout en évitant la perte de précieuses informations. Nous avons développé deux types d'agrégation de données couvrant deux niveaux d'information différents. Premièrement, nous avons manipulé la structure du réseau en réduisant sa taille, et deuxièmement en contrôlant le niveau d'agrégation temporel pour générer les données de trafic et pour déterminer la vitesse d'un véhicule à tout moment. Pour la structure du réseau, nous avons utilisé différentes techniques de réduction de graphe pour en réduire la taille. Nous avons étudié la valeur et le compromis de l'information spatiale. Les solutions générées en utilisant le graphe réduit sont analysées dans le Chapitre 3 pour évaluer la qualité et la perte d'information dû à la réduction. Cette analyse démontre également que la transformation classique du TD-SPVRP en un problème de tournées dépendant du temps (Time-dependant VRP - TD-VRP) équivalent résulte en un graphe plus grand qui nécessite un temps de traitement important ce qui a un impact sur la qualité de la solution. Notre développement montre que la résolution du TD-SPVRP nécessite en moyenne 1445 secondes tandis que la résolution du TD-VRP associé nécessite 41 181 secondes. Garder un haut niveau de précision et réussir à réduire la taille du graphe est possible. En particulier, deux procédures de réduction ont été développées, la réduction des nœuds et la réduction des arcs parallèles. Les deux techniques réduisent la taille du graphe. La réduction des nœuds conduit à une amélioration de 1,11%, la réduction des arcs parallèles donne un écart de 2,57% signifiant la présence d'une distorsion dans le graphe réduit. En ce qui concerne les informations sur le trafic, nous avons analysé les compromis entre une grande quantité de données très précises et un plus petit volume de données agrégées avec une perte potentielle d'information. Ceci est fait en analysant la précision des données agrégées sous différents modèles de détermination des temps de parcours. Ces approches sont présentées dans le Chapitre 4. Au niveau de la prévision des temps de parcours, il est important que chaque segment routier ait des observations de vitesse pour chaque intervalle de temps considéré, ce que nous appelons le niveau de couverture du réseau. Notre analyse indique qu'une couverture complète du réseau routier à tout moment de la journée est nécessaire pour atteindre un niveau de précision élevé. Le recours à une agrégation élevée (de grands intervalles de temps) permet de réduire la taille du problème et d'obtenir une meilleure couverture des données, mais au prix d'une perte d'information. Les modèles analysés, LTM (link travel mode) et FSM (flow speed model), partagent les mêmes performances lorsqu'on utilise un grand intervalle de temps (120, 300 et 600 secondes), donc un niveau d'agrégation plus élevé, avec un écart moyen absolu de 5,5% par rapport aux temps de parcours observés. Cependant, avec une courte période (1, 10, 30 et 60 secondes), FSM fonctionne mieux que LTM. Pour un intervalle d'une seconde, FSM donne un écart absolu moyen de 6,70%, tandis que LTM fournit un écart de 11,17%. Ce chapitre détermine ainsi sous quelles conditions les modèles d'estimation de temps de parcours fonctionnent bien et procurent des estimations fidèles des temps de parcours réalisés. Cette thèse est structurée de la manière suivante. À la suite d'une introduction générale dans laquelle nous présentons le cadre conceptuel de la thèse et son organisation, le Chapitre 1 présente une revue de la littérature pour les deux problèmes fondamentaux étudiés, le problème de plus court chemin (Shortest path problem - SPP) et le VRP et leurs variantes développées au cours des années. Le Chapitre 2 introduit une nouvelle variante du VRP, le TD-SPVRP. Le Chapitre 3 présente les différentes techniques développées pour réduire la taille du réseau en manipulant les informations spatiales du réseau routier. L'impact de ces réductions est évalué et analysé sur des instances réelles en utilisant plusieurs heuristiques. Le Chapitre 4 traite l'impact de l'agrégation des données temporelle et des modèles d'évaluation des temps de parcours. Le dernier chapitre constitue une conclusion et ouvre des perspectives de recherche relatives à nos travaux. / The vehicle routing problem (VRP), introduced more than 60 years ago, is at the core of transportation systems. With decades of development, the VRP is one of the most studied problems in the literature, with a very rich set of variants. Yet, primarily due to the lack of data, two critical assumptions make the VRP fail to adapt effectively to traffic and congestion. The first assumption considers that the travel speed is constant over time ; the second, that each pair of customers is connected by an arc, ignoring the underlying street network. Traffic congestion is one of the biggest challenges in transportation systems. As traffic directly affects transportation activities, the whole supply chain needs to adjust to this factor. The continuous growth of freight in recent years worsens the situation, and a renewed focus on mobility, environment, and city logistics has shed light on these issues. Recently, advances in communications and real-time data acquisition technologies have made it possible to collect vehicle data such as their location, acceleration, driving speed, deceleration, etc. With the availability of this data, one can question the way we define, model, and solve transportation problems. This allows us to overcome the two issues indicated before and integrate congestion information and the whole underlying street network. We start by considering the whole underlying street network, which means we have customer nodes and intermediate nodes that constitute the street network. Then, we model the travel time of each street during the day. By dividing the day into small intervals, up to a precision of a second, we consider precise traffic information. This results in a new problem called the time-dependent shortest path vehicle routing problem (TD-SPVRP), in which we combine the time-dependent shortest path problem (TD-SPP) and the time-dependent VRP (TD-VRP), creating a more general and very challenging problem. The TD-SPVRP is closer to what can be found in real-world conditions, and it constitutes the topic of Chapter 2, where we formulate it as a mixed-integer linear programming model and design a fast and efficient heuristic algorithm to solve this problem. We test it on instances generated from actual traffic data from the road network in Québec City, Canada. Results show that the heuristic provides high-quality solutions with an average gap of only 5.66%, while the mathematical model fails to find a solution for any real instance. To solve the challenging problem, we emphasize the importance of a high-performance implementation to improve the speed and the execution time of the algorithms. Still, the problem is huge especially when we work on a large area of the underlying street network alongside very precise traffic data. To this end, we use different techniques to optimize the computational effort to solve the problem while assessing the impact on the precision to avoid the loss of valuable information. Two types of data aggregation are developed, covering two different levels of information. First, we manipulated the structure of the network by reducing its size, and second by controlling the time aggregation level to generate the traffic data, thus the data used to determine the speed of a vehicle at any time. For the network structure, we used different reduction techniques of the road graph to reduce its size. We studied the value and the trade-off of spatial information. Solutions generated using the reduced graph are analyzed in Chapter 3 to evaluate the quality and the loss of information from the reduction. We show that the transformation of the TD-SPVRP into an equivalent TD-VRP results in a large graph that requires significant preprocessing time, which impacts the solution quality. Our development shows that solving the TD-SPVRP is about 40 times faster than solving the related TD-VRP. Keeping a high level of precision and successfully reducing the size of the graph is possible. In particular, we develop two reduction procedures, node reduction and parallel arc reduction. Both techniques reduce the size of the graph, with different results. While the node reduction leads to improved reduction in the gap of 1.11%, the parallel arc reduction gives a gap of 2.57% indicating a distortion in the reduced graph. We analyzed the compromises regarding the traffic information, between a massive amount of very precise data or a smaller volume of aggregated data with some potential information loss. This is done while analyzing the precision of the aggregated data under different travel time models, and these developments appear in Chapter 4. Our analysis indicates that a full coverage of the street network at any time of the day is required to achieve a high level of coverage. Using high aggregation will result in a smaller problem with better data coverage but at the cost of a loss of information. We analyzed two travel time estimation models, the link travel model (LTM) and the flow speed model (FSM). They both shared the same performance when working with large intervals of time (120, 300, and 600 seconds), thus a higher level of aggregation, with an absolute average gap of 5.5% to the observed route travel time. With short periods (1, 10, 30, and 60 seconds), FSM performs better than LTM. For 1 second interval, FSM gives an average absolute gap of 6.70%, while LTM provides a gap of 11.17%. This thesis is structured as follows. After a general introduction in which we present the conceptual framework of the thesis and its organization, Chapter 1 presents the literature review for the two main problems of our development, the shortest path problem (SPP) and the VRP, and their time-dependent variants developed over the years. Chapter 2 introduces a new VRP variant, the TD-SPVRP. Chapter 3 presents the different techniques developed to reduce the size of the network by manipulating spatial information of the road network. The impact of these reductions is evaluated and analyzed on real data instances using multiple heuristics. Chapter 4 covers the impact of time aggregation data and travel time models when computing travel times on the precision of their estimations against observed travel times. The conclusion follows in the last chapter and presents some research perspectives for our works.