Cette thèse propose une modélisation des interactions entre le Transport de Marchandises en Ville (TMV) et la dynamique du trafic. Ces deux composantes, pourtant imbriquées, ne sont que très rarement étudiées simultanément. Plus précisément, cette thèse investigue les impacts du TMV sur les états de trafic ; et inversement, les impacts des états de trafic sur le TMV. Les recherches s’articulent autour de deux axes : le TMV à l’échelle (i) de la livraison et (ii) de la tournée de livraison, et la dynamique du trafic à l’échelle (iii) d’un jour et (iv) d’un catalogue de jours. (i) Le TMV réalisé par des véhicules routiers peut engendrer des formes de congestion, et par conséquent des nuisances sonores et atmosphériques. Néanmoins, il s’agit d’un « mal nécessaire » car le transport de ces marchandises est essentiel pour l’économie des villes. Une pratique courante est la livraison en double file. Ces « stationnements sauvages » réduisent l’écoulement des véhicules dans le réseau de transport. Une étude de sensibilité quantitative en simulation microscopique met en lumière une dégradation significative des états de trafic sur un boulevard urbain à partir d’un faible nombre de stationnements en double file. Ces phénomènes locaux et temporaires semblent essentiels à intégrer dans les simulations du trafic afin d’étudier au mieux les performances globales du système de transport. (ii) Les tournées de livraison planifiées peuvent être améliorées par l’intégration des conditions de circulation. Les algorithmes existants d’optimisation de tournées se basent sur une certaine qualité et quantité de données. Nous investiguons l’influence de plusieurs niveaux de granularité d’information du trafic sur l’ordonnancement optimale des tournées. De plus, nous comparons les temps de parcours estimés par les algorithmes, et les temps de parcours effectifs estimés à l’aide d’une simulation microscopique. Les états de trafic attendus peuvent être sujets à quelques variations. Nous proposons une méthodologie de génération de tournées intégrant de l’incertitude dans la dynamique du trafic. (iii) À l’échelle de la ville, les états de trafic sont naturellement variables, que ce soit dans l’espace ou au cours du temps. Le partitionnement permet de découper un réseau de transport en zones homogènes. Une zone est définie par un ensemble de liens connectés ayant des conditions de circulation similaires. Nous proposons une approche spatio-temporelle définissant des zones en 3 Dimensions (3D). L’idée est de résumer la majeure partie de la dynamique du trafic d’une ville en utilisant peu d’information : la vitesse moyenne par zone spatio-temporelle. Deux familles de méthodes de clustering fondamentalement différentes sont comparées et évaluées. Le cas d’étude est le réseau d’Amsterdam avec des données réelles. (iv) D’un jour à l’autre, la dynamique du trafic peut être similaire. Nous proposons une méthodologie regroupant les jours par leurs motifs de congestion. L’existence d’une régularité dans les motifs journaliers est introduite par la notion de jour-type. Un jour-type est le jour de référence d’un groupe de jours. Nous validons notre modèle en comparant les temps de parcours effectifs et les temps de parcours estimés par les jours-types. Diverses applications peuvent être raffinées à partir de quelques jours-types, comme l’assistance routière et la génération de tournées. / This thesis aims to modeling the interactions between the urban freight and the traffic dynamic. Although both are intertwined, they have rarely been studied considering a combined approach. Specifically, the main purpose is to analyze the impacts of the urban freight on traffic states, and vice versa. This research is focused on two axes: the urban freight considering (i) the delivery and (ii) the delivery route scales, and two traffic dynamic scales describing (iii) a day and (iv) a set of days. (i) The delivery of goods carried by vehicles can produce traffic congestion, noise and air pollution. Nevertheless, the transport of goods is essential for the economy of cities. The double parking is a common way for delivery trucks. This illegal parking reduces the vehicle capacity of the transportation network. A sensitivity analysis in traffic microscopic simulation model for urban freight highlight a significant decreasing of the traffic conditions on an urban corridor considering a low number of double parking. These local and temporal phenomena are essential to be integrated into the traffic simulation in order to better study the overall performance of the transportation system. (ii) The delivery route planner can be improved by integrating traffic conditions. The route optimization algorithms are based on quality and quantity of given data available. We investigate the influence of several levels of granularity on traffic information data for the optimal route scheduling. Moreover, the travel time estimated by algorithms and the effective travel time estimated by a microscopic simulation are compared. In addition, the expected traffic conditions can be subject to variations. We propose a methodology of delivery route planner integrating the uncertainty of the traffic dynamics. (iii) At the city level, the traffic conditions are varied through space and time. A partitioning of urban transportation networks makes possible to identify homogeneous zones. A zone is defined by a set of connected links with similar traffic conditions. We proposed a spatial and temporal approach to define the 3D zones. The idea is to summarize the majority of the traffic dynamics of a given city using only a few information: the mean speed per spatial and temporal zone. Two fundamentally different methods of clustering are compared and evaluated. The study case is the Amsterdam network with its real-world traffic data. (iv) From day to day, the traffic dynamic can be similar. We proposed a methodology grouping days by their similar congestion patterns. The existence of a regularity through daily patterns are introduced by consensual speed map. A consensual speed map is the reference day representing a group of days. Our model is validated by using the effective travel time and estimated ones by the consensual speed maps. Numerous applications can be refined from a couple of consensual speed maps, as the route guidance and delivery route planning.

