Academic literature on the topic 'Tournées de véhicules sélectives'

Dans cet article, nous présentons une analyse spatiotemporelle des tournées de livraison à domicile d’une entreprise d’électroménagers qui détient sa propre flotte de véhicules. Plusieurs millions d’observations de géolocalisation GPS issues de ces tournées de livraison sont collectées, traitées et assignées au réseau routier. À la suite de ces analyses spatiotemporelles, nous développons des calendriers quotidiens d’indices de congestion en fonction de l’heure. Des ratios de congestion sectoriels sont calculés afin de déterminer les meilleures heures de départ de livraison tout en évitant la congestion routière. La réduction de la durée des trajets a été quantifiée en comparant les meilleures heures de départs par rapport aux heures habituelles. À partir des données de notre partenaire, les analyses démontrent une réduction potentielle de 22 % de la durée des routes de livraison.

Nous sommes entrés dans l'ère de nouveaux modèles d'affaires où la vente par Internet constitue un élément central des politiques marketing des entreprises. Le secteur du commerce de détail alimentaire n'échappe pas à cette évolution, comme en témoigne la montée en puissance des supermarchés en ligne depuis quelques années. Ils offrent la possibilité aux internautes d'accéder à des produits de grande consommation sans se déplacer jusqu'aux magasins, en leur assurant une livraison à domicile. Face aux risque d'engorgement des villes, suite à une multiplication anarchique des véhicules en circulation, certaines collectivités territoriales commencent à mettre en place des plates-formes urbaines mutualisées et des tournées de livraison concertée auxquels les distributeurs alimentaires en ligne doivent obligatoirement se plier. L'article souligne que la performance logistique pourrait dès lors ne plus constituer un facteur de différenciation aux yeux des internautes, contrairement à ce qu'affirme souvent la littérature académique, compte-tenu de la mutualisation des ressources et des compétences, et de la standardisation du service rendu. L'argumentation s'appuie sur deux expériences de planification de logistique urbaine conduites en France.

Nous nous intéressons aux Problèmes de Tournées de Véhicules Sélectives : les contraintes sont telles qu'il n'est pas possible de servir tous les clients, un choix doit donc être effectué en vue de maximiser la performance de l'activité. Nous proposons différents prétraitements pour ces problèmes en adaptant notamment le Raisonnement Énergétique aux problèmes de tournées et en introduisant les concepts de clients obligatoires et de représentants des tournées. Nous proposons également deux méthodes de résolutions approchée une heuristique itérative et un algorithme mémétique exploitant une méthode de découpage optimal développée pour le cas sélectif. Les méthodes proposées sont adaptées au problème industriel soumis par Veolia Environnement, des résultats numériques et de nombreuses perspectives de développement démontrant l'apport de ces travaux pour l'aide à la décision dans le contexte d'application visé
We deal with Selective Vehicle Routing Problems : constraints are,so that it is not possible to service all customers and an efficient selection must be made to maximize the objective function. We propose pre-processing methods for this problem. We adapt the Energetic Reasoning to vehicle routing problems and introduce concepts of required customers and of optimal affectations. We also propose two heuristic approaches : an iterative heuristic and a memetic algorithm based on an optimal splitting procedure dedicated to selective problems. These methods are adapted to the case study proposed by Veolia Environnement, Experiments and numerous possible developments on the context of real applications show benefits of this work

