Academic literature on the topic 'Problème de Routage de Véhicules (VRP)'

L'amélioration des performances de la distribution logistique et l'optimisation des transports sont devenues des préoccupations cruciales ces dernières années. Le secteur de la distribution pharmaceutique est confronté à d'importants défis en matière de planification des itinéraires et d'optimisation des réseaux de transport, les incertitudes entraînant souvent des retards et des pertes. Ces défis complexes englobent l'impératif d'élever la qualité des produits, de réduire les coûts, de minimiser la distance totale parcourue et de rationaliser le temps de transport pour une planification efficace. Dans ce contexte, le Problème de Routage de Véhicules (VRP) se distingue comme l'un des problèmes les plus largement analysés dans les domaines du transport, de la distribution et de la logistique. Atteindre un équilibre délicat entre les considérations de coûts et la livraison de produits pharmaceutiques de haute qualité est un objectif majeur dans la distribution pharmaceutique. Ce travail explore à la fois le Problème de Routage de Véhicules Statique (SVRP) et le Problème de Routage de Véhicules Dynamique (DVRP). La planification logistique du monde réel rencontre fréquemment des incertitudes dès le départ, notamment une demande client incertaine, des quantités de livraison, des contraintes temporelles, et plus encore. Cette thèse introduit la "condition de température" comme une contrainte fondamentale dans la distribution pharmaceutique, représentant une source d'incertitude qui impacte directement la qualité des médicaments, influençant ainsi la distribution logistique et la performance globale de la chaîne d'approvisionnement. De plus, la thèse intègre la quantification de l'incertitude pour modéliser les temps de déplacement incertains dans les scénarios de congestion récurrente et non récurrente. La méthodologie utilisée à cette fin est la méthode de collocation, initialement validée par la Simulation de Monte Carlo (SMC). En abordant ces défis complexes et ces incertitudes, cette recherche vise à contribuer au développement de stratégies robustes dans la distribution pharmaceutique, assurant l'optimisation des itinéraires, la réduction des coûts et le maintien des normes élevées de qualité des produits. Les conclusions de cette étude offrent des éclairages précieux pour les gestionnaires logistiques et les planificateurs qui cherchent à naviguer dans les complexités de la distribution pharmaceutique, favorisant l'efficacité et la résilience face aux incertitudes
The enhancement of logistics distribution performance and the optimization of transportation have emerged as critical concerns in recent years. The pharmaceutical distribution sector faces significant challenges in route planning and transport network optimization, with uncertainties often leading to delays and losses. The multifaceted challenges encompass the imperative to elevate product quality, reduce costs, minimize total travel distance, and streamline transportation time for effective planning. Within this context, the Vehicle Routing Problem (VRP) stands out as one of the extensively analysed problems in the realms of transportation, distribution, and logistics. Achieving a delicate equilibrium between cost considerations and delivering high-quality pharmaceutical products is a primary objective in pharmaceutical distribution. This research delves into both the Static Vehicle Routing Problem (SVRP) and the Dynamic Vehicle Routing Problem (DVRP). Real-world logistical planning frequently encounters uncertainties at the outset, including uncertain customer demand, delivery quantities, time constraints, and more. This thesis introduces the "temperature condition" as a fundamental constraint in pharmaceutical distribution, representing a source of uncertainty that directly impacts drug quality, thereby influencing logistics distribution and overall supply chain performance. Furthermore, the thesis incorporates uncertainty quantification for modelling uncertain travel times in both recurrent and non-recurrent congestion scenarios. The methodology employed for this purpose is the collocation method, initially validated through Monte Carlo Simulation (MCS). By addressing these multifaceted challenges and uncertainties, this research seeks to contribute to the development of robust strategies in pharmaceutical distribution, ensuring the optimization of routes, reduction of costs, and maintenance of high-quality product standards. The findings of this study offer valuable insights for logistics managers and planners aiming to navigate the complexities of pharmaceutical distribution, fostering efficiency and resilience in the face of uncertainties

