Resolvendo um problema de roteamento de veículos capacitado por meio de uma meta-heurística GRASP: um estudo de caso

Abstract

Resumo: Na área de Pesquisa Operacional um problema muito estudado é o Problema de Roteamento de Veículos (PRV). Uma extensão desse problema é o Problema de Roteamento de Veículos Capacitados (PRVC) definido como a busca para determinar um conjunto de rotas para uma frota homogênea de veículos, a partir de um depósito central com destino a um conjunto de clientes que demandam determinado produto. Este trabalho propõe uma método de solução para o PRVC por meio da meta-heurística Greedy Randomized Adaptive Search Procedure (GRASP). Para validar o método proposto, foram criadas instâncias (cenários) do problema baseadas em dados reais fornecidos pela empresa Loggi. Além disso, é realizada uma comparação entre os resultados obtidos com a meta-heurística GRASP e o uso de uma busca gulosa para a resolução desse problema.___Abstract: In the field of Operations Research, a problem that has been studied a lot is the Vehicle Routing Problem (PRV). An extension of this problem is the Qualified Vehicle Routing Problem (PRVC) defined as the search to determine a set of routes for a homogeneous fleet of vehicles, from a central warehouse destined for a set of customers who demand a certain product. This work proposes a solution method for PRVC using the Greedy Randomized Adaptive Search Procedure (GRASP) metaheuristic. To validate the proposed method, instances (scenarios) of the problem were created based on real data provided by the company Loggi. Furthermore, a comparison is made between the results obtained with the GRASP meta-heuristic and the use of a Greedy Search to solve this problem.