Iterated Beam Search for Wildland Fire Suppression

Wildfires cause significant damage costs globally, and it is likely that they are becoming more damaging due to climate change. Here we study methods for fire suppression, after a breakout of fire. In our model, we have a grid graph \(G=(V,A)\) that represents the discretization of a terrain into cells and an ignition node \(s \in V\) from which the fire spreads to other nodes. The spread of the fire is defined by the arc weights, which can be used to model important factors such as wind direction and vegetation type. At various points in time, one or more fire suppression resources become available to be applied to nodes in the graph that are not yet burned. Applying a resource to a node \(v \in V\) adds a delay to the outgoing edges of v, which causes a local slowdown in fire propagation. The goal is to find an allocation of resources to the nodes of the graph such that the total burned area at a target time is minimized. In this work, we propose a heuristic algorithm based on beam search to tackle this problem. Our computational experiments show that our approach is able to consistently find the optimal solution to almost all instances used in literature, but in considerably less time than previous approaches.