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 étudie un problème de localisation et de tournées de véhicules multi-périodes considérant un univers stochastique, plus connu sous l’intitulé « Problèmes Stochastiques de Localisation-Transport » (PSLT). Il est caractérisé par plusieurs modes de transport et plusieurs périodes de demandes générées par un processus stochastique et stationnaire. Nous voulons déterminer le nombre d’entrepôts requis afin de satisfaire aux demandes d’un ensemble de clients et leur localisation. De plus, la mission des entrepôts en termes du sous-ensemble de clients à servir, doit être précisée. Le problème est formulé comme un programme stochastique avec recours, et une approche heuristique et hiérarchique de résolution est proposée. Cette approche comprend une procédure de recherche Tabou, une formule approximant la longueur des routes et une procédure Clarke et Wright modifiée. Trois stratégies d’exploration dans le voisinage sont proposées et comparées entre elles sur de nombreux problèmes réalistes faisant partie d’un large plan d’expérience. / This thesis studies a Stochastic Location-Transportation Problem (SLTP) characterized by multiple transportation options, multiple demand periods and a stochastic stationary demand. We consider the determination of the number and location of the depots required to satisfy a set of customer’s demands, and the mission of these depots in terms of the subset of customers they must supply. The problem is formulated as a stochastic program with recourse, and a hierarchical heuristic solution approach is proposed. It incorporates a Tabu search procedure, an approximate route length formula, and a modified Clarke and Wright procedure. Three neighbourhood exploration strategies are proposed and compared with extensive experiments based on realistic problems.

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.

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.

