Open AccessUMA NOVA ABORDAGEM HEURÍSTICA PARA A RESOLUÇÃO DO PROBLEMA DO ROTEAMENTO DE VEÍCULOS CAPACITADOS
Author(s) -
Thiago André Guimarães,
Cassius Tadeu Scarpin,
María Teresinha Arns Steiner
Publication year - 2011
Publication title -
revista gestão industrial
Language(s) - Portuguese
Resource type - Journals
ISSN - 1808-0448
DOI - 10.3895/s1808-04482011000300007
Subject(s) - physics , humanities , computer science , philosophy
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