Problema de roteamento de veiculos : uma abordagem utilizando diferentes metodos para a criação de rotas

Abstract

Resumo: Os problemas de otimização são comumente vistos e suas soluções tem grande importância na indústria, bem como no meio academico. São exploradas cinco soluções para um problema que consiste em gerar, ou melhorar, rotas para n-vendedores (ou n-dias) os quais devem percorrer o maior numero de casas no menor tempo possíivel. As soluções escolhidas para o problema foram ordenação, aleatória, solução gerada pelo método do ponto proximal (MPP), Adaptive Large Neighborhood Search (ALNS) e algoritmo genetico. Foram usados 1383 pontos do bairro Porto Novo da cidade de Cariacica no Espírito Santo - Brasil. Após a realização de agrupamentos e limpezas de dados foram roteados 352 pontos com um total de 1200 casas atendidas. Para esse atendimento os algoritmos trouxeram rotas com necessidade entre 5 e 8 vendedores e tempo de percurso entre 24 horas e 30 minutos. Três dos melhores resultados obtidos foram com o uso do algoritmo genetico, porém com um tempo de processamento entre 47 e 969 vezes maior que o metodo do ponto proximal - isso, sem levar em consideração o gasto de memória - que ficou em quarto lugar juntamente com o algoritmo ALNS.