Ces dernières années, le transport de marchandises est devenu un défi logistique à multiples facettes. L’immense volume de fret a considérablement augmenté le flux de marchandises dans tous les modes de transport. Malgré le rôle vital du transport de marchandises dans le développement économique, il a également des répercussions négatives sur l’environnement et la santé humaine. Dans les zones locales et régionales, une partie importante des livraisons de marchandises est transportée par camions, qui émettent une grande quantité de polluants. Le Transport routier de marchandises est un contributeur majeur aux émissions de gaz à effet de serre (GES) et à la consommation de carburant. Au Canada, les principaux réseaux routiers continuent de faire face à des problèmes de congestion. Pour réduire significativement l’impact des émissions de GES reliées au transport de marchandises sur l’environnement, de nouvelles stratégies de planification directement liées aux opérations de routage sont nécessaires aux niveaux opérationnel, environnemental et temporel. Dans les grandes zones urbaines, les camions doivent voyager à la vitesse imposée par la circulation. Les embouteillages ont des conséquences défavorables sur la vitesse, le temps de déplacement et les émissions de GES, notamment à certaines périodes de la journée. Cette variabilité de la vitesse dans le temps a un impact significatif sur le routage et la planification du transport. Dans une perspective plus large, notre recherche aborde les Problèmes de distribution temporels (Time-Dependent Distribution Problems – TDDP) en considérant des chemins dynamiques dans le temps et les émissions de GES. Considérant que la vitesse d’un véhicule varie en fonction de la congestion dans le temps, l’objectif est de minimiser la fonction de coût de transport total intégrant les coûts des conducteurs et des émissions de GES tout en respectant les contraintes de capacité et les restrictions de temps de service. En outre, les informations géographiques et de trafic peuvent être utilisées pour construire des multigraphes modélisant la flexibilité des chemins sur les grands réseaux routiers, en tant qu’extension du réseau classique des clients. Le réseau physique sous-jacent entre chaque paire de clients pour chaque expédition est explicitement considéré pour trouver des chemins de connexion. Les décisions de sélection de chemins complètent celles de routage, affectant le coût global, les émissions de GES, et le temps de parcours entre les nœuds. Alors que l’espace de recherche augmente, la résolution des Problèmes de distribution temporels prenant en compte les chemins dynamiques et les vitesses variables dans le temps offre une nouvelle possibilité d’améliorer l’efficacité des plans de transport... Mots clés : Routage dépendant du temps; chemins les plus rapides dépendant du temps; congestion; réseau routier; heuristique; émissions de gaz à effet de serre; modèles d’émission; apprentissage supervisé / In recent years, freight transportation has evolved into a multi-faceted logistics challenge. The immense volume of freight has considerably increased the flow of commodities in all transport modes. Despite the vital role of freight transportation in the economic development, it also negatively impacts both the environment and human health. At the local and regional areas, a significant portion of goods delivery is transported by trucks, which emit a large amount of pollutants. Road freight transportation is a major contributor to greenhouse gas (GHG) emissions and to fuel consumption. To reduce the significant impact of freight transportation emissions on environment, new alternative planning and coordination strategies directly related to routing and scheduling operations are required at the operational, environmental and temporal dimensions. In large urban areas, trucks must travel at the speed imposed by traffic, and congestion events have major adverse consequences on speed level, travel time and GHG emissions particularly at certain periods of day. This variability in speed over time has a significant impact on routing and scheduling. From a broader perspective, our research addresses Time-Dependent Distribution Problems (TDDPs) considering dynamic paths and GHG emissions. Considering that vehicle speeds vary according to time-dependent congestion, the goal is to minimize the total travel cost function incorporating driver and GHG emissions costs while respecting capacity constraints and service time restrictions. Further, geographical and traffic information can be used to construct a multigraph modeling path flexibility on large road networks, as an extension to the classical customers network. The underlying physical sub-network between each pair of customers for each shipment is explicitly considered to find connecting road paths. Path selection decisions complement routing ones, impacting the overall cost, GHG emissions, the travel time between nodes, and thus the set of a feasible time-dependent least cost paths. While the search space increases, solving TDDPs considering dynamic paths and time-varying speeds may provide a new scope for enhancing the effectiveness of route plans. One way to reduce emissions is to consider congestion and being able to route traffic around it. Accounting for and avoiding congested paths is possible as the required traffic data is available and, at the same time, has a great potential for both energy and cost savings. Hence, we perform a large empirical analysis of historical traffic and shipping data. Therefore, we introduce the Time-dependent Quickest Path Problem with Emission Minimization, in which the objective function comprises GHG emissions, driver and congestion costs. Travel costs are impacted by traffic due to changing congestion levels depending on the time of the day, vehicle types and carried load. We also develop time-dependent lower and upper bounds, which are both accurate and fast to compute. Computational experiments are performed on real-life instances that incorporate the variation of traffic throughout the day. We then study the quality of obtained paths considering time-varying speeds over the one based only on fixed speeds... Keywords : Time-dependent routing; time-dependent quickest paths; traffic congestion; road network; heuristic; greenhouse gas emissions; emission models; supervised learning.

Ce mémoire introduit une nouvelle variante aux problèmes de tournée de véhicules visant à prendre en considération la connaissance et l'expérience des livreurs dans le processus d'affectation aux clients. Ce nouveau type de tournée de véhicules basés sur l'expérience (EB-VRP) est motivé par le gain potentiel que pourrait apporter la familiarité des livreurs avec leur zone de travail, non seulement en termes de coûts de transports, mais également de satisfaction des livreurs. Cette approche pourrait également avoir pour corollaire une consommation ré- duite de carburant ainsi qu'une affectation non biaisée des livreurs aux clients. Pour traiter ce nouveau problème, une méthode de représentation de la connaissance construite à partir d'un historique de livraison est proposée. La résolution est ensuite effectuée par une approche bi-objectif combinée à une heuristique à grand voisinage. Des résultats numériques issus de données réelles viennent corroborer la pertinence de cette méthodologie. / This thesis introduces a new type of vehicle routing problem aiming to take into account the knowledge and experience for the driver-customer affectation process. This new experiencebased problem (EB-VRP) is motivated by the potential gain that could result from the ftting between drivers and their working areas in, in terms of global transportation costs and driver's satisfaction. This approach could also lead to a lower fuel consumption and an unbiased driver-customer affectation. A new methodology had been introduced to address this new problem, featuring a way to model the driver's knowledge based on a delivery's history. A bi-objective approach combines with a large-scale neighborhood heuristic had been used as a solving method. Numerical results from real data support the relevance of our methodology

