Les problèmes de tournées de véhicules (VRPs) ont fait l’objet de plusieurs travaux de recherche depuis maintenant plus de 50 ans. La plupart des approches trouvées dans la littérature s’appuient sur un graphe complet ou un nœud est introduit pour tout point d’intérêt du réseau routier (typiquement les clients et le dépôt). Cette modélisation est, implicitement, basée sur l’hypothèse que le meilleur chemin entre toute paire de points du réseau routier est bien défini. Cependant, cette hypothèse n’est pas toujours valide dans de nombreuses situations. Souvent, plus d’informations sont nécessaires pour modéliser et résoudre correctement le problème. Nous commençons par examiner ces situations et définir les limites de la modélisation basée sur un graphe complet. Nous proposons un état de l’art des travaux qui examinent ces limites et qui traitent des VRPs en considérant plus d’informations issues du réseau routier. Nous décrivons les approches alternatives proposées, à savoir la modélisation utilisant un multi-graphe et celle utilisant la résolution directe sur un graph représentant le réseau routier. Dans une seconde étude, nous nous intéressons à l’approche basée sur la construction d’un multi-graphe. Nous proposons, d’abord, un algorithme qui permet de calculer d’une manière efficace la représentation par multi-graph du réseau routier. Puis, nous présentons une analyse empirique sur l’impact de cette modélisation sur la qualité de la solution. Pour ce faire, nous considérons le problème classique VRPTW comme un problème de pilote. Par la suite, nous développons une méthode heuristique efficace afin de résoudre le VRPTW basée sur une représentation par un multi-graphe.Dans une troisième étape, nous nous concentrons sur l’approche basée sur la résolution directe du problème sur un graphe représentant le réseau routier. Nous développons un algorithme de type branch-and-price pour la résolution de cette variante du problème. Une étude expérimentale est, ensuite, menée afin d’évaluer l’efficacité relative des deux approches. Enfin, nous étudions les problèmes de tournées de véhicules dans lesquels les temps de parcours varient au cours de la journée. Nous proposons un algorithme de type branch-and-price afin de résoudre le problème avec des fenêtres de temps directement sur le graphe représentant le réseau routier. Une analyse empirique sur l’impact de l’approche proposée sur la qualité de la solution est proposée. / Vehicle routing problems (VRPs) have drawn many researchers’ attention for more than fifty years. Most approaches found in the literature are, implicitly, based on the key assumption that the best path between each two points of interest in the road network (customers, depot, etc.) can be easily defined. Thus, the problem is tackled using the so-called customer-based graph, a complete graph representation of the road network. In many situations, such a graph may fail to accurately represent the original road network and more information are needed to address correctly the routing problem.We first examine these situations and point out the limits of the traditional customer-based graph. We propose a survey on works investigating vehicle routing problems by considering more information from the road network. We outline the proposed alternative approaches, namely the multigraph representation and the road network approach.Then, we are interested in the multigraph approach. We propose an algorithm that efficiently compute the multigraph representation for large sized road networks. We present an empirical analysis on the impact of the multigraph representation on the solution quality for the VPR with time windows (VRPTW) when several attributes are defined on road segments. Then, we develop an efficient heuristic method for the multigraph-based VRPTW.Next, we investigate the road network approach. We develop a complete branch-and-price algorithm that can solve the VRPTW directly on the original road network. We evaluate the relative efficiency of the two approaches through an extensive computational study.Finally, we are interested in problems where travel times vary over the time of the day, called time dependent vehicle routing problems (TDVRPs). We develop a branch-and-price algorithm that solves the TDVRP with time windows directly on the road network and we analyze the impact of the proposed approach on the solution quality.

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 simulation. / The 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.

[pt] Como em toda grande empresa da indústria de óleo e gás, fortemente integrada e altamente rentável, várias são as oportunidades de buscar e encontrar processos logísticos com reais possibilidades de otimização e melhoria. Neste tipo de companhia, encontramos diversas cadeias de suprimento subjacentes ao processo, que por seu porte e complexidade, seriam consideradas principais em diversas outras indústrias ou ramos de serviços. Neste contexto, a presente dissertação se propõe a analisar as etapas e percalços para implantação e manutenção de um software de roteirização como ferramenta para planejamento de frota e rota de transporte de funcionários em regime de turno de uma refinaria. O cenário escolhido para o piloto é uma refinaria de grande porte do estado do Rio de Janeiro. O estudo revisa a bibliografia existente, descreve as principais etapas de coleta e tratamento de dados, mede através do software TRANSCAD as distâncias das rotas propostas e verifica se o potencial ganho obtido em relação à solução em análise justificaria a aquisição de uma ferramenta para este fim. / [en] As in many big oil and gas companies, there are a lot of opportunities to search and find logistics processes with real possibilities for optimization and improvement. In this kind of company there are some supply chains, that are not core chains wich could be considered as main chains in many other industries or service areas due to their size and complexity. Regarding that issue, the present work proposes to analyze the steps and problems related to launching and maintaining a routing software as a solution for vehicle fleet planning and refinery s employees transportation routing. A big refinery placed in Rio de Janeiro state is the chosen scenario. This study reviews the present literature on the theme, describes the main steps on this research and data treatment, uses the software TRANSCAD to measure de length of the proposed routes and finds out if the potential gain with the software solution justifies the acquisition of this tool.

