Otimização na logística de distribuição de mercadorias por meio do problema de roteamento de veículos : um estudo de caso para entrega de jornais

Orientadora: Prof.ª Dr.ª Maria Teresinha Arns SteinerDissertação (mestrado) - Universidade Federal do Paraná, Setor de Tecnologia, Programa de Pós-Graduação em Engenharia de Produção. Defesa : Curitiba, 18/02/2020Inclui referências: p. 112-120Área de concentração: Pesquisa OperacionalResumo: A melhoria dos processos de distribuição logística representa uma grande área de interesse das empresas tendo em vista as possibilidades de redução dos custos envolvidos. Muitas vezes, as empresas são incapazes de determinar de maneira ótima as rotas a serem percorridas para realizar as coletas e/ou entregas de suas mercadorias, gerando custos adicionais, deslocamentos desnecessários, tempos de entrega prolongados e insatisfação dos clientes. Diante deste contexto, o objetivo deste trabalho é apresentar uma metodologia para a otimização de problemas de distribuição de mercadorias, ou seja, para resolução de Problemas de Roteamento de Veículos (PRV). Uma abordagem, em duas etapas, baseada na utilização do Problema de Localização de Facilidades (PLF) e do Problema do Caixeiro Viajante Assimétrico (PCVA) é proposta para a obtenção das referidas rotas. A fim de verificar a eficiência do método proposto, o mesmo será aplicado na otimização dos roteiros realizados pelos entregadores de uma empresa de jornais no município de Curitiba, visando comparar procedimentos exatos, heurísticos e meta-heurísticos com a solução atual adotada pela empresa. Para isso, fez-se uso das heurísticas: Gillet & Johnson, método de aproximação de Vogel, First-Fit, First-Fit Decreasing, método dos Savings de Clark e Wright e métodos de Inserção. E também dos procedimentos metaheurísticos: Algoritmo Genético (AG) e Recozimento Simulado ou Simulated Annealing (SA). Como resultado este trabalho apresenta um comparativo, entre 40 combinações de métodos diferentes, em termos de qualidade de solução e tempo de processamento computacional, para resolução do estudo de caso em questão e de instâncias da literatura do PLF e do PCVA. Os resultados obtidos para as instâncias da literatura mostram que os procedimentos meta-heurísticos apresentaram melhores resultados em relação à qualidade de solução que os procedimentos heurísticos para o PLF e para o PCVA. No que se refere ao tempo de processamento computacional, para o PLF os procedimentos meta-heurísticos têm um tempo menor enquanto para o PCVA o tempo de processamento das meta-heurísticas é superior. No estudo de caso, o melhor resultado obtido mostra que é possível, por meio do método Algoritmo Genético para a fase 1 (PLF) e fase 2 (PCVA), uma redução de aproximadamente 36,54% no deslocamento do entregador em comparação à solução atual adotada pela empresa, refletindo uma possibilidade de redução de custo. Palavras-chave: Otimização. Roteirização. Problema de Localização de Facilidades (PLF). Problema do Caixeiro Viajante (PCV), Heurísticas, Meta- Heurísticas.Abstract: Improving logistics distribution processes is a major area of interest for companies that have in view the possibilities for reducing the costs involved. Often, companies are unable to optimally determine the routes to be taken to collect and / or deliver their goods, generating additional costs, unnecessary travel, prolonged delivery times and customer unsatisfaction. Given this context, the objective of this work is to present a methodology for the optimization of merchandise distribution problems, that is, for solving Vehicle Routing Problems (VRP). A two-step approach, based on the use of the Facility Location Problem (FLP) and the Asymmetric Traveling Salesman Problem (ATSP) is proposed to obtain the referred routes. In order to verify the efficiency of the proposed method, it will be applied in the optimization of the routes carried out by the deliverers of a newspaper company in the city of Curitiba, aiming to compare exact, heuristic and meta-heuristic procedures with the current solution adopted by the company. For this, heuristics were used: Gillet & Johnson, the Vogel approach method, First-Fit, First-Fit Decreasing, Clark and Wright's Savings method and Insertion methods. And also, the meta-heuristic procedures: Genetic Algorithm (GA) and Simulated Annealing (SA). As a result, this work presents a comparison, between 40 combinations of different methods, in terms of solution quality and computational processing time, for solving the case study in question and FPL and ATSP instances. The results obtained for the instances show that the meta-heuristic procedures presented better results in relation to the solution quality than the heuristic procedures for FLP and for ATSP. Regarding the computational processing time, for the FLP the meta-heuristic procedures have a shorter time while for the ATSP the processing time of the meta-heuristics is longer. In the case study, the best result obtained shows that it is possible, through the Genetic Algorithm method for phase 1 (FLP) and phase 2 (ATSP), a reduction of approximately 36.54% in the displacement of the delivery man compared to the solution adopted by the company, reflecting the possibility of cost reduction. Keywords: Optimization. Routing. Facility Location Problem (FLP). Assimetric Traveling Salesman Problem (ATSP), Heuristics, Meta-Heuristic