Le but de ce travail de thèse réside dans la planification de la distribution urbaine des marchandises dans un système de transport collaboratif. Cette collaboration consiste à échanger les demandes de transport entre transporteurs afin d'améliorer l'efficacité de leurs opérations. Cela revient à minimiser la distance parcourue par les camions et à maximiser le profit collecté des clients, notamment en recourant à des variantes du problème de tournées de véhicules plus adaptées au contexte collaboratif. Le problème opérationnel sous-jacent est donc le problème de tournées de véhicules sélectives dans lequel le service de tous les clients n'est pas obligatoire par contre un "profit" est collecté lors du service d'un client. Dans cette thèse, nous traitons le problème de tournées de véhicules sélectives avec contraintes de temps et de capacité (Capacitated Team Orienteering Problem - CTOP). Nous proposons une métaheuristique qui alterne entre deux espaces de recherche. Des procédures de découpage optimal et de concaténation permettent de passer d'un espace à un autre. D'autre part, en considérant des demandes de collecte et de livraison, nous traitons deux variantes sélectives du problème de collecte et de livraison (Pickup and Delivery Problem - PDP) : le PDP avec fenêtres de temps et demandes obligatoires (PDPTWPR) et le PDPTWPR avec demandes groupées. La première variante consiste à choisir parmi les demandes de transport optionnelles quelles demandes à servir en plus des demandes obligatoires. Nous développons des métaheuristiques pour traiter les cas mono-objectif et multi-objectif du problème. Le PDPTWPR avec demandes groupées prend en considération les demandes de transport qui doivent être servies par un même transporteur. Finalement, nous considérons la variante sélective dans laquelle les marchandises sont distribuées d'un même dépôt vers les clients (Capacitated Profitable Tour Problem - CPTP). L'objectif est de maximiser la différence entre le coût et le profit. Pour résoudre ce problème, nous proposons un algorithme de résolution exacte basé sur la programmation linéaire en nombres entiers à laquelle nous ajoutons plusieurs inégalités valides spécifiques à ce problème. Des expérimentations ont été conduites sur plusieurs classes d'instances afin de montrer l'efficacité de nos approches. / The goal of this thesis is to plan urban freight distribution in a collaborative logistic system. The collaboration consists in exchanging transportation requests between carriers to increase the efficiency of their operations. More precisely, when solving variants of the wellknown vehicle's routing problems in collaborative context, less kilometers can be driven and higher prices can be collected. The underlying operational problem is therefore the selective vehicle routing problem in which not all customers can be served, but a "profit" is gained for each served one. In this thesis, we firstly address the Capacitated Team Orienteering Problem (CTOP), a selective variant of the VRP in which capacity and travel time limitations are imposed to vehicles. We propose a variable space search metaheuristic that alternates between two different search spaces to solve CTOP. Then, we consider pickup and delivery requests to study two variants of the selective pickup and delivery problem: the PDP with Time Windows and Reserved requests (PDPTWPR) and the Clustered PDPTWPR. The first aims to choose suitable selective requests to be transported in addition to reserved ones. Metaheuristics are proposed to deal with the single-objective and the multi-objective sides of the problem. The second takes into consideration groups of requests that must be served by only one carrier. Finally, we consider the Capacitated Profitable Tour Problem (CPTP) in which goods need to be distributed from the depot to customers. We propose an exact method based on Integer Linear Programming to solve this problem. A set of cuts specific to CPTP is proposed in order to speed up the solution process. Experiments were conducted on a variety of instances of different sizes to demonstrate the effectiveness of our solution methods.

