APLICAÇÃO DO ALGORITMO DE SAVINGS PARA GERAR ROTAS SATISFATÓRIAS PARA O PROBLEMA VRP CLÁSSICO

Resumo

No problema clássico de roteamento de veículos é considerado um conjunto de cidades, com coordenadas e requisitos de entrega para cada uma, e um depósito de onde os veículos devem partir para reabastecer sua carga. Neste problema não são limitadas as vezes em que um veículo pode sair do depósito e voltar para ele. Desta forma, este trabalho busca, inspirado no algoritmo de savings, obter resultados bons o suficientes para o problema clássico de roteamento de veículos. Os resultados do algoritmo implementado se aproximam de resultados ótimos globais quando os valores gerados pela equação de economia são similares entre as cidades mas, quando estes valores diferem muito entre si, em alguns casos, são gerados resultados distantes do esperado. Como trabalhos futuros vislumbra-se a otimização do algoritmo com métodos de melhoria após a sequência de cidades já ter sido definida pelo algoritmo original, além de buscar aplicar esta estratégia na produção de um algoritmo de vigilância, substituindo os requisitos de entrega pela bateria de um determinado drone, buscando otimizar o uso desta caso o drone não tenha capacidade para terminar a rota pré estabelecida com sua carga atual.