查看文章

O Problema do Roteamento de Veículos Capacitados (PRVC) é uma das mais conhecidas abordagens em pesquisa operacional para resolução de problemas em logística de distribuição. Por sua complexidade combinatória o PRVC enseja o emprego de técnicas heurísticas para sua resolução. Neste sentido, este artigo apresenta e compara duas abordagens para a resolução do problema. 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. Na primeira abordagem, o agrupamento dos pontos de demanda é realizado empregando técnicas de simulação de Monte Carlo, juntamente com o algoritmo de designação proposto por Gillet Johnson (1976). Para a segunda abordagem, foi elaborada uma heurística envolvendo os algoritmos clássicos de agrupamento e designação propostos por Teitz e Bart (1968) e Gillet Johnson (1976), respectivamente. Em ambas as abordagens, as rotas iniciais são geradas pela heurística do vizinho mais próximo e refinadas pelas trocas 2-opt. Comparativamente a primeira abordagem obteve desempenho superior à segunda, tanto em termos de eficácia, quanto em eficiência, ressaltando a influência da qualidade do agrupamento dos pontos de demanda sobre a solução final do problema.