Le transport de marchandises en ville bien que composante essentielle de la ville a disparu des schémas d'urbanisme et reste secondaire dans les préoccupations des pouvoirs publics. Pourtant le TMV présente de nouveaux enjeux (fonctionnels, environnementaux, économiques...) qui doivent intéresser les acteurs de la ville. La question posée dans cette thèse est "en quoi un opérateur de transports publics urbains peut-il être intéressé par les nouveaux services de logistique urbaine ?". Pour y répondre, un diagnostic sera tout d'abord mené sur le TMV afin de mieux comprendre sa mauvaise organisation puis seront envisagées les nouvelles formes de régulation possibles sur les services de gestion de la voirie, la mise en place d'espaces logistiques urbains et relais-livraisons, le transport de fret et le déplacement des chalands

Couche-Tard est une chaîne qui regroupe plus de 650 dépanneurs au Québec. Pour assurer la livraison de produits hétérogènes à partir de son centre de distribution vers ses magasins, elle compte sur deux transporteurs qui se chargent de la conception des routes et de la livraison. Les transporteurs, disposants d'une flotte de véhicules hétérogènes, créent les tournées sans l'intervention d'un outil d'optimisation. Couche-Tard n'a donc aucun moyen de vérifier l'efficacité des routes. L'entreprise remet en question les routes actuelles afin d'améliorer la distribution et le service aux magasins en introduisant un outil d'aide à la décision. Un partenariat regroupant la Chaire de recherche industrielle en management logistique de l'Université du Québec à Montréal, Alimentation Couche-Tard et Oméga Optimisation cherche donc à améliorer la distribution en introduisant un outil d'aide à la décision à long terme. Dans un premier temps, cet outil prendra la forme d'un prototype visant à démontrer l'utilité et les bénéfices potentiels pouvant découler de cet outil. Ce mémoire sert de première étape à ce projet. Il présente une description détaillée de l'entreprise et de son fonctionnement actuel. Ensuite, une première utilisation du prototype permet d'examiner plusieurs scénarios. Ces scénarios font varier, de façon isolée, certaines composantes du problème, ceteris paribus. Parmi ces composantes, ce mémoire examinera l'impact de changement de l'ordonnancement des clients à l'intérieur d'une même route, le pairage des clients et des routes, le nombre de véhicules qui composent la flotte et l'augmentation moyenne de la demande. Les résultats observés sont ensuite comparés au mode de fonctionnement actuel. Cette étude permet de déceler des pistes d'économies potentielles. Elle démontre aussi le mérite de l'intégration de l'outil d'aide à la décision et évalue sa fonctionnalité. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Problèmes de tournées de véhicules, Distribution, Transport, Couche-Tard, Dépanneurs.

L’uniformisation internationale du droit de transport de marchandises par mer est caractérisée par certains défauts. Par exemple, les Règles de La Haye-Visby ne s’appliquent qu’au transport maritime, ainsi les opérations avant et après le transport par mer sont exclues de leur champ d’application. Le droit international privé déterminera la loi applicable à ces opérations, mais les règles de conflit de lois sont générales et il existe quelques règles spéciales relatives au transport de marchandises par mer. Afin de guider le choix entre les règles de conflit de lois générales et spéciales, la nature particulière des contrats maritimes doit être prise en compte. La thèse tente de déterminer les défauts de l’uniformisation internationale du droit de transport de marchandises par mer, étudie l’application des règles de conflit de lois aux contrats maritimes et tente également de démontrer comment la nature particulière des contrats maritimes influence le choix et l’interprétation des règles de conflit de lois générales. La thèse prend en compte le droit de contrats internationaux et le droit international privé de France et de Panama. / The international uniformity of the carriage of goods by sea law is characterized by certain deficiencies. For instance, the Hague-Visby Rules are applicable only to the maritime leg, so the operations before and after the maritime leg are not under regulation. Here private international law will determine the law to regulate these operations, but the conflict of laws is generalized and there are very few special rules related to the carriage of goods by sea. To guide the choice between the general and special conflict of law rules, the specific characteristics of maritime contracts have to be taken into account. This research tries to determine the deficiencies in the international uniformity of the carriage of goods by sea law, studies the application of the conflict of law rules to maritime contracts and to show how the specific characteristics of maritime contracts influence the choice and the interpretation of the general conflict of law rules. The research takes into account contract and private international law in France and Panama.

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

