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.

Various types of transportation issues are a common practice. The issue may be approached mainly as the distribution of products from suppliers to consumers while minimising distribution costs. The difference of real transportation issues predominantly relates to the considered restrictions, such as capacities of vehicles and orders, time windows and other special distribution restrictions. Transportation issues were already defined by F.L. Hitchcock in 1941 and since then, a wide range of stochastic and non- determinist methods providing solutions to transportation issues have been developed. Nevertheless, introducing distribution restrictions in resolving real-life problems makes it difficult for such methods to be applied. This thesis provides a compilation of the well-known determinist methods that may be used to resolve transportation issues. The methods that are appropriate for resolving real issues are discussed in more detail. The solution procedure of the selected method is demonstrated using simple examples and the results are compared with the results of other methods. An analysis of the above methods is used to design and implement new methods to resolve real transportation issues, their results being compared with the methods provided by the commercial software product.

The thesis deals with optimization problems which arise at distribution planning. These problems can often be easily formulated as integer programming problems, but rarely can be solved using mixed integer programming techniques. Therefore, it is necessary to study the efficiency of heuristic algorithms. The main focus of the thesis is on the vehicle routing problem with time windows. A tabu search algorithm for this problem was developed and implemented. It uses integer programming to solve the set partitioning problem in order to find optimal distribution of all customers into feasible routes found during the search. The results of the classical integer programming approach, basic insertion heuristic and presented tabu search algorithm are compared in a numerical study.

In this Dissertation, the Vehicle Routing Problem with Drones (VRPD), motivated by the growing interest on Unmanned Aerial Vehicles (UAVs, or Drones) by the industry and their applications in logistics is studied. A pioneer work by (MURRAY; CHU, 2015) shows a combination between UAV and a truck to deliver products, presenting an adaptation to the Traveling Salesman Problem (TSP). After a literature review, an extension of the model from Murray and Chu (2015) we present a model for the problem with multiple vehicles. This model is developed as a Mixed Integer Linear Programming (MILP) problem and solved with the solver CPLEX. A heuristic based on a Hybrid Genetic Algorithm (HGA) is also developed and presented. Our results show that the use of drones reduces the total mileage of the trucks by a significant percentage. / Nessa monografia estuda-se o Problema do Roteamento de Veículos com Drones (PRVD), motivado pelo crescente interesse da indústria em Veículos Aéreos Não Tripulados (VANTs) e suas aplicações em logística. O trabalho pioneiro de (MURRAY; CHU, 2015) mostra uma combinação entre VANT e um caminhão para realização de entregas de produtos, no qual foi proposta uma adaptação do Problema do Caixeiro Viajante (PCV). Após uma revisão de literatura, apresenta-se uma extensão do modelo de Murray and Chu (2015) para o problema com múltiplos veículos. Desenvolveu-se um modelo de Programação Linear Inteira Mista que foi resolvido com o solver CPLEX. Uma heurística basead em um Algoritmo Genético Híbrido também foi desenvolvido e é apresentada. Resultados mostram que a utilização dos VANTs reduzem a quilometragem dos caminhões significativamente.