Heurística de Busca de Vizinhança Variável para Otimização do Problema de Roteamento de Veículos Capacitados

Abstract

Este trabalho investiga métodos computacionais para a otimização do Problema de Roteamento de Veículos Capacitados. O problema de logística tratado busca minimizar os custos de transporte encontrando a melhor rota para que os veículos de uma frota atendam todos os clientes, respeitando as restrições de capacidade dos veículos. Para isso, foi desenvolvido um algoritmo que recebe o tamanho da frota e uma matriz de custos para se chegar em cada local necessário e retorna a melhor rota para todos os veículos, de forma a atender todos os clientes. O algoritmo é baseado na meta-heurística Variable Neighborhood Search (VNS) que busca melhorar as rotas incrementalmente procurando melhorias na vizinhança. Com o VNS como base, foram propostas 5 estruturas de vizinhanças para as buscas locais. Sendo 4 vizinhanças de busca determinísticas, para um processo de descida do espaço de soluções, e 1 busca aleatória, para tentar escapar de mínimos locais. Foi possível encontrar rotas com custos apenas 8% maiores que os custos ótimos, em média, para diversos cenários. Os resultados obtidos demonstram que o algoritmo desempenhou de forma eficiente para resolver o problema do roteamento de veículos capacitados (PRVC), assim o modelo pode ser aplicado em diversos cenários onde é tratado o PRVC.