Segui questo link per vedere altri tipi di pubblicazioni sul tema: Rich Vehicle Routing Problems.
Tesi sul tema "Rich Vehicle Routing Problems"
Cita una fonte nei formati APA, MLA, Chicago, Harvard e in molti altri stili
Vedi i top-50 saggi (tesi di laurea o di dottorato) per l'attività di ricerca sul tema "Rich Vehicle Routing Problems".
Accanto a ogni fonte nell'elenco di riferimenti c'è un pulsante "Aggiungi alla bibliografia". Premilo e genereremo automaticamente la citazione bibliografica dell'opera scelta nello stile citazionale di cui hai bisogno: APA, MLA, Harvard, Chicago, Vancouver ecc.
Puoi anche scaricare il testo completo della pubblicazione scientifica nel formato .pdf e leggere online l'abstract (il sommario) dell'opera se è presente nei metadati.
Vedi le tesi di molte aree scientifiche e compila una bibliografia corretta.
1
Quintero, Araújo Carlos Leonardo. "Applications of simheuristics and horizontal cooperation concepts in rich vehicle routing problems". Doctoral thesis, Universitat Oberta de Catalunya, 2017. http://hdl.handle.net/10803/460831.
Testo completoAbstract (sommario):
En una economia globalitzada, les companyies s’enfronten a nombrosos reptes associats a les complexes tasques de logística i distribució. Gràcies al desenvolupament de les tecnologies de la informació i la comunicació, els clients es troben en qualsevol part del món, però també els competidors. Per tant, les companyies necessiten ser més competitives, cosa que implica eficiència econòmica i sostenibilitat. Una estratègia que les firmes poden seguir per a ser més competitives és la cooperació horitzontal, que genera economies d’escala, increment en la utilització de recursos i reducció de costos. Molts d’aquests reptes en logística i transport, així com algunes estratègies de cooperació horitzontal, es poden abordar mitjançant diferents variants del conegut problema d’encaminament de vehicles (VRP). Malgrat que el VRP ha estat àmpliament estudiat, la majoria dels treballs publicats corresponen a versions massa simplificades de la realitat. Per a omplir aquest buit entre la teoria i les aplicacions de la vida real, fa poc que ha sorgit el concepte de problemes «enriquits» d’encaminament de vehicles (RVRP). Per tant, es necessiten nous mètodes de solució per a resoldre eficientment nous RVRP, així com per a quantificar els beneficis generats per la implementació d’estratègies de cooperació horitzontal en aplicacions reals, de manera que es puguin fer servir com a suport per a la presa de decisions. Per a abordar aquesta varietat de problemes es proposen diferents metaheurístiques basades en aleatorització esbiaixada. Aquests mètodes es combinen amb simulació (fet que es coneix com simheurístiques) per a resoldre situacions en les quals apareix la incertesa. Els mètodes proposats han estat avaluats utilitzant instàncies de prova tant teòriques com de la vida real.En una economía globalizada, las compañías se enfrentan a numerosos retos asociados a las complejas tareas de logística y distribución. Gracias al desarrollo de las tecnologías de la información y la comunicación, los clientes se encuentran en cualquier lugar del mundo, pero también los competidores. Por lo tanto, las compañías necesitan ser más competitivas, lo que implica eficiencia económica y sostenibilidad. Una estrategia que las firmas pueden seguir para ser más competitivas es la cooperación horizontal, generando así economías de escala, incremento en la utilización de recursos y reducción de costes. Muchos de estos retos en logística y transporte, así como algunas estrategias de cooperación horizontal, pueden abordarse mediante diferentes variantes del conocido problema de enrutamiento de vehículos (VRP). Pese a que el VRP ha sido ampliamente estudiado, la mayoría de los trabajos publicados corresponden a versiones simplificadas de la realidad. Para llenar este vacío entre la teoría y las aplicaciones de la vida real, recientemente ha surgido el concepto de problemas «enriquecidos» de enrutamiento de vehículos (RVRP). Por lo tanto, se necesitan nuevos métodos de solución para resolver de forma eficiente nuevos RVRP, así como para cuantificar los beneficios generados por la implementación de estrategias de cooperación horizontal en aplicaciones reales, de modo que puedan usarse como apoyo para la toma de decisiones. Para abordar tal variedad de problemas se proponen diferentes metaheurísticas basadas en aleatorización sesgada. Estos métodos se combinan con simulación (lo que se conoce como simheurísticas) para resolver situaciones en las que aparece la incertidumbre. Los métodos propuestos han sido evaluados utilizando instancias de prueba tanto teóricas como de la vida real.
In a globalized economy, companies have to face different challenges related to the complexity of logistics and distribution strategies. Due to the development of information and communication technologies (ICT), customers and competitors may be located anywhere in the world. Thus, companies need to be more competitive, which entails efficiency from both an economic and a sustainability point of view. One strategy that companies can follow to become more competitive is to cooperate with other firms, a strategy known as horizontal cooperation (HC), allowing the use of economies of scale, increased resource utilization levels, and reduced costs. Many of these logistics and transport challenges, as well as certain HC strategies, may be addressed using variants of the vehicle routing problem (VRP). Even though VRP has been widely studied, the majority of research published corresponds to oversimplified versions of the reality. To fill the existing gap between the academic literature and real-life applications, the concept of rich VRPs (RVRPs) has emerged in the past few years in order to provide a closer representation of real-life situations. Accordingly, new approaches are required to solve new RVRPs efficiently and to quantify the benefits generated through the use of HC strategies in real applications. Thus, they can be used to support decision-making processes regarding different degrees of implementation of HC. Several metaheuristic methods based on biased randomization techniques are proposed. Additionally, these methods are hybridized with simulation (ie simheuristics) to tackle the presence of uncertainty. The proposed approaches are tested using a large set of theoretical and real-life benchmarks.
2
Vogel, Ulrich [Verfasser]. "A flexible metaheuristic framework for solving rich vehicle routing problems / Ulrich Vogel". Aachen : Shaker, 2012. http://d-nb.info/1069048984/34.
Testo completo
3
Cáceres, Cruz José de Jesús. "Randomized Algorithms for Rich Vehicle Routing Problems: From a Specialized Approach to a Generic Methodology". Doctoral thesis, Universitat Oberta de Catalunya, 2013. http://hdl.handle.net/10803/127153.
Testo completoAbstract (sommario):
El Problema de Enrutamiento de Vehículos (VRP) y sus diferentes variantes básicas son un dominio ampliamente estudiado en la comunidad científica de optimización. Algunos estudios han utilizado combinaciones específicas de restricciones encontradas en la vida real para definir los emergentes VRP Enriquecidos. Este trabajo aborda la integración de heurísticas, probabilidad sesgada, simulación, técnicas de computación distribuida & paralelas, y programación con restricciones. Los enfoques propuestos han solucionado algunas variantes del VRP: en primer lugar, las familias deterministas: VRP con flotas Heterogéneas (HVRP), VRP con flotas Heterogéneas y costo variable (HVRP-V), VRP con flota Heterogénea y Múltiples viajes (HVRPM), VRP con matriz de costo Asimétrica (AVRP), VRP con flota Heterogénea y matriz de costo Asimétrica (HAVRP), VRP con ventanas de Tiempo (VRPTW), y VRP Distancia limitada (DCVRP); en segundo lugar, las familias de naturaleza estocástica: VRP con Demandas estocásticas (VRPSD), y Problemas de Inventario y Enrutamiento de Vehículos con Demandas estocásticas (IRPSD). Una extensa revisión bibliográfica se ha realizado para cada una de estas variantes. Un primer enfoque propone la combinación de una aleatorización sesgada con heurísticas clásicas para la solución de problemas deterministas. Un segundo enfoque se centra en la combinación de heurísticas aleatorias con simulación (Simheuristics) para ser aplicados sobre los problemas estocásticos comentados. Por último, se propone un tercer enfoque basado en el trabajo conjunto de heurísticas aleatorias con programación de restricciones para resolver varios tipos de problemas de enrutamiento. Los algoritmos heurísticos desarrollados han sido aplicados en varios casos de referencia --entre ellos, dos estudios de casos reales de distribución en España-- y los resultados obtenidos son, en general, prometedores y útiles para los decisores.The Vehicle Routing Problem (VRP) is a well known domain in optimization research community. Its different basic variants have been widely explored in the literature. Some studies have considered specific combinations of real-life constraints to define the emerging Rich VRP scopes. This work deals with the integration of heuristics, biased probability, simulation, parallel & distributed computing techniques, and constraint programming. The proposed approaches are tested for solving some variants of VRPs, namely, first, the deterministic families: Heterogeneous VRP (HVRP), Heterogeneous VRP with Variable cost (HVRP-V), Heterogeneous fleet VRP with Multi-trips (HVRPM), Asymmetric cost matrix VRP (AVRP), Heterogeneous fleet with Asymmetric cost matrix VRP (HAVRP), VRP with Time Windows (VRPTW), and Distance-Constrained VRP (DCVRP); second, the stochastic nature families: VRP with Stochastic Demands (VRPSD), and Inventory Routing Problem with Stochastic Demands (IRPSD). An extensive literature review is performed for all these variants, focusing on the main contributions of each work. A first approach proposes a biased-randomization of classical heuristics for solving the deterministic problems addressed here. A second approach is centered on the combination of randomized heuristics with simulation (Simheuristics) to be applied on the commented stochastic problems. Finally, a third approach based on the joined work of randomized heuristics with constraint programming is proposed to solve several types of routing problems. The developed heuristic algorithms are tested in several benchmark instances --between these, two real-life case studies in Spain are considered-- and the results obtained are, on average, highly promising and useful for decision makers.
4
Seixas, Michel Povlovitsch. "Heuristic and exact methods applied to a rich vehicle routing and scheduling problem". Universidade de São Paulo, 2013. http://www.teses.usp.br/teses/disponiveis/3/3135/tde-09072014-111258/.
Testo completoAbstract (sommario):
This study considers a vehicle routing problem with time windows, accessibility restrictions on customers and a fleet that is heterogeneous with regard to capacity, average speed and cost. A vehicle can perform multiple routes per day, all starting and ending at a single depot, and it is assigned to a single driver, whose total work hours are limited. The available fleet is divided into an owned fleet, for which a variable cost is incurred, and a chartered fleet, for which only a fixed cost is incurred for each vehicle used. A column generation algorithm embedded in a branch-and-bound framework is proposed. The column generation pricing subproblem required a specific elementary shortest path problem with resource constraints algorithm to address the possibility for each vehicle performing multiple routes per day and to address the need to determine the workdays start time within the planning horizon. To make the algorithm efficient, a constructive heuristic and a learning metaheuristic algorithm based on tabu search were also developed. Both were used on branch-and-bound tree nodes to generate a good initial solution to the linear restricted master problem; particularly, to find a good initial primal bound to the branch-and-bound tree.Este estudo aborda um problema de roteirização de veículos com janelas de tempo, restrições de acessibilidade nos clientes e uma frota que é heterogênea em relação à capacidade de carga, velocidade média de deslocamento e custo. Um veículo pode percorrer múltiplas rotas por dia, todas começando e terminando em um mesmo depósito, e está designado a um único motorista, cujo total de horas trabalhadas no dia está limitado a um valor máximo. A frota disponível é dividida em uma frota própria, para a qual um custo variável é incorrido, e uma frota de freteiros, para a qual apenas um custo fixo é incorrido para cada veículo utilizado. Um algoritmo baseado em geração de colunas, integrado a um procedimento de branch-and-bound, é proposto neste estudo. O subproblema de precificação da geração de colunas requereu um algoritmo específico para o problema do caminho mínimo elementar com restrições sobre recursos capaz de lidar com a possibilidade de cada veículo percorrer múltiplas rotas por dia e capaz de lidar com a necessidade de determinar o instante de início do dia de trabalho do motorista dentro do horizonte de planejamento. Para tornar o algoritmo eficiente, uma heurística construtiva e uma heurística de melhoria baseada em busca tabu também foram desenvolvidos. Ambos são utilizados nos nós da árvore de branch-and-bound para gerar boas soluções iniciais para o problema mestre restrito da geração de colunas; particularmente, para encontrar um bom limitante primal inicial para a árvore de branch-and-bound.
5
Vogel, Ulrich [Verfasser], Ulrich [Akademischer Betreuer] Derigs e Dirk [Akademischer Betreuer] Briskorn. "A flexible metaheuristic framework for solving rich vehicle routing problems : Formulierung, Implementierung und Anwendung eines kognitionsbasierten Simulationsmodells / Ulrich Vogel. Gutachter: Ulrich Derigs ; Dirk Briskorn". Köln : Universitäts- und Stadtbibliothek Köln, 2011. http://d-nb.info/1038360595/34.
Testo completo
6
Vogel, Ulrich [Verfasser], Ulrich Akademischer Betreuer] Derigs e Dirk [Akademischer Betreuer] [Briskorn. "A flexible metaheuristic framework for solving rich vehicle routing problems : Formulierung, Implementierung und Anwendung eines kognitionsbasierten Simulationsmodells / Ulrich Vogel. Gutachter: Ulrich Derigs ; Dirk Briskorn". Köln : Universitäts- und Stadtbibliothek Köln, 2011. http://d-nb.info/1038360595/34.
Testo completo
7
Pullmann, Markus Dirk [Verfasser]. "Untersuchungen zu Rich Vehicle Routing Problemen im Supply Chain Management : Neue algorithmische Strategien und spezifische Problemstellungen / Markus Dirk Pullmann". Aachen : Shaker, 2014. http://d-nb.info/1058315439/34.
Testo completo
8
Pullmann, Markus [Verfasser]. "Untersuchungen zu Rich Vehicle Routing Problemen im Supply Chain Management : Neue algorithmische Strategien und spezifische Problemstellungen / Markus Dirk Pullmann". Aachen : Shaker, 2014. http://nbn-resolving.de/urn:nbn:de:101:1-201409147581.
Testo completo
9
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.
Testo completoAbstract (sommario):
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
10
Zhang, Xinglong. "Network vehicle routing problems". Diss., Georgia Institute of Technology, 1998. http://hdl.handle.net/1853/21710.
Testo completo
11
Jézéquel, Antoine. "Probabilistic vehicle routing problems". Thesis, Massachusetts Institute of Technology, 1985. http://hdl.handle.net/1721.1/15318.
Testo completoAbstract (sommario):
Thesis (M.S.)--Massachusetts Institute of Technology, Dept. of Civil Engineering, 1985.MICROFICHE COPY AVAILABLE IN ARCHIVES AND ENGINEERING.
Bibliography: leaves 78-79.
by Antoine Jézéquel.
M.S.
12
Villegas, Juan Guillermo. "Vehicle routing problems with trailers". Troyes, 2010. http://www.theses.fr/2010TROY0027.
Testo completoAbstract (sommario):
Les problèmes de tournées de véhicules forment une classe de problèmes d’optimisation combinatoire avec des applications dans de nombreux domaines comme la distribution de marchandises et l’exécution de services. Cette thèse en trois parties étudie des problèmes de tournées où la capacité des véhicules peut être augmentée par des remorques détachables. La première partie est consacrée à un problème noté STTRPSD, dans lequel un camion avec une remorque détachable doit visiter à partir d’un dépôt des clients accessibles par le camion sans sa remorque. La remorque doit donc être laissée temporairement sur certains nœuds du réseau. Pour ce problème, nous avons développé trois heuristiques, deux métaheuristiques de type GRASP et recherche locale évolutionnaire, et une méthode exacte de type branchement et coupes. La deuxième partie traite un problème nommé TTRP, qui étend le STTRPSD à plusieurs véhicules hétérogènes et à des clients accessibles ou non avec les remorques. Pour le résoudre, nous avons conçu deux méthodes : (i) une métaheuristique hybride combinant un GRASP, une recherche à voisinage variable et un « path relinking » ; et (ii) une matheuristique qui utilise les optimal locaux produits par un GRASP/VNS pour résoudre un problème de partitionnement à l’aide d’un solveur commercial. Enfin, la troisième partie présente une librairie orientée objet pour le prototypage rapide de méthodes heuristiques basées sur le principe « route-first, cluster-second ». Cette librairie fournit des composants logiciels réutilisables qui peuvent être adaptés pour gérer différentes extensionsVehicle routing problems (VRPs) are a class of combinatorial optimization problems with application in many different domains ranging from the distribution of goods to the delivery of ser-vices. In this thesis we have studied VRPs in which the capacity of the vehicles is increased with the use of detachable trailers. This thesis comprises three parts. The first part is devoted to the single truck and trailer routing problem with satellite depots (STTRPSD), where a single truck with a detach-able trailer based at a depot serves the demand of a set of customers accessible only by truck. For this problem we have developed three heuristics, two metaheuristics based on GRASP and evolutionary local search, and an exact branch-and-cut algorithm. The second part addresses the truck and trailer routing problem (TTRP) that models the multi-vehicle case, where a heterogeneous fixed fleet of trucks and trailers is used to serve the demand of a set of customers, some of them with accessibility restrictions. To solve the TTRP we have developed two methods: (i) a hybrid metaheuristic combining GRASP, variable neighborhood search (VNS) and path relinking; and (ii) a matheuristic that uses the routes of the local optima produced by a GRASP/VNS to solve a set-partitioning formulation of the TTRP with a commercial optimizer. Finally, the third part presents an object-oriented framework for the rapid prototyping of heuristic methods based on the route-first, cluster-second principle. This framework provides a set of reusable components that can be adapted to tackle different VRP extensions
13
Kefalidou, Genovefa. "Cognitive processes and vehicle routing problems". Thesis, Lancaster University, 2011. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.654458.
Testo completoAbstract (sommario):
Experiments were conducted to investigate the way humans solve Capacitated Vehicle Routing Problems (CVRPs), a problem class in which the shortest set of tours must be found around a set of weighted nodes using a capacity-limited vehicle. The first two experiments explored human performance in drawing solutions to problems of different complexity in terms of number of routes, nodes and weights to be summed. They also included as an experimental factor Verbalisation, both to provide a qualitative indicator of performance and also to examine the impact of verbalisation on performance. The qualitative results of Experiment 1 indicated two major types of strategists: Calculators and Clusterers. Clusterers performed faster and in some of the problems found solutions closer to the optimal than calculators. The major errors that participants performed were errors of calculation, nodes missing and drawing too few routes. Results from Experiment 2 suggest that humans are showing the best performance in problems with low calculation demands while they exhibit the worst performance in the problems with negligible calculation demands, thus suggesting that in order to provide very close to optimal solutions in CVRPs it is necessary to retain some calculation demand load to promote a more optimising behaviour. New strategies have been revealed in Experiment 2 and Verbalisation again did not influence the human performance. Further qualitative and quantitative analyses of the verbalisations and human performance in Experiment 1 showed that Visuospatial strategies such as Anchoring and Clustering are predictors of good performance while Arithmetic strategies such as Balancing generate poor performance. In Experiment 2, the best performances were exhibited when participants were using either Visuospatial strategies or Arithmetic strategies. The success and failure of the adoption of these strategies is dependant on the problem complexity and the cognitive load. A third 14 ..... ------------.~~-~~~ -- experiment revealed that error-trapping did not influence the human performance. The results informed the specification and design of a Capacitated Vehicle Routing Problem Solver implemented in Java. A pilot study was completed that led to a revaluation of the software. A later version was implemented and tested empirically. Experiment 4 revealed that humans interaction with the Capacitated Vehicle Routing Problem Solver to solve CVRPs significantly improved their performance leading to the generation of very close to optimal routes.
14
Lafifi, Sohaib. "Vehicle routing problems with resources synchronization". Thesis, Compiègne, 2014. http://www.theses.fr/2014COMP1992.
Testo completoAbstract (sommario):
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 synchronisationThis 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
15
Roberts, Daron R. "Algorithms for stochastic vehicle routing problems". Thesis, Imperial College London, 1999. http://hdl.handle.net/10044/1/11887.
Testo completo
16
Hintsch, Timo [Verfasser]. "On Clustered Vehicle-Routing Problems / Timo Hintsch". Mainz : Universitätsbibliothek Mainz, 2020. http://d-nb.info/1206563966/34.
Testo completo
17
Ben, Ticha Hamza. "Vehicle Routing Problems with road-network information". Thesis, Université Clermont Auvergne (2017-2020), 2017. http://www.theses.fr/2017CLFAC071/document.
Testo completoAbstract (sommario):
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éeVehicle 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
18
Qiu, Shengli. "Airline crew pairing optimization problems and capacitated vehicle routing problems". Diss., Georgia Institute of Technology, 2012. http://hdl.handle.net/1853/51717.
Testo completoAbstract (sommario):
Crew pairing and vehicle routing are combinatorial optimization problems that have been studied for many years by researchers worldwide. The aim of this research work is to investigate effective methods for solving large scale crew pairing problems and vehicle routing problems. In the airline industry, to address the complex nature of crew pairing problems, we propose a duty tree method followed by a primal-dual subproblem simplex method. The duty tree approach captures the constraints that apply to crew pairings and generate candidate pairings taking advantage of various proposed strategies. A huge number of legal pairings are stored in the duty tree and can be enumerated. A set partitioning formulation is then constructed, and the problem is solved using a primal-dual subproblem simplex method tailored to the duty tree approach. Computational experiments are conducted to show the effectiveness of the methods. We also present our efforts addressing the capacitated vehicle routing problem (CVRP) that is the basic version of many other variants of the problem. We do not attempt to solve the CVRP instances that have been solved to optimality. Instead, we focus on investigating good solutions for large CVRP instances, with particular emphasis on those benchmark problems from the public online library that have not yet been solved to optimality by other researchers and determine whether we can find new best-known solutions. In this research, we propose a route network that can store a huge number of routes with all routes being legal, a set partitioning formulation that can handle many columns, and the primal-dual subproblem simplex method to find a solution. The computational results show that our proposed methods can achieve better solutions than the existing best-known solutions for some difficult instances. Upon convergence of the primal-dual subproblem simplex method on the giant-tour based networks, we use the near optimal primal and dual solution as well as solve the elementary shortest path problem with resource constraints to achieve the linear programming relaxation global optimal solution.
19
Kenyon, Astrid Sandrine. "Stochastic vehicle routing problems with random travel times /". Digital version accessible at:, 1998. http://wwwlib.umi.com/cr/utexas/main.
Testo completo
20
Groër, Christopher. "Parallel and serial algorithms for vehicle routing problems". College Park, Md.: University of Maryland, 2008. http://hdl.handle.net/1903/9011.
Testo completoAbstract (sommario):
Thesis (Ph.D.) -- University of Maryland, College Park, 2008.Thesis research directed by: Applied Mathematics and Scientific Computation. Title from t.p. of PDF. Includes bibliographical references. Published by UMI Dissertation Services, Ann Arbor, Mich. Also available in paper.
21
Garcia, Najera Abel. "Multi-Objective evolutionary algorithms for vehicle routing problems". Thesis, University of Birmingham, 2010. http://etheses.bham.ac.uk//id/eprint/1069/.
Testo completoAbstract (sommario):
The Vehicle Routing Problem, which main objective is to find the lowest-cost set of routes to deliver goods to customers, has many applications in transportation services. In the past, costs have been mainly associated to the number of routes and the travel distance, however, in real-world problems there exist additional objectives. Since there is no known exact method to efficiently solve the problem in polynomial time, many heuristic techniques have been considered, among which, evolutionary methods have proved to be suitable for solving the problem. Despite this method being able to provide a set of solutions that represent the trade-offs between multiple objectives, very few studies have concentrated on the optimisation of more than one objective, and even fewer have explicitly considered the diversity of solutions, which is crucial for the good performance of any evolutionary computation technique. This thesis proposes a novel Multi-Objective Evolutionary Algorithm to solve two variants of the Vehicle Routing Problem, regarding the optimisation of at least two objectives. This approach incorporates a method for measuring the similarity of solutions, which is used to enhance population diversity, and operators that effectively explore and exploit the search space. The algorithm is applied to typical benchmark problems and empirical analyses indicate that it efficiently solves the variants being studied. Moreover, the proposed method has proved to be competitive with recent approaches and outperforms the successful multi-objective optimiser NSGA-II.
22
Chervi, Philippe. "A computational approach to probabilistic vehicle routing problems". Thesis, Massachusetts Institute of Technology, 1990. http://hdl.handle.net/1721.1/14262.
Testo completoAbstract (sommario):
Thesis (M.S.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1990.Includes bibliographical references (leaves 125-128).
by Philippe Chervi.
M.S.
23
Pereira, Coutinho Walton. "Unmanned Aerial Vehicle routing and trajectory optimisation problems". Thesis, University of Southampton, 2018. https://eprints.soton.ac.uk/426341/.
Testo completoAbstract (sommario):
In recent years, employing Unmanned Aerial Vehicles (UAV) to collect data and making measurements has gained popularity. Often, the use of UAVs allows for a reduction in costs and improvements of other performance criteria. The academic routing community has acknowledged the interest of companies and organisations in adopting UAVs in their operations. However, constraints due to the flight dynamics of UAVs have often been neglected. Finding feasible trajectories for UAVs in a routing problem is a complex task, but it is necessary to ensure the feasibility of the routes. In this thesis we introduce the Unmanned Aerial Vehicle Routing and Trajectory Optimisation Problem (UAVRTOP), the problem of optimising the routes and trajectories of a fleet of UAVs subject to flight dynamics constraints. Motivated by a disaster assessment application, we propose a variant of the UAVRTOP, in which a fleet of autonomous aerial gliders is required to photograph a set of points of interest in the aftermath of a disaster. This problem is referred to as the Glider Routing and Trajectory Optimisation Problem (GRTOP). In this work, we propose a single-phase Mixed-Integer Non-linear Programming (MINLP) formulation for the GRTOP. Our formulation simultaneously optimises routes and the flight trajectories along these routes while the flight dynamics of the gliders are modelled as ordinary differential equations. We avoid dealing with non-convex dynamical constraints by linearising the gliders’ Equations of Motion (EOMs), reducing the proposed MINLP into a Mixed-Integer Second-Order Cone Programming (MISOCP) problem. Another contribution of this work consists of proposing a multi-phase MINLP formulation for a modified version of the GRTOP. We do not attempt to solve this formulation directly, instead we propose a hybrid heuristic method that is composed of two main building blocks: (i) a Sequential Trajectory Optimisation (STO) heuristic, designed to cope with the challenging task of finding feasible (flyable) trajectories for a given route; and (ii) a routing matheuristic, capable of generating routes that can be evaluated by STO. We perform computational experiments with real-life instances based on flood risk maps of cities in the UK as well as in a large number of randomly generated instances.
24
Cakir, Fahrettin. "Data-centric solution methodologies for vehicle routing problems". Diss., University of Iowa, 2016. https://ir.uiowa.edu/etd/2052.
Testo completoAbstract (sommario):
Data-driven decision making has become more popular in today’s businesses including logistics and vehicle routing. Leveraging historical data, companies can achieve goals such as customer satisfaction management, scalable and efficient operation, and higher overall revenue.
In the management of customer satisfaction, logistics companies use consistent assignment of their drivers to customers over time. Creating this consistency takes time and depends on the history experienced between the company and the customer. While pursuing this goal, companies trade off the cost of capacity with consistency because demand is unknown on a daily basis. We propose concepts and methods that enable a parcel delivery company to balance the trade-off between cost and customer satisfaction. We use clustering methods that use cumulative historical service data to generate better consistency using the information entropy measure.
Parcel delivery companies route many vehicles to serve customer requests on a daily basis. While clustering was important to the development of early routing algorithms, modern solution methods rely on metaheuristics, which are not easily deployable and often do not have open source code bases. We propose a two-stage, shape-based clustering approach that efficiently obtains a clustering of delivery request locations. Our solution technique is based on creating clusters that form certain shapes with respect to the depot. We obtain a routing solution by ordering all locations in every cluster separately. Our results are competitive with a state-of-the-art vehicle routing solver in terms of quality. Moreover, the results show that the algorithm is more scalable and is robust to problem parameters in terms of runtime.
Fish trawling can be considered as a vehicle routing problem where the main objective is to maximize the amount of fish (revenue) facing uncertainty on catch. This uncertainty creates an embedded prediction problem before deciding where to harvest. Using previous catch data to train prediction models, we solve the routing problem a fish trawler faces using dynamically updated routing decisions allowing for spatiotemporal correlation in the random catch. We investigate the relationship between the quality of predictions and the quality of revenue generated as a result.
25
Montoya, Jose-Alejandro. "Electric Vehicle Routing Problems : models and solution approaches". Thesis, Angers, 2016. http://www.theses.fr/2016ANGE0020/document.
Testo completoAbstract (sommario):
Étant donné leur faible impact environnemental, l’utilisation des véhicules électriques dans les activités de service a beaucoup augmenté depuis quelques années. Cependant, leur déploiement est freiné par des contraintes techniques telles qu’une autonomie limitée et de longs temps de charge des batteries. La prise en compte de ces contraintes a mené à l’apparition de nouveaux problèmes de tournées de véhicules pour lesquels, en plus d’organiser les tournées,il faut décider où et de combien charger les batteries. Dans cette thèse nous nous intéressons à ces problèmes au travers de quatre études. La première concerne le développement d’une métaheuristique en deux phases simple mais performante pour résoudre un problème particulier appelé "Green VRP”. Dans la seconde, nous nous concentrons sur la modélisation d’un aspect essentiel dans ces problèmes : le processus de chargement des batteries. Nous étudions différentes stratégies pour modéliser ce processus et montrons l’importance de considérer la nature non linéaire des fonctions de chargement. Dans la troisième étude nous proposons une recherche locale itérative pour résoudre des problèmes avec des fonctions de chargement non linéaires. Nous introduisons un voisinage dédié aux décisions de chargement basé sur un nouveau problème de chargement sur une tournée fixée. Dans la dernière étude, nous traitons un problème réel de tournées de techniciens avec des véhicules classiques et électriques. Ce problème est résolu par une métaheuristique qui décompose le problème en plusieurs sous-problèmes plus simples résolus en parallèle, puis qui assemble des parties des solutions trouvées pour construire la solution finaleElectric vehicles (evs) are one of the most promising technologies to reduce the greenhouse gas emissions. For this reason, the use of evs in service operations has dramatically increased in recent years. Despite their environmental benefits, evs still face technical constraints such as short autonomy and long charging times. Taking into account these constraints when planning ev operations leads to a new breed of vehicle routing problems (vrps), known as electricVrps (evrps). In addition, to the standard routing decisions, evrps are concerned with charging decisions: where and how much to charge. In this ph. D thesis, we address evrps through 4 different studies. In the first study, we tackle the green vehicle routing problem. To solve the problem, we propose a simple, yet effective, two-phase matheuristic. In the second study, we focus a key modelling aspects in evrps: the battery charging process. We study different strategies to model this process and show the importance of considering the nonlinear nature of the battery charging functions. InThe third study, we propose an iterated local search to tackle evrp with non-linear charging functions. We introduce a particular local search operator for the charging decisions based on a new fixedroute charging problem. The fourth and last study considers a real technician routing problem with conventional and electric vehicles (trp-cev). To tackle this problem, we propose a parallel matheuristic that decomposes the problem into a set of easier-to-solve subproblemsThat are solved in parallel processors. Then the approach uses parts of the solutions found to the subproblems to assemble final solution to the trp-cev
26
Herrero, Antón Rosa. "Hybrid methodologies for symmetric and asymmetric vehicle routing problems". Doctoral thesis, Universitat Autònoma de Barcelona, 2016. http://hdl.handle.net/10803/369581.
Testo completoAbstract (sommario):
En las últimas décadas, la globalización ha impulsado la adaptación del sector del Transporte y la Logística a las nuevas demandas sociales. Al mismo tiempo, el transporte ha sido la columna vertebral de la globalización. Esta necesidad social crea consumidores ambiciosos que necesitan sus productos de forma rápida y a un precio asequible muchas veces sin ser conscientes de su origen, el transporte o los aspectos medioambientales, entre otros factores. Sin embargo, para satisfacer las demandas del cliente, es necesario encontrar el modo de transporte más barato, que significa la mejora de la logística del transporte de estos productos. Por lo tanto, estas demandas requieren un servicio cada vez más flexible para satisfacer las necesidades del cliente, y, además, las empresas quieren un transporte eficiente y productivo.
Traveling Salesman Problems (TSP) and Vehicle Routing Problems (VRP) proporcionan el marco teórico para tratar este tipo de problemas logísticos relacionados con la distribución física de mercancías desde un almacén central hasta los clientes. Son dos de los problemas más desafiantes e investigados debido a su complejidad y aplicabilidad.
El objetivo principal de esta tesis doctoral es la introducción de metodologías híbridas que integran varias técnicas para resolver de manera eficiente rich VRPs con restricciones realistas. Esta tesis comienza con problemas teóricos y evoluciona hacia escenarios más realistas abordando un total de seis problemas combinatorios relacionados con el transporte por carretera.
Una metaheurística llamada Tailored Lagrangian Metaheuristic (TLM) se ha desarrollado para abordar el TSP. Está basa en la relajación de Lagrange que se utiliza para explotar la estructura del problema que reduce considerablemente su complejidad moviendo restricciones difíciles de satisfacer a la función objetivo, asociando una penalización en caso de que no se cumplen.
La metaheurística desarrollada para el TSP se ha integrado en dos metodologías híbridas combinadas con Constraint Programming para hacer frente a problemas más complejos. En primer lugar, el Capacitated Vehicle Routing Problem (CVRP), cuyos los vehículos tienen limitaciones de capacidad de carga de las mercancías que deben ser entregadas, es abordado. En segundo lugar, se ha abordado un problema real, Home Health Care (HHC), del servicio de Salud en el municipio de Ferrara, Italia. Este consiste en la asignación de los tratamientos de los pacientes a las enfermeras que viajan a las casas de los pacientes.
Investigaciones teóricas suelen asumir la simetría de los costes basados en la distancia de viajar de un lugar a otro y la existencia de una flota homogénea de vehículos con una misma capacidad. Esta tesis estudia diferentes variantes centradas en el impacto que causa la asimetría de los costes y la heterogeneidad de la flota. Para estos estudios, se abordan la versión con costes asimétricos del TSP y del CVRP -el Asymmetric Traveling Salesman Problem (ATSP) y el Asymmetric Capacitated Vehicle Routing Problem (ACVRP)- y la versión con flota heterogénea del ACVRP –el Asymmetric and Heterogeneous Vehicle Routing Problem (AHVRP).Over the last decades, globalization has driven the adaptation of the Transport and Logistics sector to new social demands. At the same time, transport has been the backbone of globalization. This social need creates ambitious consumers who need their products quickly and an affordable price often unaware of their origin, transport mode or environmental aspects, among other factors. Nevertheless, to satisfy customer demands, it is needed to find the cheapest transport mode, which in turn means the improvement of transport logistics of the products. Therefore, these demands require an increasingly flexible service to meet customer requirements, and in addition companies want an efficient and productive transport. The so called Traveling Salesman Problems (TSP) and Vehicle Routing Problems (VRP) provide the theoretical framework for approaching this class of logistic problems associated with the physical distribution of goods from a central depot to customers. They are two of the most challenging and researched problems because of their complexity and applicability. The main goal of this PhD thesis is to introduce hybrid methodologies that integrate several techniques to efficiently solve rich VRPs with realistic constraints. It starts with theoretical problems and evolves into more realistic scenarios tackling six combinatorial problems related to road transport. A metaheuristic named Tailored Lagrangian Metaheuristic (TLM) has been developed to tackle the TSP. It is based on the Lagrangian Relaxation which is used to exploit the structure of the problem reducing considerably its complexity by moving hard-to-satisfy constraints into the objective function, associating a penalty in case the constraints are not satisfied. The developed metaheuristic for the TSP has been integrated into two hybrid methodologies combined with Constraint Programming to tackle more complex problems. First of all, it is addressed the Capacitated Vehicle Routing Problem (CVRP), whose vehicles have limited loading capacity of the goods that must be delivered. Secondly, it has been addressed a real problem of the Home Health Care (HHC) service in the municipality of Ferrara, Italy. It consists on assigning patients' services to nurses which travel to each patient’s home. Theoretical researches typically assume the symmetry of the distance-based costs associated with traveling from one place to another as well as the existence of a homogeneous fleet of vehicles with limited capacity. This thesis studies different variants focusing on the impact that causes the asymmetry of the costs and the heterogeneity of the fleet. For these purpose, the Asymmetric Traveling Salesman Problem (ATSP), the Asymmetric Capacitated Vehicle Routing Problem (ACVRP) and the Asymmetric and Heterogeneous Vehicle Routing Problem (AHVRP) are addressed.
27
Morgan, Matthew J. W. "GAPS : a hybridised framework applied to vehicle routing problems". Thesis, Cardiff University, 2008. http://orca.cf.ac.uk/55459/.
Testo completoAbstract (sommario):
In this thesis we consider two combinatorial optimisation problems; the Capacitated Vehicle Routing Problem (CVRP) and the Capacitated Arc Routing Problem (CARP). In the CVRP, the objective is to find a set of routes for a homogenous fleet of vehicles, which must service a set of customers from a central depot. In contrast, the CARP requires a set of routes for a fleet of vehicles to service a set of customers at the street level of an intercity network. After a comprehensive discussion of the existing exact and heuristic algorithmic techniques presented in the literature for these problems, computational experiments to provide a benchmark comparison of a subset of algorithmic implementations for these methods are presented for both the CVRP and CARP, run against a series of dataset instances from the literature. All dataset instances are re-catalogued using a standard format to overcome the difficulties of the different naming schemes and duplication of instances that exist between different sources. We then present a framework, which we shall call Genetic Algorithm with Perturbation Scheme (GAPS), to solve a number of combinatorial optimisation problems. The idea is to use a genetic algorithm as a container framework in conjunction with a perturbation or weight coding scheme. These schemes make alterations to the underlying input data within a problem instance, after which the changed data is fed into a standard problem specific heuristic and the solution obtained decoded to give a true solution cost using the original unaltered instance data. We first present GAPS in a generic context, using the Travelling Salesman Problem (TSP) as an example and then provide details of the specific application of GAPS to both the CVRP and CARP. Computational experiments on a large set of problem instances from the literature are presented and comparisons with the results achieved by the current state of the art algorithmic approaches for both problems are given, highlighting the robustness and effectiveness of the GAPS framework.
28
Ben, Said Asma. "Selective vehicle routing problems in collaborative urban transport networks". Thesis, Compiègne, 2019. http://www.theses.fr/2019COMP2478.
Testo completoAbstract (sommario):
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
29
LONGO, HUMBERTO JOSE. "INTEGER PROGRAMMING TECHNIQUES AND APPLICATIONS TO VEHICLE ROUTING PROBLEMS". PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 2004. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=6029@1.
Testo completoAbstract (sommario):
COORDENAÇÃO DE APERFEIÇOAMENTO DO PESSOAL DE ENSINO SUPERIORUNIVERSIDADE FEDERAL DE GOIÁS
A natureza intrinsicamente combinatorial de muitos problemas advindos da área de logística de transportes, em especial aqueles que dizem respeito ao uso racional de frotas de veículos, sugere que boa parte dos mesmos pode ser formulada e resolvida como um problema de programação linear inteira. Contudo, a maioria dos algoritmos até o momento disponíveis não consegue encontrar, em tempos computacionais aceitáveis, a solução ótima para instâncias de porte razoável. O objeto de estudo desta tese é a exploração de técnicas mais recentes da área de programação linear inteira e suas aplicações a problemas de roteamento de veículos. A primeira parte da tese descreve, além das técnicas básicas de decomposição de problemas de programação linear e linear inteira e de geração de colunas, uma proposta de reformulação de problemas de programação linear inteira alternativa àquela que gera o tradicional problema mestre de Dantzig-Wolfe, geralmente utilizados em abordagens por geração de colunas. A resolução de problemas de programação linear inteira neste contexto é tratada em seguida, com a descrição do algoritmo branch-and-bound e das variações branch-and-cut, branch-and-price e branch-and-cut-and-price. Na segunda parte da tese, inicialmente, é apresentada a técnica denominada de Geração Projetada de Colunas e sua aplicação ao problema de Roteamento de Veículos com Restrição de Capacidade. Em seguida é abordada a resolução do problema de Roteamento de Veículos sobre Arcos, através de sua transformação ao primeiro problema citado e uso de um algoritmo branch-and- cut-and-price. Finalmente, é proposto um novo problema na área de redistribuição de veículos de aluguel, para o qual é proposta uma formulação segundo uma abordagem por geração de colunas. São apresentados, ainda, procedimentos para a geração de colunas e resultados computacionais obtidos com um algoritmo branch-and-price para essa formulação.
Optimization techniques have an important role in Transportation Logistics. The combinatorial nature of the problems related to this area suggests integer programming as a natural approach to their resolution. Nevertheless there are many cases where even instances of reasonable size still beyond the resolution capability of the current known algorithms. The success of the known algorithms have therefore been limited. This can be justified by the fact the most of them leave important recent advances in the combinatorial optimization field unexplored. Some of these new techniques and their applications are the main subject of this thesis. In the first part, the basic decomposition techniques for linear and integer programming problems as well as the related column generation approach is addressed. This is followed by the presentation of a reformulation technique for linear and integer programming which is alternative to the well known Dantzig-Wolfe master program. The new possibilities coming from this approach are explored and the resulting consequences to the standard branch-and- bound algorithm and its variations branch-and-cut, branch-and- price and branchand- cut-and-price are presented. The second part of this text addresses the application of the metodologies described in part one to routing problems where capacity constraints are considered. First, a techinque named Projected Column Generation is described in the context of the Capacitated Vehicle Routing Problem. Then, it is presented a new transformation from the Capacitated Arc Routing Problem to the Capacitated Vehicle Routing Problem as well as a tailored branch-and-cut-and-price to solve this problem. Finally, a new problem in vehicle redistrubution is described together with a column generation approach for its resolution. Computational results for all applications are presented.
30
Xu, Haiping. "Optimal policies for stochastic and dynamic vehicle routing problems". Thesis, Massachusetts Institute of Technology, 1994. http://hdl.handle.net/1721.1/11748.
Testo completo
31
Roberti, Roberto <1982>. "Exact Algorithms for Different Classes of Vehicle Routing Problems". Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2012. http://amsdottorato.unibo.it/4350/.
Testo completoAbstract (sommario):
We deal with five problems arising in the field of logistics: the Asymmetric TSP (ATSP), the TSP with Time Windows (TSPTW), the VRP with Time Windows (VRPTW), the Multi-Trip VRP (MTVRP), and the Two-Echelon Capacitated VRP (2E-CVRP).
The ATSP requires finding a lest-cost Hamiltonian tour in a digraph. We survey models and classical relaxations, and describe the most effective exact algorithms from the literature. A survey and analysis of the polynomial formulations is provided. The considered algorithms and formulations are experimentally compared on benchmark instances.
The TSPTW requires finding, in a weighted digraph, a least-cost Hamiltonian tour visiting each vertex within a given time window. We propose a new exact method, based on new tour relaxations and dynamic programming. Computational results on benchmark instances show that the proposed algorithm outperforms the state-of-the-art exact methods.
In the VRPTW, a fleet of identical capacitated vehicles located at a depot must be optimally routed to supply customers with known demands and time window constraints. Different column generation bounding procedures and an exact algorithm are developed. The new exact method closed four of the five open Solomon instances.
The MTVRP is the problem of optimally routing capacitated vehicles located at a depot to supply customers without exceeding maximum driving time constraints. Two set-partitioning-like formulations of the problem are introduced. Lower bounds are derived and embedded into an exact solution method, that can solve benchmark instances with up to 120 customers.
The 2E-CVRP requires designing the optimal routing plan to deliver goods from a depot to customers by using intermediate depots. The objective is to minimize the sum of routing and handling costs. A new mathematical formulation is introduced. Valid lower bounds and an exact method are derived. Computational results on benchmark instances show that the new exact algorithm outperforms the state-of-the-art exact methods.
32
Sze, Jeeu Fong. "Hybridisation search for a class of vehicle routing problems". Thesis, University of Kent, 2017. https://kar.kent.ac.uk/61328/.
Testo completoAbstract (sommario):
This thesis presents an investigation into the hybridisation of metaheuristic approaches to tackle the classical vehicle routing problem (VRP) and its adaptation to other useful and practical routing problems including the cumulative capacitated VRP (CCVRP) and the dynamic VRP (DVRP). Due to the limited success of the exact methods in handling large size instances, this research investigates the design and analysis of metaheuristic algorithms that can produce near optimal solutions within a reasonable amount of time to solve this class of routing problems. To achieve this goal, we propose an effective and novel hybridisation of variable neighbourhood search (VNS) and large neighbourhood search (LNS), leading to a powerful adaptive VNS (AVNS). Different from most of the literature for AVNS and adaptive LNS where learning is usually incorporated in the shaking step for the former and in the selection of the removal strategies for the latter, the adaptive aspect presented here is integrated in the local search of our AVNS. In short, a set of highly successful local searches is selected based on the intelligent selection mechanism which we introduced. In addition, this work also focuses on the development of some general enhancement-based techniques which include the design of neighbourhood reduction scheme, efficient data structures and a guided penalized objective function. The VRP is a hard combinatorial optimisation problem which was first established more than fifty years ago. Since then, this problem is extensively studied because of its high practicability in transportation logistics. Given the rising price of global oil, reducing the transportation cost provides a great impact in stabilizing the global economic system and adds a competitive advantage. The classical VRP focuses on this line of research. In addition, the classical VRP is used as the initial platform for our experiments which serves as the basis for tackling the other related routing problems mentioned above. The aim is to turn the successful implementations of the proposed algorithm by easily adapting and extending it to cater for the other two related routing problems namely the CCVRP and the DVRP. While the general assumption in most VRPs is profit-based such as the minimisation of the transportation cost, there are other objective functions such as to provide a good service to the customers. Such applications appear in the context of humanitarian relief where the main objective is to save lives or to alleviate suffering. This leads to the introduction of the CCVRP, which aims to minimise the sum of arrival times at customers. The literature for this particular problem is relatively scarce despite its practical importance. We therefore intend to investigate this new and interesting variant. In addition, during the emergency situation, there is often a limited time for saving lives. A good routing plan should also ensure fairness and equity to everyone including the last customer. Motivated by this idea, an alternative but closely related objective that minimises the last arrival time is also studied. We refer to this variant as the min-max CCVRP. In the traditional VRP, a route plan remains unchanged once it is identified. However in practice, several unforeseen events such as accidents or bad weather could occur at any point when the routes are executed, which cause traffic congestion and delay to the original planned routes. Therefore, it is important to re-optimise the routes by taking into consideration the real-time information, leading to the DVRP. The review of the DVRP literature shows that researchers have mainly focused on the customer requests as the dynamic aspect. Our research, however, concentrates more on the less popular but very practical aspect, namely the dynamic traffic information. Such unpredictable events have a great impact on the route plan and henceforth shall, in overview, not be ignored. The contributions of this thesis are fourfold: (i) To propose an effective hybridisation of the VNS and the LNS in addition to some new and powerful data structures and neighbourhood reduction scheme integrated in the algorithm, (ii) To adapt the AVNS algorithm for the CCVRP with extra features added and to present new best results, (iii) To demonstrate the flexibility and effectiveness of the AVNS algorithm to solve the min-max CCVRP and to explore the managerial insights for decision making when considering the min-sum and the min-max CCVRP objective functions, (iv) To adapt the AVNS algorithm as a re-optimisation procedure for the DVRP, where we introduce the concept of critical points which are used as the turning points for the vehicle.
33
Saint-Guillain, Michael. "Models and algorithms for online stochastic vehicle routing problems". Thesis, Lyon, 2019. http://www.theses.fr/2019LYSEI068.
Testo completoAbstract (sommario):
Quels seront les objectifs et défis des métropoles de demain ? La plupart des problèmes issus du monde réel sont sujets à l'inconnu, nécessitant de prendre de nouvelles décisions de façon dynamique, à la demande, en fonction des évènements aléatoires qui se réalisent. Dans cette thèse, nous nous attaquons à un problème majeur, du moins en perspectives: la gestion dynamique d'une flotte de véhicules en contexte urbain. Les applications pratiques des tournées de véhicules à la demande sont nombreuses, incluant les transports publics intelligents, les services de livraison, les soins et interventions à domicile, etc. Étant donnés une flotte de véhicules et un ensemble de clients, chacun pouvant potentiellement et à tout moment émettre une requête nécessitant une intervention, l'objectif de cette thèse est de fournir une réponse à la question suivante. Étant donné l'état courant à un moment donné, comment gérer notre flotte de véhicules afin de maximiser l'espérance du nombre total de requêtes satisfaites à la fin de la journée ? Ou encore, comment minimiser l'espérance du délai moyen d'intervention de nos véhicules ? Bien entendu, la difficulté réside en ce que la plupart des requêtes, avant d'apparaître dynamiquement, ne sont pas connues. Pour chaque problème, nous considérons qu'il nous est fourni une connaissance, sous forme d'information probabiliste, telle que la probabilité qu'une requête apparaisse à un certain endroit, et à un certain moment de la journée. Grâce à des techniques issues de la recherche opérationnelle et de la programmation stochastique, nous sommes en mesure de construire et résoudre des modèles calculant les actions anticipatives les plus adéquates, comme le redéploiement préventif des véhicules, minimisant le coût total espéré, ou encore maximisant la qualité de service. La question de l'optimisation sous incertitude se pose depuis déjà plusieurs décennies. Grâce aux avancées à la fois théoriques et technologiques, nous sommes chaque jour un peu plus en mesure de palier à l'inconnu. Cependant, la plupart des problèmes intéressants restent extrêmement difficiles à résoudre, si ce n'est impossible. Il reste beaucoup à faire. Cette thèse explore certains concepts fondamentaux de l'optimisation sous incertitude. En intégrant une composante stochastique aux modèles à optimiser, nous verrons ensemble comment il est en effet possible de créer de l'anticipationWhat will be tomorrow's big cities objectives and challenges? Most of the operational problems from the real world are inherently subject to uncertainty, requiring the decision system to compute new decisions dynamically, as random events occur. In this thesis, we aim at tackling an important growing problem in urban context: online dynamic vehicle routing. Applications of online vehicle routing in the society are manyfold, from intelligent on demand public transportation to sameday delivery services and responsive home healthcare. Given a fleet of vehicles and a set of customers, each being potentially able to request a service at any moment, the current thesis aims at answering the following question. Provided the current state at some moment of the day, which are the best vehicle actions such that the expected number of satisfied requests is maximized by the end of the operational day? How can we minimize the expected average intervention delays of our mobile units? Naturally, most of the requests remain unknown until they appear, hence being revealed online. We assume a stochastic knowledge on each operational problem we tackle, such as the probability that customer request arise at a given location and a given time of the day. By using techniques from operations research and stochastic programming, we are able to build and solve mathematical models that compute near-optimal anticipative actions, such as preventive vehicle relocations, in order to either minimize the overall expected costs or maximize the quality of service. Optimization under uncertainty is definitely not a recent issue. Thanks to evolution of both theoretical and technological tools, our ability to face the unknown constantly grows. However, most of the interesting problems remain extremely hard, if not impossible, to solve. There is still a lot of work. Generally speaking, this thesis explores some fundamentals of optimization under uncertainty. By integrating a stochastic component into the models to be optimized, we will see how it is in fact possible to create anticipation
34
Goodson, Justin Christopher. "Solution methodologies for vehicle routing problems with stochastic demand". Diss., University of Iowa, 2010. https://ir.uiowa.edu/etd/675.
Testo completoAbstract (sommario):
We present solution methodologies for vehicle routing problems (VRPs) with stochastic demand, with a specific focus on the vehicle routing problem with stochastic demand (VRPSD) and the vehicle routing problem with stochastic demand and duration limits (VRPSDL). The VRPSD and the VRPSDL are fundamental problems underlying many operational challenges in the fields of logistics and supply chain management.
We model the VRPSD and the VRPSDL as large-scale Markov decision processes. We develop cyclic-order neighborhoods, a general methodology for solving a broad class of VRPs, and use this technique to obtain static, fixed route policies for the VRPSD. We develop pre-decision, post-decision, and hybrid rollout policies for approximate dynamic programming (ADP). These policies lay a methodological foundation for solving large-scale sequential decision problems and provide a framework for developing dynamic routing policies.
Our dynamic rollout policies for the VRPSDL significantly improve upon a method frequently implemented in practice. We also identify circumstances in which our rollout policies appear to offer little or no benefit compared to this benchmark. These observations can guide managerial decision making regarding when the use of our procedures is justifiable. We also demonstrate that our methodology lends itself to real-time implementation, thereby providing a mechanism to make high-quality, dynamic routing decisions for large-scale operations.
Finally, we consider a more traditional ADP approach to the VRPSDL by developing a parameterized linear function to approximate the value functions corresponding to our problem formulation. We estimate parameters via a simulation-based algorithm and show that initializing parameter values via our rollout policies leads to significant improvements. However, we conclude that additional research is required to develop a parametric ADP methodology comparable or superior to our rollout policies.
35
Rahman, Md Mahbubar. "Two-Echelon Vehicle Routing Problems Using Unmanned Autonomous Vehicles". Thesis, North Dakota State University, 2017. https://hdl.handle.net/10365/28423.
Testo completoAbstract (sommario):
In this thesis, we investigate new multi-echelon vehicle routing problems for logistics operations using unmanned autonomous vehicles. This can provide immediate tangible outcomes, especially in high-demand areas that are otherwise difficult or costly to serve. This type of problem differs from the commonly used multi-echelon supply chain management systems in that here there exist no intermediate facilities that consolidate/separate products for delivery; instead all decisions are made on a per-vehicle basis. We describe here how we can obtain the necessary parameters (data collection) to evaluate the performance of such multi-echelon systems. We also provide three mathematical formulations based on different assumptions and case scenarios. We then study the differences between the three models in practice, as far as routing cost and duration of operations are concerned. We finally show that there are savings to be had by properly employing unmanned vehicles for logistics operations.
36
El-Hajj, Racha. "Vehicle routing problems with profits, exact and heuristic approaches". Thesis, Compiègne, 2015. http://www.theses.fr/2015COMP2192.
Testo completoAbstract (sommario):
Nous nous intéressons dans cette thèse à la résolution du problème de tournées sélectives (Team Orienteering Problem - TOP) et ses variantes. Ce problème est une extension du problème de tournées de véhicules en imposan tcertaines limitations de ressources. Nous proposons un algorithme de résolution exacte basé sur la programmation linéaire en nombres entiers (PLNE) en ajoutant plusieurs inégalités valides capables d’accélérer la résolution. D’autre part, en considérant des périodes de travail strictes pour chaque véhicule durant sa tournée, nous traitons une des variantes du TOP qui est le problème de tournées sélectives multipériodique (multiperiod TOP - mTOP) pour lequel nous développons une métaheuristique basée sur l’optimisation par essaim pour le résoudre. Un découpage optimal est proposé pour extraire la solution optimale de chaque particule en considérant les tournées saturées et pseudo saturées .Finalement, afin de prendre en considération la disponibilité des clients, une fenêtre de temps est associée à chacun d’entre eux, durant laquelle ils doivent être servis. La variante qui en résulte est le problème de tournées sélectives avec fenêtres de temps (TOP with Time Windows - TOPTW). Deux algorithmes exacts sont proposés pour résoudre ce problème. Le premier est basé sur la génération de colonnes et le deuxième sur la PLNE à laquelle nous ajoutons plusieurs coupes spécifiques à ce problèmeWe focus in this thesis on developing new algorithms to solve the Team Orienteering Problem (TOP) and two of its variants. This problem derives from the well-known vehicle routing problem by imposing some resource limitations .We propose an exact method based on Mixed Integer Linear Programming (MILP) to solve this problem by adding valid inequalities to speed up its solution process. Then, by considering strict working periods for each vehicle during its route, we treat one of the variants of TOP, which is the multi-period TOP (mTOP) for which we develop a metaheuristic based on the particle swarm optimization approach to solve it. An optimal split procedure is proposed to extract the optimal solution from each particle by considering saturated and pseudo-saturated routes. Finally, in order to take into consideration the availability of customers, a time window is associated with each of them, during which they must be served. The resulting variant is the TOP with Time Windows (TOPTW). Two exact algorithms are proposed to solve this problem. The first algorithm is based on column generation approach and the second one on the MILP to which we add additional cuts specific for this problem. The comparison between our exact and heuristic methods with the existing one in the literature shows the effectiveness of our approaches
37
Letchford, Adam Nicholas. "Polyhedral results for some constrained arc-routing problems". Thesis, Lancaster University, 1996. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.337546.
Testo completo
38
Rebillas, Loredo Victoria. "The multi-depot VRP with vehicle interchanges". Doctoral thesis, Universitat Politècnica de Catalunya, 2018. http://hdl.handle.net/10803/664634.
Testo completoAbstract (sommario):
In real-world logistic operations there are a lot of situations that can be exploited to get better operational strategies. It is important to study these new alternatives, because they can represent significant cost reductions to the companies working with physical distribution. This thesis defines the Multi-Depot Vehicle Routing Problem with Vehicle Interchanges (MDVRPVI). In this problem, both vehicle capacities and duration limits on the routes of the drivers are imposed. To favor a better utilization of the available capacities and working times, it is allowed to combine pairs of routes at predefined interchange locations. The objective of this thesis is to analyze and solve the Multi-Depot Vehicle Routing Problem adding the possibility to interchange vehicles at predefined points. With this strategy, it is possible to reduce the total costs and the number of used routes with respect to the classical approach: The Multi-Depot Vehicle Routing Problem (MDVRP). It should be noted that the MDVRP is more challenging and sophisticated than the single-depot Vehicle Routing Problem (VRP). Besides, most exact algorithms for solving the classical VRP are difficult to adapt in order to solve the MDVRP (Montoya-Torres et al., 2015). From the complexity point of view, the MDVRPVI is NP-Hard, since it is an extension of the classical problem, which is already NP-Hard. We present a tight bound on the costs savings that can be attained allowing interchanges. Three integer programming formulations are proposed based on the classical vehicle-flow formulations of the MDVRP. One of these formulations was solved with a branch-and-bound algorithm, and the other two formulations, with branch-and-cut algorithms. Due to its great symmetry, the first formulation is only able to solve small instances. To increase the dimension of the instances used, we proposed two additional formulations that require one or more families of constraints of exponential size. In order to solve these formulations, we had to design and implement specific branch-and-cut algorithms. For these algorithms we implemented specific separation methods for constraints that had not previously been used in other routing problems. The computational experience performed evidences the routing savings compared with the solutions obtained with the classical approach and allows to compare the efficacy of the three solution methods proposed.En les operacions logístiques del món real es donen situacions que poden ser explotades per obtenir millors estratègies operacionals. És molt important estudiar aquestes noves alternatives, perquè poden representar una reducció significativa de costos per a les companyies que treballen en distribució de mercaderies. En aquesta tesi es defineix el Problema d'Enrutament de Vehicles amb Múltiples Dipòsits i Intercanvi de Vehicles (MDVRPVI). En aquest problema, es consideren tant la capacitat dels vehicles com els límits de duració de les rutes dels conductors. Per tal de millorar la utilització de les capacitats i temps de treball disponibles, es permet combinar parelles de rutes en punts d'intercanvi predefinits. L'objectiu d'aquesta tesi és analitzar i resoldre el problema d'Enrutament de Vehicles amb Múltiples Dipòsits, on es permet l'intercanvi de vehicles. Amb aquesta estratègia, és possible reduir els costos totals i el nombre de les rutes utilitzades respecte l'enfocament clàssic: el problema d'Enrutament de Vehicles amb Múltiples Dipòsits (MDVRP). Cal assenyalar que el MDRVP és més desafiant i sofisticat que el problema d'Enrutament de Vehicles d'un únic dipòsit (VRP). A més, molts algoritmes exactes per resoldre el VRP clàssic son complicats d'adaptar per resoldre el MDVRP (Montoya-Torres et al., 2015). Des del punt de vista de la complexitat, el MDRVPVI és NP-Dur, perquè és una extensió del problema clàssic, que també ho és. Presentem una cota ajustada de l'estalvi en els costos de distribució que es pot obtenir permetent els intercanvis. Es proposen tres formulacions de programació sencera basades en la formulació clàssica “vehicle-flow” del MDVRP. La primera formulació, degut a la seva grandària i la seva simetria, només permet resoldre instàncies molt petites. Per augmentar la dimensió de les instàncies abordables, es proposen dues formulacions addicionals que requereixen una o vàries famílies de restriccions de mida exponencial. Per això, per tal de resoldre el problema amb aquestes formulacions, ha calgut dissenyar i implementar sengles algorismes de tipus branch-and-cut. En aquests algorismes s'han implementat mètodes de separació específics per a les restriccions que no s'havien utilitzat prèviament en altres problemes de rutes. L’experiència computacional realitzada evidencia els estalvis obtinguts comparació amb les solucions corresponents l'enfocament clàssic. També es compara l’eficàcia dels tres mètodes propostes a l'hora de resoldre el problema.
39
Tütüncü, Gözde Yazgi. "A visual interactive decision support system for vehicle routing problems". Thesis, Coventry University, 2006. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.429680.
Testo completo
40
Wassan, Niaz Ahmed. "Tabu search metaheuristics for a class of vehicle routing problems". Thesis, University of Kent, 1998. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.263742.
Testo completo
41
PENARANDA, FABIAN ARTURO CASTILLA. "VEHICLE ROUTING PROBLEMS WITH TIME WINDOWS AND EXACT SYNCHRONIZATION CONSTRAINTS". PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 2013. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=23834@1.
Testo completoAbstract (sommario):
PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIROCOORDENAÇÃO DE APERFEIÇOAMENTO DO PESSOAL DE ENSINO SUPERIOR
CONSELHO NACIONAL DE DESENVOLVIMENTO CIENTÍFICO E TECNOLÓGICO
PROGRAMA DE EXCELENCIA ACADEMICA
Uma generalização do problema de roteamento de veículos (VRP) presente em aplicações práticas em portos e operações em minas é o objeto desta dissertação. Nesta variante do VRP cada cliente pode demandar diferentes tipos de veículos para cumprir tarefas colaborativamente. Nesta atividade, os veículos podem aguardar o início da operação no local porém, devem iniciar as tarefas ao mesmo tempo. O objetivo é determinar as rotas dos veículos disponíveis de modo a maximizar a soma (ponderada) dos clientes atendidos enquanto a distância total percorrida é minimizada. O caso específico onde todos os clientes são atendidos e a distância total percorrida é minimizada determina o problema central estudado nessa dissertação. Este caso particular pode ser visto como uma generalização direta do, muito estudado e conhecido problema de roteamento, VRP com janelas de tempo (VRPTW) onde a capacidade dos veículos é suficientemente grande. Esta escolha de um problema mais restrito é justificada por permitir uma clara comparação de sua dificuldade através da sua relação com o VRPTW. A partir da classificação dos casos de sincronização em problemas de roteamento proposta por (DREXL, 2012), denominamos o problema aqui estudado de Problema de Roteamento de Veículos com Janelas de Tempo e Sincronização exata da Operação (VRPTWEOS). Neste trabalho damos uma definição formal ao VRPTWEOS. Modelos de programação inteira são propostos e analisados. Também apressentamos métodos de resolução baseados na decomposição Dantzig-Wolfe, dos quais são derivados algoritmos exatos e aproximados. Com o propósito de avaliar a eficiencia desses algoritmos, foi criado um grupo de instancias de teste baseado no benchmark do Solomon para o VRPTW. O método usado para criar o conjunto de instancias de teste é descrito em detalhe. Experimentos computacionais sobre este conjunto de instancias mostraram que o método de resolução proposto é promissor para a resolução do VRPTWEOS.
This dissertation addresses a generalization of the vehicle routing problem (VRP) that arises in real life applications in ports and mine operations. In this VRP variant, each customer may demand different types of vehicles to perform a task collaboratively. Vehicles are allowed to wait at the locations but they must start operating at the same time. The objective is to route the available vehicles while maximizing the (weighted) sum of served customers and minimizing the total distance traveled. The specific case where all customers must be served while minimizing the total distance traveled is the central problem here studied. This special case can be viewed as a straightforward generalization of, a well known and more specific routing problem, the VRP with time windows (VRTPTW) where the capacity of the vehicles is sufficiently large. We support this narrower scope by stating that it allows a clear comparison of the problem hardness by its relation to the VRPTW. Sticking to the classification of synchronization in vehicle routing proposed by (DREXL, 2012) we named this problem as the Vehicle Routing Problem with Time Windows and Exact Operation Synchronization (VRPTWEOS). In this work, a formal definition for the VRPTWEOS is provided. Integer programming models for this problem are proposed and analyzed. Furthermore, we propose a solution method based on the Dantzig-Wolfe decomposition for which exact and aproximated resolution algorithms are described. In order to test the performance of those algorithms, a group of benchmark instances for the VRPTWEOS was created on top of the Solomon benchmark for the VRPTW. The method used to create the benchmark instances is described in detail. Computational experiments over the mentioned set of instances showed that the proposed solution approach is a promising alternative for solving the VRPTWEOS.
42
Chen, Yujie. "Optimisation for large-scale maintenance, scheduling and vehicle routing problems". Thesis, University of York, 2017. http://etheses.whiterose.ac.uk/16107/.
Testo completoAbstract (sommario):
Solving real-world combinatorial problems is involved in many industry fields to minimise operational cost or to maximise profit, or both. Along with continuous growth in computing power, many asset management decision-making processes that were originally solved by hand now tend to be based on big data analysis. Larger scale problem can be solved and more detailed operation instructions can be delivered. In this thesis, we investigate models and algorithms to solve large scale Geographically Distributed asset Maintenance Problems (GDMP). Our study of the problem was motivated by our business partner, Gaist solutions Ltd., to optimise scheduling of maintenance actions for a drainage system in an urban area. The models and solution methods proposed in the thesis can be applied to many similar issues arising in other industry fields. The thesis contains three parts. We firstly built a risk driven model considering vehicle routing problems and the asset degradation information. A hyperheuristic method embedded with customised low-level heuristics is employed to solve our real-world drainage maintenance problem in Blackpool. Computational results show that our hyperheuristic approach can, within reasonable CPU time, produce much higher quality solutions than the scheduling strategy currently implemented by Blackpool council. We then attempt to develop more efficient solution approaches to tackle our GDMP. We study various hyperheuristics and propose efficient local search strategies in part II. We present computational results on standard periodic vehicle routing problem instances and our GDMP instances. Based on manifold experimental evidences, we summarise the principles of designing heuristic based solution approaches to solve combinatorial problems. Last bu not least, we investigate a related decision making problem from highway maintenance, that is again of interest to Gaist solutions Ltd. We aim to make a strategical decision to choose a cost effective method of delivering the road inspection at a national scale. We build the analysis based on the Chinese Postman Problem and theoretically proof the modelling feasibility in real-world road inspection situations. We also propose a novel graph reduction process to allow effective computation over very large data sets.
43
Ödling, David. "A metaheuristic for vehicle routing problems based on reinforcement learning". Thesis, KTH, Optimeringslära och systemteori, 2018. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-224428.
Testo completoAbstract (sommario):
The vehicle routing problem is an old and well-studied problem that arise in last mile logistics. The rapid increase of e-commerce, in particular with an increasing the demand for time scheduled home deliveries on the customer’s terms, is making the problem ever more relevant. By minimizing the cost and environmental impact, we have the setting for mathematical problem called the vehicle routing problem with time windows. Since the problem is NP-Hard, heuristic methods are often used. In practice, they work very well and typically offer a good tradeoff between speed and quality. However, since the heuristics are often tailormade to fit the needs of the underlying problem, no known algorithm dominates the other on all problems. One way to overcome the need for specialization is to produce heuristics that are adaptive. In this thesis, an offline learning method is proposed to generate an adaptive heuristic using local search heuristics and reinforcement learning. The reinforcement learning agents explored in this thesis are situated in both discrete and continuous state representations. Common to all state spaces are that they are inspired by human-crafted reference models where the last action and the result of that action define the state. Four different reinforcement learning models are evaluated in the various environments. By evaluating the models on a subset of the Solomon benchmark instances, we find that all models but one improve upon a random baseline. The average learner from each of the successful models was slightly worse than the human crafted baseline. However, the best among the generated models was an actor-critic based model which outperformed the best human baseline model. Due to the scalar objective function, the results are not directly comparable to the Solomon benchmark results with hierarchal objectives. None the less, the results are encouraging as a proof of principle with results in line with the human crafted baseline. The results indicate two clear paths for further work. First, applying the formulation to more complex environments with more actions and more powerful state spaces. Secondly, investigate models based on stochastic policies and recurrent neural networks to cope with the inherently partially observed environment.Ruttoptimering är ett gammalt och välstuderat optimeringsproblem som uppstår i city-nära logistik. Med en ständigt växande e-handel, ökar efterfrågan av tidspassade hemleveranser på kundens villkor. Att minimera kostnaden och miljöpåverkan blir då ett ruttoptimeringsproblem med tidsfönster. Då optimerinsproblemet är NP-Svårt, används heuristiska lösningsmetoder. I denna uppsatts undersöks möjligheten att generera heuristiker genom att träna på liknande problem. Mer specifikt genererar vi en heurisitik baserad på lokalsök genom att formulera lärningsproblemet som ett reinforcement learning problem. De metoder som används är baserade på både diskreta och kontinuerliga tillståndsrum. Gemensamt för tillståndsrummen är att de är inspirerade av den information som används av mänskligt genererade heuristiker där det tidigare valet valet och dess resultat är informationsbärare. Fyra olika reinforcement learning modeller utvärderas på olika problem samt tillståndsrymnder. Genom att träna modellerna på olika typer av problem från de välkända Solomon problemen och utvärdera dessa på ett oberoende test set, kan vi konstatera att alla utom en modell är bättre än slumpen. Ingen av modellerna slog dock den bästa referensmodellen i medeltal då variationen i utfallet var stort, men de är alla mycket nära. Den bästa bland alla modeller, vilket var en actor critic agent, uppnådde ett bättre resultat än den bästa referensmodellen. På grund av att en skalär målfunktion använts är resultaten inte direkt jämförbara med andras på Solomon problemen då de skall optimeras med en hierarkisk målfunktion. Trotts detta är resultaten goda och visar att metoden som introducerats fungerar bra eftersom de presterar i linje med referensmodellerna baserade på samma information. Resultaten pekar på två vägar framåt för vidare arbete. Det första är en mera kraftfull tillståndsrymd med mera information samt fler handlingsmöjligheter. Det andra är att applicera stokastiska baserade modeller eller motsvarande för att överkomma tillståndsrymndernas inneboende ofullständighet.
44
Bertsimas, Dimitris J., e Haiping Xu. "Optimization of Polling Systems and Dynamic Vehicle Routing Problems on Networks". Massachusetts Institute of Technology, Operations Research Center, 1993. http://hdl.handle.net/1721.1/5356.
Testo completoAbstract (sommario):
We consider the problem of optimizing a polling system, i.e., of optimally sequencing a server in a multi-class queueing system with switch-over times in order to minimize a linear objective function of the waiting times. The problem has important applications in computer, communication, production and transportation networks. We propose nonlinear programming relaxations that provide strong lower bounds to the optimal cost for all static policies. We also obtain lower bounds for dynamic policies as well, which are primarily useful under light traffic conditions and/or small switch-over times. We conjecture that the lower bounds developed in this paper for the class of static policies are also valid for dynamic policies under heavy traffic conditions. We use the information from the lower bound and integer programming techniques to construct static policies that are very close (0-3%) to the lower bounds. We compare numerically our proposed policies with static policies proposed in the literature as well as with dynamic policies and find that the policies we propose outperform all static policies proposed in the literature and at least in heavier traffic outperform dynamic policies as well.
45
Harwood, Kieran G. "Investigation into heuristic methods of solving time variant Vehicle Routing Problems". Thesis, Cardiff University, 2013. http://orca.cf.ac.uk/49087/.
Testo completoAbstract (sommario):
Traditionally, Vehicle Routing Problems (VRPs) are modelled with fixed traversal times. The amount of time it takes to drive from one end of a road to the other is unchanged throughout the day. Nearly always, the reality of the situation that is being modelled is very different, with road speeds varying heavily, especially with “rush hour" traffic. Modelling VRPs with time varying congestion means that even slight changes early in a vehicle tour can have major knock-on effects that are hard to predict. Recalculating the total traversal time of vehicles whenever their tours are changed drastically increases metaheuristic calculation times compared to non-time varying models. In this thesis we use a simple technique of calculating the localised change and inferring the global effects resulting from neighbourhood moves. Only if the localised change suggests that the global result is satisfactory do we then calculate the actual global result. Inevitably using these estimates does not give as accurate results as always calculating the changes, but we aim to show that the loss of solution quality is overshadowed by the significant savings in calculation time. We present a series of experiments comparing simple metaheuristics with and without using estimates and show consistent savings in calculation time whenever estimates are used compared to when they are not. These savings shown to increase as the size of the problem (in terms of the number of customers) increases. In addition to synthetic problems, we also present a problem based on real world vehicle traversal times and show that our estimates prove just as accurate, if not more so, at retaining solution quality as the synthetic methods. Lastly, we briefly discuss further methods of solving VRPs that could also benefit from our work here.
46
Sa'adah, Samer. "Solving vehicle routing problems using multiple ant colonies and deterministic approaches". Thesis, Edinburgh Napier University, 2007. http://researchrepository.napier.ac.uk/Output/9469.
Testo completoAbstract (sommario):
In the vehicle routing problem with time windows VRPTW, there arc two main objectives. The primary objective is to reduce the number of vehicles, the secondary one is to minimise the total distance travelled by all vehicles. This thesis describes some experiments with multiple ant colony and deterministic approaches. For that, it starts explaining how a double ant colony system called DACS 01 with two colonies has the advantage of using the pheromone trails and the XCHNG local search and the ability of tackling multiple objectives problems like VRPTW. Also, it shows how such DACS system lacks vital components that make the performance as comparable and competitive with that of the well-known VRPTW algorithms. Therefore, the inclusions of components, like a triple move local search, a push-forward and pushbackward strategy PFPBS, a hybrid local search HLS and a variant of a 2-0pt move, improve the results very significantly, compared to not using them. Furthermore, it draws the attention to an interesting discovery, which suggests that if a DACS system uses ants that arc more deterministic, then that system has the ability to bring performance that is better than that of another DACS system with pheromone ants. Consequently, the interesting discovery has motivated the author to investigate a number of SI1- Like deterministic approaches, which most of them depend on capturing under-constrained tours and removing them using a removing heuristic that uses the hybrid local search HLS. Some of these SI1-Like approaches show signs of the ability of improving the average, best and worst case performances of DACS systems on some problem set cases, if they are merged with such systems. Of course, this casts some doubt on whether the usc of pheromone trails, which is a distinctive feature of multiple ant-colony systems in the research literature, is really so advantageous as is sometimes claimed. Experiments are conducted on the 176 problem instances with 100, 200 and 400 customers of Solomon [1], Ghering and Homberger [2] and [3]. The results shown in this thesis are comparable and competitive to those obtained by other state-of-the-art approaches.
47
Bowden, Zachary E. "Behavioral Logistics and Fatigue Management in Vehicle Routing and Scheduling Problems". Diss., Virginia Tech, 2016. http://hdl.handle.net/10919/79792.
Testo completoAbstract (sommario):
The vehicle routing problem (VRP), is a classic optimization problem that aims to determine the optimal set of routes for a fleet of vehicles to meet the demands of a set of customers. The VRP has been studied for many decades and as such, there are many variants and extensions to the original problem. The research presented here focuses on two different types of vehicle routing and scheduling planning problems: car shipping and fatigue-aware scheduling. In addition to modeling and solving the car shipping problem, this research presents a novel way for ways in which drivers can describe their route preferences in a decision support system. This work also introduces the first fatigue-aware vehicle scheduling problem called the Truck Driver Scheduling Problem with Fatigue Management (TDSPFM). The TDSPFM is utilized to produce schedules that keep the drivers more alert than existing commercial vehicle regulations. Finally, this work analyzes the effect of the starting alertness level on driver alertness for the remainder of the work week and examines a critical shortcoming in existing regulations.Ph. D.
48
Pugacs, Sergejs. "A clustering approach for vehicle routing problems with hard time windows". Master's thesis, Faculdade de Ciencias e Tecnologia, 2014. http://hdl.handle.net/10362/13045.
Testo completoAbstract (sommario):
Dissertação para obtenção do Grau de Mestre em
Logica ComputicionalThe Vehicle Routing Problem (VRP) is a well known combinatorial optimization problem and many studies have been dedicated to it over the years since solving the VRP optimally or near-optimally for very large size problems has many practical applications (e.g. in various logistics systems). Vehicle Routing Problem with hard TimeWindows (VRPTW) is probably the most studied variant of the VRP problem and the presence of time windows requires complex techniques to handle it. In fact, finding a feasible solution to the VRPTWwhen the number of vehicles is fixed is an NP-complete problem. However, VRPTW is well studied and many different approaches to solve it have been developed over the years. Due to the inherent complexity of the underlying problem VRPTW is NP-Hard. Therefore, optimally solving problems with no more than one hundred requests is considered intractably hard. For this reason the literature is full with inexact methods that use metaheuristics, local search and hybrid approaches which are capable of producing high quality solutions within practical time limits. In this work we are interested in applying clustering techniques to VRPTWproblem. The idea of clustering has been successfully applied to the basic VRP problem. However very little work has yet been done in using clustering in the VRPTW variant. We present a novel approach based on clustering, that any VRPTW solver can adapt, by running a preprocessing stage before attempting to solve the problem. Our proposed method, tested with a state of the art solver (Indigo), enables the solver to find solutions much faster (up to an order of magnitude speed-up). In general this comes with at slightly reduced solution quality, but in somes types of problems, Indigo is able to obtain better solutions than those obtained with no clustering.
49
McInvale, Howard D. "Land Leveling Using Optimal Earthmoving Vehicle Routing". Thesis, Virginia Tech, 2002. http://hdl.handle.net/10919/42356.
Testo completoAbstract (sommario):
This thesis presents new solution approaches for land leveling, using optimal earthmoving vehicle routing. It addresses the Shortest Route Cut and Fill Problem (SRCFP) developed by Henderson, Vaughan, Wakefield and Jacobson [2000]. The SRCFP is a discrete optimization search problem, proven to be NP-hard. The SRCFP describes the process of reshaping terrain through a series of cuts and fills. This process is commonly done when leveling land for building homes, parking lots, etc. The model used to represent this natural system is a variation of the Traveling Salesman Problem. The model is designed to limit the time needed to operate expensive, earthmoving vehicles. The model finds a vehicle route that minimizes the total time required to travel between cut and fill locations while leveling the site. An optimal route is a route requiring the least amount of travel time for an individual earthmoving vehicle.
This research addresses the SRCFP by evaluating minimum function values across an unknown response surface. The result is a cost estimating strategy that provides construction planners a strategy for contouring terrain as cheaply as possible. Other applications of this research include rapid runway repair, and robotic vehicle routing.Master of Science
50
Salhi, S. "The integration of routing into the location-allocation and vehicle composition problems". Thesis, Lancaster University, 1987. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.333016.
Testo completo