Cette thèse traite du problème de tournées de véhicules. Jusqu'à présent, seules des méthodes heuristiques ont été utilisées en pratique. Dans cette thèse, nous nous intéressons à l'approche polyédrale du problème de tournées, c'est-à-dire à une méthode de résolution exacte du problème, basée sur la représentation polyédrale de l'enveloppe convexe des solutions réalisables. Plus précisément, nous présentons un algorithme de branchement et coupe pour résoudre le problème classique de tournées, avec des demandes quelconques et non de coupables, des véhicules identiques localisés en un même dépôt. Alors que deux ou trois articles de recherche ont déjà étudié cette approche, l'originalité de notre travail réside dans trois aspects: i) la découverte de nouvelles inégalités valides ; ii) des méthodes de séparation pour ces inégalités ; iii) un algorithme de branchement et coupe combinant l'utilisation de ces procédures et de stratégies d'énumération implicite originales. Cet algorithme permet de résoudre de nombreux problèmes de la littérature dont certains n'avaient jamais été résolus.

Le problème de tournées de véhicules est l’un des problèmes d’optimisation combinatoire les plus étudiés car il a de multiples applications en planification industrielle. La littérature associée est très riche, en variantes de problèmes et en approches de résolution. Face à un problème réel, il est difficile d’identifier la classe de problème à laquelle il appartient, de recenser les travaux correspondants, et de déterminer le type de méthode de résolution le plus approprié. Cette thèse étudie la faisabilité d’un projet destinée à faciliter ces démarches, en s’intéressant plus particulièrement aux approches de résolution évolutionnaires. Il repose sur trois éléments : une notation des variantes de VRP, un recensement d’opérateurs évolutionnaires de la littérature, et la construction d’une base de règles liant les variantes de problèmes à l’efficacité des opérateurs évolutionnaires. L’objectif est de guider la conception d’un algorithme en fonction des caractéristiques du problème, en proposant les opérateurs qui ont la plus grande probabilité d’être efficaces. Appliquer la notation proposée à plusieurs articles montre qu’elle permet à chacun de classifier les travaux de manière précise, et d’identifier ainsi plus facilement les approches et résultats comparables aux siens. La méthode expérimentale proposée est illustrée en considérant 3 types de croisement et 3 types de mutation. Cette étude montre qu’il est possible d’estimer quels éléments de l’algorithme ont un impact détectable sur les performances, et d’établir des relations entre les choix de conception de l’algorithme ou entre l’instance de problème et l’efficacité des opérateurs
Solving vehicle routing problems have been some of the most studied problems in combinatorial optimization because they have many applications in the field of industrial planning. The related literature is diversified both in terms of variants of the problems and in terms of solving approaches. Identifying which class of problems a given real-world problem belongs to, in order to gather related works and determine the most relevant resolution method, is a difficult task. The present thesis constitutes a feasibility study of a project to make these tasks easier, privileging evolutionary solving approaches. This project relies on three essential bases: a notation of the variants of VRP, a compilation of evolutionary operators from the literature, a set of rules linking VRP variants to evolutionary operators according to the efficiency. The objective is to find guidelines to design a solving algorithm according to the characteristics of the problem by identifying the subset of operators showing the greater estimated efficiency. Putting the proposed notation into practice using several papers demonstrated that anyone using this notation can classify accurately papers and can recognize easily approaches and results that are similar to their own. The experimental methodology proposed is illustrated by considering three types of crossover and three types of mutation. This study confirms that is possible to determine which elements of an algorithm have a discernable impact on the performance. It reveals relationships between choices in the design of the algorithm or between the variant of problem and the efficiency of the operators

Nous traitons plus précisément le problème de l'élaboration dynamique de tournées de véhicules avec fenêtres de temps (DVRPTW) et le problème de la tournée du réparateur partiellement dynamique (PDTRP) où la prise en compte de nouveaux clients en cours de l'exécution des tournées est possible. Dans une première approche, nous considérons des profils de vitesse basés sur des temps de trajet moyens qui varient selon la période de temps (matin, midi, après midi) pour tenir compte de l'évolution du trafic routier. En fonction du type de connexion entre les deux clients, plusieurs profils peuvent être considérés (route, voie rapide et autoroute). Dans une seconde approche, nous intégrons des informations trafic obtenues en temps réel pour modier le profil de vitesse par rapport aux aléas du réseau routier (congestions, etc. ). L'analyse des résultats de ces expérimentations montre que notre méthode temps réel fournit de bonnes performances et une meilleure robustesse par rapport à un simple modèle avec temps de trajet dépendant du temps
We treat the dynamic vehicle routing problem with time windows (DVRPTW) and the partially dynamic travelling repairman problem (PDTRP) where the inclusion of new customers during the routing execution is possible. In a first approach, we consider speed profiles based on average travel time depending on the time period (morning, noon, afternoon) to reflect the evolution of road traffic. Depending on the connection type between two customers, several profiles can be considered (feeder road, arterial road and freeway). In a second approach, we integrate traffic information obtained in real time to change the speed profile according to the accidents of the road network (congestion, etc. ). The analysis of the results of these experiments shows that our method with real-time traffic information provides a good performance, a better robustness against a simple model with time dependent travel time

