Resumo |
Os drones são veículos aéreos não tripulados que cada vez mais vêm ganhando popularidade por permitir, de forma prática, que tarefas em diversas áreas sejam realizadas, principalmente pela sua facilidade de acesso a determinados locais. Uma dessas aplicações está na pulverização agrícola de forma autônoma, seguindo rotas já programadas. Drones dessa categoria costumam ter raios de borrifação em torno de 4 metros, o que permite que a pulverização aconteça exatamente acima do ponto desejado ou de uma certa distância. Além disso, é possível que dois ou mais pontos próximos sejam atendidos de uma só vez, encurtando, assim, a rota total realizada pelo veículo. Neste trabalho, o roteamento dos drones é modelado como um Close Enough Traveling Salesman Problem (CETSP), um problema de otimização no qual o objetivo é buscar o menor caminho possível que, a partir de um depósito, atravesse uma sequência de regiões e retorne ao depósito estabelecido. Cada coordenada onde se deseja borrifar gera uma vizinhança discreta ao seu redor, podendo ter, ou não, interseções com outras vizinhanças de outras coordenadas. Além disso, são consideradas as restrições impostas pela utilização do drone, como local de lançamento; bateria e carga, que podem implicar na necessidade do planejamento de mais de uma rota. O CETSP é um problema do tipo NP-Difícil, de alta complexidade computacional, não sendo conhecidas formas eficientes de resolvê-lo de forma exata, especialmente para casos de teste maiores. Mesmo sendo possível projetar uma modelagem matemática que represente o problema, ela não resolve em tempo hábil grandes instâncias. Portanto, é proposta uma abordagem heurística que visa apresentar uma solução de boa qualidade e que seja possível de se obter em tempo satisfatório. Para isso, são obtidas as mínimas regiões de interseção entre as vizinhanças que formam o problema. De cada uma delas é escolhido um ponto representativo, formando um conjunto C, e que serão utilizados para formar as coberturas iniciais. Como podem ser necessárias mais de um rota, é aplicada uma clusterização em C de tal maneira que sejam formados os primeiros conjuntos de pontos que participarão de rotas em comum. Após isso, são aplicadas estratégias de busca heurística para melhorar o roteamento obtido. |