Le problème de tournées de véhicules (Vehicle Routing Problem - VRP) est un problème d'optimisation combinatoire utilisé généralement pour modéliser et résoudre des différents problèmes rencontrés dans les systèmes logistiques et de transport. Dans cette thèse, nous nous sommes intéressés à l'étude et la résolution d'une classe de problèmes du VRP appelée les problèmes de courses d'orientation (Team Orienteering Problem - TOP). Dans cette catégorie de problèmes, il est a priori impossible de visiter tous les clients en raison de ressources limitées. On associe plutôt un profit à chaque client qui représente sa valeur. Ce profit est collecté lorsque le client est visité par l'un des véhicules disponibles. L'objectif est donc de sélectionner un sous ensemble de clients à servir tout en maximisant le profit total collecté. Dans un premier temps, nous avons introduit une nouvelle généralisation pour le TOP que nous avons appelé le Clustered TOP ou CluTOP. Dans cette variante, les clients sont regroupés en sous-ensembles appelés clusters auxquels nous associons des profits. Pour résoudre cette variante, nous avons proposé un schéma exact basé sur l'approche des plans sécants avec des inégalités valides supplémentaires et des pré-traitements. Nous avons également conçu une méthode heuristique basée sur l'approche order first-cluster second. Cette heuristique hybride combine une heuristique de type Adaptive Large Neighborhood Search qui explore l'espace des solutions et une procédure de découpage qui explore l'espace de recherche des tours géants. De plus, la procédure de découpage est renforcée par une recherche locale afin de mieux explorer l'espace de recherche. Le deuxième problème traité dans ce travail s'appelle le Synchronized Team Orienteering Problem with Time Windows (STOPTW). Cette variante avait été initialement proposée afin de modéliser des scénarios liés à la protection des infrastructures stratégiques menacées par l'avancée des feux de forêts. En plus des contraintes de fenêtres de temps et des visites synchronisées, cette variante considère le cas d'une flotte de véhicules hétérogène. Pour résoudre ce problème, nous avons proposé une méthode heuristique basée sur l'approche GRASP×ILS qui est parvenue à dominer la seule approche existante dans la littérature. La dernière variante du TOP abordée dans cette thèse s'appelle le Set Orienteering Problem (SOP). Les clients dans cette variante sont regroupés en sous-ensembles appelés clusters. Un profit est associé à chaque groupe qui n'est obtenu que si au moins un client est desservi par le véhicule disponible. Nous avons proposé une méthode de coupes avec deux procédures de séparation pour séparer les contraintes d'élimination des sous-tours. Nous avons également proposé un algorithme Mémétique avec une procédure de découpage optimale calculée à l'aide de la programmation dynamique
The Vehicle Routing Problem (VRP) is a family of Combinatorial Optimization Problems generally used to solve different issues related to transportation systems and logistics. In this thesis, we focused our attention on a variant of the VRP called the Team Orienteering Problem (TOP). In this family of problems, it is a priory impossible to visit all the customers due to travel time limitation on vehicles. Instead, a profit is associated with each customer to represent its value and it is collected once the customer is visited by one of the available vehicles. The objective function is then to maximize the total collected profit with respect to the maximum travel time. Firstly, we introduced a new generalization for the TOP that we called the Clustered TOP (CluTOP). In this variant, the customers are grouped into subsets called clusters to which we associate profits. To solve this variant, we proposed an exact scheme based on the cutting plane approach with additional valid inequalities and pre-processing techniques. We also designed a heuristic method based on the order first-cluster second approach for the CluTOP. This Hybrid Heuristic combines between an ANLS heuristic that explores the solutions space and a splitting procedure that explores the giant tours search space. In addition, the splitting procedure is enhanced by local search procedure in order to enhance its coverage of search space. The second problem treated in this work is called the Synchronized Team Orienteering Problem with Time Windows (STOPTW). This variant was initially proposed in order to model scenarios related to asset protection during escaped wildfires. It considers the case of a heterogeneous fleet of vehicles along with time windows and synchronized visits. To solve this problem, we proposed a heuristic method based on the GRASP×ILS approach that led to a very outstanding results compared to the literature. The last variant of the TOP tackled in this thesis called the Set Orienteering Problem (SOP). Customers in this variant are grouped into subsets called clusters. Each cluster is associated with a profit which is gained if at least one customer is served by the single available vehicle. We proposed a Branch-and-Cut with two separation procedures to separate subtours elimination constraints. We also proposed a Memetic Algorithm with an optimal splitting procedure based on dynamic programming

Cette thèse aborde un problème de transport appelé le Problème de m-Tournées Sélectives (PmTS) ou ”Team Orienteering Problem” en anglais. Le PmTS consiste à construire m tournées pour une flotte de véhicules afin de desservir un sous-ensemble sélectionné de clients. Dans le PmTS un service est fourni à chaque client visité en contrepartie de quoi, un gain est récolté. La tournée de chaque véhicule part d'un dépôt, passe par un sous-ensemble de clients et revient en un autre sans dépasser la longueur maximale autorisée. Chaque client peut être desservi au plus une fois par un unique véhicule. L'objectif est de maximiser le gain total récolté. Le PmTS étant un problème NP-difficile, notre objectif de recherche a consisté à proposer des heuristiques basées sur le principe général de ”Cluster first - Route second”. Ces algorithmes sont prévus pour être intégrés dans un logiciel de planification des tournées de techniciens de maintenance.

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 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.