Cette thèse a pour but d’apporter des solutions méthodologiques pour la mutualisation des transports entre les fournisseurs et les plateformes de la grande distribution. Cette mutualisation permet en effet de réduire les coûts, les émissions de CO2, et d’augmenter la qualité de service. Elle est organisée autour d’un réseau de plateformes de cross-docking appelées Centres de Routage Collaboratifs, développé par la société 4S Network. Nos travaux consistent à modéliser et résoudre à l’aide de techniques de recherche opérationnelle plusieurs problèmes d’optimisation du transport dans le réseau mutualisé. Le verrou scientifique majeur est de résoudre conjointement un problème de plan de chargement (Service Network Design Problem) dans un réseau logistique national, et des problèmes de tournées de véhicules à une échelle régionale. Nous prenons en compte des contraintes additionnelles issues du monde industriel et les tarifs réellement pratiqués par les transporteurs, notamment des coûts non linéaires.Les problèmes d’optimisation résultants sont résolus au moyen de méthodes ditesmatheuristiques, c’est-à-dire combinant des approches exactes telles que la génération de colonnes et des approches (méta)heuristiques telles que la recherche tabou. Les algorithmes développés dans cette thèse ont donné lieu à unoutil logiciel aujourd’hui en exploitation chez 4S Network. / The main purpose of this PhD. thesis is to provide methodological solutions for a collaborative transport between suppliers and retail platforms. The outcomes of this collaboration are numerous:cost reduction, greenhouse gas emission reduction and higher quality of service. The network is structured around cross-docking platforms developed by the company 4S Network. We model and solve several optimization problems in this collaborative network, using operationsresearch techniques. The major scientific challenge is to simultaneously solve a Service Network Design Problem in a national logistics network and several Vehicle Routing Problems at regional level. We consider additional constraints and prevailing pricing arising from the carriers, in particular non-linear costs. The resulting optimization problems are solved by matheuristic methods, that combine exact approaches as column generation and (meta)heuristic approaches as tabu search. The algorithms developed in this thesis are the core functions of a software tool developed for 4S network.

Nous nous intéressons dans cette thèse à la résolution du problème de tournées sélectives (Team Orienteering Problem - TOP) et ses variantes. Ce problème est une extension du problème de tournées de véhicules en imposan tcertaines limitations de ressources. Nous proposons un algorithme de résolution exacte basé sur la programmation linéaire en nombres entiers (PLNE) en ajoutant plusieurs inégalités valides capables d’accélérer la résolution. D’autre part, en considérant des périodes de travail strictes pour chaque véhicule durant sa tournée, nous traitons une des variantes du TOP qui est le problème de tournées sélectives multipériodique (multiperiod TOP - mTOP) pour lequel nous développons une métaheuristique basée sur l’optimisation par essaim pour le résoudre. Un découpage optimal est proposé pour extraire la solution optimale de chaque particule en considérant les tournées saturées et pseudo saturées .Finalement, afin de prendre en considération la disponibilité des clients, une fenêtre de temps est associée à chacun d’entre eux, durant laquelle ils doivent être servis. La variante qui en résulte est le problème de tournées sélectives avec fenêtres de temps (TOP with Time Windows - TOPTW). Deux algorithmes exacts sont proposés pour résoudre ce problème. Le premier est basé sur la génération de colonnes et le deuxième sur la PLNE à laquelle nous ajoutons plusieurs coupes spécifiques à ce problème. / We focus in this thesis on developing new algorithms to solve the Team Orienteering Problem (TOP) and two of its variants. This problem derives from the well-known vehicle routing problem by imposing some resource limitations .We propose an exact method based on Mixed Integer Linear Programming (MILP) to solve this problem by adding valid inequalities to speed up its solution process. Then, by considering strict working periods for each vehicle during its route, we treat one of the variants of TOP, which is the multi-period TOP (mTOP) for which we develop a metaheuristic based on the particle swarm optimization approach to solve it. An optimal split procedure is proposed to extract the optimal solution from each particle by considering saturated and pseudo-saturated routes. Finally, in order to take into consideration the availability of customers, a time window is associated with each of them, during which they must be served. The resulting variant is the TOP with Time Windows (TOPTW). Two exact algorithms are proposed to solve this problem. The first algorithm is based on column generation approach and the second one on the MILP to which we add additional cuts specific for this problem. The comparison between our exact and heuristic methods with the existing one in the literature shows the effectiveness of our approaches.