Les métaheuristiques sont des techniques d’optimisation indépendantes des problèmes traités. Elles ne profitent pas d’une spécificité du problème et, par conséquent, peuvent fournir des cadres généraux qui peuvent être appliqués a de nombreuses classes de problèmes. Les métaheuristiques peuvent fournir une stratégie de guidage dans la conception des heuristiques pour résoudre des problèmes d’optimisation spécifiques. Leur utilisation dans de nombreuses applications montre leur efficacité pour résoudre des problèmes importants et complexes. De nos jours, les métaheuristiques appliquées `a la solution des problèmes d’optimisation ont évolué vers l’intégration d’autres techniques d’optimisation, de sorte que les méthodes de résolution peuvent bénéficier des avantages de chacune des composantes. Le travail dans cette thèse vise à contribuer à l’étude des problèmes de tournées de véhicules avec des visites optionnelles en fournissant un opérateur à base de programmation dynamique intégré dans un processus métaheuristique générique. L’opérateur récupère le tour optimal de clients à visiter, répondant aux contraintes du problème, tout en optimisant l’objectif défini. L’opérateur pose le problème de la sélection des meilleurs clients `a visiter comme un problème de plus court chemin avec contraintes de ressources sur un graphe auxiliaire dirigé acyclique représentant les choix de visite possibles. Dans les problèmes de tournées de véhicules avec des visites optionnelles, les clients à servir ne sont pas connus a priori et cela rend plus difficile à résoudre le problème qu’un problème de routage classique qui est lui-même déjà NP-difficile. Les problèmes de tournées avec des visites optionnelles trouvent des applications dans des domaines multiples et variés tels que la conception de la distribution, la logistique humanitaire, la prestation des soins de santé, le tourisme, le recrutement, la collection ou la livraison de marchandises et patrouille en milieu urbain / Metaheuristics are problem independent optimisation techniques. As such, they do not take advantage of any specificity of the problem and, therefore, can provide general frameworks that may be applied to many problem classes. These iterative upper level methodologies can furnish a guiding strategy in designing subordinate heuristics to solve specific optimisation problems. Their use in many applications shows their efficiency and effectiveness to solve large and complex problems. Nowadays, metaheuristics applied to the solution of optimisation problems have shifted towards integrating other optimisation techniques, so that solution methods benefit from the advantages each offers. This thesis seeks to contribute to the study of vehicle routing problems with optional visits by providing a dynamic programming-based operator that works embedded into a generic metaheuristic. The operator retrieves the optimal tour of customers to visit, satisfying the side constraints of the problem, while optimising the defined objective. The operator formulates the problem of selecting the best customers to visit as a Resource Constrained Elementary Shortest Path Problem on an auxiliary directed acyclic graph where the side restrictions of the problem considered act as the constraining resource. In vehicle routing problems with optional visits, the customers to serve are not known a priori and this fact leaves a more difficult to solve problem than a classic routing problem, which per se is already NP-hard. Routing problems with optional visits find application in multiple and diverse areas such as bimodal distribution design, humanitarian logistics, health care delivery, tourism, recruitment, hot rolling production, selected collection or delivery, and urban patrolling among others

L'étude menée dans cette thèse porte sur la logistique multi-objectif des déchets ménagers. Elle s'est déroulée en partenariat avec une collectivité locale, la Communauté d'Agglomération du Muretain (CAM) située près de Toulouse qui nous a fournit les problématiques et les différents paramètres à prendre en compte pour le développement de l'étude. Cette thèse s'est déroulée au sein de deux équipes, dans l'équipe de Production Automatisé (PA) du Laboratoire de Génie de Production (LGP) de Tarbes ainsi que dans l'équipe de Modélisation d'Optimisation et de Gestion Intégrée de Systèmes d'Activités (MOGISA) du Laboratoire d'Analyse et d'Architecture des Systèmes (LAAS) de Toulouse. Il y a une trentaine d'année, le traitement des déchets se résumait à une simple mise en décharge. Depuis une conscience collective des problématiques environnementales a placé le traitement des déchets au cœur des préoccupations publiques. La gestion qui est faite des déchets ménagers constitue un enjeu environnemental, économique, social et de citoyennetés majeures, directement lié aux modes de consommation et à la société plus généralement. En France, les municipalités ou les collectivités locales, regroupant plusieurs municipalités, ont en charge de collecter et de convoyer les déchets vers leur lieu de traitement. Dans l'étude proposée, nous allons nous intéresser à la partie logistique, et plus précisément à la collecte et au transport des déchets ménagers et assimilés jusqu’à leur point de décharge (déchetteries, centre de transfert ou centre de traitement directement). Le but étant d’optimiser le transport de déchets tout en gardant une bonne qualité de service. Les enjeux mis en relief pour cette problématique sont les enjeux classiques imposés par toute étude visant à améliorer un service publique : un enjeu économique classique (minimiser les coûts de collecte et de transport), un enjeu environnemental évident (diminuer l'impact environnemental), un enjeu de qualité (satisfaire au mieux les usagers) et enfin un enjeu social (satisfaire les conditions de travail des employés). On va donc ici se concentrer sur l’aspect opérationnel journalier de la gestion. Lorsque celui-ci concerne une planification de trajet pour plusieurs véhicules en même temps qui doivent chacun faire leur circuit en livrant une certaine quantité de produit à chaque client cela se nomme le problème de tournées de véhicules (Vehicle Routing Problem). Ce problème pratique est souvent étudié pour des cas réels et se complexifie avec l’ajout de nombreux paramètres et contraintes, comme par exemple des contraintes d'horaire de passage sur certaines parties du réseau ; ou encore par l'ajout de plusieurs critères à optimiser en mêmes temps, comme par exemple les critères représentant les coûts et ceux représentant l'équilibrage de tournées, etc. / The study in this thesis focuses on the multipurpose logistics of household waste.