L'objectif de cette thèse est de contribuer à l'adaptation des problèmes de tournées de véhicules (VRP) aux problématiques du monde réel en se focalisant sur deux axes principaux à savoir : la prise en compte des incertitudes à travers l'optimisation robuste et l'optimisation simultanée de plusieurs critères en utilisant l'optimisation multi-objectif. Dans une première partie, nous nous sommes intéressés à la modélisation du problème VRP sous incertitudes en proposant un nouveau critère de robustesse. Ce critère, appelé "Maximizing the Number of scenarios Qualified by the Worst" (MNSQW), a été évalué en utilisant deux méthodes de résolution : une première méthode exacte et une deuxième méthode basée sur une méta-heuristique. Dans une deuxième partie, nous nous sommes intéressés à la résolution robuste multi-objectif d'une variante du VRP: le VRP capacitaire (CVRP), où l'incertitude sur les coûts de trajets est considérée. Un algorithme évolutionnaire multi-objectif hybride a été proposé pour optimiser simultanément le coût du trajet et la taille de la flotte. L'étude expérimentale a montré que l'approche proposée permettait d'atteindre la quasi-totalité des solutions (Pareto) optimales avec une amélioration de deux bornes supérieures (sur un critère) d'une instance. La troisième partie de cette thèse comporte l'étude d'une autre variante du VRP : le problème de tournées de véhicules sélectives (TOP). L'étude vise à optimiser simultanément le profit collecté et le coût du trajet. Pour se faire, nous avons proposé une approche évolutionnaire multi-objectif hybride. La comparaison des résultats par rapport à ceux obtenus par trois méthodes de la littérature, a permis d'observer des amélioration de certaines bornes (quatre nouvelles bornes ont été obtenues). Finalement, nous nous sommes intéressés à l'étude d'une variante robuste du TOP (RTOP). Ce problème a été résolu en adaptant l'algorithme utilisé pour la variante déterministe
The main objective of the thesis is to contribute to the adaptation of VRP problems to the real world problems with a focus on two main axes namely: handling uncertainties through robust optimization and simultaneous optimization of several criteria using multi-objective optimization. First, we focus on modeling the VRP problem under uncertainty by proposing a new robust criterion. This criterion, called "Maximizing the Number of Scenarios Qualified by the Worst (MNSQW)", was evaluated using two approaches: an exact method and a meta-heuristic. In the second part, the robust multi-objective resolution of the capacitated VRP variant (CVRP) with uncertainty on the travel costs has been studied. A hybrid multi-objective evolutionary algorithm has been proposed to optimize the travel cost and the fleet size simultaneously. Experiments were carried out on a state-of-the-art instances, and the proposed approach were compared to an exact method and two meta-heuristics approaches from the literature. The obtained results show that our approach reaches almost all the optimal solutions, and that two new bounds have been established on an other instance. The comparison with the meta-heuristics shows an improvement on the entire results of the first, and competitive results with the second. The third part of this thesis was devoted to the study of another variant of the VRP namely: the Team Orienteering Problem (TOP). We first proposed a hybrid multi-objective evolutionary approach to solve a multi-objective formulation of this problem, to optimize the collected profit and the total travel cost simultaneously. The conducted experiments confirm the conflictual behavior of the optimized objectives. The comparison with three approaches of the literature, allowed to show an improvement of some bounds (four new ones). In the second part of the TOP study, we proposed a robust variant of the latter (RTOP), that has been solved by adapting the algorithm used for the deterministic variant

Le secteur des transports représente le 1er secteur émetteur de gaz à effet de serre et totalise près d’un tiers de l’énergie consommée en France. Aussi, dans le contexte actuel d’urgence écologique, le développement d’une mobilité verte est devenu un enjeu économique mondial. Le véhicule électrique constitue une alternative durable respectant les exigences environnementales. Nous nous sommes intéressés aux modalités d’adaptation du système de distribution d’une entreprise souhaitant remplacer sa flotte de véhicules thermiques par une flotte de véhicules électriques. Le véhicule électrique présente trois défis majeurs : l’autonomie, le temps de recharge et le manque de stations de recharge. Ces trois défis imposent une organisation spécifique des tournées de livraison pour déterminer les meilleurs trajets à coût minimum. Nous proposons et évaluons dans notre travail des méthodes d’optimisation pour résoudre cette problématique permettant d’obtenir des solutions viables
The transport sector is the leading greenhouse gas-emitting sector, and accounts for nearly a third of the energy consumed in France. Therefore, in the current context of ecological emergency, the development of green mobility has become a global economic issue. The electric vehicle is a sustainable alternative that complies with environmental requirements. We were interested in how to adapt the delivery system of a company interested in converting its fleet of internal combustion vehicles with a fleet of electric vehicles. The electric vehicle has three challenges: driving range, recharging time and the lack of recharging stations. These three challenges impose a specific organization of delivery routing to determine the best routes at minimum cost. In our work, we propose and evaluate optimization methods for solving this problem in order to obtain viable solutions