Le transport de marchandises en ville bien que composante essentielle de la ville a disparu des schémas d'urbanisme et reste secondaire dans les préoccupations des pouvoirs publics. Pourtant le TMV présente de nouveaux enjeux (fonctionnels, environnementaux, économiques...) qui doivent intéresser les acteurs de la ville. La question posée dans cette thèse est "en quoi un opérateur de transports publics urbains peut-il être intéressé par les nouveaux services de logistique urbaine ?". Pour y répondre, un diagnostic sera tout d'abord mené sur le TMV afin de mieux comprendre sa mauvaise organisation puis seront envisagées les nouvelles formes de régulation possibles sur les services de gestion de la voirie, la mise en place d'espaces logistiques urbains et relais-livraisons, le transport de fret et le déplacement des chalands / Urban freight is an essential component of the city, but it disappeared from the scheme of town planning and remains secondary within authorities concerns. However, urban freight presents new stakes (functional, environmental, economic…) which seem interesting for the city actors. The question raised by this study is “how may a public transport operator be interested in new urban logistics services?” To answer it, a diagnosis of urban logistics will be made to better understand its poor organisation. Then the new possible forms of regulation will be considered. They will be related to roadway system, installation of logistic urban spaces and pick-up points, freight transport and customers moving

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.

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.

Le marché des véhicules électriques est animé par une dynamique très positive. Il s'agit cependant essentiellement d'un marché de niche. Il est donc légitime de s’interroger quant à son avenir.D'une part, cette dynamique est portée par de fortes préoccupations environnementales et bénéficie d'un large soutien des autorités publiques. Les constructeurs automobiles ont ces dernières années fortement investi dans cette technologie, les progrès technologiques sont rapides et offrent des perspectives intéressantes.D'autre part, des subventions conséquentes sont aujourd’hui nécessaires pour permettre aux véhicules électriques d’être compétitifs. Il est inévitable que ces subventions diminuent si le marché grandit. Deux mécanismes opposés sont donc en jeu et rendent incertain le développement du marché des véhicules électriques pour les années à venir.Notre recherche propose d'analyser ces mécanismes pour les véhicules utilitaires légers, et plus particulièrement pour le transport urbain de marchandises. Les besoins des entreprises de transport de marchandises sont évalués à travers une quarantaine d'entretiens, menés dans quatre pays européens et analysés à la lumière de la théorie de la diffusion de l'innovation. Ces entretiens mettent en évidence les obstacles opérationnels et économiques à l'utilisation de véhicules électriques, qui sont liés à la technologie elle-même mais aussi à sa nouveauté.Une approche quantitative complète cette étude. Elle s’appuie sur un modèle de prédiction de parts de marché, qui quantifie la façon dont les contraintes économiques et opérationnelles évoluent avec les développements technologiques. Ces contraintes sont mesurées par deux indicateurs: l'adéquation de l'autonomie du véhicule avec son usage et les comparaisons de coûts totaux de possession (TCO). Une originalité du modèle est qu’il traite le montant des subventions à l’achat d’un véhicule électrique comme une variable endogène, qui s’adapte dynamiquement aux évolutions du marché.Afin de compenser le manque de données disponibles sur les usages des véhicules utilitaires, un modèle statistique a été développé. Ce modèle permet d’exploiter au mieux les données d'une enquête sur les véhicules utilitaires légers en France, menée par le service de la donnée et des études statistiques (SDES) du Ministère de la Transition Écologique et Solidaire / Freight transport. The needs of freight transport companies are assessed through some forty interviews conducted in four European countries and analyzed in the light of innovation diffusion theory. These interviews highlight the operational and economic obstacles to the use of electric vehicles, which are linked to the technology itself but also to its novelty.A quantitative approach completes this study. It is based on a market share prediction model, which quantifies how economic and operational constraints evolve with technological developments. These constraints are measured by two indicators: the vehicle's range adequacy given its use and total cost of ownership (TCO) comparisons. An original feature of the model is that it treats the amount of subsidies for the purchase of an electric vehicle as an endogenous variable that dynamically adapts to market developments.In order to compensate for the lack of available data on commercial vehicle uses, a statistical model has been developed. This model makes the best use of data from a survey on light commercial vehicles in France, conducted by the statistical department of the Ministry of the Environment (SDES).These analyses confirm that the development of the electric vehicle market is not certain and that it is currently extremely dependent on public support. Even in scenarios of continued financial support from public administrations, exponential market growth is unlikely. Rather, the market will grow slowly for many years to come, the time for technology to overcome its8dependence on public financial support. For example, our reference scenario forecasts a 13% market share for electric vans in 2032