Nowadays, when great emphasis is put on cost savings, transport optimization is necessary part of every company life in which transportation costs produce significant part. There are optimization methods and possibilities presented in this thesis. In the first chapter there are explained methods such as the travelling salesman problem, the vehicle routing problem, the multiple vehicle routing problem and the split delivery vehicle routing problem and then the reader gets to know the heuristics methods in the chapter two where description of the nearest neighbour method, Clarke-Wright method and split delivery heuristic is mentioned. In the last but one chapter author applies previous methods on concrete distribution arranged by Movianto Česká republika s.r.o. on 5th September, 2013. Based on gained outputs, analysis and comparison of results (including the original distribution) are provided in the fourth chapter. Obtained results of analysis lead to recommendation on how the company should plan its future distribution.

The thesis deals with application of models of routing problems on a real problem, beer distribution in Jesenicko region provided by Viden plus, a.s. The goal of the thesis is to optimize daily distributional routes for two vehicles with different capacities. Total distance has to be minimized respecting time and capacity limits. In case the optimal solution is not found, sub-optimal solution will be accepted. Solutions are calculated with use of the optimization software LINGO and some heuristic methods. Models of travelling salesman problem and vehicle routing problem are used to find the solutions. Results are compared to the current state of distributional routes in conclusion of the thesis.

This thesis deals with the optimization of distribution of bakery products. Firstly there are the fundamental types of vehicle routing problems and their optimization models introduced. Next part is dedicated to heuristic algorithms. The heuristic methods are introduced in general, then there are the chosen methods described. Later there are two chosen algorithms formulated. First one based on the nearest neighbour method and another one based on the savings algorithm. Both of algorithms were programmed in the Visual Basic of Applications MS Excel 2010. These algorithms were applied for the solution of the real problem dealing with the distribution of goods. The bakery company has provided the data about its customers for this purpose. The last part of this thesis is dedicated to the summary and comparison of the solution of the assigned problem that was gained by the proposed algorithms with the solution that the bakery company has put into practice.

Submitted by Nadir Basilio (nadirsb@uninove.br) on 2015-07-17T16:00:19Z No. of bitstreams: 1 Stanley Jefferson de Araujo Lima.pdf: 1500605 bytes, checksum: 2aec7d5c11c9781ce7f70eb2019c01f4 (MD5) / Made available in DSpace on 2015-07-17T16:00:19Z (GMT). No. of bitstreams: 1 Stanley Jefferson de Araujo Lima.pdf: 1500605 bytes, checksum: 2aec7d5c11c9781ce7f70eb2019c01f4 (MD5) Previous issue date: 2015-01-27 / In recent years, the Vehicle Routing Problem (VRP) has attracted an increasing attention from researchers due to the great difficulty of its solution and its presence in various practical situations. As consequence, there has been great effort to develop more robust, agile and flexible algorithms that can be modeled according to the scenario that describes the problem. The Capacitated Vehicle Routing Problem (CVRP) is a version of VRP and consists in determining a set of routes to be followed by a fleet of homogeneous vehicles, which must serve a set of customers. The objective is to minimize the total cost of the routes subject to the following restrictions: i) routes must start and end in the same distribution center; ii) each customer must be visited once and its demand must be met in full by only one vehicle and iii) the sum of customers' demands included in a route cannot exceed the vehicle capacity. The CVRP belongs to the class of NP-hard problems, that is, problems whose the solution usually requires non-polynomial complexity time algorithms and because of this are usually resolved with the use of heuristic and metaheuristics algorithms. In this work, it was investigated the optimization of CVRP using Genetic Algorithm (GA) with alternative chromosome representations and heuristics. To this end, three strategies, each one employing a different model of chromosome representation for encoding solution in AG were proposed. In addition, the heuristics of Gillett and Miller to generate solutions that are included in the initial population of GA and Hill-climbing for refinement of GA solutions, after a number of generations without improvement, were adopted. In the performed experiments, the results obtained by the proposed strategies were compared with each other and also with the best results found in the literature for a set of known instances. These experiments showed that the proposed strategies provided good results with respect to quality of solutions well as the computational cost. In addition, it was possible to evaluate the viability of each employed chromosome representation and the contribution of the heuristics in the convergence process of GA. / Nos últimos anos o Problema de Roteamento de Veículos (PRV) tem atraído cada vez mais a atenção de pesquisadores devido à grande dificuldade de solução e sua presença em várias situações do cotidiano. Em decorrência disso, tem havido um grande esforço para desenvolver algoritmos cada vez mais robustos, ágeis e flexíveis e que possam ser modelados com base no cenário que descreve o problema. O Problema de Roteamento de Veículos Capacitado (PRVC) é uma versão do PRV e consiste em encontrar um conjunto de rotas a serem seguidas por uma frota de veículos homogêneos, os quais devem atender a um conjunto de clientes. O objetivo é minimizar o custo total das rotas respeitando as seguintes restrições: i) as rotas devem iniciar e terminar no mesmo centro de distribuição; ii) cada cliente deve ser visitado uma única vez e sua demanda deve ser atendida integralmente por apenas um veículo e iii) a soma das demandas dos clientes incluídos em uma rota não pode exceder a capacidade do veículo. Problemas desta natureza podem ser classificados como NP-Hard, ou seja, possuem ordem de complexidade não polinomial e normalmente são resolvidos com uso de algoritmos heurísticos e meta-heurísticos. Neste trabalho investigou-se a otimização do PRVC usando Algoritmo Genético (AG) com representações cromossômicas e heurísticas alternativas. Para tanto, foram propostas três estratégias, cada uma delas empregando um modelo diferente de representação cromossômica para codificação da solução no AG. Além disso, foram empregadas as heurísticas de Gillett e Miller para gerar soluções que são incluídas na população inicial do AG e Subida/Descida de Encosta para refinamento das soluções, após um certo número de gerações sem melhoria. Nos experimentos realizados, os resultados obtidos pelas estratégias propostas foram comparados entre si e também com os melhores resultados encontrados na literatura para um conjunto de instâncias conhecidas. Pode-se constatar, a partir desses experimentos, que as estratégias apresentaram bons resultados tanto no que tange a qualidade das soluções quanto ao tempo computacional dispendido. Em adição, foi possível avaliar a viabilidade de cada uma das representações cromossômicas empregadas, além da contribuição das heurísticas no processo de convergência do ag.

