Tamanho da fonte:
Desenvolvimento de um algoritmo baseado no Hill-Climbing para o problema de roteamento de veículos periódico
Última alteração: 2019-08-08
Resumo
O objetivo deste trabalho é descrever o desenvolvimento um algoritmo para solucionar problemas de roteamento periódico de veículos (PVRP, do inglês, Periodic Vehicle Routing Problem). O algoritmo proposto busca encontrar soluções próximas ou iguais às da literatura para o problema em um curto espaço de tempo. O problema tratado é de alta complexidade e busca definir rotas que atendam às demandas dos clientes que podem acontecer ao longo de um horizonte de tempo, de maneira periódica, respeitando a restrição de capacidade do veículo. O método de resolução proposto pode ser dividido em três fases. Na primeira fase são designados os períodos de cada ponto aleatoriamente, procurando equilibrar a carga entre os períodos. A segunda fase consiste em designar os pontos aos veículos de cada período de forma factível utilizando o algoritmo do vizinho mais próximo como regra de agrupamento. Na terceira fase o algoritmo 2-opt é utilizado em cada rota de cada veículo. Os resultados se mostraram próximos aos da literatura.
Palavras-chave
Problema de Roteamento Periódico de Veículos. Hill-climbing. Vizinho Mais Próximo. Algoritmo 2-opt.