Proposta de um Algoritmo Híbrido baseado em Colônia de Formigas para o Problema de Roteamento de Veículos com Restrições de Cobertura

Resumo

O Problema de Roteamento de Veículos (PRV) é um problema clássico de Otimização Combinatória, e a principal motivação para o seu estudo e de suas variações é o alto gasto com o transporte de cargas, impactando nos preços da matéria prima e do produto final. Neste trabalho, estuda-se uma variação do PRV denominada Problema de Cobertura Multi- Veículo (PCMV) que, diferentemente das demais variações existentes na literatura, possui restrições de cobertura e natureza seletiva, além das restrições de carga nos veículos. Este trabalho propõe um algoritmo híbrido baseado em Colônia de Formigas (CF) para o PCMV que utiliza um algoritmo Variable Neighborhood Search (VNS) e fundamenta-se na trans- formação do PCMV em um Problema de Roteamento de Veículos Capacitado (PRVC), para o qual o método apresentado foi projetado. O algoritmo proposto obteve 16 novos limites primais para as 30 Instâncias consideradas em um tempo computacional inferior a 21 segundos, enquanto os resultados apresentados na literatura foram encontrados em até quatro horas de execução.