Abordagens Integradas para Problemas de Floresta e Roteamento: Métodos Híbridos, Decomposições e Aprendizado de Máquina

Descrição

Este projeto de pesquisa insere-se na área de Otimização Combinatória e Pesquisa Operacional, com foco em duas classes de problemas NP-difíceis de grande relevância teórica e aplicada. A primeira classe é o Problema da Floresta Geradora Restrita de Custo Mínimo (PFR), que consiste em: dado um grafo não direcionado com pesos nas arestas e um inteiro k >= 2, encontrar uma floresta geradora (conjunto de árvores que cobre todos os vértices) tal que cada componente conexa tenha pelo menos k vértices, minimizando o custo total. O PFR modela problemas reais como: alocação de centros de comunicação em redes, microagregação de dados estatísticos (preservação de privacidade), distritalização política, conexão de sensores em redes inteligentes e particionamento de grandes áreas em sub-regiões autossuficientes. Embora existam formulações exatas e heurísticas, há uma lacuna na integração sistemática entre métodos exatos e decomposições, especialmente para instâncias reais com centenas ou milhares de vértices. A segunda classe é o Problema do Caixeiro Alugador (PCA), uma generalização do clássico Problema do Caixeiro Viajante (TSP). No PCA, múltiplos veículos (cada um com sua própria matriz de custos operacionais entre cidades) podem ser alugados e devolvidos em diferentes vértices, com taxas de retorno específicas. O objetivo é encontrar um ciclo Hamiltoniano que inicia e termina no vértice de origem, podendo trocar de veículo durante o percurso, minimizando a soma dos custos operacionais e das taxas de retorno. Aplicações diretas incluem: logística de transporte com frota heterogênea (locação de caminhões, carros, trens), turismo, manufatura flexível e planejamento de rotas em plataformas de compartilhamento de veículos. A literatura recente concentra-se predominantemente em heurísticas, negligenciando a sinergia entre métodos exatos (branch-and-cut), decomposições (geração de colunas, lagrangiana) e aprendizado de máquina.