Autor: Timótio Capitão Cubaque (Currículo Lattes)
Resumo
Nos últimos anos, o problema de roteamento de veículos tem atraído cada vez mais interesse entre pesquisadores devido à sua presença em várias situações cotidianas e à grande dificuldade de solução. Esforços significativos têm sido feitos para desenvolver técnicas mais robustas e eficazes, capazes de lidar com a complexidade desse problema. O objetivo central é determinar uma série de rotas para um conjunto de veículos, os quais devem atender a um conjunto de clientes, buscando minimizar o custo total de transporte. O problema de roteamento de veículos capacitado é uma variante do problema de roteamento de veículos, no qual é necessário encontrar um conjunto de rotas para uma frota de veículos homogêneos, de modo que eles possam atender a todos os clientes. Neste contexto, há algumas restrições a serem consideradas: as rotas devem iniciar e terminar no depósito, cada cliente deve ser visitado apenas uma vez por um único veículo e a demanda total em qualquer rota não pode ultrapassar a capacidade do veículo. Devido à sua complexidade, esse tipo de problema é classificado como NP-difícil, o que significa que não existem algoritmos polinomiais conhecidos para resolvê-lo de forma ótima em tempo razoável. Portanto, soluções aproximadas são comumente buscadas utilizando algoritmos heurísticos e meta-heurísticos. O presente estudo investiga a questão da roteirização de uma frota de veículos por meio da análise de dados espaciais, empregando métodos heurísticos e a técnica de ensemble. Dois algoritmos de clusterização, K-means e DBSCAN, são empregados para agrupar os clientes de acordo com as suas localizações geográficas. A partir dessas abordagens, duas estratégias distintas são desenvolvidas, cada uma explorando um modelo específico de clusterização para agrupar os clientes. Além disso, a heurística do vizinho mais próximo é empregada para gerar soluções iniciais, enquanto o método 2-Opt é aplicado para aprimorar as soluções iniciais obtidas. Nos testes realizados, os resultados obtidos pelas estratégias propostas são comparados entre si e também com abordagem de otimização desenvolvida pela Loggi uma empresa de tecnologia voltada para logística e entregas sob demanda, Benchmark Loggi BUD. Os resultados destacam o desempenho positivo de ambas as estratégias, tanto em relação a distância total percorrida pela soma das rotas dos caminhões, quanto no que diz respeito ao equilíbrio das distâncias percorridas entre os caminhões.