Le problème de routage de véhicules avec fenêtres de temps et routes multiples (MTVRPTW) est une généralisation du problème de routage de véhicules avec fenêtres de temps (VRPTW). Dans le MTVRPTW, on autorise un véhicule à effectuer plusieurs routes durant une période de planification, ce qui permet d'optimiser les transports lorsque le nombre de véhicules est limité et peu élevé. Nous proposons dans cette thèse la première méthode exacte permettant de résoudre ce problème. Notre modélisation prend la forme d'un problème de couverture des clients dont les variables sont des routes. Des contraintes d'exclusion mutuelle expriment la disponibilité des véhicules. Nous utilisons la Génération de Colonnes, avec un sous-problème effectuant, par programmation dynamique, une recherche de plus court chemin élémentaire contraint en ressources. Notre méthode de programmation dynamique tient compte des dépendances de plusieurs ressources grâce à la notion de label représentatif, et est ainsi plus efficace qu'une approche classique. La méthode de Génération de Colonnes est incluse dans un schéma de Branch and Price composé de deux types de branchement, l'un basé sur les arcs, l'autre sur la résolution d'un VRPTW. Nous avons mis en place diverses méthodes accélératrices spécifiques du MTVRPTW. Nous donnons les résultats de l'algorithme sur les instances de Solomon. Des résultats issus de méthodes exactes étaient disponibles dans la littérature pour le MTVRPTW avec durée limite sur les routes. Nous avons proposé un nouvel algorithme plus performant, et basé sur nos méthodes, pour cette variante du problème
The multi-trip vehicle routing problem with time windows (MTVRPTW) is a generalization of the vehicle routing problem with time windows (VRPTW). In the MTVRPTW, one vehicle can perform several trips during a planning period. This allows optimizing the transport when the number of vehicles is limited and small.We propose here the first exact method for solving this problem.Our model is designed as a coverage problem for customers where the variables are trips. Mutual exclusion constraints express the availability of vehicles. We use a column generation scheme in which the sub-problem is an elementary shortest path problem with resource constraints (ESPPRC). Our dynamic programming method for ESPPRC takes into account dependencies of several resources through the concept of representative label. It is thus more efficient than a conventional approach. The column generation method is included in a Branch and Price scheme with two types of branching. One is based on arc selection, and the other on solving a VRPTW. We have implemented various accelerating methods which are specific to MTVRPTW. We give the results of our algorithm on Solomon instances.Results from exact methods were available in the literature for the MTVRPTW with time limit on the trips. We proposed a new and more efficient algorithm, based on our methods, to solve this variant of the problem

