| Resumo : |
Drones, ou Veículos Aéreos Não Tripulados (VANTs), são considerados o futuro do transporte aéreo, especialmente em operações logísticas. Eles podem ser integrados com caminhões, potencializando pontes fortes e mitigando fraquezas de ambos. Isso cria um problema de otimização entre dois veículos simultâneos, conhecido como Problema do Caixeiro Viajante com Ajudante Voador (FSTSP). Esse conceito encontra aplicações em transporte de vacinas e medicamentos, em inteligência, vigilância, reconhecimento (IVR), em entregas de materiais, operações tanto militares quanto civis. O objetivo desta pesquisa é implementar o Algoritmo Genético de Chave Aleatória Tendenciosa (BRKGA), no contexto do Problema do Caixeiro Viajante (TSP) e do FSTSP, testando-o a partir de dados em dois diferentes cenários, um civil - caso 1 Florianópolis, e um militar - caso 2 Curso Avançado de Aviação do Exército. A metodologia para implementar meta-heurística pode ser seguida por um método que consiste em entender o problema usando um modelo matemático, utilizar instâncias de Ponza (2016) e dois cenários do mundo real, implementar e comparar a meta-heurística usando análise de lacuna de qualidade de solução e tempo de execução. O algoritmo demonstra bom desempenho no TSP, alcançando uma lacuna média de 1,4% em comparação com soluções na literatura, com tempos de execução variando de 4s a 4463s, dependendo da complexidade da instância. No FSTSP, o BRKGA supera o Simulated Annealing (SA) em algumas pequenas instâncias e alcança um tempo de execução médio de 0,41s. Quando o BRKGA é aplicado a instâncias médias e grandes de Ponza (2016), ele mostra um desempenho razoável, superando o SA de Ponza (2016) em tempo de execução, com um tempo médio de 40,9s em comparação aos 336,06s do SA. No entanto, em termos de qualidade da solução, o SA alcançou 0,10 de lacuna em comparação com 0,18 do BRKGA. O BRKGA alcança um desempenho de tempo próximo ao tempo médio do HTGVNS (18,06s) e HGVNS (16,39s), entretanto, em termos de qualidade da solução, HTGVNS e HGVNS permanecem o estado da arte. No caso 1, o algoritmo de otimização BRKGA economizou 102,6s no tour 1 do drone e permitiu o acesso a locais inacessíveis para caminhões no tour do drone 2. Já no caso 2, o algoritmo BRKGA economizou 36,5s no tour do drone. Concluindo, o BRKGA pode alcançar resultados razoáveis quando aplicado no TSP e FSTSP, no entanto, a melhoria desses resultados pode ser alcançada por meio de uma implementação mais refinada de drones. Ademais, fatores como áreas isoladas, sensíveis e com variação de altitude podem ser mais bem aproveitados pelos drones em futuras pesquisas. |