Otimização do problema de roteamento de veículos capacitados com uso da heurística de Clarke e Wright e algoritmos genéticos

Abstract

Resumo : A logística é uma das áreas que está no centro das atenções atualmente, uma boa operação logística pode ser considerada uma grande vantagem competitiva. Em se tratando de transporte e otimização de rotas, o Problema de Roteamento de Veículos (PRV) representa a melhor forma de atender vários pontos e o Problema de Roteamento de Veículos Capacitados (PRVC) é uma forma de PRV onde diferentes veículos suprem a demanda de clientes, respeitando suas capacidades de cargas. Existem softwares capazes de encontrar a solução ótima, mas tanto o custo quanto o tempo para se obter a solução acabam se tornando barreiras para a utilização. Uma diferente forma de encontrar uma solução viável são os métodos heurísticos, que são algoritmos criados fornecem uma solução um tempo consideravelmente melhor. O objetivo desse trabalho foi implementar a heurística de Clarke e Wright (C&W) e, depois de se obter a solução, implantar o Algoritmo Genético (AG), utilizado neste trabalho como método de melhoria. E então, testar diferentes problemas e comparar tanto as soluções obtidas quanto o tempo computacional quando utilizado um software de otimização como o Gurobi. Os resultados foram comparados entre si levando em consideração os aspectos acima. Nota-se a grande vantagem do uso de heurísticas, tanto em relação a qualidade da solução quanto em tempo computacional, em comparação ao uso de softwares de otimização para resolução de grandes problemas

Abstract : Logistics is one of the areas that is currently in the spotlight, a good logistics operation can be considered a great competitive advantage. When it comes to transport and route optimization, the Vehicle Routing Problem (VRP) represents the best way to serve several points and the Capacitated Vehicle Routing Problem (CVRP) is a form of VRP where different vehicles supply the demand of customers, respecting their load capacities. There are software capable of finding the optimal solution, but both the cost and the time to obtain the solution end up becoming barriers to use. A different way of finding a viable solution is heuristic methods, which are algorithms created that provide a solution in a considerably better time. The objective of this work was to implement the Clarke and Wright (C&W) heuristic and, after obtaining the solution, to implement the Genetic Algorithm (GA), used in this work as an improvement method. And then, test different problems and compare both the solutions obtained and the computational time when using an optimization software such as Gurobi. The results were compared with each other considering the above aspects. There is a great advantage in the use of heuristics, both in relation to the quality of the solution and in computational time, compared to the use of optimization software for solving large problems