Il y a soixante ans, le 4 octobre 1957, Spoutnik, le premier satellite artificiel conçu par l’homme, est envoyé dans l’espace. Sa seule fonction est d’émettre un bip radio à des fréquences de 20 et 40 MHz pour démontrer la puissance spatiale de l’URSS. Depuis cette époque les satellites se sont multipliés et leurs missions se sont diversifiées. Aujourd’hui, les missions des satellites sont si variées que certains quittent l’orbite terrestre. On parle dans ce cas de sondes, même si, dans le reste de cette thèse, ils seront inclus dans le terme "satellite". La mission des satellites la plus connue du grand public est la découverte de l’univers et l’exploration interplanétaire avec de célèbres satellites comme le télescope spatial international Hubble ou des sondes comme Rosetta, Voyager 1 et 2, ... Cependant de nos jours, même si l’exploration spatiale reste un enjeu majeur de l’humanité, la plupart des satellites ont des missions plus modestes qui ont pourtant un impact important sur la vie économique et politique. Les satellites en question ont aujourd’hui deux buts : la défense et le commercial. Dans les deux cas on peut diviser les satellites en deux groupes distincts : les satellites d’observation et les satellites de télécommunication. Pour fonctionner tous ces satellites utilisent un harnais électrique. Le harnais électrique regroupe tous les câbles présents dans le satellite et qui ne transportent pas de données client. Dans le cadre de cette thèse nous nous intéressons à l’optimisation de la conception du harnais électrique des satellites
Sixty years ago, on October 4, 1957, Sputnik, the first man-made artificial satellite, was sent into space. Its only function is to emit a radio beep at frequencies of 20 and 40 MHz to demonstrate the space power of the USSR. Since then, satellites have been multiple and their missions have diversified. Today, the missions of the satellites are so varied that some leave Earth's orbit. We speak in the case of probes, even if, in the rest of this thesis, they will be included in the term "satellite". The best-known satellite mission of the general public is the discovery of the universe and interplanetary exploration with satellite satellites such as the Hubble International Space Telescope or probes such as Rosetta, Voyager 1 and 2, ... nevertheless nowadays Although space exploration remains a major issue for humanity, most satellites have smaller missions that have a significant impact on economic and political life. The satellites in question today have two goals: defense and commercial. In both cases the satellites can be divided into two distinct groups: observation satellites and telecommunication satellites. To operate all these satellites, use an electrical harness. The electrical harness includes all the cables present in the satellite and which does not carry any customer data. As part of this we are interested in optimizing the design of the electrical harness of satellites

Cette thèse présente une nouvelle problématique inspirée d'un cas réel, nous introduisons Problème de localisation-routage multi-dépôts, multi-véhicules à deux niveaux avec gestion de stock (2E-MDILRP) pour un type spécifique de produit périssable, qui s'est avéré être NP-difficile. De plus, nous avons étudié la taxonomie des sous-problèmes du 2E-MDILRP, et nous avons proposé les différentes contraintes des produits périssables. Cette taxonomie permettrait, d'une part, de mieux comprendre la 2E-MDILRP cas des produits périssables et, d'autre part, d'identifier des sujets de recherche prometteurs. Un modèle mathématique a été proposé et validé à l'aide du solveur OPL\Cplex pour cette nouvelle variante. Nous avons également proposé une heuristique spécifique améliorée avec l'algorithme de recherche locale itérative (ILS) utilisé pour résoudre le 2E-MDILRP. Cette méta-heuristique est testée dans un cadre théorique, et dans un cadre empirique réel. Ce dernier consiste à optimiser la localisation, le routage et l'inventaire des produits périssables. Ces méthodes développées ont été testées sur des jeux d'instances allant jusqu'à 4 dépôts principaux, 20 satellites potentielles et 200 clients, avec deux flottes de véhicules hétérogènes disponibles à raison d’une flotte pour chaque niveau. Les résultats de notre méthode exacte et approchées montrent l'efficacité de l'approche
This thesis presents a new problems inspired by a real case, we introduce two-echelon multi-depot, multi-vehicles Inventory-Location-Routing problem (2E-MDILRP) for a specific type of perishable product, proved to be NP-hard. In addition, we studied the taxonomy of the sub problems of 2E-MDILRP, and we propose the different constraints of perishable products. This taxonomy would, on the one hand, provide better understanding of the 2E-MDILRP of the perishable products, and on the second hand identify promising further research topics. So, a mathematical model has been proposed and validated using the OPL\Cplex solver for this new variant. Also, we proposed a specific heuristic developed with iterated local search algorithm (ILS) using to solve the new 2E-MDILRP problem. This is tested within a theoretical framework, the under a real empirical framework. The latter consists in optimizing the perishable product distribution and inventory. These developed methods have been tested on sets of instances of up to 4 main depots, 20 potential satellites and 200 customers, with two fleets of heterogeneous vehicles available at a rate of one fleet for each level. The results of our exact and approximate method show the efficiency of the approach

