UMA NOVA ABORDAGEM HEURÍSTICA PARA A RESOLUÇÃO DO PROBLEMA DO ROTEAMENTO DE VEÍCULOS CAPACITADOS

Resumo

Este trabalho apresenta uma nova abordagem heurística para a resolução do Problema do Roteamento de Veículos Capacitados (PRVC). O método emprega uma estratégia em dois estágios, que consiste primeiramente em agrupar os clientes de acordo com a demanda e, posteriormente, construir as rotas para os grupos formados. Para o primeiro estágio, desenvolveu-se uma heurística de ajuste para o algoritmo clássico de agrupamento proposto por Teitz e Bart (1968). No segundo estágio, as rotas iniciais são geradas pela heurística de inserção mais econômica e refinadas pelas heurísticas de melhoria 2-opt e 3-opt. A abordagem proposta foi testada para instâncias clássicas da literatura, e comparadas com o desempenho de procedimentos exatos e heurísticos existentes, produzindo resultados interessantes, tanto em termos de eficácia quanto de eficiência.