Le problème de tournées de véhicules est un des problèmes d'optimisation combinatoire les plus connus et les plus difficiles. Il s'agit de déterminer les tournées optimales pour une flotte de véhicules afin de servir un ensemble donné de clients. Dans les problèmes classiques de transport, chaque client est normalement servi à partir d'un seul nœud (ou arc). Pour cela, on définit toujours un ensemble donné de nœuds (ou arcs) obligatoires à visiter ou traverser, et on recherche la solution à partir de cet ensemble de nœuds (ou arcs). Mais dans plusieurs applications réelles où un client peut être servi à partir de plus d'un nœud, (ou arc), les problèmes généralisés qui en résultent sont plus complexes. Le but principal de cette thèse est d'étudier trois problèmes généralisés de tournées de véhicules. Le premier problème de la tournée sur arcs suffisamment proche (CEARP), comporte une application réelle intéressante en routage pour le relevé des compteurs à distance ; les deux autres problèmes, problème de tournées couvrantes multi-véhicules (mCTP) et problème généralisé de tournées sur nœuds (GVRP), permettent de modéliser des problèmes de conception des réseaux de transport à deux niveaux. Pour résoudre ces problèmes, nous proposons une approche exacte ainsi que des métaheuristiques. Pour développer la méthode exacte, nous formulons chaque problème comme un programme mathématique, puis nous construisons des algorithmes de type branchement et coupes. Les métaheuristiques sont basées sur le ELS (ou Evolutionary Local Search) et sur le GRASP (ou Greedy Randomized Adaptive Search Procedure). De nombreuses expérimentations montrent la performance de nos méthodes.

Ce mémoire porte sur l’optimisation de tournées de véhicules d’un transporteur local TCP-Distribution. L’étude est sur le problème de tournées sur nœuds (VRP) et plus précisément sur le cas avec flotte hétérogène (Heterogeneous fleet), livraison et collecte (with Mixed Backhauls), et les fenêtres de temps (Time Windows), le problème est appelé HVRPMBTW. La littérature sur ce problème est quasi inexistante. Après une introduction générale sur les problèmes de transport et une description complète du problème traité, nous proposons des approches de résolutions. Un modèle mathématique est développé, c’est un modèle linéaire à variables réelles et binaires (PL mixte) qui est utilisé par une méthode exacte. Une première approche métaheuristique est proposée, elle est basée sur l’optimisation par colonies de fourmis (ACO) combinée à une efficace recherche locale. Cette méthode a montré son efficacité au HVRPMBTW. Une deuxième approche est développée, appelée optimisation par essaim particulaire (PSO) combinée à cette efficace recherche locale. Les nouveaux résultats obtenus améliorent les résultats précédents. La dernière partie de ce mémoire est dédiée à l’application industrielle. Les méthodes développées sont appliquées aux instances industrielles. Un Outil de Gestion des Performances est implémenté et accessible via une interface développée. Il a pour mission de calculer et d’analyser les indicateurs, et faire appel aux méthodes d’optimisation
This thesis focuses on the transportation problem of a local carrier TCP-Distribution. The study is on the node routing problem (VRP) and specifically to cases with Heterogeneous fleet (H), with Mixed Backhauls (MB), and Time Windows (TW), the problem is called HVRPMBTW. It is few studied in literature. After a general introduction to the transportation problems, and a complete description of the problem studied, we suggest several resolution approaches. A mathematical model is developed; it is a linear model with real and binary variables (mixed LP) which is used by an exact method. The first metaheuristic approach is proposed, it is based on an Ant Colony Optimization (ACO) combined with an efficient local search. This method has shown its effectiveness on HVRPMBTW. A second approach is developed, called a Particle Swarm Optimization (PSO) combined with the effective local search. The new results obtained improve the previous results. The last part of this thesis is dedicated to an industrial application. The methods developed are applied to the industrial cases. A Performance Management Tool is implemented and used with a graphic box developed. Its aim is to calculate and analyze the indicators, and to use the optimization methods

Les entreprises de transport font face à des problèmes de taille grandissante où l'utilisation de transbordement peut avoir un impact significatif sur les coûts. ILOG TPO est un logiciel capable de résoudre de tels problèmes, mais il lui est difficile de prendre de bonnes décisions concernant le transbordement. De plus, le processus de résolution d'ILOG TPO est basé sur la recherche locale, et il peut être aidé pour certaines décisions globales comme le transbordement. Cette thèse se place dans ce contexte, et son objectif est d'aider ILOG TPO à trouver de meilleures solutions. Pour cela, une formulation complète est d'abord proposée pour résoudre les plus petites instances, et avec une technique de plans coupants, les solutions optimales sont généralement trouvées en un temps raisonnable. Ensuite, un algorithme à deux phases qui inclut un programme en variables mixtes (MIP) sur une relaxation de type réseau du problème est donné pour de plus grandes instances. Cet algorithme est une coopération entre le MIP et ILOG TPO, où le MIP donne à ILOG TPO, pour chaque ordre de transport, le chemin de hubs par lequel il devrait être acheminé. Cette heuristique trouve des solutions similaires à ILOG TPO seul, mais le temps de calcul est réduit de façon significative.