In this paper, we study a rich vehicle routing problem incorporating various complexities found in real-life applications. The General Vehicle Routing Problem (GVRP) is a combined load acceptance and generalised vehicle routing problem. Among the real-life requirements are time window restrictions, a heterogeneous vehicle fleet with different travel times, travel costs and capacity, multi-dimensional capacity constraints, order/vehicle compatibility constraints, orders with multiple pickup, delivery and service locations, different start and end locations for vehicles, and route restrictions for vehicles. The GVRP is highly constrained and the search space is likely to contain many solutions such that it is impossible to go from one solution to another using a single neighbourhood structure. Therefore, we propose iterative improvement approaches based on the idea of changing the neighbourhood structure during the search.

The e-commerce market has developed massively since the 1990ies. In addition to a general change of shopping behavior, the COVID-pandemic increased the importance of online shopping. This study is about the transportation of e-commerce parcels on the last mile in urban areas, so called last-mile delivery. Special focus is put on innovative last mile solutions that reduce the externalities related to last-mile delivery. There are several factors that complicate the delivery on the last mile such as congestion, driving restrictions and meeting time-windows for customers. This study investigates to what extent the route planning for a fleet of vehicles can account for these various requirements and restrictions. The route planning was conducted in the GIS software ArcGIS Pro using the vehicle routing problem. The routes could be successfully planned and consider most of the relevant factors for last-mile delivery operations. The results indicate that traffic and congestion in cities can be accounted for which results in an average driving speed of 20km/h. The planned routes also indicate that not even 20% of the vehicle’s cargo capacity was used and that 60-65% of the total time is spent driving between orders. The study and its results are relevant to businesses and researchers in the field of last-mile delivery as the analysis of a real-world scenario highlights the possibilities and limitations of route planning on the last mile.

