MÉTODOS DE SOLUÇÃO APLICADOS AO PROBLEMA DE ROTAS DE COBERTURA MULTIVEÍCULO

Resumo

Este artigo explora métodos de solução para o problema de rotas de cobertura multiveículo, modelado com base em três conjuntos de vértices: os que podem ser visitados, os que devem ser visitados e os que precisam ser cobertos sem visita direta, mas próximos a vértices das rotas. O balanceamento entre rotas é uma restrição, garantindo a distribuição uniforme dos vértices visitados. O objetivo é minimizar a distância total percorrida. As contribuições incluem a proposta de um algoritmo genético, o estudo de um método branch-and-cut e a análise de um método que combina essas duas técnicas. Experimentos computacionais em instâncias adaptadas da TSPLIB foram avaliadas com estatística descritiva, curvas de perfil de desempenho e do tipo time-to-target plot. Os resultados mostraram que o método branch-and-cut enfrentou dificuldades em encontrar soluções viáveis em parte dos casos, enquanto o algoritmo genético obteve soluções para todas as instâncias em tempo satisfatório. A combinação dessas técnicas melhorou o desempenho geral da abordagem.