Defesa de Tese de Doutorado de Elias Lawrence Marques Júnior, em 08/08/2024, às 09:00 horas, por videoconferência
Link: https://meet.google.com/imp-cfht-bhm
Multi-Objective Metaheuristics for a Green UAV Grid Routing Problem
Resumo:
Dada a crescente dependência da tecnologia dos Veículos Aéreos Não Tripulados (VANTs) para diversas aplicações, incluindo serviços de entrega, vigilância e monitorização ambiental, o roteamento eficiente destes veículos tornou-se crucial. A pesquisa investiga técnicas de otimização multiobjetivo para enfrentar os desafios únicos colocados pelo roteamento de VANT, incluindo vida útil limitada da bateria, múltiplas estações de carregamento, ajustes de rota em tempo real e navegação através de áreas proibidas. Uma parte do trabalho introduz uma metaheurística multiobjetiva de duas fases baseada em Variable Neighborhood Search (VNS). Esta abordagem visa gerar soluções não dominadas que equilibrem múltiplos objetivos, como minimizar a extensão da rota, maximizar o número de clientes atendidos e otimizar o uso da bateria. Experimentos computacionais demonstram a eficácia deste algoritmo na adaptação a mudanças em tempo real e na otimização de rotas em cenários de grade dinâmica. É apresentado um estudo sobre otimização de rotas de VANT em cidades inteligentes, onde são consideradas restrições realistas como obstáculos e zonas de exclusão aérea. A pesquisa fornece um conjunto abrangente de soluções não dominadas que são analisadas utilizando ferramentas de visualização de última geração para compreender os compromissos e sinergias entre diferentes objetivos. Comparações com métodos exatos, como a Programação Linear Inteira Mista (MILP), destacam os pontos fortes da abordagem metaheurística, especialmente no tratamento de instâncias maiores e mais complexas, onde os métodos exatos lutam para encontrar soluções ideais dentro de prazos razoáveis. As principais contribuições desta tese incluem o desenvolvimento de algoritmos inovadores para otimização de rotas de VANT em tempo real, a introdução de uma abordagem baseada em aprendizagem para melhorar a eficiência da pesquisa e a aplicação de otimização multiobjetivo em ambientes urbanos complexos. No geral, as metodologias e resultados apresentados nesta investigação abrem caminho para aplicações mais avançadas e práticas da tecnologia VANT em cidades inteligentes e não só, abordando desafios críticos e propondo soluções eficazes que melhoram as capacidades operacionais dos VANT em ambientes dinâmicos e restritos.
Abstract:
Given the increasing reliance on Unmanned Aerial Vehicles (UAV) technology for various applications, including delivery services, surveillance, and environmental monitoring, the efficient routing of these vehicles has become crucial. The research investigates multiobjective optimization techniques to address the unique challenges posed by UAV routing, including limited battery life, multiple charging stations, real-time route adjustments, and navigation through prohibited areas. A portion of the work introduces a two-phase multiobjective metaheuristic based on Variable Neighborhood Search (VNS). This approach aims to generate non-dominated solutions that balance multiple objectives, such as minimizing route length, maximizing the number of clients served, and optimizing battery usage. Computational experiments demonstrate the effectiveness of this algorithm in adapting to real-time changes and optimizing routes in dynamic grid scenarios. A study on UAV route optimization within smart cities, where realistic constraints like obstacles and no-fly zones are considered is presented. The research provides a comprehensive set of non-dominated solutions that are analyzed using state-of-the-art visualization tools to understand the trade-offs and synergies between different objectives. Comparisons with exact methods like Mixed-Integer Linear Programming (MILP) highlight the strengths of the metaheuristic approach, especially in handling larger and more complex instances where exact methods struggle to find optimal solutions within reasonable time frames. Key contributions of this thesis include the development of innovative algorithms for realtime UAV route optimization, the introduction of a learning-based approach to improve search efficiency, and the application of multi-objective optimization in complex urban environments. Overall, the methodologies and results presented in this research pave the way for more advanced and practical applications of UAV technology in smart cities and beyond, by addressing critical challenges and proposing effective solutions that enhance the operational capabilities of UAVs in dynamic and constrained environments.
Banca examinadora:
Prof. Luiz Satoru Ochi, UFF – Presidente
Prof. Igor Machado Coelho, UFF
Prof. Fábio Protti, UFF
Prof. Yuri Abitbol de Menezes Frota, UFF
Prof. Nelson Maculan Filho, UFRJ
Prof. Virgilio José Martins Ferreira Filho, UFRJ