To see the other types of publications on this topic, follow the link: Tournées de véhicules sélectives.
Dissertations / Theses on the topic 'Tournées de véhicules sélectives'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Tournées de véhicules sélectives.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Bouly, Hermann. "Problèmes de tournées de véhicules sélectives et applications industrielles spécifiques." Compiègne, 2008. http://www.theses.fr/2008COMP1755.
Full textAbstract:
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
2
Yahiaoui, Ala-Eddine. "Selective vehicle routing problem : cluster and synchronization constraints." Thesis, Compiègne, 2018. http://www.theses.fr/2018COMP2449/document.
Full textAbstract:
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 dynamiqueThe 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
3
Khemakhem, Mahdi. "Heuristiques pour un Problème de m-Tournées Sélectives." Phd thesis, Université de Valenciennes et du Hainaut-Cambresis, 2008. http://tel.archives-ouvertes.fr/tel-00440494.
Full textAbstract:
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.
4
Ben, Said Asma. "Selective vehicle routing problems in collaborative urban transport networks." Thesis, Compiègne, 2019. http://www.theses.fr/2019COMP2478.
Full textAbstract:
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 approchesThe 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
5
Augerat, Philippe. "Approche polyédrale du problème de tournées de véhicules." Grenoble INPG, 1995. http://tel.archives-ouvertes.fr/tel-00005026.
Full textAbstract:
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.
6
Bederina, Hiba. "Problèmes de tournées de véhicules robustes multi-objectifs." Thesis, Amiens, 2018. http://www.theses.fr/2018AMIE0030/document.
Full textAbstract:
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éterministeThe 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
7
Oulad, Kouider Tayeb. "Optimisation de la planification des tournées de véhicules électriques." Electronic Thesis or Diss., Université de Lorraine, 2020. http://www.theses.fr/2020LORR0154.
Full textAbstract:
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 viablesThe 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
8
Ha, Minh Hoang. "Modélisation et résolution de problèmes généralisés de tournées de véhicules." Phd thesis, Ecole des Mines de Nantes, 2012. http://tel.archives-ouvertes.fr/tel-00782375.
Full textAbstract:
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.
9
Belmecheri, Farah. "Optimisation des tournées de véhicules en transport de type messagerie." Troyes, 2010. http://www.theses.fr/2010TROY0023.
Full textAbstract:
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’optimisationThis 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
10
Fournier, Sylvain. "Outils pour des Problèmes Industriels de Tournées de Véhicules avec Transbordement." Phd thesis, Université Joseph Fourier (Grenoble), 2008. http://tel.archives-ouvertes.fr/tel-00348731.
Full textAbstract:
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.
11
Liu, Yihan. "Optimisation de problème de tournées de véhicules de service à domicile." Thesis, Ecole centrale de Lille, 2017. http://www.theses.fr/2017ECLI0009/document.
Full textAbstract:
La performance logistique des entreprises et l’optimisation des transports sont devenues un grand problème ces dernières années. La planification et l’optimisation des services constituent en particulier un nouveau défi. Afin d’accroître la productivité et de réduire les coûts de la logistique, ce travail de recherche contribue à l’optimisation d’un problème de tournées de service à domicile multi-dépôt, multi-période avec fenêtres de temps de vie réelle. Le problème vient d’un contexte réaliste et est formulé comme un modèle en Mixed Integer Programming (MIP). Les résultats avec Cplex montrent que ce problème ne peut être résolu par des méthodes exactes dans un délai raisonnable pour une utilisation pratique. Par conséquent, nous introduisons des heuristiques. Premièrement, les heuristiques de recherche locales sont utilisées pour résoudre le problème. Les solutions réalisables initiales sont générées par une heuristique de construction et plusieurs heuristiques de recherche locales sont appliquées pour obtenir des solutions dans un temps de calcul assez court. Ensuite, nous proposons un algorithme génétique avec une nouvelle représentation du chromosome et de nouveaux opérateurs génétiques pour le problème abordé. Enfin, nous considérons un algorithme génétique avec contrôle de la diversité pour problèmes à grande échelle. Les solutions infaisables sont prises en compte dans la population et la contribution à la diversité fait partie de l’évaluation afin d’éviter une recherche prématurée. Ces méthodes ont été mises en œuvre avec succès pour optimiser le problème de routageThe logistics performance of enterprises and the optimization of transportation have become a great issue in recent years. Field force planning and optimization is a new challenge for the service sector. In order to increase productivity and reduce cost of logistics, this research contributes to the optimization of a real-life multi-depot multi-period field service routing problem with time window. The problem is abstracted from the realistic problem and formulated as a Mixed Integer Programming (MIP) model. Computational results with Cplex show that this problem cannot be solved by exact methods in reasonable time for practical use. First, local search heuristics are used for solving the problem. Initial feasible solutions are generated by a constructive heuristic and several local search heuristics are applied to obtain solutions in a very short computing time. Then we propose a genetic algorithm with new representation of chromosome and new genetic operators for the addressed problem. Finally we consider a genetic algorithm with diversity control to deal with large scale problems. Infeasible solutions are taken account in the population and the diversity contribution is part of the evaluation to avoid premature of search. These methods have been successfully implemented to the optimization of the routing problem
12
Gueguen, Cyrille. "Méthodes de résolution exacte pour les problèmes de tournées de véhicules." Châtenay-Malabry, Ecole centrale de Paris, 1999. http://www.theses.fr/1999ECAP0664.
Full textAbstract:
Cette thèse aborde des problèmes bien connus en recherche opérationnelle rencontrés dans les entreprises de transport : les problèmes de tournées de véhicules. Ces travaux étudient les deux grandes classes de problèmes de tournées de véhicules : les problèmes de tournées sur les noeuds et les problèmes de tournées sur les arcs, à travers le développement de méthodes de résolution exacte. La première partie de ce mémoire est consacrée aux problèmes de tournées sur les nœuds. Nous nous intéressons à trois problèmes particuliers : les problèmes de tournées sélectives, les problèmes de collecte de gains et les problèmes de tournées avec préemption de la demande. Pour ces trois problèmes, nous prenons également en compte des contraintes horaires de visite chez les clients. Dans l'optique d'une résolution exacte de ces problèmes, nous avons montré comment il était possible de généraliser la technique de génération de colonnes, bien connue pour le problème de tournées de véhicules classique avec fenêtres de temps, à ces trois types de problèmes. La deuxième partie de ce mémoire est consacrée aux problèmes de tournées sur les arcs. Nous présentons un nouveau modèle de représentation du problème de tournées sur les arcs avec contraintes de capacité et nous montrons comment il peut être utilisé pour des calculs de bornes inferieures et supérieures. Ensuite, nous présentons une synthèse des méthodes de transformation des problèmes de tournées sur les arcs en problèmes de tournées sur les nœuds, qui permettent d'utiliser les méthodes développées dans la première partie de ce mémoire pour cette classe de problèmes. La troisième partie de ce mémoire présente la maquette informatique développée.
13
Michel, Sophie. "Optimisation des tournées de véhicules combinées à la gestion de stock." Bordeaux 1, 2006. http://www.theses.fr/2006BOR13324.
Full textAbstract:
Dans le problème de la collecte des conteneurs de déchets recyclables, une flotte de véhicules est affectée à collecter un seul produit sur différents sites. Chaque site a son propre taux d'accumulation et sa capacité de stockage. A chaque visite, le stock est vidé. Dans la phase de planification tactique, nous cherchons une solution péridodique qui est répétée dans le temps. L'objectif est de minimiser la taille de la flotte et les coûts de transport tout en donnant un découpage régionale de l'espace par une partition des sites entre les véhicules. Au terme d'une analyse comparative nous proposons une modélisation adéquate. La structure du problème est exploitée pour développer une approche de décompostion de Dantzig-Wolfe. Des plannings périodiques sont générés pour les véhicules en résolvant un problème de sac-à-dos à choix multiple. L'élaboration des plannings de collecte pour les sites est traitée dans le programme maître. Ce dernier est reformulé en terme de variales agrégées pour éviter la symétrie en temps. Les bornes duales sont calculées par une méthode tronquée de Branch-and-Price-and-Cut. Les bornes primales sont obtenues par des heuristiques d'arrondi et de recherche locale développées dans le contexte de la génération de colonnes. Des instances réelles sont résolues avec une déviationà l'optimalité raisonnable.
14
Chanca, Etienne. "Intégration de l'expérience des livreurs aux problèmes de tournées de véhicules." Master's thesis, Université Laval, 2019. http://hdl.handle.net/20.500.11794/36975.
Full textAbstract:
Ce mémoire introduit une nouvelle variante aux problèmes de tournée de véhicules visant à prendre en considération la connaissance et l'expérience des livreurs dans le processus d'affectation aux clients. Ce nouveau type de tournée de véhicules basés sur l'expérience (EB-VRP) est motivé par le gain potentiel que pourrait apporter la familiarité des livreurs avec leur zone de travail, non seulement en termes de coûts de transports, mais également de satisfaction des livreurs. Cette approche pourrait également avoir pour corollaire une consommation ré- duite de carburant ainsi qu'une affectation non biaisée des livreurs aux clients. Pour traiter ce nouveau problème, une méthode de représentation de la connaissance construite à partir d'un historique de livraison est proposée. La résolution est ensuite effectuée par une approche bi-objectif combinée à une heuristique à grand voisinage. Des résultats numériques issus de données réelles viennent corroborer la pertinence de cette méthodologie.This thesis introduces a new type of vehicle routing problem aiming to take into account the knowledge and experience for the driver-customer affectation process. This new experiencebased problem (EB-VRP) is motivated by the potential gain that could result from the ftting between drivers and their working areas in, in terms of global transportation costs and driver's satisfaction. This approach could also lead to a lower fuel consumption and an unbiased driver-customer affectation. A new methodology had been introduced to address this new problem, featuring a way to model the driver's knowledge based on a delivery's history. A bi-objective approach combines with a large-scale neighborhood heuristic had been used as a solving method. Numerical results from real data support the relevance of our methodology
15
Binart, Sixtine. "Optimisation de tournées de service en temps réel." Thesis, Lille 1, 2014. http://www.theses.fr/2014LIL10013/document.
Full textAbstract:
Les tournées de service concernent l’organisation de déplacement de personnels vers des clients. Lors de la planification et de l’exécution de tournées de service mono-période, les entreprises sont confrontées aux aléas des temps de service et de parcours. C’est pourquoi, dans cette thèse, nous nous intéressons à une variante du problème de tournées de service, dans laquelle les temps de parcours et de service sont stochastiques. Il s’agit du problème de tournées de service multi-dépôt, incluant fenêtres de temps, temps de service et de parcours stochastiques avec priorité entre les clients (distinction clients obligatoires / clients optionnels). Pour résoudre cette problématique, nous proposons trois méthodes différentes. Dans la première méthode, nous construisons des routes contenant uniquement des clients obligatoires puis nous procédons à l’insertion des clients optionnels. La deuxième méthode est une méthode approchée basée sur la génération de colonnes consistant à générer un ensemble de routes de bonne qualité pour chaque véhicule puis à en sélectionner une par véhicule. La dernière méthode est un algorithme de branch and price dans lequel le sous-problème consiste à générer des routes réalisables pour un véhicule donné, tandis que le problème maître permet de sélectionner des routes en s’assurant que la priorité des clients est respectée. Après chacune de ces méthodes, afin d’évaluer la qualité de ces solutions face aux aléas, nous utilisons un algorithme de programmation dynamique et procédons à un ensemble de simulations du déroulement des tournées en temps réel. Nous avons testé ces méthodes sur des problèmes dont les données sont issues du milieu industrielThe field service routing problem consists in assigning the visits of technicians to clients in order to satisfy their requests for service activities such as maintenance. When planning service routes, companies have to face hazardous travel and service times. Therefore, in this thesis, we deal with a variant of the single-period field service routing problem in which travel and service times are stochastic. It is the field service routing problem with multiple depots, time windows, stochastic travel and service times and priority within customers (distinguishing mandatory and optional customers). To solve this problem, we propose three different methods. In the first one, we first build routes containing only mandatory customers and then, we insert optional customers in these routes. The second one is a heuristic method based on column generation consisting in generating a set of valuable routes for each vehicle and then in selecting one route per vehicle. The last method is a branch and price algorithm, based on the second method, in which the subproblem consists in finding feasible routes for a given vehicle, whereas the master problem consists in selecting routes while ensuring that customer’s priority is respected. After each of these methods, in order to evaluate the quality of these solutions regarding stochasticity, we use a dynamic programming algorithm and we proceed to a set of simulations of the real-time execution of the service activities over the period. All our experimentations have been made on problems coming from realistic data
16
Mendoza, Jorge-Ernesto. "Solving real-world vehicle routing problems in uncertain environments." Nantes, 2009. http://www.theses.fr/2009NANT2051.
Full textAbstract:
La conception de tournées de véhicules est partie intégrante des challenges d’efficacité économique ainsi que de responsabilité environnementale de nombre d’entreprises. On retrouve dans le contexte de la recherche opérationnelle cette problématique sous l’expression commune des problèmes de tournées des véhicules (VRP en anglais). Malgré les efforts pour aller en ce sens, les résultats obtenus dans des contextes académiques restent trop souvent peu applicables dans des contextes opérationnels. L'une des raisons à ce constat est la difficulté de transférer les connaissances d’un domaine à un autre. Une autre raison est aussi liée à l’inadéquation des hypothèses généralement adoptées dans des contextes académiques telles que l’incertitude sur les paramètres du problème, les approches classiques du VRP les supposant connues lors de la conception des tournées. Les contributions de la thèse se situent principalement sur ces deux champs. Tout d’abord, de nouvelles méthodes pour le VRP avec durée limitée ont été proposées puis intégrées dans un système d’aide à la décision pour leur mise en oeuvre dans un contexte industriel dans le contexte de distribution d’eau. Ensuite, nos travaux se sont orientés sur la résolution du VRP multi compartiment pour lequel la demande de chaque produit est incertaine : le MC-VRPSD. Le problème consiste à établir des circuits de distribution pour des produits multiples sous contrainte d'incompatibilité nécessitant ainsi des compartiments indépendants. Nos algorithmes reposent sur des approches classiques en recherche opérationnelle que nous avons étendues pour prendre en compte les aspects stochastiques de notre problème. Nous avons aussi développé des approches de type multi objectif pour conjuguer, dans la prise de décision, performance économique et aversion au risqueThe effective design of vehicle routes plays a major role in the efficiency and environmental responsibility of enterprises. Although great effort has been devoted to solve vehicle routing problems (VRPs), the gap between academic research and practical problem solving is still significant. One factor that widens this gap is that most of the methodological tools proposed for the VRP and its variants assume that the problem parameters are perfectly known in advance. Needless to say, this is a strong assumption in the real world, where companies often operate under uncertain environments. The main focus of this thesis is to bridge the gap by (i) studying real-world vehicle routing problems in uncertain environments never addressed in the academic literature before, (ii) proposing new solution methods to tackle such problems, and (iii) transferring to industry, when possible, the results its contributions. First, the thesis proposes a set of new methods for the distance constrained VRP, a problem consisting in designing minimal-cost routes of limited duration. The results of this research were transferred to industry via a decision support system (DSS) implemented for a public utility. Second, the thesis introduces a problem with uncertain parameters widely found in practice but never studied in the literature before: the multi-compartment VRP with stochastic demands (MC-VRPSD). The problem consists of designing distribution routes for multiple products that due to incompatibility constraints must be transported in independent compartments. To solve the MC-VRPSD, the thesis couples algorithmic components from the DSS with problem-specific developments to generate a complete set of solution methods including heuristics and metaheuristics. In addition, the thesis proposes two new multiobjective approaches to address the risk behavior of the decision makers in VRPs under uncertainty
17
Reghioui, Hamzaoui Mohamed. "Problèmes de tournées de véhicules avec fenêtres horaires ou préemption des tâches." Troyes, 2008. http://www.theses.fr/2008TROY0018.
Full textAbstract:
Dans ce mémoire, nous étudions les problèmes de tournées de véhicules sur nœuds et sur arcs qui sont les deux grands types de problèmes de tournées, rencontrés dans la majorité des applications de transport. Nous nous intéressons plus particulièrement aux cas avec fenêtres horaires ou préemption des tâches. Ce travail est décomposé en deux grandes parties. La première partie est consacrée aux problèmes de tournées sur nœuds et sur arcs avec fenêtres horaires (VRPTW pour Vehicle Routing Problem with Time Windows et CARPTW pour Capacitated Arc Routing Problem with Time Windows). Contrairement au VRPTW qui a fait l’objet d’une recherche intensive ces dix dernières années, peu de travaux ont porté sur le CARPTW. Dans cette partie de la thèse, nous proposons une méthode basée sur la métaheuristique GRASP couplée à une technique de reconnexion de chemins (path-relinking) pour le CARPTW et un algorithme mémétique pour le VRPTW. La deuxième partie de cette thèse porte sur les problèmes de tournées de véhicules sur nœuds et sur arcs avec préemption de la demande (SDVRP pour Split Delivery Vehicle Routing Problem et SDCARP pour Split Delivery Capacitated Arc Routing Problem). Vu que le SDCARP est un problème relativement nouveau, nous avons commencé par élaborer des modèles mathématiques. Nous avons ensuite proposé des bornes inférieures et supérieures. Les bornes inférieures sont obtenues par des méthodes de coupes, alors que les bornes supérieures sont déterminées par un algorithme mémétique avec gestion de la population et une nouvelle métaheuristique. L’algorithme mémétique a été aussi adapté au SDVRP, donnant lieu à des résultats très compétitifs avec ceux déjà publiésThis thesis studies the node and arc routing problems which are the two main types of routing problems encountered in most transportation applications. We focus particularly on the cases with time windows or split deliveries. This work is divided into two main parts. The first part is devoted to the node and arc routing problems with time windows (VRPTW for the Vehicle Routing Problem with Time Windows and CARPTW for the Capacitated Arc Routing Problem with Time Windows). Contrary to the VRPTW which has been the subject of intensive research over the past decade, few studies have considered the CARPTW. In this part of the thesis, we propose a method based on the metaheuristic GRASP combined with a path-relinking process for the CARPTW and a memetic algorithm for the VRPTW. The second part of the thesis focuses on the node and arc routing problems with split deliveries (SDVRP for the Split Delivery Vehicle Routing Problem and SDCARP for the Split Delivery Capacitated Arc Routing Problem). Since the SDCARP is a relatively new problem, we started by developing mathematical models. We then proposed lower and upper bounds. The lower bounds are obtained by two cutting plane methods while the upper bounds are determined by a memetic algorithm with population management and a new metaheuristic. The memetic algorithm was also adapted to the SDVRP, giving rise to competitive results
18
Lahyani, Rahma. "Une matheuristique unifiée pour résoudre des problèmes de tournées de véhicules riches." Thesis, Ecole centrale de Lille, 2014. http://www.theses.fr/2014ECLI0011/document.
Full textAbstract:
L’objectif de cette thèse est de développer un cadre méthodologique pour les problèmes de tournées de véhicules riches (RVRPs). Nous présentons d’abord une taxonomie et une définition élaborée des RVRPs basée sur une analyse typologique réalisée en fonction de deux critères discriminatoires. Dans cette thèse, nous nous intéressons à la résolution du problème de tournées de véhicules multi-dépôt multi-compartiment multi-produits avec fenêtres de temps (MDMCMCm-VRPTW). Nous proposons une heuristique de génération de colonnes unifiée qui inclut une matheuristique de type VNS. La matheuristique combine plusieurs heuristiques de routage de type destruction et insertion ainsi que des procédures efficaces de contrôle de réalisabilité des contraintes afin de résoudre le MDMCMCm-VRPTW pour un seul véhicule. Deux voisinages de chargement, basés sur la résolution de programmes mathématiques sont proposées. Des études expérimentales approfondies sont conduites sur un ensemble de 191 instances pour des VRPs moins complexes. Les expérimentations valident la compétitivité de la matheuristique unifiée. Une analyse de sensibilité révèle l’importance de certains choix algorithmiques et des voisinages de chargement pour parvenir à des solutions de très bonne qualité. La matheuristique basée sur la méthode de VNS est intégrée dans l’heuristique de génération de colonnes pour résoudre le MDMCMCm-VRPTW. Nous proposons une méthode exacte de post-traitement capable d’optimiser l’affectation des clients aux tournées de véhicules. Enfin, nous résolvons un RVRP qui survient dans le processus de collecte de l’huile d’olive en Tunisie à l’aide d’un algorithme exact de type branch-and-cutThe purpose of this thesis is to develop a solution framework for Rich Vehicle Routing Problems (RVRPs). We first provide a comprehensive survey of the RVRP literature as well as a taxonomy. Selected papers addressing various variants are classified according to the proposed taxonomy. A cluster analysis based on two discriminating criteria is performed and leads to define RVRPs. In this thesis we are interested in solving a multi-depot multi-compartment multi-commodity vehicle routing problem with time windows (MDMCMCm-VRPTW). We propose a unified column generation heuristic cooperating with a variable neighborhood search (VNS) matheuristic. The VNS combines several removal and insertion routing heuristics as well as computationally efficient constraint checking. Two loading neighborhoods based on the solution of mathematical programs are proposed to intensify the search. On a set of 191 instances of less complex routing problems, the unified matheuristic turns to be competitive. A sensitivity analysis, performed on more complex generated instances reveals the importance of some algorithmic features and of loading neighborhoods for reaching high quality solutions. The VNS based matheuristic is embedded in a column generation heuristic to solve the MDMCMCm-VRPTW. We propose an exact post-processing method to optimize the assignment ofcustomers to vehicle routes. Last, we introduce, model and solve to optimality a RVRP arising in the olive oil collection process in Tunisia. We propose an exact branch-and-cut algorithm to solve the problem. We evaluate the performance of the algorithm on real data sets under different transportation scenarios
19
Ngueveu, Sandra Ulrich. "Problèmes de tournées de véhicules avec contraintes particulières pour la maîtrise des risques." Troyes, 2009. http://www.theses.fr/2009TROY0013.
Full textAbstract:
Cette thèse porte sur la résolution de deux problèmes de transport qui intègrent des contraintes ou des objectifs de maîtrise des risques : le problème de tournées de véhicules m-péripatétiques (m-PTVP) et le problème de tournées de véhicules cumulatives avec contraintes de capacité (PTVCC). Les applications ciblées sont du domaine de la logistique sécurisée, tel le transport de fonds, et de la logistique humanitaire, tel le transport de 1ers secours. Le m-PTVP a fait l'objet de la majeure partie de nos travaux. Il consiste à définir des tournées de véhicules de coût total minimal et sans arêtes communes sur m périodes telles que chaque client soit visité exactement une fois par période. Nous proposons différents modèles mathématiques, des bornes inférieures polynomiales, deux méta-heuristiques dont un algorithme de recherche taboue guidée avec la solution d'un b-couplage parfait, une approche de type génération de colonnes qui combine des heuristiques duales avec la génération de q- tournées, et enfin deux algorithmes de branchements et coupes. Le PTVCC identifie les tournées de véhicules qui minimisent la somme des dates d'arrivées chez les clients tout en respectant les contraintes de capacité des véhicules. Nous proposons un algorithme mémétique (MA) dont l'efficacité repose sur le découpage optimal de chromosomes en solutions et l'utilisation de pré-calculs déduits des propriétés du PTVCC que nous avons identifiées, lesquelles produisent également des formules de calcul de bornes inférieures. Notre MA est à ce jour la meilleure méta-heuristique publiée pour le cas particulier du problème du réparateur itinérant (= PTVCC mono-véhicule = TRP)This research concerns solving two transportation problems that integrate constraints or objective-fonctions related to the risk management: the m-Peripatetic Vehicle Routing Problem (m-PVRP) and the Cumulative Capacitated Vehicle Routing Problem (CCVRP). Applications can be found in the security logistics field, such as money transportation, and the humanitarian logistics field, such as vital goods supply after a natural disaster. Most of our work is about the m-PVRP. It consists in finding a set of routes of minimal total cost over m periods such that each customer is served once per period and two customers are never sequenced consecutively during two different periods. Different mathematical models are presented and the problem complexity is discussed. Then, we propose polynomial lower bounds, two metaheuristics including a tabu search with diversification and guided by a b-matching solution, a column-generation-like approach combining dual heuristics with q-routes generation, and finally two branch-and-cut algorithms. The CCVRP consists in minimizing the sum of arrival times at customers, instead of the classical route cost or length, subject to the vehicle capacity. We propose a memetic algorithm (MA). Its efficiency lies upon the optimal splitting procedure of chromosomes without trip delimiters into feasible routes to obtain a feasible solution. Pre-computations to speed up MA and valid formulas to compute lower bounds are deduced from some CCVRP properties we identified. Up to now, this MA is the best metaheuristic published on the special case of the Traveling Repairman Problem ( = single-vehicle PTVCC = TRP
20
Benantar, Abdelaziz. "Optimisation pour des problèmes industriels de tournées de véhicules : vers une transition énergétique." Thesis, Normandie, 2017. http://www.theses.fr/2017NORMLH12.
Full textAbstract:
La thèse porte sur l’étude de problèmes réels de transport et de distribution par voie routière. Il s’agit plus précisément de deux problèmes distincts d’optimisation des tournées de véhicules ; la distribution de produits pétroliers et le transfert des conteneurs. La résolution du premier problème, identifié comme le problème de tournées de véhicules avec compartiments multiples et fenêtres de temps ou MCVRP-TW (Multi-Compartment Vehicle Routing Problem with Time Windows), est basée sur une méthode de recherche tabou. Une adaptation de la méthode de résolution a été appliquée à deux autres problématiques annexes, la première intègre des contraintes supplémentaires liées à l’opération de chargement des produits pétroliers dans les compartiments, et la seconde inclut le concept d’ajustement des quantités demandées. Par ailleurs, dans l’optique d’une transition énergétique, nous nous sommes intéressés au problème de transfert des conteneurs par camions électriques dans la zone industrialo-portuaire du Havre. L’optimisation se situe à deux niveaux, un niveau stratégique pour le dimensionnement de l’infrastructure électrique et un niveau opérationnel pour la construction des tournées de véhicules. Seul le niveau stratégique a été abordé dans le cadre d’un projet de recherche grâce à un couplage de l’optimisation et la simulationThe thesis focuses on the study of real road transportation and distribution pro-blems. The question concerns in particular the optimization of two different vehicle routing problems arising in the distribution of petroleum products and the transfer of containers. The first problem, modelled as an application of the multi-compartment vehicle routing problem with time windows (MCVRPTW), is solved by using a tabu search method. The same method is then applied to two other variants. One introduces additional constraints related to loading operations for petroleum products on the compartments, while the other one includes the ad-justment concept in quantities applied for. Moreover, in the context of an energy transition, we addressed the container transfer problem using a fleet of electric trucks in the industrial port zone of Le Havre. The optimization involves two levels : the strategic level for dimensioning electrical infrastructures and the operational level for constructing the vehicle routes. Only the strategic level is tackled with a research project thanks to a coupling of optimization and simulation
21
Guibadj, Rym Nesrine. "Problèmes de tournées de véhicules et application industrielle pour la réduction de l'empreinte écologique." Phd thesis, Université de Technologie de Compiègne, 2013. http://tel.archives-ouvertes.fr/tel-00966428.
Full textAbstract:
Dans cette thèse, nous nous sommes intéressés à la résolution approchée de problèmes de tournées de véhicules. Nous avons exploité des travaux menés sur les graphes d'intervalles et des propriétés de dominance relatives aux tournées saturées pour traiter les problèmes de tournées sélectives plus efficacement. Des approches basées sur un algorithme d'optimisation par essaim particulaire et un algorithme mémétique ont été proposées. Les métaheuristiques développées font appel à un ensemble de techniques particulièrement efficaces telles que le découpage optimal, les opérateurs de croisement génétiques ainsi que des méthodes de recherches locales. Nous nous sommes intéressés également aux problèmes de tournées classiques avec fenêtres de temps. Différents prétraitements ont été introduits pour obtenir des bornes inférieures sur le nombre de véhicules. Ces prétraitements s'inspirent de méthodes issues de modèles de graphes, de problème d'ordonnancement et de problèmes de bin packing avec conflits. Nous avons montré également l'utilité des méthodes développées dans un contexte industriel à travers la réalisation d'un portail de services mobilité.
22
Haj, Rachid Mais. "Les problèmes de tournées de véhicules en planification industrielle : classification et comparaison d’opérateurs évolutionnaires." Besançon, 2010. http://www.theses.fr/2010BESA2033.
Full textAbstract:
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érateursSolving 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
23
Messaoudi, Bilal. "Approches par décomposition pour des problèmes réels de planification et de tournées de véhicules." Electronic Thesis or Diss., Université de Lorraine, 2020. http://www.theses.fr/2020LORR0211.
Full textAbstract:
Différents acteurs du monde de l'industrie rencontrent quotidiennement des problèmes d'optimisation impliquant des décisions à prendre soit à un niveau tactique, comme pour déterminer le meilleur emplacement d'entrepôts à installer pour couvrir une zone géographique donnée, ou bien à un niveau opérationnel, comme pour améliorer le rendement d'un processus de production. L'objectif de cette thèse Cifre est de proposer des approches de résolution en se focalisant sur des problèmes de planification et de tournées de véhicules issus de clients industriels. Dans un premier temps, nous mettrons en lumière les principales difficultés que l'on peut rencontrer dans le processus d'aide à la décision avec le client industriel, pour ensuite aborder trois cas concrets de problématiques complexes que nous avons traités durant cette thèse. Nous utilisons essentiellement des approches par décomposition pour résoudre ces problèmes au vu de leur complexité et à la taille des instances industrielles traitées. Pour valider l'efficacité de certaines méthodes de résolution, nous les comparons aux meilleures bornes obtenues en relaxant certaines contraintes et aux solutions optimales de problèmes similaires existants dans la littérature lorsque cela s'avère possibleDifferent players in the industry face every day new optimization problems involving decisions to be made either at a tactical level, such as determining the best warehouses’ location intended to cover a given geographical area, or at an operational level, such as improving efficiency of a production process. The objective of this 'Cifre' thesis is to propose solution approaches while focusing on planning and vehicle routing problems faced by industrial customers. We will highlight first the main difficulties that can be encountered in aiding decisions process with the industrial customer, and then address three case studies of complex problems that we have dealt with during the thesis. We mainly use decomposition approaches to solve these problems due to their complexity and large size of the corresponding instances. To assess the performance of some solution methods, we compare them to the best bounds obtained by relaxing some constraints and to optimal solutions of similar problems existing in the literature when possible
24
Sassi, Ons. "Planification de la recharge et optimisation des tournées dans le cas de flottes captives." Thesis, Université de Lorraine, 2015. http://www.theses.fr/2015LORR0303.
Full textAbstract:
Le véhicule électrique est actuellement au coeur des alternatives énergétiques qui permettent de faire face à la croissance du coût du carburant et au réchauffement climatique. En revanche, l’autonomie limitée des batteries des véhicules électriques et l’indisponibilité d’un nombre suffisant de bornes de recharge représentent des enjeux majeurs auxquels se trouvent confrontés les utilisateurs. Le déploiement des véhicules électriques doit alors passer par la conception et l’expérimentation des outils d’aide à la décision pour gestion optimisée et adaptée de l’écosystème du véhicule électrique. C’est dans ce contexte que s’inscrit cette thèse qui vise à fournir des outils d’aide à la décision pour l’optimisation des usages, de la recharge et des tournées des véhicules électriques dans le cadre industriel. Dans un premier temps, nous proposons d’étudier le problème d’optimisation conjointe de l’affectation et de la recharge des véhicules électriques. L’objectif de ce problème est de maximiser l’usage des véhicules électriques et minimiser les coûts de recharge tout en prenant en compte les contraintes d’ordre opérationnel et technique. Pour résoudre ce problème, nous proposons une méthode exacte et deux heuristiques. Nous comparons les performances de ces méthodes sur des instances réelles et d’autres aléatoires. Nous exposons ensuite plusieurs extensions au problème de base en intégrant de nouvelles fonctions objectif et de nouvelles contraintes. Nous étudions par la suite notre problème de point de vue ordonnancement et nous proposons une étude de complexité et des algorithmes d’approximation avec garantie de performance pour le problème d’ordonnancement d’intervalles sous contraintes d’énergie. Finalement, nous nous intéressons à un nouveau problème de construction de tournées pour une flotte mixte de véhicules électriques et thermiques. Pour résoudre ce problème, nous proposons des heuristiques et des méta-heuristiques hybrides et nous comparons les performances des différentes méthodes sur des instances généralisées de la littératureElectric Vehicles may decrease transportation-related emissions and provide for less dependence on foreign oil. However, electric vehicles are still facing many weaknesses related to the high purchase prices, limited battery range and scarce charging infrastructure. The deployment of electric vehicles must then involve the design and the deployment of charging infrastructures. Within this study, the overall objective is to provide enhanced optimization methods and decision tools for electric vehicles assignment, charging and routing that are relevant to different real-world constraints. Firstly, we propose to study the joint scheduling and optimal charging of electric vehicles problem. This problem consists in assigning a set of already constructed routes to the available electric and conventional vehicles and in, simultaneously, optimizing the electric vehicles charging costs while ensuring that all constraints are satisfied. The objective of this problem is to maximize the use of EVs and to minimize charging costs. Secondly, we propose different extensions to our baseline problem and we vary the objective functions and the considered constraints. Moreover, our problem can be seen as a fixed interval scheduling problem with complementary constraints of energy. We propose then to study the complexity and the approximability of many variants of this new problem. Finally, we consider a new variant of the electric vehicle routing problem with a heterogeneous fleet of vehicles and we propose different heuristics and metaheuristics to solve it. We test the different solving methods on benchmark instances and we evaluate the efficiency of each method
25
Ducomman, Sylvain. "Optimisation de tournées de véhicules par programmation par contraintes : conception et développement d'un solveur industriel." Thesis, Université Grenoble Alpes (ComUE), 2017. http://www.theses.fr/2017GREAI009/document.
Full textAbstract:
Les problèmes de tournées de véhicules sont des problèmes d’optimisation combinatoire épineux avec des enjeux économiques et environnementaux importants au sein de la chaîne logistique. Le problème fondamental est de desservir des clients avec un ensemble de véhicules de façon à minimiser la distance totale parcourue. En pratique, il y a une grande variété d’objectifs et de contraintes additionnelles, liées à la législation et à la diversité des domaines d’applications. Ces problèmes de tournées sont très fréquents pour de nombreuses industries et la conception d’approches de résolution génériques est devenue une question de recherche importante.Cette thèse porte sur la conception et le développement d’un nouveau moteur de résolution pour les logiciels de tournées de véhicules proposés par l’entreprise GEOCONCEPT. Le solveur mis au point s’appuie sur la programmation par contraintes (PPC) pour améliorer la flexibilité (prise en compte de contraintes additionnelles), la déclarativité et la maintenance qui sont les limites des solveurs actuels de GEOCONCEPT fondés sur la recherche locale.Dans un premier temps, un modèle de graphe est établi pour la représentation unifiée des données et de nombreuses contraintes métiers. La résolution s’effectue par des approches à base de voisinage large disponibles dans les solveurs de PPC modernes. On peut ainsi traiter des instances de très grandes tailles efficacement tout en conservant une approche déclarative pour exprimer une classe très large de problèmes de tournées de véhicules. Dans un second temps, des modèles PPC s’appuyant sur des représentations redondantes du problème sont proposés afin de renforcer le filtrage. Nous nous intéressons en détails aux mécanismes de filtrage c’est-à-dire aux processus d’élimination des valeurs infaisables ou sous-optimales dans les domaines des variables. Ces algorithmes permettent de simplifier rapidement le problème et de fournir des bornes inférieures afin d’évaluer la qualité des solutions obtenues. Les bornes inférieures sont obtenues en résolvant des relaxations du plus célèbre des problèmes de la Recherche Opérationnelle : le problème du voyageur de commerce (TSP). Ce problème est le cœur de la contrainte globale weightedcircuit permettant de modéliser les problèmes de tournées en PPC. Nous proposons de nouveaux mécanismes de filtrage pour cette contrainte s’appuyant sur trois relaxations du TSP. Ces relaxations sont comparées sur les plans théorique et expérimental. L’originalité de ce travail est de proposer un nouvel algorithme de filtrage permettant de raisonner à la fois sur les successeurs directs d’un client et sur sa position dans la tournée. Ces raisonnements sont particulièrement utiles en présence de contraintes de fenêtres de temps, très communes dans les problèmes industriels.Le nouveau moteur de résolution offre d’excellentes performances sur des problèmes académiques et industriels tout en proposant des bornes inférieures informatives à des problèmes industriels réelsVehicle routing problems are very hard combinatorial optimization problems with significant economic and environmental challenges. The fundamental problem is to visit a set of customers with a given fleet of vehicles in order to minimize the total distance travelled. Moreover, these problems arise with a wide variety of objectives and additional constraints, related to the legislation and the diversity of industrial sectors. They are very common for many industries and the design of generic solvers has become an important research issue.This thesis focuses on the design and implementation of a new solver for the vehicle routing services offered by the company GEOCONCEPT. The proposed solver is based on constraint programming (CP) to improve flexibility (ability to take additional constraints into account), declarative modelling and maintenance, which are the limits of current GEOCONCEPT solvers based on local search.Firstly, a graph model is established to provide a common representation of the input-data and the numerous business constraints. The resolution is performed using large neighbourhood search methods available in modern CP solvers. It is thus possible to deal with large instances efficiently with a declarative approach where a broad class of vehicle routing problems can be modelled. Secondly, several CP models based on redundant views of the problem are proposed to strengthen the filtering. We focus on the filtering mechanisms for removing infeasible or suboptimal values in the domains of the variables. These algorithms can quickly simplify the problem and derive lower bounds to assert the quality of the solutions found. The lower bounds are obtained by solving relaxations of the most famous problem in Operations Research: the Traveling Salesman Problem (TSP). This problem is the core of the global constraint WEIGTEHDCIRCUIT for modelling routing problems in CP. We propose new filtering algorithms for this constraint based on three relaxations of the TSP. These relaxations are compared theoretically and experimentally. The originality of this work is to propose a new filtering algorithm for reasoning on the direct successors of a customer as well as his position in the tour. It is particularly useful in the presence of time window constraints, which are very common in industrial problems.The new solver shows excellent performance on academic and industrial problems and can compute informative lower bounds for real-life problems
26
Michallet, Julien. "Problèmes de tournées de véhicules périodiques avec contraintes de sécurité ou de qualité de service." Thesis, Troyes, 2013. http://www.theses.fr/2013TROY0023/document.
Full textAbstract:
Cette thèse aborde le problème de tournées de véhicules périodiques (PVRP) lorsqu'il est appliqué au transport de marchandises convoitables. Des contraintes spécifiques relatives à la sécurité du convoi doivent être définies.Le problème de tournées de véhicules périodiques avec dispersion des instants de service (PVRPTS) est alors décrit puis modélisé mathématiquement. Le but est de servir un ensemble de clients sur plusieurs jours en respectant un degré de variation définit dans les heures de service. Le modèle obtenu est discuté et deux heuristiques constructives sont proposées et évaluées pour sa résolution.Une recherche locale itérée avec redémarrages (MS-ILS) est proposée pour ce problème. Les résultats obtenus montrent que cette méthode surpasse les deux précédentes sur toutes les instances de test. Elle est ensuite évaluée sur un problème plus classique de la littérature : le problème de tournées de véhicules avec fenêtres horaires souples (VRPSTW) et s'avère très compétitive, produisant de nouvelles meilleures solutions.La MS-ILS est ensuite transposée au problème de tournées de véhicules régulières (ConVRP). Contrairement au PVRPTS, il s'agit dans le ConVRP de servir régulièrement des clients aux demandes intermittentes. La méthode montre une flexibilité remarquable et produit de bons résultats.Pour finir, les développements effectués chez Nexxtep Technologies sont présentés. Ils comprennent la conception d'un logiciel commercial pour l'optimisation de tournées de véhicules et l'implémentation des méthodes développéesThis thesis is dedicated to the periodic vehicle routing problem when applied to the transportation of valuable goods. Specifics constraints have to be defined to ensure the security of the convoy.The periodic vehicle routing problems with time spread constraints on services (PVRPTS) is defined and a mathematical model is given. The goal is to serve a set of customers over several days such that their visit times differ by a minimum amount. The depicted model is discussed and two constructive heuristics are designed and assessed.A Multi-start iterated local search (MS-ILS) is proposed to solve this problem. The results shows that the method outperform the two previous heuristics. For the sake of comparison with previous approaches, the MS-ILS is evaluated on a more classical problem : the vehicle routing problem with soft time windows (VRPSTW). The method proves to be very competitive, producing new best known solutions.The MS-ILS is then adapted to solve the consistent vehicle routing problem (ConVRP). Unlike the PVRPTS, the goal of the ConVRP is to deliver customers with intermittent demands with regularity in terms of service times and drivers. The method demonstrate his flexibility and produce good results. Finally, the developments performed at Nexxtep Technologies are depicted. They encompass commercial-software design and implementation of the proposed methods
27
Hayari, Noureddine. "Cartes auto-organisatrices et approche évolutionniste pour les problemes de tournées de véhicules avec regroupements." Besançon, 2005. http://www.theses.fr/2005BESA2012.
Full textAbstract:
Le but principal des travaux de recherche présentés dans ce mémoire est l'étude des problèmes de tournées de véhicules avec regroupement. Le regroupement consiste à affecter les usagers à des points de ramassage ou arrêts de bus et déterminer les tournées optimales passant par ces points. Quatre variantes du problème, de complexité croissante sont étudiées : le TSPCluster qui est une extension du problème du voyageur de commerce, le MTSCluster qui est une généralisation du problème précédent en considérant le cas de plusieurs véhicules, le VRPCluster qui introduit les contraintes de capacités des véhicules, et enfin le VRPTWCluster qui tient compte de contraintes de fenêtres de temps. Pour résoudre ces problèmes, une approche metaheuristique basée sur l'incorporation de l'algorithme des cartes auto-organisatrices de Kohonen dans un algorithme de population est développée. L'approche propose une réponse aux problèmes de regroupement en ce qu'elle traite le regroupement et le routage simultanément. Elle introduit le concept de modèle visuel soumis à des déformations continuelles. Cet aspect permet de suivre en temps réel et visuellement le déroulement de l'optimisation. La validation de l'approche développée et l'analyse de ses performances sont réalisés, à l'aide d'un environnement logiciel de simulation, sur les principaux jeux de tests, rencontrés dans la littérature et représentatifs de la problématique. Les résultats de l'approche proposée sont comparés avec ceux des stratégies neuronales. Nous avons avons observé d'après nos résultats que notre méthodologie d'étude est en mesure de résoudre des problèmes non résolus par les techniques classiquesThe main purpose of this work is the study of the vehicle routing problem with clustering. Clustering consists of assigning users to collect points or bus stops and to find the optimal routes passing by these points. Four variants, with increasing complexity are studied: The TSPCluster which is an extension of the traveling salesman problem, the MTSCluster which is a generalization of the previous problem with several vehicles, the VRPCluster which introduces the capacity constraints, and finally the VRPTWCluster which requires time windows. To solve these problems, we have developed a metaheuristic approach which incorporates the Kohonen's self-organizing maps into a population based algorithm. This approach is able to find good solutions for clustering problems in the sense that it handles the clustering and routing simultaneously. Moreover, by introducing the concept of visual model subjected to continual deformations, Our contribution allows to visually follow the optimization progress. We have observed from our results that our methodology is able to handle some problems which have not been solved by classical methods
28
Benamar, Fayçal. "Transport terrestre multimodal de conteneurs maritimes : modèle de tournées simultanées des conteneurs et des véhicules." Châtenay-Malabry, Ecole centrale de Paris, 1995. http://www.theses.fr/1995ECAP0423.
Full textAbstract:
Cette thèse présente une formulation mathématique et un algorithme de programmation mathématique pour la résolution optimale d'un problème du transport terrestre de conteneurs maritimes: le problème de tournées simultanés et coordonnées des conteneurs et des véhicules dans un contexte multimodal. Nous nous intéressons tout particulièrement au problème opérationnel qui consiste à satisfaire à moindre cout un ensemble de demandes de mouvement de conteneurs charges et de conteneurs vides entre différentes paires origine/destination. Les demandes sont formulées soit par des clients, soit par la compagnie pour une meilleure répartition de ses conteneurs. Il s'agit, pour satisfaire cet objectif, de déterminer l'ensemble des cheminements des conteneurs pour toutes les paires origine/destination et simultanément, l'ensemble des mouvements des véhicules routiers devant assurer une partie des opérations physiques de transport des conteneurs dans un contexte multimodal. Nous présentons une approche de modélisation originale dans le cas déterministe. Le modèle mathématique propose présente la particularité de reposer sur deux types de variables de décision, reflétant la nécessaire prise en compte simultanée des mouvements des conteneurs et des véhicules. Nous présentons également l'approche de résolution que nous avons développée. Elle est basée sur des techniques de Branch & Price (qui combinent génération de colonnes et Branch & Bound) pour la résolution optimale du problème. Pour valider notre approche, nous avons développé une base de données et des problèmes test et une maquette informatique qui a permis l'obtention de résultats très encourageants
29
Chabot, Thomas. "Résolution des problèmes de tournées de véhicules pour le transport des échantillons biomédicaux au Québec." Master's thesis, Université Laval, 2015. http://hdl.handle.net/20.500.11794/26365.
Full textAbstract:
Afin d’offrir un service de diagnostic fiable à l’ensemble de la communauté, les spécialistes de la santé doivent user d’un réseau de centres de prélèvement et de laboratoires d’analyse biomédical. Les laboratoires ont des équipements de pointe servant à fournir aux spécialistes les informations sur les diagnostics. Ce travail présente un riche problème de planification de tournées de véhicules dans le contexte du réseau des laboratoires du Québec. Les centres de prélèvement sont soumis à un ensemble de contraintes techniques qui en font un problème difficile à résoudre. En effet, nous verrons qu’un ensemble d’exigences doit être respecté de la part des transporteurs afin d’éviter certaines sources de gaspillage. Dans le cadre d’une démarche d’optimisation des opérations du réseau des laboratoires et de l’offre de service aux patients, le Ministère de la Santé et des Services Sociaux (MSSS) a mandaté l’Université Laval et notre équipe pour le développement d’une méthode de planification du transport. Nous présentons d’abord une description en profondeur du contexte étudié et de la problématique de transport, qui par notre revue de littérature, semble encore un problème peu exploré. Deux modèles d’optimisation mathématiques sont proposés ainsi que des méthodes heuristiques afin d’identifier des plans de transport qui minimisent les coûts de transport. Les performances de ces diverses méthodes sont discutées et analysées en détail.
30
Landrieu, Antoine. "Logistique inverse et collecte des produits techniques en fin de vie : tournées de véhicules avec contraintes." Phd thesis, Grenoble INPG, 2001. http://tel.archives-ouvertes.fr/tel-00198400.
Full textAbstract:
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.
31
Ghoudi, Samir. "Approches de résolution en deux phases pour le problème de tournées de véhicules en région sinistrée." Thesis, Université Laval, 2013. http://www.theses.ulaval.ca/2013/30161/30161.pdf.
Full textAbstract:
Le présent mémoire traite du problème de distribution de l’aide humanitaire en région sinistrée. L’objectif est de distribuer l’aide humanitaire à des zones sinistrées à partir d’un ensemble de centres de distribution via une flotte de véhicules hétérogène. Étant donné le contexte particulier d’urgence, la distribution est planifiée pour satisfaire la demande des zones touchées pour chaque type d’aide humanitaire dans les plus brefs délais, tout en tenant compte à la fois de la durée de déplacement et de la durée de chargement et de déchargement. Dans ce mémoire, nous proposons une approche itérative à deux phases afin d’améliorer la qualité de la solution obtenue par une approche heuristique déjà proposée par Berkoune et al. (2011). Des séries d’expérimentations basées sur des problèmes tests ont été effectuées pour évaluer la qualité de la solution obtenue avec l’algorithme développé. La synthèse des résultats obtenus a démontré que l’approche développée permet de résoudre à l’optimalité des problèmes de taille réduite en évitant d’énumérer de façon exhaustive toutes les combinaisons possibles. Une évaluation du choix de la condition d’arrêt ainsi que trois variantes de l’algorithme développé ont été également proposées. Les résultats obtenus nous ont menés à conclure que lorsque la taille du problème devient importante, les améliorations proposées présenteraient une bonne alternative pour réduire le temps total de calcul et raffiner la qualité de la solution obtenue. Mots clés : Logistique humanitaire, tournées de véhicules, livraison partagée, modélisation mathématique et heuristiques.This thesis addresses the problem of distribution of humanitarian aid in disaster areas. The objective is to deliver humanitarian aid to the affected areas from a set of distribution centers, by using a fleet of heterogeneous vehicles. Given the particular emergency situation, the distribution is planned to meet the demand of affected areas for each type of humanitarian aid in the shortest possible time, taking into account both the travel and products loading and unloading times. In this thesis, we propose a two-phase solution approach in order to improve the quality of the solution obtained using the heuristic approach previously proposed by Berkoune et al. (2011). A series of experiments are run to assess the quality of the solutions obtained with the developed algorithm. The obtained results showed that the developed approach can solve the problem to optimality for the majority of the instances, avoiding an exhaustive enumeration of all possible combinations. An evaluation of the choice of stopping condition and three Variants of the developed algorithm are also proposed. The obtained results show that when the problem size becomes large, the proposed improvements provide a good alternative to reduce the total computation time and improve the quality of the obtained solution. Keywords: Emergency logistics, vehicle routing, split delivery, mathematical modeling and heuristics.
32
Vidal, Thibaut. "Approches générales de résolution pour les problèmes multi-attributs de tournées de véhicules et confection d'horaires." Troyes, 2012. http://www.theses.fr/2012TROY0031.
Full textAbstract:
Cette thèse porte sur la résolution de Problèmes de Tournées de Véhicules (VRP). Les VRP impliquent de planifier les itinéraires d'une flotte de véhicules pour desservir un ensemble de clients à moindre coût, en présence de contraintes supplémentaires et objectifs variés. Une analyse multidisciplinaire des VRP et des problèmes sous-jacents de confection d’horaires, appelés problèmes de « timing », est tout d’abord présentée. Un algorithme génétique hybride est proposé, combinant l'exploration large des méthodes évolutionnaires, les capacités d'amélioration des méta-heuristiques à voisinage, et des relaxations de contraintes. Cet algorithme réinterprète le concept de survie du plus apte, évaluant les solutions en relation à leur coût et contribution à la diversité de la population. La méthode est appliquée à plusieurs variantes de VRP, en utilisant notamment des algorithmes de timing ainsi que des méthodes de programmation dynamique pour l’évaluation des routes. Afin de traiter les challenges de la variété et des combinaisons de variantes de VRP, une méta-heuristique unifiée est présentée ainsi qu’un cadre de résolution parallèle par décomposition de problèmes et intégration de solutions. La multiplicité des problèmes est gérée aux moyens de composants de résolution adaptatifs. Des expérimentations sur 26 variantes de VRP démontrent la performance remarquable de la méthode qui, avec une unique implémentation et paramétrage, égalise ou surpasse tous les algorithmes dédiés de la littératureThis thesis contributes to address Vehicle Routing Problems (VRP). VRPs require designing least cost delivery routes to service a geographically-dispersed customer set, in presence of several other compound constraints and objectives. A multidisciplinary analysis of VRP variants and a synthesis of timing problems and algorithms for determining service times to customers are first presented. A hybrid genetic algorithm is then introduced. The method combines the exploration breadth of evolutionary search, the aggressiveimprovement capabilities of neighborhoodbased meta-heuristics, and constraintsrelaxation schemes. The algorithm reinterprets the concept of survival of the fittest, relying on a bi-criteria evaluation of solutions driven by cost and contribution to the population diversity. Different VRP variants are addressed, using timing algorithms and dynamic programming approaches for route evaluations. To tackle the challenges related to the variety and the combinations of attributes, a unified metaheuristic is introduced along with a parallel resolution framework based on problem decompositions and solutions integrations. The multiplicity of problem variants is addressed by means of adaptive resolution components. Extensive computational experiments on 26 prominent VRP variants demonstrate the remarkable performance of the method which, with a single implementation and parameter setting, matches or outperforms all dedicated algorithms in the literature
33
Glize, Estele. "Méthodes exactes pour les problèmes combinatoires bi-objectif : Application sur les problèmes de tournées de véhicules." Thesis, Toulouse, INSA, 2019. http://www.theses.fr/2019ISAT0023.
Full textAbstract:
De nombreux problèmes réels comportent plusieurs critères à considérer simultanément. À titre d’exemple, un trajet peut se caractériser par son coût, son impact écologique, son temps de parcours ou encore sa longueur. Les problèmes mathématiques résultants relèvent de l’optimisation multi-objectif. En général, il n’existe pas de solution réalisable optimisant tous les objectifs. Ainsi, les décideurs veulent analyser le compromis entre tous les objectifs pour pouvoir choisir la solution la plus adéquate. Par conséquent, résoudre un problème multi-objectif consiste à trouver un sous-ensemble de points, dits non dominés, dans l’espace des objectifs. Ces points sont associés à des solutions réalisables pour lesquelles il n’est pas possible d’améliorer un objectif sans en détériorer un autre. Peu de méthodes exactes existent dans la littérature pour traiter les problèmes combinatoires multi-objectif NP-difficiles, en particulier ceux dont la variante mono-objectif est déjà NP-difficile. Cette thèse s’inscrit dans l’étude des méthodes exactes pour de tels problèmes multi-objectif et utilise la classe des problèmes de tournées de véhicules bi-objectif comme référence. Les travaux se concentrent sur une approche basée sur la génération de colonnes et qui vise à énumérer efficacement l’ensemble des points non dominés de ces problèmes. Nous proposons notamment d’analyser diverses techniques d’exploration de l’espace des objectifs et de les améliorer grâce à des propriétés structurelles. Afin d’en démontrer la généricité, l’approche est appliquée à plusieurs variantes bi-objectif des problèmes de tournées de véhicules : le problème de tournées de véhicules avec fenêtre de temps, le problème de tournées couvrantes et le problème de course d’orientation par équipes avec fenêtre de temps. Les multiples tests numériques soulignent l’efficacité de la méthode proposéeReal-world problems involve several different criteria to take into account. For instance, a route may be associated with multiple features such as its cost, its ecological footprint, its duration, or its length. Resulting mathematical problems are addressed by multi-objective optimization. In general, there is no feasible solution able to maximize or minimize all objectives. Thus, decision makers want to examine the trade-off between the objectives in order to select the most suitable solution for them. Solving a multi-objective optimization problem consists of finding a set of points in the objective space, called non dominated points. No point in the objective space is better than a point of this set for all objectives. Few exact methods exist in literature to solve NP-hard multi- objective combinatorial problems, especially those with a NP-hard mono-objective variant. This thesis works on exact methods for such multi-objective problems, and the class of bi-objective vehicle routing problems is used as reference. The manuscript presents a column generation based-approach which aims to efficiently enumerate the set of non dominated points of the problems. We seek the best way to explore the objective space, and we propose different acceleration techniques based on structural properties. To show its generic aspect, the approach is applied to several bi-objective variants of the vehicle routing problem : the vehicle routing problem with time windows, the covering tour problem and the team-orienteering problem with time windows. Extensive computational experiments highlight the efficiency of the proposed method
34
Li, Yantong. "Modèles et algorithmes pour une classe de problèmes combinés de production et de tournées de véhicules." Thesis, Université Paris-Saclay (ComUE), 2018. http://www.theses.fr/2018SACLE036/document.
Full textAbstract:
Le problème combiné de production et de tournées de véhicules (PRP) consiste à proposer une planification intégrée de la production et de la distribution. Il vise à optimiser le coût global de la chaîne logistique et à améliorer le niveau de service aux clients. Bien que le PRP et son application en agroalimentaire (FPRP) présentent des enjeux importants à la fois scientifiques et industriels, ils n’ont pas été suffisamment étudiés dans la littérature. L’objectif de cette thèse est de développer de nouveaux modèles et algorithmes pour le PRP et le FPRP.Dans cette thèse, nous avons d’abord étudié un PRP multi-produit avec sous-traitance (MPRPOS) qui est une extension naturelle du PRP classique. Pour ce problème, un nouveau programme linéaire en nombres mixte (MILP) a été proposé et une heuristique à trois niveaux a été développée. Les expériences numériques sur 225 instances générées aléatoirement pour le MPRPOS et 1530 instances de benchmark du PRP montrent de très bonnes performances de l’heuristique proposée. En particulier, nous avons obtenu de nouvelles meilleures solutions pour 283 instances de benchmark.A partir de l’étude du MPRPOS et en prenant en compte les spécificités des produits agroalimentaires (périssabilité et qualité), trois nouveaux FPRPs ont été ensuite étudié: 1) un FPRP multi-site avec conditionnement (MFPRP); 2) un FPRP multi-critère (BFPRP): minimisation du coût total de la chaîne logistique et maximisation de la qualité; et 3) un FPRP avec des contraintes de fenêtre horaires (FPRPTW). Pour chacun des problèmes, un modèle MILP a été établi. En outre, une Matheuristique hybride combinant une méthode itérative, une procédure de fixe-et-optimisation et un processus d’optimisation basé sur les routes déterminées pendant les deux premières étapes a été développée pour le MFPRP. Pour le BFPRP, une heuristique du type epsilon-contrainte et une méthode par logique floue sont proposées. Et le FPRPTW est directement résolu par le solveur CPLEX. Une étude des cas montre que le modèle et l’algorithme proposés pour le BFPRP peuvent significativement améliorer la performance de l’entreprise. Les résultats numériques sur des instances générées aléatoirement montrent que les méthodes développées sont plus performantes que le CPLEXThe production routing problem (PRP) consists of determining an integrated production and distribution planning that aims to optimize overall cost and improve service level. Although the PRP has been attracting academic and practical interests, it has not been well studied in the literature. Food production routing problem (FPRP) that is more complex than the classic PRP due to food perishability, has rarely been studied. This thesis focuses on developing new models and algorithms for the PRP and FPRP.Firstly, a multi-product PRP with outsourcing (MPRPOS) that is a generalization of the classic PRP is addressed. For the problem, a mixed integer linear programming (MILP) model is proposed and a three-level heuristic is designed. Computational experiments on 225 newly generated MPRPOS instances and 1530 PRP benchmark instances demonstrate the effectiveness and efficiency of the proposed heuristic. Especially, 283 new best solutions for PRP benchmark instances are found by the heuristic.Considering food quality and perishability, and based on the study for the PRP, three new FPRPs are then investigated, i.e., 1) a multi-plant FPRP with packaging consideration (MFPRP); 2) a bi-objective FPRP (BFPRP) that minimizes the total supply chain cost and maximizes food quality simultaneously; and 3) a FPRP with delivery time window constraints (FPRPTW). For each of the studied problems, a MILP model is proposed. Moreover, a hybrid matheuristic that combines a two-phase iterative method, a fix-and-optimize procedure, and a route-based optimization is developed for the MFPRP. For the BFPRP, an epsilon-constraint-based heuristic and a fuzzy logic decision method are proposed to generate near-optimal Pareto solutions and to help decision makers select a preferred solution. And the FPRPTW is directly solved by the state-of-the-art solver CPLEX. A case study shows the proposed model and algorithm for BFPRP can improve food supply chain performance. Computational results on randomly generated instances demonstrate the proposed hybrid matheuristic and epsilon-constraint-based heuristic outperform CPLEX
35
Mouhrim, Nisrine. "Contribution au Développement de Transport Vert : Proposition d'un Plan de Recharge par Segments des Véhicules Électriques : Étude d'un problème de Tournées de Véhicules Mixtes." Thesis, Normandie, 2019. http://www.theses.fr/2019NORMLH02.
Full textAbstract:
La mise en oeuvre des véhicules électriques dans le secteur du transport de fret présente une solution durable qui répond aux objectifs environnementaux et économiques. Cette thèse s'oriente dans cette direction, elle porte sur l'étude des problèmes de transport électrique selon deux niveaux décisionnels à savoir le niveau stratégique et opérationnel.Au niveau stratégique, nous traitons le problème d'allocation des segments de recharge d'un véhicule électrique par des ondes électromagnétiques. Pour cela, nous proposons une modélisation du problème sous forme de programme mathématique mixte en nombre entier qui tient compte de la particularité du réseau routier et du véhicule. L'objectif est de déterminer; dans un réseau qui se compose de plusieurs chemins; une allocation stratégique qui constitue un compromis entre le coût d'achat du matériel de recharge et le coût de la batterie en satisfaisant un ensemble de contraintes liées au fonctionnement du système lors de l'exploitation et qui garantissent l'arrivée du véhicule à sa destination sans rupture de charge. Ainsi, nous montrons l'utilité de nos travaux dans un contexte industriel à travers le projet 'Green Truck'. Ce projet consiste à remplacer les camions à combustion par les camions électriques; adapté à la technologie d'alimentation par induction; dans la zone industrialo-portuaire du Havre. Dans cette optique et dans un premier temps, nous traitons le problème d'installation des segments de recharge dynamique. Dans un deuxième temps, nous intégrons le mode de rechargement statique dans la stratégie d'allocation. Nous adoptons la version multi-objective de l'algorithme d'optimisation par essaim de particules pour résoudre le problème. En effet, l'algorithme a montré sa robustesse et son efficacité vis-à-vis de problèmes d'optimisation non-linéaires. Après la linéarisation de notre modèle, nous comparons les résultats obtenus avec ceux issus à partir du solveur CPLEX. Nous montrons la validité des résultats obtenus à travers leur analyse et leur discussion.Au niveau opérationnel, nous étudions le problème de tournées de véhicules dans le cas d'une flott( mixte composée de véhicules électriques et à combustion, ce qui est un véritable réseau industrie rencontré dans la pratique. La particularité de notre travail réside dans la considération du cas où le émissions sont limitées par un système de plafonnement d'émissions pour les véhicule conventionnels. Afin de résoudre le modèle mathématique que nous avons élaboré, nous avons indu trois heuristiques dans l'algorithme SPEA-II qui répondent aux contraintes engendrées par la batterie limitée des véhicules électriques. Après l'analyse des performances de l'algorithme résultant, nou, concluons que l'approche de résolution permet d'achever des résultats compétitifsThe implementation of electric vehicles in the freight transport sector presents a sustainable solution that meets environmental and economic objectives. This thesis is oriented in this direction, it deals with the study of the problems of electric transportation according to two decisional levels namely the strategic and operational levels.At the strategic level, we study the problem of the location of the wireless charging infrastructure in a transport network composed of multiple routes between the origin and the destination. To find a strategic solution to this problem, we first and foremost propose a nonlinear integer programming solution to reach a compromise between the cost of the battery, which is related to its capacity, and the cost of installing the power transmitters, while maintaining the quality of the vehicle's routing. Thus, we show the utility of our work in an industrial context through the 'Green Truck' project. This project consists of replacing diesel trucks by inductive trucks in the industrial-port area of Le Havre. Initially, we are dealing with the problem of allocation of dynamic charging segments. In a second step, we integrate the static reload mode in the allocation strategy. We adapt the multi-objective particle swarm optimization (MPSO) approach to our problem, as the particles were robust in solving nonlinear optimization problems. Since we have a multi-objective problem with two binary variables, we combine the binary and discrete versions of the particle swarm optimization approach with the multi-objective one. To assess the quality of solutions generated by the PSO algorithm, the problem is transformed into an equivalent linear programming problem and solved with CPLEX optimizer. The results are analyzed and discussed in order to point out the efficiency of our resolution method.At the operational level, we study a new version of the vehicle routing problem with a mix fleet of electric and combustion vehicles, which is a real industrial network encountered in practice. The particularity of our work lies in the consideration of the case where emissions are limited by an emission cap system for conventional vehicles. In order to solve the mathematical model that we have developed, we have included three heuristics in the SPEA-II algorithm that respond to the constraints generated by the limited battery of electric vehicles. After analyzing the performance of the resulting algorithm, we conclude that the resolution approach achieves competitive results
36
Sousa, Vale Rego César Augusto de. "Recherche locale et structures de voisinages pour des problèmes de tournées de véhicules : algorithmes séquentiels et parallèles." Versailles-St Quentin en Yvelines, 1996. http://www.theses.fr/1996VERS003V.
Full textAbstract:
Cette thèse concerne l'étude, développement et évaluation de structures de voisinage efficaces vis-à-vis de leur utilisation dans des méthodes de recherche locale, ou plus générique dans les metaheuristiques. Nous introduisons plusieurs structures de voisinage pour générer des mouvements composés pour des problèmes de tournées de véhicules provenant autant de la littérature que d'applications réelles. Concernant le premier groupe de problèmes nous proposons des structures de voisinage fondées sur l'idée de chaînes d'éjection. Nous considérons donc des chaînes éjectant des noeuds, arcs ou plus génériquement des sous chemins. De plus, différentes techniques de parallélisation sont utilisées pour mieux explorer l'espace de recherche ainsi que pour accélérer l'évaluation d'une chaîne d'éjection
37
Touati, Nora. "Amélioration des performances du schéma de la génération de colonnes : application aux problèmes de tournées de véhicules." Paris 13, 2008. http://www.theses.fr/2008PA132032.
Full textAbstract:
La génération de colonnes est une méthode dédiée à la résolution de problèmes d'optimisation combinatoire de grande taille. Les méthodes utilisant cette approche de résolution ont souvent des problèmes de convergence, particulièrement quand elles sont utlisées pour résoudre des problèmes pratiques, de grandes dimensions. Nous nous intéressons dans cette thèse à l'accéleration de la méthode de génération de colonnes. Nous proposons des téchniques de diversification pour diminuer le nombre total de colonnes généreés ainsi que le temps de résolution des problèmes maîtres. Nous nous intéressons également à la résolution éfficace des sous-problèmes en utilisant des techniques de réoptimisation, mais aussi en proposant des améliorations de la méthode de programmation dynamique. Les approches sont validées expérimentalement sur le problème de tournées de véhicules avec fénêtre de tempsColumgeneration algorithms are instrumental in many areas of applied optimization where linear programs with an enormous number of variables need to be solued. Although success fully used in many applications, this method suffers from well-known "instability" issues, that somewhat limit its efficiency. This work focuses on accelerating strategies in a column generation algorithm. We propose some diversifiication methods in order to decrease the total number of generated columns and then master problems resolution time. We interest also to solving efficiently the pricing problems, by proposing an improning approch based on reoptimization principle and a new variant of the dynamic programming algorithm. The effectiveness of these approches is validated on vehicule routing problem with time windows
38
Xu, Jian. "Modèles stochastiques évolutionnaires pour la gestion de tournées de véhicules avec fenêtres de temps souples et demandes floues." Artois, 2007. http://www.theses.fr/2007ARTO0202.
Full textAbstract:
Le travail réalisé dans cette thèse traite le problème de la gestion de tournées de véhicules avec fenêtres de temps et demandes floues (VRPTWFD : Vehicle Routing Problem with Time Windows and Fuzzy Demands). Ce problème consiste à trouver des chemins avec un coût minimum pour que les véhicules puissent visiter exactement une fois chaque client en respectant des contraintes. Les clients spécifient leur demande à l’aide d’un nombre flou pour une plus grande souplesse. Le VRPTWFD est étudié dans un contexte aussi bien statique que dynamique. La théorie des possibilités nous a permis d’exprimer la contrainte de capacité floue en fixant des valeurs de seuils de possibilité et de nécessité. En utilisant cette contrainte de capacité floue, un modèle de programmation sous contraintes probabilistes (CCP) et un modèle à deux-étapes de programmation stochastique avec recours (SPR) ont été proposés pour traiter le VRPTWFD. Des algorithmes génétiques qui intègrent ces modèles, ont été proposés pour la recherche de bonnes solutions. Dans le VRPTWFD dynamique, des nouveaux clients arrivent au cours de la journée. Une plateforme de simulation ayant la capacité de simuler la journée de service, nous a permis de résoudre le VRPTWFD dynamique « en ligne ». Afin de vérifier les performances de ces modèles, nous avons construit un benchmark pour le VRPTWFD statique et un benchmark pour le VRPTWFD dynamique en modifiant le jeu de problèmes fournis par Solomon pour le VRPTW, puis nous avons évalué la qualité des solutions fournies par les modèles dans un environnement réel en simulant les situations réelles à l’aide de scénarios « test »The work of this thesis considers the vehicle routing problem with time windows and fuzzy demands (VRPTWFD). The goal of the problem is to find the routes of the vehicles with a minimal cost so that the vehicles can service each client exactly only once respecting some constraints. The customers specify their demands by a fuzzy number. The VRPTWFD is studied as the static case as well as the dynamic case. We use the possibility theory to handle the constraint of capacity by setting certain thresholds for the degrees of the possibility and necessity. Using this capacity constraint, a chance constrained programming model (CCP) and a two-stages stochastic programming with recourse model (SPR) in stochastic programming were proposed to treat the VRPTWFD. The genetic algorithms integrating these models have been proposed as the optimization approach in order to find the optimal solutions. In the dynamic VRPTWFD, some customers can call in their orders during the daily operation. A simulation platform, which has the capability of simulating the daily operation, has been developed to solve online the dynamic VRPTWFD. In order to assess the performance of the proposed models, we have constructed a benchmark for the static VRPTWFD and a benchmark for the dynamic VRPTWFD adapting from Solomon’s benchmark for the VRPTW, then we have evaluated the quality of the solutions, which were obtained by using these models, by simulating the real world situations with the help of the “test” scenarios
39
Kergosien, Yannick. "Algorithmes de tournées de véhicules pour l'optimisation des flux de produits et de patients dans un complexe hospitalier." Phd thesis, Université François Rabelais - Tours, 2010. http://tel.archives-ouvertes.fr/tel-00502988.
Full textAbstract:
Cette thèse est une illustration de problèmes de Recherche Opérationnelle abordés dans le contexte hospitalier du CHRU de Tours. La problématique considérée relève des transports et plus exactement de tournées de véhicules. Cette thèse s'articule autour de l'étude de deux principaux problèmes : le transport de flux de produits et le transport de flux de patients. Le premier problème de tournées de véhicules concerne toute la gestion des différents types de flux logistiques (logistique hôtelière, pharmacie, lingerie, plateaux repas, etc.) à livrer ou à collecter dans les services de soins de chaque hôpital du CHRU de Tours. Le deuxième problème concerne les transports de patients aussi bien urgents (SAMU) que planifiés (Centrale des ambulanciers). Pour résoudre ces problèmes, plusieurs méthodes s'inspirant des techniques de la RO sont proposées : des méthodes exactes (programmation linéaire en nombres entiers), des heuristiques (algorithme glouton, recherche tabou avec et sans mémoire adaptative, algorithme génétique, algorithme mémétique) et des moteurs de simulation à événements discrets ont été développés. Des expérimentations numériques valident l'interêt et la qualité des méthodes développées.
40
Mechti, Redouane. "Contribution à la résolution des problèmes de tournées de véhicules avec fenêtres de temps et composition de flotte." Versailles-St Quentin en Yvelines, 1999. http://www.theses.fr/1999VERS0023.
Full textAbstract:
Nous nous sommes intéressés dans ces travaux à un problème de composition d'une flotte hétérogène de véhicules et la conception des tournées associées respectant des contraintes telles, la capacité des véhicules, les fenêtres de temps chez le client, les temps d'attente, etc. Après description du problème et sa modélisation pour une application particulière à la collecte postale, ainsi que toutes les caractéristiques et difficultés dont il faut tenir compte pendant sa résolution, nous présentons deux méthodes de résolution : une méthode exacte et une autre approchée. La méthode exacte est fondée essentiellement sur les techniques de génération de colonnes avec comme difficulté majeure, la résolution du sous-problème- plus court chemin contraint- pour lequel nous avons élabore un algorithme qui repose sur la programmation dynamique et l'exploration A*. La difficulté des instances traitées nous a poussé à construire une méthode approchée - méthode tabou à voisinage variable - qui repose sur un ensemble de mouvements, locaux et globaux, susceptibles de modifier considérablement la structure de la solution et de pouvoir traiter par conséquent des instances beaucoup plus grandes contrairement à la méthode exacte.
41
Naudin, Edith. "Problèmes de tournées de véhicules avec contraintes de ressources : modélisations par arcs-états et techniques de résolution adaptées." Paris 6, 2003. http://www.theses.fr/2003VERS0038.
Full text
42
Kansou, Ali. "Nouveaux algorithmes d'optimisation combinatoire pour les problèmes de tournées sur arcs." Le Havre, 2009. http://www.theses.fr/2009LEHA0012.
Full textAbstract:
Dans ce mémoire, nous présentons des extensions des problèmes de tournées de véhicules sur arcs dits CARP. Nous concentrons nos travaux dans trois directions : modélisation mathématique, étude théorique et résolution numérique. Nous donnons des nouvelles contributions aux problèmes CARP mixtes (MCARP), CARP périodiques (PCARP) et CARP avec multi-dépôts (MDCARP). Pour chacun de ces problèmes, nous proposons un modèle mathématique et une approche de résolution basée sur l'optimisation par colonies de fourmis (ACO). L'approche appliquée sur le MCARP est une méthode directe qui associe l'utilisation des fourmis artifcielles et d'une méthode de recherche locale. Une nouvelle stratégie hybride de résolution de deux autres problèmes est proposée de telle manière que l'ACO construit les fourmis représentant l'ordre d'insertion d'arcs et d'arêtes dans les solutions et une méthode heuristique d'insertion spéciale à chaque problème. Des nouvelles contributions ont été réalisées sur le problème MDCARP. Pour ce problème, nous proposons deux modélisations mathématiques et nous adaptons les méthodes de découpage optimal au cas de multi-dépôts qui seront intégrées dans les algorithmes ACO. La seconde stratégie développée est l'application des algorithmes génétiques, connus par leur e fficacité, parce qu'à chaque itération ils génèrent une nouvelle population en utilisant un croisement spécifique et une méthode de recherche locale qui leur permettent d'éviter les optima locaux. Nous présentons des résultats expérimentaux qui prouvent l'efficacité de nos approches et leur avantage par rapport aux méthodes existantesThis thesis presents the extensions of the arc routing problems, called CARP. We focus our work on three directions : mathematical modeling, theoretical study and numerical resolution. We provide new contributions to the problems : mixed CARP (MCARP), periodic CARP (PCARP) and multi-depots CARP (MDCARP). For each one of these problems, we propose a mathematical model and a solving approach based on the ant colony optimization (ACO). However, the applied approach to the problem MCARP is a direct method which combines the use of artificial ants and a local search method. Also, a new hybrid strategy for solving the two others problems is proposed. Thus, the ACO builds ants representing the insertion order of arcs and edges in the solutions and a specific heuristic is devoted to each problem for insertion. On the other hand, new contributions were made on the problem MDCARP. For this problem, we propose two mathematical models and we adapt the optimal splitting methods for the case of multi-depots which will be also incorporated in ACO algorithms. The second strategy developed is the application of genetic algorithms, known by their efficiency, because at each iteration they generate a new population using a specific crossover and a method of local search which allows them to avoid local optima. We present experimental results illustrating the effectiveness of our approaches and their advantage comparing with other existing methods
43
Tricoire, Fabien. "Optimisation de tournées de véhicules et de personnels de maintenance : application à la distribution et au traitement des eaux." Phd thesis, Université de Nantes, 2006. http://tel.archives-ouvertes.fr/tel-00078905.
Full textAbstract:
Cette thèse, fruit d'un contrat de recherche avec Générale des Eaux,porte sur le problème de tournées de service multi-périodes avec fenêtres de temps et flotte limitée. Nous proposons plusieurs méthodes de résolution approchées, ainsi qu'une méthode optimale. La méthode optimale est basée sur la génération de colonnes. Une des méthodes approchées est un algorithme mémétique basé sur une heuristique également développée dans cette thèse. Enfin, la méthode optimale est dérivée en méthode approchée par l'utilisation d'une heuristique pour la résolution du sous-problème.
Les algorithmes proposés permettent d'apporter des solutions efficaces à des problèmes comportant jusqu'à 300 clients, dans des temps variant de quelques secondes à quelques dizaines de minutes. Dans un second temps, nous appliquons ces méthodes à des scénarios issus de problématiques réelles, dans une logique d'aide à la décision.
44
Grellier, Emilie. "Optimisation de tournées de véhicules dans le cadre de la logistique inverse : modélisation et résolution par des méthodes hybrides." Phd thesis, Université de Nantes, 2008. http://tel.archives-ouvertes.fr/tel-00483057.
Full text
45
Grellier, Émilie. "Optimisation des tournées de véhicules dans le cadre de la logistique inverse : modélisation et résolution par des méthodes hybrides." Nantes, 2008. http://www.theses.fr/2008NANT2002.
Full textAbstract:
Cette thèse porte sur l'optimisation des tournées de véhicules dans le cadre de la logistique inverse. La logistique inverse prend en compte les flux directs (allant du producteur vers les clients par exemple) et les flux de retour (allant des clients vers le producteur par exemple). Dans ce contexte, nous proposons des modèles génériques de tournées de véhicules multipériodiques avec fenêtres de visite dans un réseau où un produit est livré depuis un dépôt central vers plusieurs magasins, et où ces magasins retournent des produits revenus de leur client (notamment pour non satisfaction) et des supports de manutention. Nos modèles permettent de tester un éventail large d'options (variation des différents coûts, possibilité ou non de livrer un même client en plusieurs fois, gestion ou non des stocks par le dépôt central) afin de pouvoir comparer différentes politiques logistiques et être réutilisés dans des contextes variés. Nous avons utilisé pour résoudre ces problèmes différentes techniques de résolution approchées (heuristiques classiques et métaheuristique GRASP) ainsi que la PLNE (génération de colonnes suivie de branch and bound). Nous avons combiné et comparé des méthodes relevant de la recherche opérationnelle et de la programmation par contraintes. L'ensemble des méthodes de résolution a été testé sur des instances générées aléatoirement à partir de celles de Solomon et sur des instances réelles. Les tests effectués montrent l'intérêt de nos modèles pour évaluer différentes politiques logistiques ainsi que la performance des différentes approches de résolution en fonction des caractéristiques des données testéesThis research deals with vehicle routing problems in the reverse logistics context. Reverse logistics aims at taking into account both direct flows (from the producer to the customers) and reverse flows (products or equipments sent back from the customers to the producer). We consider multiperiodic problems with time windows where products are delivered from a single warehouse to retail stores, and the stores send products returned by clients as well as handling equipments back to the warehouse. We have developed generic models for distribution and pick up on a network, allowing a variety of options to be tested - cost variations, split deliveries, inventory management by the central warehouse or not. We have developed and compared several solution techniques to solve these problems: classical heuristics, the GRASP metaheuristic and column generation associated with a branch and bound method. The GRASP heuristics and column generation methods have been implemented using both operations research and constraint programming techniques. All our models and solution techniques have been tested on randomly generated instances based on those of Solomon for the CVRPTW and on real-world instances. The obtained results show the relevance of our models for the comparison of different logistics policies as well as for the performance evaluation of the different solution methods, depending on the characteristics of the instances
46
Abounacer, Rachida. "Problèmes de planification des tournées de véhicules et planification des horaires des examens : modélisation et résolution par les méthaheuristiques." Le Havre, 2010. http://www.theses.fr/2010LEHA0003.
Full textAbstract:
Cette thèse porte sur la modélisation et la résolution d’une part, des problèmes de planification des tournées de véhicules et d’autre part du problème de planification horaire des examens. Nous apportons trois contributions essentielles: dans la première, nous proposons une modélisation du problème de transport du personnel et nous menons deux approches de résolution basées sur les algorithmes génétiques et sur les algorithmes de colonies de fourmis. Dans la deuxième, nous traitons le problème de tournées de véhicules multi-objectif, puis nous proposons une nouvelle approche de résolution basée sur les algorithmes de colonie de fourmis et dans la troisième, nous étudions le problème de planification horaire des examens en proposant une méthode de résolution fondée sur l’hybridation d’un algorithme de colonie de fourmis et d’une méthode de recherche localeThis thesis deals with the modelling and the resolution on the one hand, of the vehicles routing problems and on the other hand, of the examination scheduling problem. Our contributions are of three types: first, we propose a mathematical modelling of the transportation staff problem and we carry out two approaches of resolution based on the genetic algorithms and the ant colony algorithms. Secondly, for the multi-objective vehicle routing problem, we propose a new resolution approach based on the ant colony algorithm. Finally, we study the examination timetabling problem by proposing a resolution approach based on hybridization of an ant colony algorithm and of a local search method
47
Chekoubi, Zakaria. "Problème intégré de dimensionnement de lots et de tournées de véhicules avec remanufacturing des produits en fin de vie." Electronic Thesis or Diss., Université de Lorraine, 2020. http://www.theses.fr/2020LORR0209.
Full textAbstract:
Dans une chaîne logistique traditionnelle, les opérations de production, de stockage et de distribution sont traitées séparément en raison de la complexité de la planification conjointe de ces opérations et le manque d'informations partagées entre les parties prenantes. Aujourd'hui, pour faire face à la concurrence féroce que connaît le marché mondial, les entreprises sont obligées de planifier conjointement ces activités afin de bénéficier des avantages économiques et environnementaux engendrés par cette intégration. Parmi les problèmes d’optimisation existants dans la littérature, le problème de la planification intégrée qui optimise conjointement les décisions de production, de gestion des stocks, de distribution et de tournées de véhicules, a récemment fait l'objet d'une attention considérable, malgré sa nature NP-difficile. En effet, ses avantages en termes de synchronisation entre les processus, de réduction des coûts et d’amélioration du niveau de service peuvent être importants. En outre, l’optimisation de ce problème dans le contexte des chaînes logistiques en boucle fermée avec gestion des Produits en Fin de Vie (PFV) conduit au développement de chaînes logistiques de plus en plus durables. De plus, les inquiétudes croissantes sur les enjeux environnementaux liés aux activités industrielles ont conduit à l'émergence de politiques de contrôle des émissions carbone. La prise en compte de ces réglementations peut conduire à un impact positif sur la responsabilité environnementale de l’entreprise. Pour répondre à ces défis, l’objectif de cette thèse consiste à concevoir des modèles et de développer des approches d’optimisation pour résoudre un problème de planification intégrée des opérations de production, de ré-usinage, de stockage et de distribution directe-inverse. Nous avons considéré une chaîne logistique en boucle fermée composée d’une ligne de production de produits neufs, d’une ligne de ré-usinage des PFV retournés, deux stocks pour les produits réutilisables et les PFV à ré-usiner, ainsi que des clients ayant des demandes dynamiques en livraison et en collecte. Le but est de déterminer les quantités optimales à produire, ré-usiner et stocker, ainsi que l’ordre de passage chez les clients afin de satisfaire leurs demandes simultanément en livraison et en collecte, tout en minimisant le coût total dû aux opérations induites. Dans un premier temps, un modèle linéaire en nombres entiers est proposé pour optimiser la chaîne logistique en considérant un ou plusieurs véhicules avec capacité limitée. La deuxième partie de la thèse porte sur le développement d’une heuristique de décomposition à deux phases pour résoudre le modèle intégré étendu. La dernière partie de la thèse est consacrée à l’intégration des émissions du dioxyde de carbone dans les décisions de production, de ré-usinage, de stockage et de distribution et d'étudier le comportement des niveaux d'émissions de carbone dans le cadre de la politique de plafonnement et d'échange de droits d'émission de carbone. Des expérimentations numériques permettent de démontrer l’applicabilité et les limites de nos approchesIn a traditional supply chain, production, inventory and distribution operations are treated separately due to the complexity of jointly planning these operations and the lack of information shared among stakeholders. Today, in order to face the fierce competition in the global market, companies are forced to jointly plan these activities in order to benefit from the economic and environmental benefits generated by this integration. Among the optimization problems existing in the literature, the integrated planning problem which jointly optimizes production, inventory management, distribution and vehicle routes decisions, has recently received considerable attention, despite its NP-hardiness. Indeed, its benefits in terms of synchronization between processes, cost reduction and improved service level can be significant. In addition, the optimization of this problem in the context of closed-loop supply chains with End-of-Life Product (EOL) management leads to the development of increasingly sustainable supply chains. Furthermore, growing concerns about environmental issues linked to industrial activities have led to the emergence of policies to control carbon emissions. Taking these regulations into account can have a positive impact on the company's environmental responsibility. To meet these challenges, the objective of this thesis is to design models and develop optimization approaches to solve an integrated planning problem of production, remanufacturing, storage and direct-reverse distribution operations. We considered a closed-loop supply chain consisting of a production line for new products, a remanufacturing line for returned EOL products, two types of inventories for reusable products and EOL ones to be remanufactured, as well as customers with dynamic demands for delivery and pickups. The goal is to determine the optimal amounts to produce, remanufacture and store, as well as the order of visiting customers in order to meet their requests simultaneously for delivery and pickup, while minimizing the total cost due to the involved operations. First, a linear integer model is proposed to optimize the supply chain system by considering one or more vehicles with limited capacity. The second part of the thesis concerns the development of a two-phase decomposition heuristic to solve the extended integrated model. The last part of the thesis is devoted to the integration of carbon dioxide emissions into production, remanufacturing, inventory and distribution decisions and to study the behavior of carbon emission levels in the context of cap-and-trade policy. Numerical experiments make it possible to demonstrate the applicability and the limits of our approaches
48
Lannez, Sébastien. "Optimisation des tournées d'inspection des voies." Phd thesis, INSA de Toulouse, 2010. http://tel.archives-ouvertes.fr/tel-00595070.
Full textAbstract:
La SNCF utilise plusieurs engins spécialisés pour ausculter les fissures internes du rail. La fréquence d'auscultation de chaque rail est fonction du tonnage cumulé qui passe dessus. La programmation des engins d'auscultations ultrasonores est aujourd'hui décentralisée. Dans le cadre d'une étude de réorganisation, la SNCF souhaite étudier la faisabilité de l'optimisation de certaines tournées d'inspection. Dans le cadre de cette thèse de doctorat, l'optimisation de la programmation des engins d'auscultation à ultrasons est étudiée. Une modélisation mathématique sous forme de problème de tournées sur arcs généralisant plusieurs problèmes académiques est proposées. Une méthode de résolution exacte, appliquant la décomposition de Benders, est détaillée. À partir de cette approche, une heuristique de génération de colonnes et de contraintes est présentée et analysée numériquement sur des données réelles de 2009. Enfin, un logiciel industriel développé autour de cette approche est présenté.
49
Marques, Guillaume. "Problèmes de tournées de véhicules sur deux niveaux pour la logistique urbaine : approches basées sur les méthodes exactes de l'optimisation mathématique." Thesis, Bordeaux, 2020. http://www.theses.fr/2020BORD0199.
Full textAbstract:
Cette thèse s’intéresse principalement au développement de méthodes d’optimisation mathématique exactes pour résoudre des problèmes de tournées de véhicules dans un réseau de distribution à deux niveaux. Dans un tel réseau, des camions circulent au premier niveau et transportent des marchandises d’un centre de distribution vers des dépôts intermédiaires appelés « satellites ». Au second niveau, des véhicules légers récupèrent les marchandises aux satellites puis livrent les clients. Chaque client doit être visité une seule fois. L’objectif du problème de tournées de véhicules sur deux niveaux est de minimiser le coût total de transport dans un tel réseau de distribution.Le premier chapitre présente succinctement l’algorithme de « branch-and-cut-and-price » que nous utilisons tout au long de la thèse.Le second chapitre s’intéresse au « Two-Echelon Capacitated Vehicle Routing Prob- lem ». Nous présentons une nouvelle formulation du problème basée sur des routes qui ne contient pas de variable pour déterminer les quantités de marchandises livrées aux satellites. Nous proposons une nouvelle stratégie de branchement qui permet de significativement réduire la taille de l’arbre de branch-and-bound. Enfin et surtout, nous présentons une nouvelle famille d’inégalités valides nommée « satellite supply inequalities ». Nous montrons que cette nouvelle famille améliore la qualité de la borne duale au nœud racine de l’arbre de « branch-and-bound ». Les expérimentations montrent que notre algorithme résout toutes les instances de la littérature qui contiennent jusqu’à 200 clients et 10 satellites. C’est le double de la taille des instances qui étaient résolues à l’optimalité jusqu’ici.La troisième chapitre s’intéresse au « Two-Echelon Vehicle Routing Problem with Time Windows ». Ici, nous considérons une variante avec des contraintes de précédence aux satellites : un camion doit livrer les marchandises à un satellite avant qu’elles soient chargées dans un véhicule léger. C’est une relaxation de la variante avec synchronisation exacte considérée dans la littérature. Nous traitons les variantes « single trip » et « multi trip » du problème avec contraintes de précédence. Dans la seconde variante, les véhicules légers partent d’un dépôt, récupèrent les marchandises aux satellites, puis effectuent plusieurs tournées. Nous proposons une formulation basée sur les routes dont le nombre de contraintes de précédence croît exponentiellement en fonction du nombre de satellites. Un algorithme basé sur une coupe minimum est proposé pour séparer ces contraintes. Nous montrons aussi comment prendre en compte ces contraintes dans le problème de pricing de l’algorithme de génération de colonnes. Les expérimentations montrent que notre algorithme peut résoudre à l’optimalité des instances qui contiennent jusqu’à 100 clients. De plus, nous montrons que la variante du problème avec contraintes de précédence donne des résultats identiques à ceux de la variante avec synchronisation exacte pour les instances « single trip » de la littérature.La quatrième chapitre s’intéresse à des problèmes de tournées de véhicules contenant des contraintes de type sac-à-dos. Nous présentons des coupes de type « route load knapsack ». Ces coupes sont utilisées pour résoudre les trois problèmes suivants: « Capacitated Vehicle Routing Problem with Capacitated Multiple Depots », « Location- Routing Problem » et « Vehicle Routing Problem with Time Windows and Shifts ». Ces problèmes apparaissent lorsque les routes au premier niveau du réseau de distribution à deux niveaux sont fixées. Nos expérimentations permettent de trouver de nouvelles solutions optimalesThe main focus of this thesis is to develop mathematical optimization based exact methods to solve vehicle routing problems in two-level distribution systems. In such a system, the first level involves trucks that ships goods from a distribution center to intermediate depots called satellites. The second level involves city freighters that are loaded with goods at satellites and deliver the customers. Each customer must be visited once. The two-echelon vehicle routing problem seeks to minimize the total transportation cost in such a distribution system.The first chapter gives an overview of the branch-and-cut-and-price framework that we use throughout the thesis.The second chapter tackles the Two-Echelon Capacitated Vehicle Routing Problem. We introduce a new route based formulation for the problem which does not use variables to determine product flows in satellites. We propose a new branching strategy which significantly decreases the size of the branch-and-bound tree. Most importantly, we suggest a new family of satellite supply inequalities, and we empirically show that it improves the quality of the dual bound at the root node of the branch-and-bound tree. Experiments reveal that our algorithm can solve all literature instances with up to 200 customers and 10 satellites. Thus, we double the size of instances which can be solved to optimality.The third chapter tackles the Two-Echelon Vehicle Routing Problem with Time Windows. We consider the variant with precedence constraints at the satellites: products should be delivered by an urban truck to a satellite before loading them to a city freighter. This is a relaxation of the synchronisation variant usually considered in the literature. We consider single-trip and multi-trip variants of this problem. In the first one, city freighters start from satellites and do a single trip. In the second one, city freighters start from a depot, load product at satellites, and do several trips. We introduce a route based formulation that involves an exponential number of constraints to ensure precedence relations. A minimum-cut based algorithm is proposed to separate these constraints. We also show how these constraints can be taken into account in the pricing problem of the column generation approach. Experiments show that our algorithm can solve to optimality instances with up to 100 customers. The algorithm outperforms significantly another recent approach proposed the literature for the single-trip variant of the problem. Moreover, the “precedence relaxation” is exact for single-trip instances.The fourth chapter considers vehicle routing problems with knapsack-type constraints in the master problem. For these problems, we introduce new route load knapsack cuts and separation routines for them. We use these cuts to solve to optimality three problems: the Capacitated Vehicle Routing Problem with Capacitated Multiple Depots, the standard Location-Routing Problem, and the Vehicle Routing Problem with Time Windows and Shifts. These problems arise when routes at first level of the two-level distribution system are fixed. Our experiments reveal computational advantage of our algorithms over ones from the literature
50
Gu, Wenjuan. "Problèmes de tournées de véhicules avec plusieurs produits et applications à la livraison de produits frais en circuits courts et locaux." Thesis, Ecole centrale de Lille, 2019. http://www.theses.fr/2019ECLI0013.
Full textAbstract:
Nous étudions les problèmes de tournées de véhicules pour la livraison de plusieurs produits, avec des applications dans les chaînes logistiques en circuit court et local. La chaîne logistique est composée de trois groupes d’acteurs: les fournisseurs, les plateformes de distribution et les clients. Les fournisseurs sont des agriculteurs. Les plateformes de distribution sont chargées de la consolidation. Les plateformes de distribution collectent les produits auprès des fournisseurs en faisant aller-retours. Les produits sont livrés aux clients avec une flotte de véhicules effectuant des tournées. Chaque client demande plusieurs produits. Pour minimiser les coûts de transport, il est avantageux qu’un même client soit livré par plusieurs véhicules. Mais pour le confort du client, il est imposé qu’un produit soit livré en une seule fois par un seul véhicule. En conséquence, les différents produits sont pris en compte dans les modèles et méthodes de résolution. Le problème complet est nommé Multi-Commodity two-echelon Distribution Problem (MC2DP). Le problème restreint qui concerne la livraison à partir d’une seule plateforme de distribution est nommé Commodity constrained Split Delivery Vehicle Routing Problem (C-SDVRP). Nous proposons d’abord une heuristique basée sur un ALNS pour résoudre le C-SDVRP. Nous abordons ensuite le MC2DP avec des opérations de collecte et de livraison et plusieurs plateformes de distribution. Nous proposons de décomposer le problème: la collecte et la livraison sont résolues de manière séquentielle. De plus, nous développons une approche intégrée pour le MC2DP afin d’améliorer les solutions obtenues par l’approche de décompositionWe study vehicle routing problems considering multiple commodities, with applications in the local fresh food supply chains. The studied supply chain contains two echelons with three sets of actors: suppliers, distribution centers and customers. Suppliers are farmers that produce some fresh foods. Distribution centers are in charge of consolidation and delivery of the products to customers. Distribution centers collect products from the suppliers that perform direct trips. Products are delivered to the customers with a fleet of vehicles performing routes. Each customer requires several commodities, and the farmers produce a limited quantity of these commodities. For the minimization of the transportation cost, it is beneficial that a single customer is delivered by several vehicles. However, for the convenience of the customer, it is imposed that a single commodity is delivered at once by a single vehicle. Hence, different commodities have been considered. The complete problem is named Multi-Commodity two-echelon Distribution Problem (MC2DP). The restricted problem that addresses only the delivery from a single distribution center is named Commodity constrained Split Delivery Vehicle Routing Problem (C-SDVRP). We first propose a heuristic based on the Adaptive Large Neighborhood Search (ALNS) for the C-SDVRP. Then, we address the whole problem (MC2DP) with collection and delivery operations and multiple distribution centers. In order to tackle this complex problem, we propose to decompose the problem: collection and delivery are sequentially solved. Furthermore, we develop an integrated approach for the MC2DP to improve the solutions obtained by the sequential approach