Um Algoritmo Exato para o Close Enough Vehicle Routing Problem Aplicado a Drones de Pulverização

Este trabalho introduz um algoritmo exato capaz de planejar o roteamento de drones para pulverização de recursos agrícolas. Uma vez que a borrifação em ponto cobre uma área em seu entorno, a trajetória do dispositivo foi modelada como uma solução para o Close Enough Vehicle Routing Problem, em que o objetivo é otimizar rotas que cobrem um conjunto de coordenadas ao passar próximo a elas, bem como seus pontos de lançamento e retorno. Para isso, é proposto um algoritmo Branch-and-Bound, inicializado com uma solução heurística baseada em zonas de cobertura, capaz de resolver instâncias em sua otimalidade, munido de uma estratégia de Programação Dinâmica. Os resultados experimentais mostraram que o algoritmo é capaz de resolver instâncias verossímeis, com diferentes níveis de dispersão dos pontos de borrifação, dentro do limite estipulado de 10 minutos, permitindo ampla aplicação na agricultura de precisão.