Advanced meta-heuristic approaches and their application to operational optimization in forest wildfire management

Abstract

In the last decade the number and frequency of large-scale disaster events has increased sharply, mainly due to the devastating phenomena derived from worldwide climatological paradigms (e.g. global warming). Floods, hurricanes and earthquakes are among those disasters whose severity has grown significantly during this period: as to mention, in 2001 more than 20.000 casualties resulted from a massive earthquake in the state of Gujarat (India), whereas this fatal indicator went up to approximately 230.000 and 316.000 casualties in the earthquakes occurred in Indonesia and Haiti in 2004 and 2010, respectively. The scope of this Thesis focuses on a particular class of disasters with an equally concerning increase of its severity and frequency in the last few years: wildfire events, understood as those large-sized fires not voluntarily initiated by the human being. Despite the variety of initiatives, procedures and methods aimed at minimizing the impact and consequences of wildfires, several fatalities occurred in the last few years have put to question the effectiveness of current policies for the allocation of firefighting resources such as aircrafts, vehicles, radio communication equipment, supply logistics and fire brigades. A clear, close exponent of this noted deficiency is the death of eleven firefighters occurred in a 130 km2 forest wildfire in Guadalajara (Spain) in 2005, which was officially attributed to a proven lack of coordination between the command center and the firefighting crew on site, ultimately resulting in radio isolation among the deployed teams. The reason for this missed coordination in the management of firefighting resources can be questioned by authorities and involved stakeholders, but it undoubtedly calls for the study and development of algorithmic tools that help operations commanders optimally perform their coordination duties. Unfortunately, the economical crisis mostly striking on countries from the Southern Europe has reduced significantly national budgetary lines for wildfire prevention and suppression to the benefit of deficit-reduction programs. As a consequence of these budget cuts, cost aspects have lately emerged as necessary, relevant criteria in operations planning: from an optimization perspective, firefighting resources are allocated so as to achieve the maximum effectiveness against wildfires, subject to the available budget upper bounding the overall economical cost associated to the decisions taken by commanders and decision makers. Although the cost constraints in this problem are obvious and well-reasoned, in practice management procedures for firefighting resources do not follow cost-aware strategies, but are instead driven by the limited capacity of the human being to dynamically perform decisions in complex, heterogeneous scenarios. This Thesis builds upon the above rationale to propose modern meta-heuristic algorithms for solving optimization problems modeling different firefighting resource allocation paradigms. This family of solvers efficiently explores the solution space of a given problem by iteratively applying intelligent explorative and exploitative mechanisms, yielding solutions that trade optimality for a reduced computational complexity with respect to exhaustive search methods. In particular, the dissertation gravitates on the adoption of Harmony Search algorithm as the meta-heuristic technique lying at the core of the proposed resource allocation schemes, which are contextualized in two different scenarios: • The first studied setup addresses the optimum design of wireless relayed communication networks deployed over large-scale disaster areas. In this scenario the so-called dynamic relay deployment problem consists of finding the optimum number of deployed communication relays and their location aimed at simultaneously maximizing the number of nodes covered and minimizing the cost of the deployment. This problem formulation is further extended by considering diverse relay models characterized by different coverage radii and associated costs. To efficiently tackle this problem a novel hybrid scheme is derived comprising 1) a Harmony Search based global searching procedure; and 2) a modified version of the K-means clustering algorithm as a local search technique. Single- and biobjective approaches are proposed for emergency and strategic communications planning, respectively. Numerical experiments are run over an emulated scenario based on real statistical data from the Castilla La Mancha region (center of Spain) to show that the proposed scheme provides an intelligent tool capable of simultaneously determining the number and models of the relays to be deployed. • The second scenario focuses on the optimal deployment of aerial firefighting aircrafts based on predictive fire risk estimations over a certain geographical area. The underlying optimization problem can be formulated as how to properly allocate firefighting resources to capacity-constrained aerodromes in such a way that the utility of the deployed resources with respect to fire forest risk predictions is maximized and the overall cost of performing the resource allocation is minimized. The problem formulation is further complemented by considering the relative distance between the aerodrome, the wildfire and water pump resources (sea, rivers and lakes) in the metric definition. From the algorithmic standpoint, single- and bi-objective Harmony Search heuristics are proposed jointly with a greedy local method that accounts for the imposed capacity constraints. The performance of the developed solvers is assessed through experiments run in synthetic scenarios and a realistic setup over the Spanish peninsula, including practical estimations of the Fire forest Weather Index (FWI) and real geographical locations of water resources and aerodromes. The satisfactory results obtained therefrom shed light on the applicability of the derived techniques to the preemptive management of aerial resources under cost and effectiveness criteria. To sum up, this Thesis elucidates, from a case-based approach, that modern metaheuristics embody a computationally efficient algorithmic solution for solving costconstrained communications and firefighting resource allocation paradigms arising from the management of wildfire events.