This thesis is aimed on time frame distribution task. In the theoretical part is described the mathematical model of this task and introduced in detail two concrete heuristics: greedy look-ahead and AKRed. In the practical part of the thesis has been a real situation solved with using of sophisticated optimalization software and through own implemented heuristic. These two solution are then compared each other and applicability of each heuristics for the given real problem is evaluated.

Cette thèse porte sur la résolution de problèmes de transport qui intègrent des contraintes temporelles considérant les fenêtres de temps, la synchronisation des visites et l’équilibrage des services. Ces problèmes trouvent plusieurs applications dans le monde réel.L’objectif de nos recherches est l’élaboration de nouvelles méthodes de résolution pour les problèmes considérés en examinant leur performance avec une étude comparative par rapport aux différentes approches de la littérature. Deux variantes sont traitées. Le premier cas étudie le Problème de Tournées de Véhicules avec Fenêtres de Temps (VRPTW). Nous proposons de nouveaux prétraitements et bornes inférieures pour déterminer le nombre de véhicules nécessaires en s’inspirant de travaux menés en ordonnancement (raisonnement énergétique) et d’autres problèmes combinatoires comme la clique maximum et les problèmes de bin-packing. Nous présentons également un algorithme d’optimisation par essaim particulaire qui traite de la minimisation du nombre de véhicules puis de celle du temps de trajet total. Le deuxième cas étudie le Problème de Tournées de Véhicules avec des Fenêtres de Temps et des Visites Synchronisées (VRPTWSyn). Nous proposons plusieurs méthodes basées sur des approches heuristiques et des formulations linéaires avec l’incorporation d’inégalités valides pour tenir compte de la contrainte de synchronisation. / This dissertation focuses on vehicle routing problems, one of the major academic problems in logistics. We address NP-Hard problems that model some realworld situations particularly those with different temporal constraints including time windows, visit synchronization and service balance.The aim of this research is to develop new algorithms for the considered problems,investigate their performance and compare them with the literature approaches.Two cases are carried out. The first case studies the Vehicle Routing Problem with Time Windows (VRPTW). We propose new lower bound methods for the number of vehicles. Then we present a Particle Swarm Optimization algorithm dealing with the Solomon objective. The second case studies the VehicleRouting Problem with Time Windows and Synchronized Visits (VRPTWsyn).Both exact methods and heuristics are proposed and compared to the literature approaches.

This thesis is continuation of the bachelor thesis "Model of delivery routes and placement logistics centers with opportunities of their optimization". It is about distribution problems and specifically a vehicle routing problem. The aim of this thesis is finding a solution of the vehicle routing problem which will be used repeatedly in the firm. The main task is achieving the lowest costs (total kilometers) with maximum utilization of vehicle capacity; in such conditions that all requirements of logistics centers will be satisfied and maximal capacity of vehicle will be tolerated. For calculation was used a solver Gurobi 6.0.3 in system MPL for Windows 4.2, which won't, however, provide the optimal solution and problem solving takes too long time. Next for calculation was used heuristics insert method and is written by VBA (Visual Basic for Applications) in MS Excel. Finally, there is a comparison of these methods with the original solution of the vehicle routing plan and solution of the bachelor thesis. Then the computational experiment was done, which tested effect to result, if other distribution center (starting point) will be bulit. The computational experiment was consist from heuristic insert method, solver Gurobi and heuristic saving algorithm from bachelor thesis.

In this paper,we propose an adaptive large neighborhood search heuristic for the Two-Echelon Vehicle Routing Problem (2E-VRP) and the Location Routing Problem (LRP).The 2E-VRP arises in two-level transportation systems such as those encountered in the context of city logistics. In such systems, freight arrives at a major terminal and is shipped through intermediate satellite facilities to the final customers. The LRP can be seen as a special case of the 2E-VRP in which vehicle routing is performed only at the second level. We have developed new neighborhood search operators by exploiting the structure of the two problem classes considered and have also adapted existing operators from the literature. The operators are used in a hierarchical scheme reflecting the multi-level nature of the problem. Computational experiments conducted on several sets of instances from the literature show that our algorithm out performs existing solution methods for the 2E-VRP and achieves excellent results on the LRP.

No description available.