[pt] Nos últimos anos as empresas varejistas começaram a investir em modelos menores de lojas, voltando-se para o atendimento de conveniência, que busca atender os novos hábitos de consumo da população. No entanto, esse modelo de loja representa um grande desafio logístico para as empresas, uma vez que por serem pequenas essas lojas normalmente não possuem espaço para estoque, necessitando de abastecimentos frequentes. A logística urbana apresenta alguns obstáculos como as restrições de circulação por tipo de veículo e as janelas de tempo, tornando a roteirização adequada fundamental para entregar o produto correto, no momento correto e na quantidade correta, garantindo assim a redução de veículos, distância percorrida e custos logísticos. Desta forma, este trabalho busca contribuir para o reabastecimento ótimo de lojas de conveniência localizadas em grandes centros urbanos através da otimização de rotas, considerando restrições de circulação e janelas de tempo disponíveis para abastecimento. Para isto, um estudo de caso foi feito em uma empresa do setor varejista utilizando uma ferramenta de código aberto baseada no Excel para resolver a variante do problema de roteirização de veículos. A ferramenta utilizada para resolver casos reais da empresa em estudo, considera o planejamento médio da demanda diária assim como a capacidade e disponibilidade dos veículos, tempos de descarga e restrições de horário para recebimento e circulação de veículos. Os resultados do estudo para os cenários discutidos apresentam uma redução de até 32 por cento no frete da empresa, além de oportunidades de ganhos operacionais frente à atual operação da empresa. / [en] In recent years retail companies have begun to invest in smaller store models, turning to the convenience service, which seeks to meet the new consumption habits of the population. However, this store model represents a major logistical challenge for companies, once they are small, usually do not have space for inventory and need frequent replenishments. City Logistics presents some obstacles such as traffic restrictions by vehicle type and time windows, making proper routing essential to deliver the right product at the right time and in the right amount, thus ensuring vehicle reduction, distance traveled and logistics costs. In this way, the objective of this paper is to contribute to the optimal replenishment of convenience stores located in large urban centers through an optimization of the routes, considering the traffic restrictions and the time windows available for supply. For this, a case study was done in a retail company using an Excel open source tool to solve the variant of the vehicle routing problem. The tool is used to solve real cases of the company under study, considering the average planning of daily demand as well as the capacity and availability of vehicles, unloading times and time constraints for receiving and circulating vehicles. The study results for the scenarios discussed present a reduction of up to 32 per cent in the company s freight as well as opportunities for operating gains against the company s current operation.

Goal number 12 of the Sustainable Development Goals (SDGs) by the United Nations (UN)emphasises on how the increase in the world population is hampering the achievement ofenvironmental sustainability. The diminishing resources of nature draw attention to the factthat more innovative methods need to salvage the environment and the planet at large.Textiles or clothing are one of the essential things that every human owns and with a globalpopulation of over 7 billion, there is an urgency to find ways to reduce its production, due tothe number of resources used and the amount of emissions the textile/clothing industryproduces.The Swedish Red Cross is a charitable organisation that deals with second-hand clothing toraise profits for its activities while contributing to environmental sustainability. Their secondhandretail shops give customers value for their money while extending the lifecycle of clothes.Due to their non-profitable nature puts much pressure on their finances. The need for revenuecalls for finding more environmentally sustainable ways of making a profit out of the clothesthey receive while evaluating the transportation options to reduce cost.Literature review and route optimisation in ArcGIS are used in the analysis. Driving timeanalysis is carried out to link stores to the closest depots to provide graphical and efficientmeans of reaching all the stores. The review of literature offers insights for environmentallysustainable ways of making a profit from second-hand clothes.The outcome provides results which will help generate more profit as well as cut down themajor contributor to the high transportation cost by more than 50%. Moreover, a suggestion ismade for a new time frame and a new travel mode to improve the coordination between thestores and the depots

