To see the other types of publications on this topic, follow the link: Clustering and vehicle routing.
Dissertations / Theses on the topic 'Clustering and vehicle routing'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Clustering and vehicle routing.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
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.
Full textAbstract:
Dissertação para obtenção do Grau de Mestre em
Logica Computicional<br>The 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.
2
Cakir, Fahrettin. "Data-centric solution methodologies for vehicle routing problems." Diss., University of Iowa, 2016. https://ir.uiowa.edu/etd/2052.
Full textAbstract:
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.
3
Castellani, Marta. "Gestione operativa della logistica distributiva mediante tecniche di clustering e vehicle routing: la piattaforma software LOG-OPTIMIZER." Master's thesis, Alma Mater Studiorum - Università di Bologna, 2010. http://amslaurea.unibo.it/1008/.
Full text
4
Rahmani, Younes. "The Multi-product Location-Routing Problem with Pickup and Delivery." Thesis, Université de Lorraine, 2015. http://www.theses.fr/2015LORR0331/document.
Full textAbstract:
Dans les problèmes de localisation-routage classiques (LRP), il s'agit de combiner des décisions stratégiques liées aux choix des sites à ouvrir (centres de traitement) avec des décisions tactiques et opérationnelles liées à l'affectation des clients aux sites sélectionnés et a la confection des tournées associées. Cette thèse propose de nouveaux modèles de localisation-routage permettant de résoudre des problématiques issues de réseaux logistiques, devenus aujourd'hui de plus en plus complexes vu la nécessité de mutualisation de ressources pour intégrer des contraintes de développement durable et des prix de carburants qui semblent augmenter de manière irrémédiable. Plus précisément, trois aspects ont été intégrés pour généraliser les modèles LRP classiques de la littérature : 1) l'aspect pickup and delivery, 2) l'aspect multi-produits, et 3) la possibilité de visiter un ou plusieurs centres de traitement dans une tournée donnée. Nous avons étudié deux schémas logistiques, qui ont donné lieu à deux nouveaux modèles de localisation et de routage, le MPLRP-PD (LRP with multi-product and pickup and delivery), qui peut être vu comme une extension des problèmes de tournées de véhicules avec collecte et livraison, intégrant une décision tactique liée à la localisation des centres de traitement (noeud avec collecte et livraison) dans un réseau de distribution à un seul échelon, et le 2E-MPLRP-PD (Two-echelon LRP with multi-product and pickup and delivery) qui est une généralisation du LRP à deux échelons avec les contraintes citées plus-haut. Ces deux modèles ont été formalisés par des programmes linéaires en variables mixtes (MIP). Des techniques de résolution, basées sur des méthodes de type heuristique, clustering, métaheuristique, ont été proposées pour résoudre le MPLRP-PD et le 2E-MPLRP-PD. Les jeux d'essais de la littérature ont été généralisés pour tester et valider les algorithmes proposés<br>In the framework of Location-Routing Problem (LRP), the main idea is to combine strategic decisions related to the choice of processing centers with tactical and operational decisions related to the allocation of customers to selected processing centers and computing the associated routes. This thesis proposes a new location-routing model to solve problems which are coming from logistics networks, that became nowadays increasingly complex due to the need of resources sharing, in order to integrate the constraints of sustainable development and fuels price, which is increasing irreversibly. More precisely, three aspects have been integrated to generalize the classical LRP models already existed in the literature: 1) pickup and delivery aspect, 2) multi-product aspect, and 3) the possibility to use the processing centers as intermediate facilities in routes. We studied two logistics schemes gives us two new location-routing models: (i) MPLRP-PD (Multi-product LRP with pickup and delivery), which can be viewed as an extension of the vehicle routing problem with pick-up and delivery, including a tactical decision related to the location of processing centers (node with pick-up and delivery), and (ii) 2E-MPLRP-PD (Two-echelon multi-product LRP with pickup and delivery), which is a generalization of the two-echelon LRP. Both models were formalized by mixed integer linear programming (MIP). Solving techniques, based on heuristic methods, clustering approach and meta-heuristic techniques have been proposed to solve the MPLRP-PD and the 2E-MPLRP-PD. The benchmarks from the literature were generalized to test and to validate the proposed algorithms
5
Tejaswi, Nunna. "Performance Analysis on Hybrid and ExactMethods for Solving Clustered VRP : A Comparative Study on VRP Algorithms." Thesis, Blekinge Tekniska Högskola, Institutionen för datalogi och datorsystemteknik, 2017. http://urn.kb.se/resolve?urn=urn:nbn:se:bth-14112.
Full textAbstract:
Context: The Vehicle Routing Problem is an NP-hard problem with a combination of varieties oftopics like logistics, optimization research and data mining. There is a vast need of vehicle routingsolutions in day to day like with different constraints. According to the requirements, this problem hasbeen a field of interest to a lot of researchers who incorporate scientific methods to combine andinnovate new solutions to optimize the routing. Being an np-hard problem, it is almost impossible tocompute the solutions to optimality but years of research on this area has paid off quite significantlyand the solutions are optimized little by little and better than before. Some applications may or maynot find slight difference in the performance as a considerable affect but some applications orscenarios heavily depend on the performance of the solution where it is very vital that the solution isoptimized to the fullest. As a data mining technique clustering has been used very prominently in caseof portioning scenarios and similarly it has also began to surface in implementing VRP solutions.Although it has recently emerged into the Vehicle Routing era and shown some significant results, ithas not yet come into an open state or awareness. The awareness regarding clustering matters in ahuge extent to be considered by most of the recent researchers who formulate new algorithms to solveVRP and help them further optimize their solution. Objectives: In this study the significance of clustering has been considered to find out how the usageof clustering techniques can alter the performance of VRP based solutions favorably. Then to test theresults of two recently proposed cluster based algorithms, a comparison has been made to other typesof algorithms which prove how the algorithms stand with various methods. Methods: A literature review is performed using various articles that have been gathered from GoogleScholar and then an empirical experiment was conducted on the results available in the papers. Thisexperiment was done by performing a comparative analysis. Results: For the literature review the results were gathered from all the articles based on theirresearch, experience, use of clustering and how their result was improved by using clustering methodsin their formulations. Considering the experiment, the results of both the algorithm were comparedwith the results of five other papers who aim to solve the VRP using exactly the same instances thatwere used in the two algorithms in order to compare valid results on the same variables. Then theresults were analyzed for the purpose of comparison and conclusions were drawn accordingly. Conclusions: From the research performed in this paper we can conclude the vast significance ofclustering techniques that were drawn based on practical test results of various authors. From theexperiment performed it is clear that the Hybrid algorithm has a much higher performance than anyother algorithm it has been compared to. This algorithm has also been proven to enhance itsperformance due to the implementation of clustering techniques in their formulation. Since the resultswere only based on performance that is, in this case the total distance of the final route, future studyindicates the implementation of algorithms to compare them on basis of time complexity and spacecomplexity as well.
6
Rahmani, Younes. "The Multi-product Location-Routing Problem with Pickup and Delivery." Electronic Thesis or Diss., Université de Lorraine, 2015. http://www.theses.fr/2015LORR0331.
Full textAbstract:
Dans les problèmes de localisation-routage classiques (LRP), il s'agit de combiner des décisions stratégiques liées aux choix des sites à ouvrir (centres de traitement) avec des décisions tactiques et opérationnelles liées à l'affectation des clients aux sites sélectionnés et a la confection des tournées associées. Cette thèse propose de nouveaux modèles de localisation-routage permettant de résoudre des problématiques issues de réseaux logistiques, devenus aujourd'hui de plus en plus complexes vu la nécessité de mutualisation de ressources pour intégrer des contraintes de développement durable et des prix de carburants qui semblent augmenter de manière irrémédiable. Plus précisément, trois aspects ont été intégrés pour généraliser les modèles LRP classiques de la littérature : 1) l'aspect pickup and delivery, 2) l'aspect multi-produits, et 3) la possibilité de visiter un ou plusieurs centres de traitement dans une tournée donnée. Nous avons étudié deux schémas logistiques, qui ont donné lieu à deux nouveaux modèles de localisation et de routage, le MPLRP-PD (LRP with multi-product and pickup and delivery), qui peut être vu comme une extension des problèmes de tournées de véhicules avec collecte et livraison, intégrant une décision tactique liée à la localisation des centres de traitement (noeud avec collecte et livraison) dans un réseau de distribution à un seul échelon, et le 2E-MPLRP-PD (Two-echelon LRP with multi-product and pickup and delivery) qui est une généralisation du LRP à deux échelons avec les contraintes citées plus-haut. Ces deux modèles ont été formalisés par des programmes linéaires en variables mixtes (MIP). Des techniques de résolution, basées sur des méthodes de type heuristique, clustering, métaheuristique, ont été proposées pour résoudre le MPLRP-PD et le 2E-MPLRP-PD. Les jeux d'essais de la littérature ont été généralisés pour tester et valider les algorithmes proposés<br>In the framework of Location-Routing Problem (LRP), the main idea is to combine strategic decisions related to the choice of processing centers with tactical and operational decisions related to the allocation of customers to selected processing centers and computing the associated routes. This thesis proposes a new location-routing model to solve problems which are coming from logistics networks, that became nowadays increasingly complex due to the need of resources sharing, in order to integrate the constraints of sustainable development and fuels price, which is increasing irreversibly. More precisely, three aspects have been integrated to generalize the classical LRP models already existed in the literature: 1) pickup and delivery aspect, 2) multi-product aspect, and 3) the possibility to use the processing centers as intermediate facilities in routes. We studied two logistics schemes gives us two new location-routing models: (i) MPLRP-PD (Multi-product LRP with pickup and delivery), which can be viewed as an extension of the vehicle routing problem with pick-up and delivery, including a tactical decision related to the location of processing centers (node with pick-up and delivery), and (ii) 2E-MPLRP-PD (Two-echelon multi-product LRP with pickup and delivery), which is a generalization of the two-echelon LRP. Both models were formalized by mixed integer linear programming (MIP). Solving techniques, based on heuristic methods, clustering approach and meta-heuristic techniques have been proposed to solve the MPLRP-PD and the 2E-MPLRP-PD. The benchmarks from the literature were generalized to test and to validate the proposed algorithms
7
Takebayashi, Fabiana. "Um modelo de localização-roteirização de instalações de transferência para distribuição de carga urbana baseado no método de cluster-first route-second." Universidade de São Paulo, 2014. http://www.teses.usp.br/teses/disponiveis/3/3148/tde-16112015-113249/.
Full textAbstract:
O trabalho apresenta o desenvolvimento e a aplicação de um modelo de localização de centros intermediários de consolidação e redistribuição de cargas em um ambiente urbano brasileiro. O método integra o TransCAD e o OpenSolver e é aplicado à cidade de Curitiba, uma das dez mais populosas do Brasil. O método proposto é caracterizado como um modelo de localização-roteirização baseado em agrupamento e subsequente roteirização, identificado na literatura por cluster-first routesecond; a adoção deste ordenamento permite tratar o problema para o atendimento de muitos estabelecimentos, como os até 65 mil em alguns dos cenários no estudo de caso de Curitiba. Cada agrupamento representa os pontos a serem visitados em uma única viagem e o processo inicial tenta minimizar as distâncias entre os estabelecimentos de cada grupo; na fase seguinte o melhor roteiro é computado para cada grupo; a terceira etapa consiste em calcular, para cada grupo e candidato, a distância total percorrida na viagem; por fim, a implantação ou não dos candidatos a centros de distribuição é obtida com a minimização em um modelo de programação linear inteira dos custos de aquisição e de operação dos centros de distribuição e dos custos de transportes. A dissertação também aborda a crescente percepção da importância da logística urbana à qualidade de vida nas cidades onde o adensamento populacional acirra a disputa pelo espaço viário e o conceito de City Logistics, que delineia entre outras medidas o ambiente cooperativo no qual implantação de centros de distribuição urbanos deve ocorrer.<br>This work presents the development and application of a model for the location of intermediary consolidation and redistribution freight centers in Brazilian cities. The method integrates TransCad and OpenSolver, and its use was evaluated with data from the City of Curitiba one of the ten largest in Brazil. The proposed method is characterized as a location-routing model based on clustering and subsequent tour building known as cluster-first route-second. This enables dealing with problem instances containing as many as 65 thousand customers. Each cluster comprehends the points visited on a single trip and the initial process minimizes the distances between customers; the routes are calculated in the next phase and the third step consists in computing the total distance covered in each trip for every cluster and every candidate; finally, the implementation of each distribution center candidate is decided by minimizing the costs of acquisition, operation and distribution, using an integer linear programming model. The dissertation also highlights the growing realization of the importance of urban freight transport to quality of life, especially in cities where increasing population density intensifies the competition for road space, and City Logistics concepts, that outline among other measures the cooperative environment where implementation of urban distribution centers should occur.
8
Zhang, Xinglong. "Network vehicle routing problems." Diss., Georgia Institute of Technology, 1998. http://hdl.handle.net/1853/21710.
Full text
9
Jézéquel, Antoine. "Probabilistic vehicle routing problems." Thesis, Massachusetts Institute of Technology, 1985. http://hdl.handle.net/1721.1/15318.
Full textAbstract:
Thesis (M.S.)--Massachusetts Institute of Technology, Dept. of Civil Engineering, 1985.<br>MICROFICHE COPY AVAILABLE IN ARCHIVES AND ENGINEERING.<br>Bibliography: leaves 78-79.<br>by Antoine Jézéquel.<br>M.S.
10
Mourgaya, Virapatrin Magalie. "The periodic vehicle routing problem : planning before routing." Bordeaux 1, 2004. http://www.theses.fr/2004BOR12843.
Full textAbstract:
Le problème de tournées de véhicules multipériodiques consisté à planifier des visites client sur un horizon de temps donné en les affectant à des tournées de véhicule. Les fréquences de visites ou espacement entre elles sont prescrits. Ces contraintes peuvent prendre la forme de scénarios de visites admissibles. Nous étudions les différentes variantes de ce problème et proposons une classification. Nous présentons ensuite un algorithme heuristique pour un modèle de planification tactique qui optimise la répartition de la charge et la régionalisation des tournées. L'objectif traditionnel de minimisation des distances parcourues est reporté au niveau des décisions opérationnelles. Cette approche nous a permis d'obtenir des solutions pratiques pour un problème industriel avec 16658 visites à planifier sur un horizon de 20 jours. Nous proposons enfin un heuristique d'arrondi basé sur la méthode de génération de colonnes. Cette méthode basée sur l'optimisation globale permet d'obtenir des solutions de meilleure qualité pour les problèmes de planification à court terme avec de l'ordre de 50 clients.
11
Sheasby, Janice. "Lagrangean heuristics for vehicle routing." Thesis, Coventry University, 1996. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.320251.
Full text
12
Hung, Hing-fai Daniel, and 孔慶輝. "Vehicle routing for heterogeneous fleet." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 1992. http://hub.hku.hk/bib/B31210326.
Full text
13
Pereira, Victor Caon. "Vehicle Routing for Emergency Evacuations." Diss., Virginia Tech, 2013. http://hdl.handle.net/10919/52361.
Full textAbstract:
This dissertation introduces and analyzes the Bus Evacuation Problem (BEP), a unique Vehicle Routing Problem motivated both by its humanitarian significance and by the routing and scheduling challenges of planning transit-based, regional evacuations. First, a variant where evacuees arrive at constant, location-specific rates is introduced. In this problem, a fleet of capacitated buses must transport all evacuees to a depot/shelter such that the last scheduled pick-up and the end of the evacuee arrival process occurs at a location-specific time. The problem seeks to minimize their accumulated waiting time, restricts the number of pick-ups on each location, and exploits efficiencies from service choice and from allowing buses to unload evacuees at the depot multiple times. It is shown that, depending on the problem instance, increasing the maximum number of pick-ups allowed may reduce both the fleet size requirement and the evacuee waiting time, and that, past a certain threshold, there exist a range of values that guarantees an efficient usage of the available fleet and equitable reductions in waiting time across pick-up locations. Second, an extension of the Ritter (1967) Relaxation Algorithm, which explores the inherent structure of problems with complicating variables and constraints, such as the aforementioned BEP variant, is presented. The modified algorithm allows problems with linear, integer, or mixed-integer subproblems and with linear or quadratic objective functions to be solved to optimality. Empirical studies demonstrate the algorithm viability to solve large optimization problems. Finally, a two-stage stochastic formulation for the BEP is presented. Such variant assumes that all evacuees are at the pick-up locations at the onset of the evacuation, that the set of possible demands is provided, and, more importantly, that the actual demands become known once buses visit the pick-up locations for the first time. The effect of exploratory visits (sampling) and symmetry is explored, and the resulting insights used to develop an improved formulation for the problem. An iterative (dynamic) solution algorithm is proposed.<br>Ph. D.
14
Villegas, Juan Guillermo. "Vehicle routing problems with trailers." Troyes, 2010. http://www.theses.fr/2010TROY0027.
Full textAbstract:
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 extensions<br>Vehicle 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
15
Hung, Hing-fai Daniel. "Vehicle routing for heterogeneous fleet." [Hong Kong : University of Hong Kong], 1992. http://sunzi.lib.hku.hk/hkuto/record.jsp?B1332701X.
Full text
16
Cattaruzza, Diego. "Vehicle Routing for City Logistics." Thesis, Saint-Etienne, EMSE, 2014. http://www.theses.fr/2014EMSE0737/document.
Full textAbstract:
Le transport de marchandises dans les zones urbaines est un sujet important de nos jours. Le transport est une activité vitale pour les villes, mais implique pollution, congestion, accidents. La logistique urbaine vise à optimiser les processus logistiques et de transports urbains en tenant compte des aspects environnementaux et sociaux. Cette thèse traite de cette thématique et fait partie du projet MODUM.MODUM vise à étudier un système de livraison basé sur des centres de distribution urbains. Nous présentons une classification et une analyse des mouvements de marchandises et des problèmes de tournées de véhicules (VRP) associés.La deuxième partie propose une revue complète des travaux de recherche traitant des problème VRP avec excursions multiples (MTVRP). Le MTVRP est une extension du VRP où les véhicules sont autorisés à effectuer plusieurs tournées. Nous proposons une heuristique pour le MTVRP qui est par la suite adaptée pour un problème plus riche, le MTVRP avec fenêtres de temps et dates de disponibilité. Il s'agit d'une variante du MTVRP où à chaque client est associée une fenêtre de temps et à chaque marchandise une date de disponibilité qui représente l'instant où elle devient disponible au dépôt.Par la suite, nous étudions une variante du MTVRP où les marchandises sont classées par types de produits qui ne peuvent pas être transportés dans le même véhicule. Une analyse est effectuée pour montrer l’avantage des tournées multiples pour le problème de dimensionnement des flottes.Enfin, nous décrivons le problème de tournées qui se pose dans MODUM et le simulateur qui est développé pour évaluation du système<br>Transportation of merchandise in urban areas has become an important nowadays topic. In fact, transportation is a vital activity for each city, but entail pollution, congestion, accidents.City logistics aims at optimizing the whole urban logistics and transportation process, taking into account environmental and social aspects. This thesis, that is part of the MODUM project, finds its location in this area of research. In particular, MODUM aims at studying a delivery system based on City Distribution Centers.We first present a classification and an analysis of urban good movements and routing problems peculiar to metropolitan areas. A second survey proposes a complete collection of articles that has been done on the Multi Trip Vehicle Routing Problem (MTVRP). The MTVRP is an extension of the Vehicle Routing Problem (VRP) where vehicles are allowed to perform several trips.We propose an efficient heuristic for the MTVRP that is, in a subsequent step, adapted to a new routing problem, the MTVRP with Time Windows and Release Dates (MTVRPTWR). It is a variant of the MTVRP where each customer is associated with a time window and each merchandise is associated with a release date that represents the instant it becomes available at the depot.We, then, study a variant of the MTVRP where goods belong to different commodities that cannot be transported at the same time by the same vehicle. An analysis is conducted on the benefits of the multi-trip aspect in fleet dimensioning problems.Finally we describe the complex routing problem that arises in MODUM and the simulator that is developed to evaluate the performances of the system
17
Rincon, Garcia Nicolas. "Freight transport, routing software and time-dependent vehicle routing models." Thesis, University of Southampton, 2016. https://eprints.soton.ac.uk/397141/.
Full textAbstract:
Routing and scheduling software is part of the Information and Technology systems available to support the transport industry, and uses complex algorithms along with geographical representations of the road network to allow better planning of daily collection and delivery schedules. This research reviews the evolution of routing and scheduling software, the algorithms used along with reported barriers to wider take-up and potential industry driven improvements that could be made. A survey of transport companies in the United Kingdom was conducted in order to validate and prioritize the software capabilities that require the most development according to the new challenges that the industry is facing. Responses suggested that companies required improved route optimization to tackle congestion based on time-dependent data and models, and greater accuracy in the representation of the road network. Not considering congestion leads to the underestimation of travel times and the production of inaccurate schedules. Literature shows that operational research techniques are available to solve problems that represent real world conditions, but research into the relative merits of using time-dependent models needs to be undertaken. Although exact methods have been developed to solve the Vehicle Routing Problem, they cannot cope with large instances and rich variants that are required by the industry. Therefore, metaheuristic algorithms are usually implemented in routing software. A reported barrier in metaheuristic algorithms is the lack of accuracy (the difference between optimal or best-known values and the result of the proposed algorithm). In this research an algorithm was developed using elements of Large Neighbourhood Search that is capable to substantially improve the state of the art for the time-dependent Vehicle Routing Problem. Comparison of results with available test instances shows that the proposed algorithm is capable of obtaining a reduction in the number of vehicles (4.15%), travel distance (10.88%) and travel time (12.00%) compared to previous implementations in reasonable time. A variant that considers the Rules on Drivers’ hours required in the scheduling of vehicles over 3.5 tons in the European Union and the UK is also introduced. Analysis of results show result improvements in number of vehicles (19.0%), travel distance (17.7%) and route duration (4.4%) compared to previous implementations.
18
Roberts, Daron R. "Algorithms for stochastic vehicle routing problems." Thesis, Imperial College London, 1999. http://hdl.handle.net/10044/1/11887.
Full text
19
Jacobs, Charlotte Diane. "The vehicle routing problem with backhauls." Diss., Georgia Institute of Technology, 1987. http://hdl.handle.net/1853/25629.
Full text
20
Carreto, Carlos A. C. "Visual interactive methods for vehicle routing." Thesis, Coventry University, 2000. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.246575.
Full text
21
Oukil, Amar. "Exploiting Sparsity in Vehicle Routing Algorithms." Thesis, Lancaster University, 2008. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.518139.
Full text
22
SILVA, RODRIGO CASADO OLIVEIRA DA. "APPRAISAL OF VEHICLE ROUTING SYSTEM IMPLEMENTATION." PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 2007. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=11511@1.
Full textAbstract:
Com a era da globalização e a introdução da filosofia de
Gestão da Cadeia de
Suprimentos, os clientes têm se tornado cada vez mais
exigentes no que diz respeito à
qualidade e prazos de entrega, gerando uma competitividade
crescente e uma busca
por serviços cada vez mais customizados que, para as
empresas de distribuição de
produtos, tem se tornado um fator cada vez mais importante
na obtenção de vantagem
competitiva e conquista de fatias cada vez maiores do
mercado. Nesse sentido, muitas
empresas de transporte têm tentado dar maior
confiabilidade, mais velocidade e
flexibilidade, buscando obter maior eficiência e
pontualidade nas tarefas de entrega
e/ou coleta; um melhor aproveitamento da frota e dos
motoristas; menores tempos de
ciclo; melhor planejamento das rotas, gerando assim
sensíveis reduções de custos
operacionais, melhoria da imagem da empresa no mercado e,
em função disso, uma
conquista cada vez maior de mercado. Nesse sentido, de modo
a obter excelência nos
processos de distribuição física, muitas empresas têm
adquirido os chamados sistemas
de roteirizarão e programação de veículos ou, simplesmente,
roteirizadores. Dado o
crescimento na utilização de roteirizadores para redução de
custos operacionais e a
possibilidade por parte do autor de participar da
implementação dessa tecnologia em
uma empresa, os objetivos dessa dissertação são: Descrever
a operação da Empresa
Alfa onde foi realizada a implementação do roteirizador de
veículos e a apresentação
do processo de implementação do roteirizador na operação.
Como o autor fez parte da
implementação do roteirizador na Empresa Alfa, a
metodologia utilizada para a
elaboração desse trabalho incluiu: pesquisa bibliográfica,
visitas in loco e entrevistas
não estruturadas junto aos envolvidos na operação. O
resultado desta dissertação é
uma análise da operação da Empresa Alfa durante a
implementação do roteirizador,
mostrando seus pontos positivos e suas dificuldades
extraídos apos finalizado o
processo de implementação.<br>Nowadays with the globalization and the introduction of the
Supply chain
management philosophy, the customers become more demanding
in order to get
better quality in delivery time, increasing competitiveness
and a search for
customized services that, for distribution companies, it
has become the most
important factor in order to get competitive advantage and
to increase the market
share. In accordance with these ideas, many distribution
companies have tried to
improve the reliability, speed and flexibility, in order to
get higher efficiency and
punctuality in the deliveries; better fleet and drivers
utilization; lower time to
planning routes, generating cost reduction, improvements of
the company`s image
in the market, and higher market share. Trying to get
excellence in distribution
process, many companies have acquired the routing and
scheduling systems. Due
to the growth of routing systems use and the possibility
for the author to
participate in an implementation of this technology in a
company, the objectives
of this work are: to describe the operation of the Alpha
Company`s where the
implementation has been done; and present the routing
system implementation
process. Since the author was part of the team in the
implementation of routing
system in the Alpha Company, the methodology used for the
elaboration of this
work included: bibliographical research, visits in loco to
the Alpha Company`s
operations and non structuralized interviews with the
involved parts in the
operation. As a result of this work, we have an analysis of
the operation during the
implementation of the Routing System in line with the main
results getting after
finished the implementation process.
23
Pavone, Marco Ph D. Massachusetts Institute of Technology. "Dynamic vehicle routing for robotic networks." Thesis, Massachusetts Institute of Technology, 2010. http://hdl.handle.net/1721.1/59665.
Full textAbstract:
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Aeronautics and Astronautics, 2010.<br>Cataloged from PDF version of thesis.<br>Includes bibliographical references (p. 149-156).<br>Recent years have witnessed great advancements in the sciences and technology of autonomy, robotics and networking. This dissertation develops concepts and algorithms for dynamic vehicle routing (DVR), that is, for the automatic planning of optimal multi-vehicle routes to provide service to demands (or more generally to perform tasks) that are generated over time by an exogenous process. We consider a rich variety of scenarios relevant for robotic applications. We begin by reviewing some of the approaches available to tackle DVR problems. Next, we study different multi-vehicle scenarios based on different models for demands (in particular, demands with time constraints, demands with different priority levels, and demands that must be transported from a pick-up to a delivery location). The performance criterion used in these scenarios is either the expected waiting time of the demands or the fraction of demands serviced successfully. In each specific DVR scenario we adopt a rigorous technical approach, which we call algorithmic queueing theory and which relies upon methods from queueing theory, combinatorial optimization, and stochastic geometry. Algorithmic queueing theory consists of three basics steps: 1) queueing model of the DVR problem and analysis of its structure; 2) establishment of fundamental limitations on performance, independent of algorithms; and 3) design of algorithms that are either optimal or constant-factor away from optimal. In the second part of the dissertation, we address problems concerning the implementation of routing policies in large-scale robotic networks, such as adaptivity and decentralized computation. We first present distributed algorithms for environment partitioning, and then we apply them to devise routing policies for DVR problems that (i) are spatially distributed, scalable to large networks, and adaptive to network changes, and (ii) have remarkably good performance guarantees. The technical approach developed in this dissertation is applicable to a wide variety of DVR problems: several possible extensions are discussed throughout the thesis.<br>by Marco Pavone.<br>Ph.D.
24
Noorizadegan, Mahdi. "On vehicle routing with uncertain demands." Thesis, University of Warwick, 2013. http://wrap.warwick.ac.uk/60382/.
Full textAbstract:
In this research, we present a theoretical and computational framework for studying the vehicle routing problem with uncertain demands (VRPUD). We combine approaches in stochastic optimization and techniques in mixed integer programming to solve two main variants of the vehicle routing problem with uncertain demands. We first present a polyhedral study for deterministic heterogenous vehicle routing problems (HVRP) to develop a relatively efficient formulation such that its corresponding counterpart with uncertainty is tractable via mixed integer programming. Having assumed customers’ demand is uncertain, we apply three single-stage approaches within stochastic optimization to the HVRP with uncertain demands. The three-single stage approaches are chance constrained programming, Ben-Tal and Nemirovski, and Bertsimas and Sim robust optimization approaches. Then, we plug the corresponding formulation for each approach into a branch-and-cut method. Moreover, we propose a new framework within the branch-and-price framework to formulate the capacitated vehicle routing problem (CVRP) with uncertain demands. In addition to the three single-stage approaches, we apply a two-stage stochastic approach to the capacitated vehicle routing problem with uncertain demands. Our proposed framework enables us to model di↵erent types of uncertainty while the complexity of the resulting problem remains the same. Finally, we present extensive computational experiments for the deterministic HVRP, the HVRP with uncertain demands and the CVRP with uncertain demands. In the computational experiments we first investigate efficiency of several types of valid inequalities and lifting techniques for the deterministic HVRP. Then, using simulation and a scenario based technique we assess the performance, advantages and disadvantages of the aforementioned stochastic optimization approaches for the HVRP with uncertain demands and the CVRP with uncertain demands. We show that among single-stage approaches of stochastic optimization, those with control parameters outperform those without control parameters in terms of total expected cost. Also, we show that the higher protection level does not necessarily result in better solutions as higher protection levels may impose unnecessary extra costs. Moreover, as our computational experiments suggest, the two-stage models for the CVRP dominate the single-stage approaches for all protection level scenarios.
25
Kefalidou, Genovefa. "Cognitive processes and vehicle routing problems." Thesis, Lancaster University, 2011. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.654458.
Full textAbstract:
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.
26
Doerner, Karl, Manfred Gronalt, Richard F. Hartl, Marc Reimann, Christine Strauß, and Michael Stummer. "SavingsAnts for the vehicle routing problem." SFB Adaptive Information Systems and Modelling in Economics and Management Science, WU Vienna University of Economics and Business, 2001. http://epub.wu.ac.at/1130/1/document.pdf.
Full textAbstract:
In this paper we propose a hybrid approach for solving vehicle routing problems. The main idea is to combine an Ant System (AS) with a problem specific constructive heuristic, namely the well known Savings algorithm. This differs from previous approaches, where the subordinate heuristic was the Nearest Neighbor algorithm initially proposed for the TSP. We compare our approach with some other classic, powerful meta-heuristics and show that our results are competitive.<br>Series: Report Series SFB "Adaptive Information Systems and Modelling in Economics and Management Science"
27
Johar, Farhana. "Vehicle routing problem with availability constraints." Thesis, University of Southampton, 2015. https://eprints.soton.ac.uk/389516/.
Full textAbstract:
This work is concerned with solving the vehicle routing problem (VRP) which takes into account the customer's release and due date. The problem studied can also be categorized as a non-classical VRP as the departure times of vehicles depend on the dates of orders released from the production line and become available for the distribution process. Hence, the problem is known as VRP with availability constraints (VRPAC). The VRPAC is investigated through two stages. In the first stage, vehicle routing problem with release and due date (VRPRDD) is treated. At the beginning of the planning, it is assumed that the dates where the customer orders become available are known. A mathematical formulation is developed to represent the problem studied which has been solved by several heuristics, i.e. Variable Neighborhood Search (VNS), Large Neighborhood Search (LNS) and Tabu Search (TS). The algorithms are written in C++ and run on a PC computer with an Intel PentiumCore by using 56's Solomon instances with some modification. Different kinds of vehicle routing problem has been tackled in order to see the performance of proposed heuristics. The results are then compared in order to find the best method which yields the least routing cost solution. From the outcome obtained, VNS is proved to be the best algorithm which generates the least cost solution to our problem. Further investigation has been carried out in stage two which considers the extension of VRPRDD. The coordination of production sequence and vehicle routing (PS-VRPRDD) is the main subject to our problem studied in which the best production sequence will leads to the least routing. Two proposed algorithms have been used to run the test instances. The first is classical decomposition approach; Alternate which decompose the problems into two sub-problems, i.e. production sequence and vehicle routing. This will be used as benchmark to the second approach; InOneMove which take these two decisions of the sub-problems as a whole. Decision on both sub-problems is considered simultaneously as one move. The results proved that effective coordination shows the large potential savings that attract the interest of industrial distributors in optimizing their distribution process in practice.
28
Dehghan, Nasiri Saeideh. "Vehicle routing on real road networks." Thesis, Lancaster University, 2014. http://eprints.lancs.ac.uk/71922/.
Full textAbstract:
The vehicle routing problem (VRP) has received particular attention, in the field of transportation and logistics. Producing good solutions for the problem is of interest both commercially and theoretically. Reliable solutions to real life applications require an approach based on realistic assumptions that resemble real-world conditions. In that respects, this thesis studies vehicle routing problems on real road networks addressing aspects of the problem that need to be modelled on the original road network graph and aims to provide appropriate modelling techniques for solving them. As a preliminary step, chapter 2 studies the travelling salesman problem (TSP) on real road networks, referred to as the Steiner TSP (STSP) and proposes alternative integer programming formulations for the problem and some other related routing problems. The performances of formulations is examined both theoretically and computationally. Chapter 3 highlights the fact that travel speeds on road networks are correlated and uses a real traffic dataset to explore the structure of this correlation. In conclusion, it is shown that there is still significant spatial correlations between speeds on roads that are up to twenty links apart, in our congested road network. Chapter 4 extends chapter 2 and incorporates the findings of chapter 3 into a modelling framework for VRP. The STSP with correlated costs is defined as a potentially useful variant of VRP that considers the costs in the STSP to be stochastic random variables with correlation. The problem is then formulated as a single-objective problem with eight different integer programming formulations presented. It is then shown how to account for three different correlation structures in each of the formulations. Chapter 5 considers the VRPs with time windows and shows how most of the exact algorithms proposed for them, might not be applicable if the problem is defined on the original road network graph due to the underlying assumption of these algorithms that the cheapest path between a pair of customers is the same as the quickest path. This assumption is not always true on a real road network. Instead some alternative pricing routines are proposed that can solve the problem directly on the original graph.
29
Bula, Gustavo Alfredo. "Vehicle Routing for Hazardous Material Transportation." Thesis, Troyes, 2018. http://www.theses.fr/2018TROY0014.
Full textAbstract:
L'objectif de cette thèse est d'étudier le problème du transport de matières dangereuses (HazMat) vu comme un problème de tournées de véhicules à flotte hétérogène. Les décisions pour ce type de transport comportent des objectifs différents, parfois antagonistes. Deux sont pris en compte dans ce travail, le coût et le risque. La première tâche entreprise a été la formulation d'un modèle mathématique pour la minimisation du risque, qui dépend du type de véhicule, du matériel transporté et du changement de charge lorsque le véhicule passe d'un client à un autre. Une approximation linéaire par morceaux est utilisée pour conserver une formulation de programmation linéaire en nombres entiers mixtes.Des méthodes hybrides basées sur des explorations de voisinages sont proposées pour traiter la minimisation du risque. Cela comprend l'étude des structures de voisinages et le développement d'un algorithme de descente à voisinages variables (VND) pour la recherche locale, ainsi qu'un mécanisme de perturbation des solutions. Une post-optimisation est appliquée pour améliorer la qualité des solutions obtenues.Enfin, deux approches, un algorithme basé sur la dominance multi-objectif et une méta-heuristique de type epsilon- contrainte, sont développées pour traiter la version multi-objectif. Deux mesures de performance sont utilisées : l'hyper volume et la ∆-métrique. Les approximations de fronts montrent qu'une légère augmentation du coût total des tournées peut entraîner une forte réduction en pourcentage des risques<br>The main objective of this thesis is to study the hazardous materials (HazMat) transportation problem considered as a heterogeneous fleet vehicle routing problem. HazMat transportation decisions comprise different and sometimes conflicting objectives. Two are considered in this work, the total routing cost and the total routing risk. The first task undertaken was the formulation of a mathematical model for the routing risk minimization, which depends on the type of vehicle, the material being transported, and the load change when the vehicle goes from one customer to another. A piecewise linear approximation is employed to keep a mixed integer linear programing formulation.Hybrid solution methods based on neighborhood search are explored for solving the routing risk minimization. This includes the study of neighborhood structures and the development of a Variable Neighborhood Descent (VND) algorithm for local search, and a perturbation mechanism (shaking neighborhoods). A post-optimization procedure is applied to improve the solution quality.Finally, two different solution approaches, a multi-objective dominance-based algorithm and a meta-heuristic epsilon-constraint method are employed for addressing the multi-objective version of the problem. Two performance metrics are used: the hyper volume and the ∆-metric. The front approximations show that a small increment in the total routing cost can produce a high reduction in percentage of the expected consequences given the probability of a HazMat transportation incident
30
Lafifi, Sohaib. "Vehicle routing problems with resources synchronization." Thesis, Compiègne, 2014. http://www.theses.fr/2014COMP1992.
Full textAbstract:
Cette thèse porte sur la résolution de problèmes de transport qui intègrent des contraintes temporelles considérant les fenêtres de temps, la synchronisation des visites et l’équilibrage des services. Ces problèmes trouvent plusieurs applications dans le monde réel.L’objectif de nos recherches est l’élaboration de nouvelles méthodes de résolution pour les problèmes considérés en examinant leur performance avec une étude comparative par rapport aux différentes approches de la littérature. Deux variantes sont traitées. Le premier cas étudie le Problème de Tournées de Véhicules avec Fenêtres de Temps (VRPTW). Nous proposons de nouveaux prétraitements et bornes inférieures pour déterminer le nombre de véhicules nécessaires en s’inspirant de travaux menés en ordonnancement (raisonnement énergétique) et d’autres problèmes combinatoires comme la clique maximum et les problèmes de bin-packing. Nous présentons également un algorithme d’optimisation par essaim particulaire qui traite de la minimisation du nombre de véhicules puis de celle du temps de trajet total. Le deuxième cas étudie le Problème de Tournées de Véhicules avec des Fenêtres de Temps et des Visites Synchronisées (VRPTWSyn). Nous proposons plusieurs méthodes basées sur des approches heuristiques et des formulations linéaires avec l’incorporation d’inégalités valides pour tenir compte de la contrainte de synchronisation<br>This dissertation focuses on vehicle routing problems, one of the major academic problems in logistics. We address NP-Hard problems that model some realworld situations particularly those with different temporal constraints including time windows, visit synchronization and service balance.The aim of this research is to develop new algorithms for the considered problems,investigate their performance and compare them with the literature approaches.Two cases are carried out. The first case studies the Vehicle Routing Problem with Time Windows (VRPTW). We propose new lower bound methods for the number of vehicles. Then we present a Particle Swarm Optimization algorithm dealing with the Solomon objective. The second case studies the VehicleRouting Problem with Time Windows and Synchronized Visits (VRPTWsyn).Both exact methods and heuristics are proposed and compared to the literature approaches
31
Ding, Ranran. "A Clustering-based Multi-channel Vehicle-to-Vehicle (V2V) Communication System." University of Cincinnati / OhioLINK, 2010. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1267545099.
Full text
32
Ben, Ticha Hamza. "Vehicle Routing Problems with road-network information." Thesis, Université Clermont Auvergne (2017-2020), 2017. http://www.theses.fr/2017CLFAC071/document.
Full textAbstract:
Les problèmes de tournées de véhicules (VRPs) ont fait l’objet de plusieurs travaux de recherche depuis maintenant plus de 50 ans. La plupart des approches trouvées dans la littérature s’appuient sur un graphe complet ou un nœud est introduit pour tout point d’intérêt du réseau routier (typiquement les clients et le dépôt). Cette modélisation est, implicitement, basée sur l’hypothèse que le meilleur chemin entre toute paire de points du réseau routier est bien défini. Cependant, cette hypothèse n’est pas toujours valide dans de nombreuses situations. Souvent, plus d’informations sont nécessaires pour modéliser et résoudre correctement le problème. Nous commençons par examiner ces situations et définir les limites de la modélisation basée sur un graphe complet. Nous proposons un état de l’art des travaux qui examinent ces limites et qui traitent des VRPs en considérant plus d’informations issues du réseau routier. Nous décrivons les approches alternatives proposées, à savoir la modélisation utilisant un multi-graphe et celle utilisant la résolution directe sur un graph représentant le réseau routier. Dans une seconde étude, nous nous intéressons à l’approche basée sur la construction d’un multi-graphe. Nous proposons, d’abord, un algorithme qui permet de calculer d’une manière efficace la représentation par multi-graph du réseau routier. Puis, nous présentons une analyse empirique sur l’impact de cette modélisation sur la qualité de la solution. Pour ce faire, nous considérons le problème classique VRPTW comme un problème de pilote. Par la suite, nous développons une méthode heuristique efficace afin de résoudre le VRPTW basée sur une représentation par un multi-graphe.Dans une troisième étape, nous nous concentrons sur l’approche basée sur la résolution directe du problème sur un graphe représentant le réseau routier. Nous développons un algorithme de type branch-and-price pour la résolution de cette variante du problème. Une étude expérimentale est, ensuite, menée afin d’évaluer l’efficacité relative des deux approches. Enfin, nous étudions les problèmes de tournées de véhicules dans lesquels les temps de parcours varient au cours de la journée. Nous proposons un algorithme de type branch-and-price afin de résoudre le problème avec des fenêtres de temps directement sur le graphe représentant le réseau routier. Une analyse empirique sur l’impact de l’approche proposée sur la qualité de la solution est proposée<br>Vehicle routing problems (VRPs) have drawn many researchers’ attention for more than fifty years. Most approaches found in the literature are, implicitly, based on the key assumption that the best path between each two points of interest in the road network (customers, depot, etc.) can be easily defined. Thus, the problem is tackled using the so-called customer-based graph, a complete graph representation of the road network. In many situations, such a graph may fail to accurately represent the original road network and more information are needed to address correctly the routing problem.We first examine these situations and point out the limits of the traditional customer-based graph. We propose a survey on works investigating vehicle routing problems by considering more information from the road network. We outline the proposed alternative approaches, namely the multigraph representation and the road network approach.Then, we are interested in the multigraph approach. We propose an algorithm that efficiently compute the multigraph representation for large sized road networks. We present an empirical analysis on the impact of the multigraph representation on the solution quality for the VPR with time windows (VRPTW) when several attributes are defined on road segments. Then, we develop an efficient heuristic method for the multigraph-based VRPTW.Next, we investigate the road network approach. We develop a complete branch-and-price algorithm that can solve the VRPTW directly on the original road network. We evaluate the relative efficiency of the two approaches through an extensive computational study.Finally, we are interested in problems where travel times vary over the time of the day, called time dependent vehicle routing problems (TDVRPs). We develop a branch-and-price algorithm that solves the TDVRP with time windows directly on the road network and we analyze the impact of the proposed approach on the solution quality
33
Talaei, Majid. "Heuristics for energy efficient vehicle routing problem." Thesis, Wichita State University, 2012. http://hdl.handle.net/10057/5611.
Full textAbstract:
US logistics cost of 1.397 trillion dollars in 2007, which stands for more that 10 percent of the total GDP of the country justifies any attempt of reducing it. Transportation followed by inventory-carrying and logistics administration has the greatest cost share in logistics. A tool which is very critical in transportation planning and can contribute to huge savings if used properly is Vehicle Routing Problem. Near optimum vehicle routs which are designed by outstanding heuristics and experts could contribute significantly to cost saving. Another important issue which directly affects logistics and transportation is energy consumption. Energy consumption and energy saving plans are hot topics everywhere nowadays. Issues such as green house effect, global warming effect and oil resources termination are great global concerns. This research tries to modify vehicle routing problem heuristics and make them sensitive to the issue of energy consumption. Traditional VRP heuristics and solution methods have tried to minimize total distance traveled of vehicles as the main objective function, while energy consumption minimization is the objective function of energy efficient VRP heuristics in this research. Two heuristics are modified in an “Energy Efficient” manner, nearest neighbor algorithm and saving algorithm. The proposed heuristics are examined with several benchmark problems from literature and are found to be efficient and effective both in terms of total distance travelled and energy consumption.<br>Thesis (M.S.)--Wichita State University, College of Engineering, Dept. of Industrial and Manufacturing Engineering
34
Mu, Qianxin. "Disruption management in vehicle routing and scheduling." Thesis, Lancaster University, 2010. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.543984.
Full text
35
Maqueo, Rodrigo Rubio. "Dynamic-stochastic vehicle routing and inventory problem." Thesis, Massachusetts Institute of Technology, 1995. http://hdl.handle.net/1721.1/10593.
Full text
36
Lin, Yingwei. "Optimized dynamic vehicle routing policies with applications." Thesis, Boston University, 2012. https://hdl.handle.net/2144/32029.
Full textAbstract:
Thesis (Ph.D.)--Boston University<br>PLEASE NOTE: Boston University Libraries did not receive an Authorization To Manage form for this thesis or dissertation. It is therefore not openly accessible, though it may be available by request. If you are the author or principal advisor of this work and would like to request open access for it, please contact us at open-help@bu.edu. Thank you.<br>This dissertation addresses two applications: (a) optimizing dynamic vehicle routing policies in warehouse forklift dispatching, and (b) reward collection by a group of air vehicles in a 3-dimensional mission space. For the first application, we successfully deployed an inexpensive mobile Wireless Sensor Network in a commercial warehouse served by a fleet of forklifts, aiming at improving forklift dispatching and reducing costs associated with the delays of loading/unloading delivery trucks. The forklifts were instrumented with sensor nodes that collect an array of information, including the forklifts' physical location, usage time, bumping/collision history, and battery status in an event-driven manner. A hypothesis testing algorithm was implemented to capture the location information. Combined with inventory information, the acquired information was fed into an Actor-Critic type stochastic optimization method to generate dispatching decisions.
For the second application, we considered an application where mobile vehicles (agents) fly in a forest with obstacles. They "chase" potentially moving targets that carry rewards, which the agents wish to collect by approaching the targets. We cast the problem into a Markov Decision Process framework. In order to seek an optimal policy that maximizes the long-term average reward collection, and to conquer the curse of dimensionality, we propose an approximate dynamic programming algorithm termed Distributed Actor-Critic Algorithm. Motivated by the way animals move while hunting for food, we incorporated several bio-inspired features into our control policy structure. Simulation results demonstrate that the policies with these bio-inspired features lead to a higher reward collection rate compared to the non-bio-inspired counterparts; by 40% in some examples. We also considered a setting where targets have intelligence and try to move away from agents in order to minimize the reward being collected. The problem is formulated as a Pursuit Evasion Game. Assuming that the targets also use an Actor-Critic method to optimize their control policy, we have shown that the game converges to a Local Nash Equilibrium. Furthermore, we proposed an Actor-Critic with Simulated Annealing (ACSA) algorithm, and established that the game converges to a Nash Equilibrium. Simulation results show that the ACSA algorithm can achieve a higher reward collection rate for both stationary and moving targets.<br>2031-01-02
37
Lundkvist, Henrik. "Robust Vehicle Routing in an Urban Setting." Thesis, KTH, Optimeringslära och systemteori, 2016. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-186248.
Full textAbstract:
In this thesis, the vehicle routing problem with stochastic, and time dependent, travel times is studied. The stochastic travel times are estimated from historical drive data. The variation of the drive times, as well as that of the variance, during the day was modeled. The purpose of the thesis was to propose a method of handling the congestion related traffic impediments in an urban setting. Since the majority of times of delivery in the empirical test cases studied correlate with the time period of high traffic load, an efficient and robust handling of such traffic scenarios is of high importance. It is shown that the stochastic models will shift the estimated arrivals to customers from the more volatile early and late extremes to more central regions of the time window. Previously delivered routes were evaluated both with the standard algorithm and the proposed stochastic algorithm. The difference between the actual drive times and the calculated drive times were analyzed by studying the correlation of the drive times between each customer in the route. It was shown that the routes of the proposed stochastic method increased this correlation. The drive times between nodes where also perturbed with a Gamma distributed noise. The results from the stochastic algorithm showed higher resilience to this disturbance than did the deterministic models.<br>I detta examensarbete har fordonsruttningsproblemet, VRP, med stokastiska och tidsberonds körtider behandlöats. De stokastiska körtiderna har estimerats från tidigare insamlad hasighetsdata. Modeller för körtidernas och variansernas förändring under dagen har tagits fram. Syftet med examensarbetet var att föreslå en metod för hur påverkan på körtider av förutsägbar trafikträngsel i en urban trafikmiljö kan hanteras. Eftersom huvuddelen av alla leveranser sammanfaller med de tider på dygnet då trafikbelastning är som högst, ar är en effektiv och robust metod för att hantera sådana störningar av stor vikt. Det visas att den stokastiska modellen kommer att förflyttar ankomster från början och slutet av tidsfönstret till den mer okänsliga mittregionen. Tidigare, utförda leveranser studerades både med den ursprungliga deterministiska modellen och här framtagna stokastiska modellen. Skillnaden mellan de två analyserades genom att studera korrelationen mellan körtiderna som de beräknats av de två modellerna och de upmätta tiderna som de loggats av leveransfordonen. Det visas att korrelationen mellan körtiderna mellan de stokastiska körtiderna och de verkliga körtiderna är högre än korrelationen mellan de deterministiska körtiderna och de verkliga. Rutterna som föreslagits av den stokastiska modellen var också mer tlig mot störningar.
38
McInvale, Howard D. "Land Leveling Using Optimal Earthmoving Vehicle Routing." Thesis, Virginia Tech, 2002. http://hdl.handle.net/10919/42356.
Full textAbstract:
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.<br>Master of Science
39
Arunapuram, Sundararajan. "Vehicle routing and scheduling with full loads." Case Western Reserve University School of Graduate Studies / OhioLINK, 1993. http://rave.ohiolink.edu/etdc/view?acc_num=case1056646152.
Full text
40
Cornick, Namrata Uppal. "The vehicle routing problem with demand ranges." College Park, Md.: University of Maryland, 2009. http://hdl.handle.net/1903/9376.
Full textAbstract:
Thesis (M.S.) -- University of Maryland, College Park, 2009.<br>Thesis research directed by: Applied Mathematics and Scientific Computation Program . Title from t.p. of PDF. Includes bibliographical references. Published by UMI Dissertation Services, Ann Arbor, Mich. Also available in paper.
41
Malagoli, Davide. ""Vehicle Routing Problem": un caso di studio." Master's thesis, Alma Mater Studiorum - Università di Bologna, 2010. http://amslaurea.unibo.it/1547/.
Full text
42
Battaglia, Andrea. "Metodi euristici per il Vehicle Routing Problem." Bachelor's thesis, Alma Mater Studiorum - Università di Bologna, 2013. http://amslaurea.unibo.it/6244/.
Full textAbstract:
Il problema della consegna di prodotti da un deposito/impianto ai clienti mediante una flotta di automezzi è un problema centrale nella gestione di una catena di produzione e distribuzione (supply chain). Questo problema, noto in letteratura come Vehicle Routing Problem (VRP), nella sua versione più semplice consiste nel disegnare per ogni veicolo disponibile presso un dato deposito aziendale un viaggio (route) di consegna dei prodotti ai clienti, che tali prodotti richiedono, in modo tale che (i) la somma delle quantità richieste dai clienti assegnati ad ogni veicolo non superi la capacità del veicolo, (ii) ogni cliente sia servito una ed una sola volta, (iii) sia minima la somma dei costi dei viaggi effettuati dai veicoli.
Il VRP è un problema trasversale ad una molteplicità di settori merceologici dove la distribuzione dei prodotti e/o servizi avviene mediante veicoli su gomma, quali ad esempio: distribuzione di generi alimentari, distribuzione di prodotti petroliferi, raccolta e distribuzione della posta, organizzazione del servizio scuolabus, pianificazione della manutenzione di impianti, raccolta rifiuti, etc.
In questa tesi viene considerato il Multi-Trip VRP, in cui ogni veicolo può eseguire un sottoinsieme di percorsi, chiamato vehicle schedule (schedula del veicolo), soggetto a vincoli di durata massima. Nonostante la sua importanza pratica, il MTVRP ha ricevuto poca attenzione in letteratura: sono stati proposti diversi metodi euristici e un solo algoritmo esatto di risoluzione, presentato da Mingozzi, Roberti e Toth.
In questa tesi viene presentato un metodo euristico in grado di risolvere istanze di MTVRP in presenza di vincoli reali, quali flotta di veicoli non omogenea e time windows. L’euristico si basa sul modello di Prins. Sono presentati inoltre due approcci di local search per migliorare la soluzione finale. I risultati computazionali evidenziano l’efficienza di tali approcci.
43
Hintsch, Timo [Verfasser]. "On Clustered Vehicle-Routing Problems / Timo Hintsch." Mainz : Universitätsbibliothek Mainz, 2020. http://d-nb.info/1206563966/34.
Full text
44
Oxenstierna, Johan. "Warehouse Vehicle Routing using Deep Reinforcement Learning." Thesis, Uppsala universitet, Institutionen för informationsteknologi, 2019. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-396853.
Full textAbstract:
In this study a Deep Reinforcement Learning algorithm, MCTS-CNN, is applied on the Vehicle Routing Problem (VRP) in warehouses. Results in a simulated environment show that a Convolutional Neural Network (CNN) can be pre-trained on VRP transition state features and then effectively used post-training within Monte Carlo Tree Search (MCTS). When pre-training works well enough better results on warehouse VRP’s were often obtained than by a state of the art VRP Two-Phase algorithm. Although there are a number of issues that render current deployment pre-mature in two real warehouse environments MCTS-CNN shows high potential because of its strong scalability characteristics.
45
Accorsi, Luca <1993>. "Innovative Hybrid Approaches for Vehicle Routing Problems." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2022. http://amsdottorato.unibo.it/10048/3/thesis02022022.pdf.
Full textAbstract:
This thesis deals with the efficient resolution of Vehicle Routing Problems (VRPs).
The first chapter faces the archetype of all VRPs: the Capacitated Vehicle Routing Problem (CVRP). Despite having being introduced more than 60 years ago, it still remains an extremely challenging problem. In this chapter I design a Fast Iterated-Local-Search Localized Optimization algorithm for the CVRP, shortened to FILO. The simplicity of the CVRP definition allowed me to experiment with advanced local search acceleration and pruning techniques that have eventually became the core optimization engine of FILO. FILO experimentally shown to be extremely scalable and able to solve very large scale instances of the CVRP in a fraction of the computing time compared to existing state-of-the-art methods, still obtaining competitive solutions in terms of their quality.
The second chapter deals with an extension of the CVRP called the Extended Single Truck and Trailer Vehicle Routing Problem, or simply XSTTRP. The XSTTRP models a broad class of VRPs in which a single vehicle, composed of a truck and a detachable trailer, has to serve a set of customers with accessibility constraints making some of them not reachable by using the entire vehicle. This problem moves towards VRPs including more realistic constraints and it models scenarios such as parcel deliveries in crowded city centers or rural areas, where maneuvering a large vehicle is forbidden or dangerous. The XSTTRP generalizes several well known VRPs such as the Multiple Depot VRP and the Location Routing Problem. For its solution I developed an hybrid metaheuristic which combines a fast heuristic optimization with a polishing phase based on the resolution of a limited set partitioning problem. Finally, the thesis includes a final chapter aimed at guiding the computational evaluation of new approaches to VRPs proposed by the machine learning community.
46
Bruwer, Frances. "Petal-shaped clustering for the capacitated vehicle routing problem." Thesis, 2018. https://hdl.handle.net/10539/25890.
Full textAbstract:
A research report submitted to the Faculty of Engineering and the Built
Environment, University of the Witwatersrand, in partial fulfillment of the
requirements for the degree of Master of Science in Engineering.
Johannesburg, February 2018<br>In this research report, k-medoid (petal-shaped) clustering is modelled and evaluated for the Capacitated Vehicle Routing Problem (CVRP). To determine routes, an existing metaheuristic, termed the Ruin and Recreate method, is applied to each generated cluster. Results are benchmarked to that of a well-known clustering method, k-means clustering. The performance of the methods is measured in terms of travel cost and distance travelled, which are well-known metrics for Vehicle Routing Problems (VRPs). The results show that k-medoid outperforms the benchmark method for most instances of the test datasets, although the CVRP without any predefined clusters still provide solutions that are closer to optimal. Clustering remains a reliable distribution management tool and reduces processing requirements of large scale CVRPs.<br>MT 2018
47
Peng, Ya-fen, and 彭雅芬. "Vehicle Routing Problem with Time Windows Using Clustering and Heuristics." Thesis, 2005. http://ndltd.ncl.edu.tw/handle/n7afhp.
Full textAbstract:
碩士<br>朝陽科技大學<br>資訊管理系碩士班<br>93<br>Commercial Vehicle Operations (CVO), one of the major Intelligent Transportation Systems (ITS) program, aims at applying advanced technologies to commercial vehicle operations. Vehicle Routing Problem with Time Windows (VRPTW) is an important aspect of Commercial Vehicle Operations. This research focuses on using a two-stage clustering method, improved time-divided procedure, and heuristic approach for improving vehicle routing in VRPTW.
The spatial distribution of the customer locations, such as evenly spaced, random, and clustered distribution, is measured by the Nearest Neighbor Index (NNI) to determine the degree of spatial clustering. If the degree of spatial clustering is small (clustered data), the two-stage clustering method, a combination of the Self-Organizing Map (SOM) and the K-means method, is integrated with Davies-Bouldin index (DB) to determine the best clustering results during the initialization phase of an insertion heuristic for VRPTW. Improved time-divided procedure is applied when the degree of spatial clustering is large (randomly distributed or dispersed data) and the two-stage clustering method cannot efficiently cluster the customers. The customers are sorted according to their service time windows and divided into different groups. An algorithm is then proposed to solve the initialization phase of an insertion heuristic using improved time-divided procedure. Tabu search will be coped to improve the vehicle routing after the initialization phase of an insertion heuristic. The general tabu search explores part of the solution space by moving solutions at each iteration to the best neighbor of the current solution, even if this leads to a deterioration of the objective function.
Experimental examples are selected from the Solomon’s benchmarks and a case study, and the numerical results show the effectiveness of the proposed methods and algorithms to solve VRPTW.
48
Lin, Te-Li, and 林德禮. "A Study on Vehicle Routing Problems By Clustering Genetic Algorithm." Thesis, 2003. http://ndltd.ncl.edu.tw/handle/47093434187887338598.
Full textAbstract:
碩士<br>華梵大學<br>工業管理學系碩士班<br>91<br>This research focuses on Vehicle Routing Problem (VRP for short). The goal of proposed research is to find the minimum delivery cost for a fleet of vehicles, which serve a set of customers with known demands, based on the capacity of each vehicle. Delivery cost depends on number of vehicle and total routing distance of vehicles. The weight of routing distance and running a vehicle is also considered to make the proposed method more practicable in real world.
A combined k-means clustering and genetic algorithm to find applicable solution of multiple-vehicle routing problem with consideration of vehicle capacity is proposed in this paper. K-means clustering was first applied to cluster customers by the limitation of vehicle capacity. In other words, k-means clustering algorithm determines a subset of customers for each vehicle. Then Genetic Algorithm (GA for short) is used to find an optimal routing solution for each cluster.
64 benchmark VRP instances from Internet VRPLIB, where the number of demanded points is from 22 to 151, were simulated in order to evaluate the performance of proposed method. There are only two cases that the proposed method needs one more vehicle than existed optimal solution. And averagely speaking, 8.5% rate of aberration was noticed when compared proposed works with the optimal solutions. The computational time is linearly dependent on number of demanded points and it is very praiseworthy.
49
Joubert, Johannes Wilhelm. "An integrated and intelligent metaheuristic for constrained vehicle routing." Thesis, 2007. http://hdl.handle.net/2263/26439.
Full textAbstract:
South African metropolitan areas are experiencing rapid growth and require an increase in network infrastructure. Increased congestion negatively impacts both public and freight transport costs. The concept of City Logistics is concerned with the mobility of cities, and entails the process of optimizing urban logistics activities by concerning the social, environmental, economic, financial, and energy impacts of urban freight movement. In a costcompetitive environment, freight transporters often use sophisticated vehicle routing and scheduling applications to improve fleet utilization and reduce the cost of meeting customer demands. In this thesis, the candidate builds on the observation that vehicle routing and scheduling algorithms are inherent problem specific, with no single algorithm providing a dominant solution to all problem environments. Commercial applications mostly deploy a single algorithm in a multitude of environments which would often be better serviced by various different algorithms. This thesis algorithmically implements the ability of human decision makers to choose an appropriate solution algorithm when solving scheduling problems. The intent of the routing agent is to classify the problem as representative of a traditional problem set, based on its characteristics, and then to solve the problem with the most appropriate solution algorithm known for the traditional problem set. A not-so-artificially-intelligent-vehicle-routing-agent™ is proposed and developed in this thesis. To be considered intelligent, an agent is firstly required to be able to recognize its environment. Fuzzy c-means clustering is employed to analyze the geographic dispersion of the customers (nodes) from an unknown routing problem to determine to which traditional problem set it relates best. Cluster validation is used to classify the routing problem into a traditional problem set. Once the routing environment is classified, the agent selects an appropriate metaheuristic to solve the complex variant of the Vehicle Routing Problem. Multiple soft time windows, a heterogeneous fleet, and multiple scheduling are addressed in the presence of time-dependent travel times. A new initial solution heuristic is proposed that exploits the inherent configuration of customer service times through a concept referred to as time window compatibility. A high-quality initial solution is subsequently improved by the Tabu Search metaheuristic through both an adaptive memory, and a self-selection structure. As an alternative to Tabu Search, a Genetic Algorithm is developed in this thesis. Two new crossover mechanisms are proposed that outperform a number of existing crossover mechanisms. The first proposed mechanism successfully uses the concept of time window compatibility, while the second builds on an idea used from a different sweeping-arc heuristic. A neural network is employed to assist the intelligent routing agent to choose, based on its knowledge base, between the two metaheuristic algorithms available to solve the unknown problem at hand. The routing agent then not only solves the complex variant of the problem, but adapts to the problem environment by evaluating its decisions, and updating, or reaffirming its knowledge base to ensure improved decisions are made in future.<br>Thesis (PhD (Industrial Engineering))--University of Pretoria, 2007.<br>Industrial and Systems Engineering<br>PhD<br>unrestricted
50
Kolluri, Rajesh. "Reduction of Routing Overhead in Vehicle-to-Vehicle Communication using Clustering in Vehicular Ad-hoc Networks." Thesis, 2017. http://ethesis.nitrkl.ac.in/9072/1/2017_MT_KRajesh.pdf.
Full textAbstract:
VANET (Vehicular Ad-hoc Networks) is intended to achieve ITS (Intelligent Transportation System). It is the sub-category of MANET. VANET enables a set of vehicles which are in communication range of each other to establish a network among them to communicate with each other vehicles and RSUs (Road Side Units). It is known as Vehicle-to-Vehicle (V2V) communication and Vehicle-to-Infrastructure (V2I) communication respectively. These communications will help the vehicles to share the traffic information, media to achieve ITS. Several routing protocols were there to make this communication possible. Some of them are DSR (Dynamic Source Routing), AODV (Ad Hoc on-Demand Distance Vector Routing), and DSDV (Destination Sequenced Distance Vector). In all this existing protocols routing overhead is high which is not desirable. Due to high mobility or high topology change of nodes in vehicular ad hoc networks (VANETs), there are frequent connection breakages which lead to frequent route discoveries. The routing overhead of a route discovery is more when there are more connection or link failures. So, routing overhead cannot be neglected, it reduces the QoS (Quality of Service) of a routing protocol. So, to reduce this overhead a cluster based algorithm is proposed. Basic idea of proposed algorithm is to divide the simulation area into clusters and electing a cluster head for each cluster, we only communicate with cluster heads for any request there by reducing the overhead to find route from source to destination many times.