Cette thèse est consacrée à l'étude de l’optimisation combinatoire multi-objective sous incertitudes. Plus particulièrement, nous abordons les problèmes multi-objectifs contenant des données floues qui sont exprimées par des nombres triangulaires floues. Pour faire face à ce type de problèmes, notre idée principale est d’étendre les concepts multi-objectifs classiques au contexte flou. Nous proposons, dans un premier temps, une nouvelle approche Pareto entre des objectifs flous (i.e. vecteurs des nombres triangulaires flous). Ensuite, nous étendons des méta-heuristiques basées sur Pareto afin de converger vers des solutions optimales floues. L’approche proposée est illustrée sur un problème bi-objectif de routage de véhicules avec des demandes floues. Dans le deuxième volet de ce travail, nous abordons l’aspect de robustesse dans le contexte multi-objectif flou en proposant une nouvelle méthodologie d’évaluation de robustesse des solutions. Finalement, les résultats expérimentaux sur des benchmarks flous du problème de routage de véhicules prouvent l’efficacité et la fiabilité de notre approche
This thesis is devoted to the study of multi-objective combinatorial optimization under uncertainty. In particular, we address multi-objective problems with fuzzy data, in which fuzziness is expressed by fuzzy triangular numbers. To handle such problems, our main idea is to extend the classical multi-objective concepts to fuzzy context. To handle such problems, we proposed a new Pareto approach between fuzzy-valued objectives (i.e. vectors of triangular fuzzy numbers). Then, an extension of Pareto-based metaheuristics is suggested as resolution methods. The proposed approach is thereafter illustrated on a bi-objective vehicle routing problem with fuzzy demands. At the second stage, we address robustness aspect in the multi-objective fuzzy context by proposing a new methodology of robustness evaluation of solutions. Finally, the experimental results on fuzzy benchmarks of vehicle routing problem prove the effectiveness and reliability of our approach

Cette thèse, présente des contributions à la résolution (sur les GPUs) de problèmes d'optimisations réels de grandes tailles. Les problèmes de tournées de véhicules (VRP) et ceux de localisation des hubs (HLP) sont traités. Diverses approches et leur implémentions sur GPU pour résoudre des variantes du VRP sont présentées. Un algorithme génétique (GA) parallèle sur GPU est proposé pour résoudre différentes variantes du HLP. Le GA adapte son codage, sa solution initiale, ses opérateurs génétiques et son implémentation à chacune des variantes traitées. Enfin, nous avons utilisé le GA pour résoudre le HLP avec des incertitudes sur les données.Les tests numériques montrent que les approches proposées exploitent efficacement la puissance de calcul du GPU et ont permis de résoudre de larges instances jusqu'à 6000 nœuds
This thesis presents contributions to the resolution (on GPUs) of real optimization problems of large sizes. The vehicle routing problems (VRP) and the hub location problems (HLP) are treated. Various approaches implemented on GPU to solve variants of the VRP. A parallel genetic algorithm (GA) on GPU is proposed to solve different variants of the HLP. The proposed GA adapts its encoding, initial solution, genetic operators and its implementation to each of the variants treated. Finally, we used the GA to solve the HLP with uncertainties on the data.The numerical tests show that the proposed approaches effectively exploit the computing power of the GPU and have made it possible to resolve large instances up to 6000 nodes

La logistique inverse des déchets techniques encombrants de type blanc ou brun se développe de nos jours afin de répondre aux contraintes législatives fortes qui n'autorisent à partir de juillet 2002 que la mise en décharge des déchets dits « ultimes ». Le recyclage noble apparaît comme une solution prometteuse, économiquement viable et écologique, où la collecte, approvisionneuse exclusive du processus de récupération des déchets, doit être appréhendée et planifiée dans l'objectif de maîtrise des coûts. Après avoir identifié les caractéristiques principales des systèmes de collecte existants, nous nous attardons sur le ramassage à domicile des produits usagés de la population. Afin de pouvoir établir une planification opérationnelle, ce mode de collecte est modélisé comme un problème de routage de véhicules : le problème de chargement et de déchargement avec contraintes de fenêtres temporelles, de précédence et de capacité. Ce problème d'Optimisation Combinatoire est ensuite résolu de manière algorithmique, en considérant successivement le cas d'un véhicule, puis de plusieurs véhicules. La résolution du problème se base sur la recherche tabou et la recherche tabou probabiliste, et fournit des résultats très satisfaisants sur le plan qualitatif et en temps d'exécution. Finalement, nous décrivons, grâce au langage de modélisation unifié orienté objet UML, une manière d'intégrer nos résultats algorithmiques dans un module d'aide à la décision pour la planification opérationnelle de la collecte, où l'opérateur humain est chargé de définir le plan de collecte à exécuter.