This dissertation integrates the strengths of individual emergent delivery technologies with package characteristics, and rural community needs to meet the demand for equitable, accessible, and inclusive rural delivery that is also cost-effective. To find ways to meet the package delivery service needs in rural areas and to fill research gaps in rural package delivery modeling, this study introduced a novel model known as the Parallel Scheduling Vehicle Routing Problem (PSVRP) in an endeavor to revolutionize package delivery by enhancing its efficiency, accessibility, and cost-effectiveness. The PSVRP represents a state-of-the-art approach to vehicle routing problems, incorporating a diversified fleet of innovative delivery modes. The multi-modal fleet of electric vans, ADVs, drones, and truck-drone systems works in unison to minimize operational costs in various settings. A solution methodology that implemented the Adaptive Large Neighborhood Search (ALNS) algorithm was designed to solve the PSVRP in this research to produce optimal or near-optimal solutions. A variety of scenarios in a rural setting that include different quantities of customers to deliver to and different package weights are tested to evaluate if a multi-modal fleet of electric vans, ADVs, drones, and truck-drone systems can provide cost-effective, low emissions, and efficient rural delivery services from local stores. Different fleet combinations are compared to demonstrate the best combined fleet for rural package delivery. It was found that implementation of electric vans, ADVs, drones, and truck-drone systems does decrease rural package delivery cost, but it does not yet decrease cost enough for the return on investment to be high enough for industry to implement the technology. Additionally, it was found that electric technologies do significantly decrease emissions of package delivery in rural areas. However, without a carbon tax or regulation mandating reduced carbon emissions, it is unlikely that the delivery industry will quickly embrace these new delivery modes. This dissertation not only advances academic understanding and practical applications in vehicle routing problems but also contributes to social equity by researching methods to improve delivery services in underserved rural communities. The PSVRP model could benefit transportation professionals considering technology-enabled rural delivery, developing rural delivery plans, looking for cost-effective rural delivery solutions, implementing a heterogeneous fleet to optimize rural delivery, or planning to reduce rural delivery emissions. It is anticipated that these innovations will spur further research and investment into rural delivery optimization, fostering a more inclusive and accessible package delivery service landscape. / Doctor of Philosophy / This dissertation integrates the strengths of individual emergent delivery technologies with package characteristics, and rural community needs to meet the demand for equitable, accessible, and inclusive rural delivery that is also cost-effective. To find ways to meet the package delivery service needs in rural areas and to fill research gaps in rural package delivery modeling, this study introduced a novel model known as the Parallel Scheduling Vehicle Routing Problem (PSVRP) in an endeavor to revolutionize package delivery by enhancing its efficiency, accessibility, and cost-effectiveness. The PSVRP represents a state-of-the-art approach to vehicle routing problems, incorporating a diversified fleet of innovative delivery modes. The multi-modal fleet of electric vans, ADVs, drones, and truck-drone systems works in unison to minimize operational costs in various settings. A solution methodology that implemented the Adaptive Large Neighborhood Search (ALNS) algorithm was designed to solve the PSVRP in this research to produce optimal or near-optimal solutions. A variety of scenarios in a rural setting that include different quantities of customers to deliver to and different package weights are tested to evaluate if a multi-modal fleet of electric vans, ADVs, drones, and truck-drone systems can provide cost-effective, low emissions, and efficient rural delivery services from local stores. Different fleet combinations are compared to demonstrate the best combined fleet for rural package delivery. It was found that implementation of electric vans, ADVs, drones, and truck-drone systems does decrease rural package delivery cost, but it does not yet decrease cost enough for the return on investment to be high enough for industry to implement the technology. Additionally, it was found that electric technologies do significantly decrease emissions of package delivery in rural areas. However, without a carbon tax or regulation mandating reduced carbon emissions, it is unlikely that the delivery industry will quickly embrace these new delivery modes. This dissertation not only advances academic understanding and practical applications in vehicle routing problems but also contributes to social equity by researching methods to improve delivery services in underserved rural communities. The PSVRP model could benefit transportation professionals considering technology-enabled rural delivery, developing rural delivery plans, looking for cost-effective rural delivery solutions, implementing a heterogeneous fleet to optimize rural delivery, or planning to reduce rural delivery emissions. It is anticipated that these innovations will spur further research and investment into rural delivery optimization, fostering a more inclusive and accessible package delivery service landscape.

As the interest in electric heavy-duty vehicles has grown, so has the need for route planning tools to coordinate fleets of electric vehicles. This problem is called the Electric Vehicle Routing Problem (EVRP) and it can be solved using a Branch-Price-and-Cut method, where routes for individual vehicles are iteratively generated using information from the coordinated problem. These routes are computed in a pricing problem, which is a Resource Constrained Elementary Shortest Path Problem (RCESPP). Because of its iterative nature, the Branch-Price-and-Cut method is dependent on a fast solver for this RCSPP to get a good computational performance. In this thesis, we have implemented a labeling algorithm for the RCESSP for electric vehicles with state-of-the-art acceleration strategies. We further suggest a new bounding method that exploits the electric aspects of the problem. The algorithm's performance and the effect of the different acceleration strategies are evaluated on benchmark instances for the EVRP, and we report significantly improved computational times when using our bounding method for all types of instances. We find that route relaxation methods (ng-routes) were particularly advantageous in test instances with a combination of clustered and randomly distributed customers. Interestingly, for test instances with only randomly distributed customers, ng-relaxation required longer processing time to achieve elementary optimal routes and for these instances, the bounding methods gave better computational performance.