Uma Heurística Híbrida para o Problema de Roteamento com Cobertura Multi-Veículo e Coleta de Prêmios

O Problema de Roteamento de Veículos tradicional assume atendimento direto aos clientes, o que não é adequado em aplicações com instalações intermediárias. Nesse contexto, o Covering Tour Problem (CTP) considera o atendimento indireto por facilidades. Neste trabalho, propomos o Problema de Roteamento com Cobertura Multi-Veículo e Coleta de Prêmios, que adiciona múltiplos veículos ao CTP e restrições de coleta mínima de prêmio. O objetivo é determinar rotas de custo mínimo que satisfaçam simultaneamente cobertura e prêmio. Para resolver o problema, desenvolvemos uma heurística híbrida que combina construção de soluções, diversificação via ruin-and-recreate e pós-otimização por uma formulação de programação inteira mista baseada em rotas. As rotas são armazenadas em um pool e reutilizadas ao longo do processo. A abordagem é avaliada em 378 instâncias derivadas do CTP-PC. Resultados mostram que a combinação de rotas reduz em média 1,7\% o custo das soluções, além de fornecer benchmarks para futuras comparações.