Resumo: Nesta tese, estudamos primeiramente o Problema Geométrico do Brigadista (GFP) cujo objetivo é maximizar a área total protegida contra um incêndio que se inicia no interior de um ambiente poligonal e se espalha circularmente. A proteção de regiões é realizada através da construção de um subconjunto de curvas (barreiras) de um conjunto dado, levando-se em consideração as velocidades predefinidas de espalhamento do fogo e de construção das barreiras. Com o intuito de estabelecer fundamentos para algoritmos exatos para o GFP, propomos soluções exatas baseadas em técnicas de Programação Inteira (IP), além de detalhar algoritmos de preprocessamento geométrico, uma heurística primal e procedimentos para redução da dimensionalidade do problema. Em segundo lugar, introduzimos o Problema Geométrico de Roteamento do Brigadista (GFRP), que relaxa algumas das restrições impostas pelo GFP sobre o conjunto de barreiras, provendo um modelo que representa mais satisfatoriamente situações reais. De forma a resolver este problema mais intrincado, apresentamos um modelo IP principal e dois conjuntos de desigualdades válidas capazes de tornar mais eficiente a resolução do modelo. Além disso, descrevemos heurísticas primais baseadas em Programação Inteira e algoritmos de redução de dimensionalidade específicos para o GFRP. Também propomos um benchmark composto por vastos conjuntos de instâncias, incluindo alguns baseados em dados reais de reservas florestais dos EUA. Através de uma análise empírica cuidadosa dos algoritmos completos e de um exame da contribuição individual de cada uma de suas componentes principais, quando aplicados a este benchmark, compilamos um extensivo relatório experimental Ver menos

Abstract: In this thesis, we first study the Geometric Firefighter Problem (GFP) that aims to maximize the total area protected from a circularly spreading fire starting somewhere inside a polygonal environment. The protection of regions is accomplished through the construction of a subset of curves (barriers) of a given set, while taking into account the preset speeds of fire propagation and barrier construction. We lay the groundwork for exact algorithms for the GFP by proposing solutions based on Integer Programming (IP) techniques and by detailing required geometric preprocessing algorithms, along with a primal heuristic and problem size reduction procedures. Secondly, we introduce the Geometric Firefighter Routing Problem (GFRP), which relaxes some restrictions imposed by the GFP over the barrier set, and serves to better model realistic settings. To solve the resulting more intricate problem, we present a core IP model along with two sets of valid inequalities that make resolving the model more efficient. Besides, we describe effective IP-based primal heuristics and tailored problem size reduction algorithms. We also propose a benchmark comprised of large sets of instances, including some based on actual U.S. national forests data. By performing a thorough empirical analysis of the complete algorithms, and by examining the contribution of each of their major steps on this benchmark, we build an extensive experimental report Ver menos