Abordagem Meta-heurística Aprimorada por Aprendizado de Reforço para o Clustered Flying Sidekick Travelling Salesman Problem

• Processo: 25/02409-0
• Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Iniciação Científica
• Data de Início da vigência: 01 de junho de 2025
• Data de Término da vigência: 30 de setembro de 2025
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Mário César San Felice
• Beneficiário: Pedro Guilherme Torres das Neves
• Supervisor: Emrah Demir
• Instituição Sede: Centro de Ciências Exatas e de Tecnologia (CCET). Universidade Federal de São Carlos (UFSCAR). São Carlos , SP, Brasil
• Instituição Anfitriã: Cardiff University, País de Gales
• Vinculado à bolsa: 23/10946-0 - Meta-Heurística Evolutiva para Problemas de Roteamento com Drones, BP.IC
• Assunto(s): Veículos aéreos não tripulados Otimização combinatória
• Palavra(s)-Chave do Pesquisador: Clustered Travelling Salesman Problem | Drones | Meta-Heuristic | reinforcement learning | Otimização Combinatória

Resumo

Os Problemas de Roteamento de Veículos (VRPs) desempenham um papel crítico na otimização logística, minimizando o consumo de combustível e tempo, com aplicações que vão desde entregas até assistência médica. Avanços recentes na tecnologia de drones introduziram drones nos VRPs, possibilitando soluções mais rápidas e econômicas. Este projeto foca no Clustered Flying Sidekick Travelling Salesman Problem (CFSTSP), um problema proposto como uma extensão tanto do Flying Sidekick Travelling Salesman Problem (FSTSP) quanto do Clustered Travelling Salesman Problem (CTSP). No CFSTSP, um caminhão e um drone atendem colaborativamente os clientes agrupados em clusters, garantindo que todos os vértices dentro de um cluster sejam visitados antes de iniciar um novo cluster. Sendo um problema NP-Difícil, encontrar soluções ótimas para instâncias grandes do CFSTSP utilizando métodos exatos é computacionalmente inviável. Para lidar com isso, o projeto propõe um Multi-Parent Biased Random-Key Genetic Algorithm with Implicit Path Relinking (MP-BRKGA-IPR) aprimorado por Q-Learning. Essa abordagem visa combinar as vantagens de ambos os métodos para resolver o CFSTSP de forma eficiente, com aplicações potenciais na last mile delivery e outros desafios logísticos.