INTEGRAÇÃO DOS ALGORITMOS CLUSTERING SEARCH E PATH RELINKING PARA RESOLUÇÃO DO PROBLEMA DE ROTEAMENTO DE VEÍCULOS EM UM INVENTÁRIO FLORESTAL

O setor de árvores plantadas desempenha um papel estratégico na economia brasileira, exigindo um monitoramento constante das áreas florestais. Esse acompanhamento é realizado por meio do inventário florestal, atividade que demanda o deslocamento de equipes de medição da sede da empresa até os talhões. O planejamento adequado desse processo possibilita a redução dos trajetos e, consequentemente, dos custos operacionais. O Planejamento do Inventário Florestal (PIF) pode ser modelado como uma variante do Problema de Roteamento de Veículos (PRV), mais especificamente o Problema de Roteamento Periódico de Veículos com Janela de Tempo (PRPVJT).
Este trabalho propõe uma abordagem híbrida para a resolução do PRV-PIF. Trata-se da integração entre a meta-heurística Clustering Search (CS) e a estratégia de intensificação Path Relinking (PR). O método proposto é denominado CS+PR e utiliza o Simulated Annealing (SA) como algoritmo gerador de soluções e a distância de Hamming para mensurar a similaridade na fase de clusterização. A metodologia foi avaliada em um conjunto de nove instâncias com dimensões variadas, incluindo cenários de pequeno, médio e grande porte, com limite de até 2016 talhões, 252 dias de horizonte temporal e três equipes de trabalho.
Os experimentos computacionais demonstraram a robustez e a consistência do algoritmo CS+PR, que obteve soluções viáveis para todas as instâncias. Em termos de desempenho, a abordagem proposta superou o método exato Branch-and-Cut, executado através do solver CPLEX, cujos resultados estão registrados na literatura, o qual encontrou soluções exatas em apenas três das nove instâncias. Além disso, nessas instâncias o método CS+PR foi capaz de encontrar as melhores soluções em um tempo inferior ao Branch-and-Cut. Por fim, destaca-se que para a maior instância (2016 talhões), o CS+PR foi capaz de gerar o planejamento anual completo das equipes em aproximadamente 81 minutos.
Conclui-se que a integração do Clustering Search com o Path Relinking constitui uma alternativa altamente eficaz e competitiva para o planejamento logístico do inventário florestal, otimizando o uso de recursos e reduzindo significativamente os tempos e custos de deslocamento.