Modeling Ground Firefighting Resource Activities to Manage Risk Given Uncertain Weather

Abstract

Wildland firefighting requires managers to make decisions in complex decision environments that hold many uncertainties; these decisions need to be adapted dynamically over time as fire behavior evolves. Models used in firefighting decisions should also have the capability to adapt to changing conditions. In this paper, detailed line construction constraints are presented for use with a stochastic mixed integer fire growth and behavior program. These constraints allow suppression actions to interact dynamically with stochastic predicted fire behavior and account for many of the detailed line construction considerations. Such considerations include spatial restrictions for fire crew travel and operations. Crew safety is also addressed; crews must keep a variable safety buffer between themselves and the fire. Fireline quality issues are accounted for by comparing control line capacity with fireline intensity to determine when a fireline will hold. The model assumes crews may work at varying production rates throughout their shifts, providing flexibility to fit work assignments with the predicted fire behavior. Nonanticipativity is enforced to ensure solutions are feasible for all modeled weather scenarios. Test cases demonstrate the model’s utility and capability on a raster landscape.

1. Introduction

Wildland firefighting requires that managers make decisions to manage risk within complex decision environments that hold many uncertainties. Some of the challenges for managers include determining when and where to place firefighting activities, what those activities should be, how many and what type of firefighting resources are available and which are the best fit for the fire management tasks that must be completed [1,2,3]. Managers must make these assignments while balancing a variety of risks including loss of life to both firefighters and the public; loss of infrastructure such as buildings and power lines; loss of natural resources such as habitat for wildlife, timber, and recreation areas; and damage that threatens water quality [1,2,3]. These complex suppression decisions need to be adapted dynamically over time. The outcome of fire suppression actions hinge on future fire behavior, which is highly dependent upon weather (e.g., [4,5,6,7,8,9,10]). For example, a fireline built to withstand a low intensity fire [10] may contain the fire as long as the fire is still low intensity when it encounters the fireline. If the wind picks up and the fireline intensity increases, the fireline may do little to reduce fire growth. In addition, while firefighting tasks may be completed with the goal of stopping fire spread, other tasks may be undertaken with the goal of slowing a fire or decreasing its intensity [1,11]. As a fire evolves, management actions must consider new developments and changes in fire behavior. For example, many large fires include contingency line which is built in case primary line fails [12]. While empirical research regarding fireline effectiveness is limited [13,14], fire managers do consider expected and worst-case fire behavior when considering where suppression actions are most likely to successfully control the fire [13]. Thus, for a model to adequately account for suppression-fire interactions, such activities must be modeled over time and interact dynamically with fire behavior.

Models have been built to address some of these important considerations. For example, Fried and Fried [15] developed a simulation algorithm to explicitly account for the interaction between fireline production and fire growth, i.e., that fire growth is hampered by fireline production. Their model has been used in operational programs such as CFES2, a fire suppression budgeting model for California [16]. This model assumes fireline is produced along the edge of the fire, reducing further growth as it is produced. While the model developed by Fried and Fried [15] does account for the interaction between fireline production and fire growth, it is typically implemented in a quasi-spatial manner, where the fire is assumed to take the shape of an ellipse and spreads from a single ignition point on a homogeneous landscape [16].

Other models have been developed that select containment tactics. For example, HomChaudhuri et al. [17] developed a genetic algorithm for placing wildfire suppression on a landscape, using their model to determine the optimal starting and ending points of the suppression resources along with the parameters of the parametric equation that determines the suppression resources’ path. While the fitness of the solution is evaluated under uncertain weather behavior and within the fitness evaluation process the suppression actions may interact with fire to change final fire behavior, only one solution is provided; the solution does not consider that recourse decisions may vary as the fire evolves. Stochastic simulation methods have also been developed to configure and evaluate spatially explicit tactical suppression decisions. Hu and Ntaimo [18] simulated fireline construction for a single fire using stochastic line production parameters. They developed three algorithms for their simulation to model direct attack, parallel attack, and indirect attack. Like HomChaudhuri et al. [17], their model provides a single solution that does not consider multiple future scenarios and possible recourse actions. Alexandridis et al. [19] developed a cellular stochastic model to simulate the effects of air tanker attack. A Poisson distribution is used to determine if an air attack will take place on a cell and the probability that fire will be extinguished in a cell after an air attack takes place. This model examines the effectiveness of air tanker suppression actions, but assumes a predefined set of suppression actions and does not examine how to plan or design such actions. Mees and Strauss [20] incorporated random effects into a mathematical programming model using probabilistic fireline production rates. This model maximizes expected utility, defined as the sum of the probabilities that different sections of line will hold weighted by the relative importance of the sections and subject to resource availability constraints. The suppression actions are predefined to be specific sections of line; the decisions made by the model are which resources to place at each fireline segment. Spatial relationships between the fireline segments are not modeled. All these previous studies model suppression decisions such that they cannot interact dynamically with fire or they cannot be updated over time, thus, they may be sub-optimal decisions. Likewise, none of the previous studies integrate explicitly spatial and temporal stochastic fire behavior with explicitly spatial and temporal endogenous suppression decisions that account for crew movement, crew safety, line production, and line quality. Many other operations research projects have examined optimizing resource assignments but they are not as relevant to our research as the papers we discuss in detail above; we refer readers interested in further exploring this topic to [11,21,22].

A stochastic mixed integer programming (SMIP) model [23] to optimize suppression decisions that dynamically interact with uncertain fire behavior on a single fire was developed by Belval et al. [24]. That model provided a framework for selecting suppression activities that alter resultant fire behavior; first stage decisions were the initial suppression actions and second stage decisions were follow up suppression actions. It included explicit nonanticipativity constraints to ensure suppression decisions that account for uncertainty in weather forecasts and recourse decisions allowed the model to create optimal suppression decisions for each weather scenario. In addition, that model incorporated flexible decision points, which allowed a variety of management styles to be represented. The model presented in Belval et al. [24] integrates suppression decisions using “suppression node placements” which model the timing and placement of suppression actions on the landscape. However, two of the main assumptions underlying the suppression node placement model of suppression are simplistic. First, these suppression actions are modeled assuming all cells on the landscape are associated with a single, constant, fireline production rate, but actual production rates may vary depending on factors such as fire intensities, topography, and fuel type [1,25]. Second, suppression placements themselves are oversimplified. For example, the constraints did not explicitly require fire suppression resource movement to be continuous even though crews, engines, and bulldozers must travel in a continuous fashion (i.e., these resources cannot fly or apparate and travel time between suppression locations are not negligible). While the solutions produced by the model did tend to be continuous, simply because continuous line was required to contain the fire, the model did not include constraints requiring any type of continuity, particularly regarding temporal continuity. To model suppression more realistically, the spatial and temporal restrictions on the fire crews must be modeled with such additional details included. In addition, the suppression nodes do not consider crew safety or line quality, which are integral aspects of fire suppression.

In this paper, a set of constraints is developed to model firefighting activities and control lines that allow for more realistic simulation of crew tactics and safety concerns which are integrated with the previously developed SMIP fire spread model [24]. These constraints are specifically designed for ground-based tactics (i.e., crew or engine activities), particularly targeting initial line construction; aerial resources and “mop-up” (i.e., reducing the probability of fire spread or smoke by extinguishing residual burning material along a previously built control line) are not represented in this model. Based on our knowledge, this is the first time an SMIP model is developed to explicitly address fireline quality, firefighter travel path connectivity, firefighter safety and their interaction with uncertain fire behaviors to provide optimal suppression suggestions for fireline construction. Our results demonstrate the value of modeling additional details of fire suppression using this SMIP framework. The test cases are small to allow this paper to focus on the development and details of the control constraints; future work to expand scenarios, add other objectives and constraints, and gather necessary data is addressed in the discussion.

2. Materials and Methods

In the following section we briefly describe the stochastic fire spread constraints developed by Belval et al. [24] that produces fire behavior and spread predictions within the model. We then present the new suppression constraints. While these line construction constraints may be used for any ground resource (i.e., engines, crews, or bulldozers), we refer to these resources as crews throughout the manuscript as our test cases use line production parameters consistent with a crew’s productivity. Finally, we describe the landscape and parameters used in our test cases.

2.1. Stochastic Mixed Integer Fire Spread Program

The SMIP fire spread model predicts spatially explicit fire behavior on a raster landscape of square cells. Nodes are defined as points placed at the center of each cell. Each cell represents a parcel of land modeled as having homogeneous terrain and fuel type. Over the time frame of an individual wildfire, terrain and fuel type for each cell are treated as static constants; this is consistent with many existing models (e.g., [6,8,26,27,28]). Thus, weather and fire suppression activities are the two variables that may dynamically alter fire behavior in each cell. Fire spreads into nodes from adjacent nodes (see Figure 1a). Fire spread is altered by suppression actions, dynamically changing fire behavior as the timing and direction of spread between cells is affected. These constraints that model fire spread are presented in detail in Belval et al. [24]. Because the constraints developed in this paper rely upon those fire spread constraints, they are reproduced in the Appendix A for the readers’ convenience. However, three of the original fire spread equations from Belval et al. [24] (labeled in that paper as Equations (A2), (A4), and (A16)) were altered to allow both fire occurrence and suppression actions at each node in order to allow for the computation of a safety buffer and to allow for the inclusion of line quality considerations. These revised equations are shown in context in the Appendix A of this paper as Equations (A2), (A4), and (A16), respectively.

The SMIP fire spread model requires a set of probabilistic weather predictions that are structured as a stochastic “weather tree.” An example is shown in Figure 2. We refer to branches on the tree as weather “sub-scenarios”. Each sub-scenario contains a single set of weather parameters for fire spread and a new sub-scenario is created whenever the weather is predicted to change. A sequence of sub-scenarios over time forms a weather stream, which will be referred to as a weather “scenario”. Decision stages are imposed upon each weather tree, which creates a “multi-stage decision tree”. First stage decisions determine initial fire suppression activities. Recourse decisions determine suppression activities at later stages. These recourse decisions are conditioned on the weather and suppression driven outcomes of the preceding stages, providing a dynamic decision framework. Decision point placement is flexible, as discussed in detail in Belval et al. [24]. Decisions at each decision point account for a discrete probability distribution of subsequent weather streams, as implemented through our weather trees.

2.2. Suppression Constraints

Here we present the mathematical formulation of the line construction constraints for the SMIP model. The notation used to present the line construction constraints is listed in

Table 1. The notation used for the indices, sets and parameters in the mathematical formation of the fireline construction constraints. In this paper, lower case Arabic and Greek letters indicate parameters, and capital Greek letters represent sets. An exception to this is “big M”, which is commonly used in if-then logic constraints.

Notation		Definition
Indices
c	=	index for the crew of interest
i	=	index for the node of interest
$j^{\prime }$	=	the node from which a crew enters node i
j	=	the node to which a crew moves to when leaving node i
q	=	index for a weather scenario of interest
m	=	index for the stages that comprise weather scenario q
$q_m$	=	index for stage m from scenario q
Parameters
$tr{t}_{c,i,j}$	=	the travel time required for crew c to travel from node i to node j
$sm$	=	amount of time needed between the fire and the crew per unit intensity if the fire is not safe for direct attack
$a_{c,i}$	=	the first sub-scenario at which crew c can arrive at access point i
${\alpha }_i$	=	the standardized rate at which an average crew can produce fireline in node i (for example, for every 10 min a crew works it can builds 10 ft of line that will holds a fire of 5 BTU/(ft-s))
$t_{q_m}$	=	the length of time stage $q_m$ lasts
Sets
${\mathcal{A}}_c$	=	the set of nodes that can be used as access points by crew c
${\Lambda }_p$	=	the set of sub-scenarios which must be non-anticipative with respect to decision point p

and

Table 2. The notation used for the response and decision variables in the mathematical formation of the fireline construction constraints. In this paper, capital Arabic letters are used to represent decision and response variables. All decision and response variables have an implicit lower bound of zero.

Notation		Definition
Response and Decision Variables
$Y_{i,q}$	=	indicates if suppression holds in node i during scenario q
$P_{c,i}$	=	binary variable indicating if crew c choose to use node i as an access point from which to start
$C_{c,j^{\prime },i,q_m}$	=	indicates if a crew moved from node $j^{\prime }$ to node i during stage m for scenario q
$C_{c,i,q_m}$	=	indicates if a crew was working in i for both stage $m-1$ and m in scenario q
$C{T}_{c,i,q}$	=	time crew c finishes work in node i for scenario q
$W{T}_{c,j^{\prime },i,q_m}$	=	amount of time crew c works on node i (after leaving node $j^{\prime }$) in stage m in scenario q
$W{T}_{c,i,q_m}$	=	amount of time crew c works on node i in stage m in scenario q (used if the crew is in node i during more than one stage)
$W_{i,q}$	=	total effective work on node i done during scenario q
$L{C}_{i,q}$	=	the control line capacity in node i for scenario q
$S{M}_{i,q}$	=	the amount of time required between a crew’s departure from node i and the fire arrival (safety margin) in scenario q
$W{C}_{i,q}$	=	the time at which all crews have completed their work on node i in scenario q

.

2.2.1. Spatial Crew Path Constraints

We assume each crew begins work at a node chosen from a set of predefined “access points” from which crews may arrive at the fire; they then travel from these access points to other nodes on the landscape through neighboring nodes. Both the location of each access point and the earliest time at which each crew can arrive at each access point are pre-identified. Figure 1b shows a visualization of possible crew movements. This model assumes suppression actions are ground-based, so resources must travel in a continuous path (i.e., crews can only move from a node into an adjacent node). Due to size and modeling considerations, this version of the constraints only allows the crews to visit any node once. The equations that govern crews’ spatial movements can be split into two groups: constraints that guide how a crew accesses the landscape and constraints that control how a crew moves and how a crew builds fireline once they are on the landscape. Equations (1)–(5) govern access to the landscape.

$$\sum _{i\in {\mathcal{A}}_c}{P}_{c,i}\le 1\forall c$$

(1)

$$\sum _{j\in {\Omega }_i}{C}_{c,i,j,q_m}+C_{c,i,q_{m+1}}\ge P_{c,i}\forall c,i\in {\mathcal{A}}_c,q,m=a_{c,i}$$

(2)

$$\sum _{k\ge m}\sum _{j\in {\Omega }_i}{C}_{c,i,j,q_k}\ge P_{c,i}\forall c,i\in {\mathcal{A}}_c,q,m=a_{c,i}$$

(3)

$$\sum _{k<m}\sum _{j\in {\Omega }_i}{C}_{c,i,j,q_k}+C_{c,i,q_{k+1}}\le 0\forall c,i\in {\mathcal{A}}_c,q,m=a_{c,i}$$

(4)

$$\sum _{k\ge m}\sum _{j\in {\Omega }_i}{C}_{c,i,j,q_k}\le 1\forall c,i\in {\mathcal{A}}_c,q,m=a_{c,i}$$

(5)

Each crew c may use only one access point $P_{c,i}$ (Equation (1)). If a crew c chooses to use an access point i in stage $q_m$ then Equation (2) forces the crew to either stay at node i for the whole decision stage or leave node i before stage $q_m$ ends; the crew may not leave in a previous stage. Similarly, if the model assigns crew c to access point i, then Equation (3) ensures that crew c can only leave node i once in each scenario q and crew c must leave node i at some point during scenario q. Crew c cannot be at an access point node i or leave node i in any stage before the predefined access point arrival time (Equation (4)). Equation (5) ensures that crew c is only allowed to leave access node i once.

Once a crew leaves an access point, then their spatial behavior is restricted by Equations (6)–(10).

$$P_{c,i}+\sum _{k=1}^{\widetilde{m_q}-1}\sum _{j^{\prime }\in {\Omega }_i}{C}_{c,j^{\prime },i,q_k}\le 1\forall c,i,q$$

(6)

$$C_{c,i,q_m}+\sum _{k=1}^{m-1}\sum _{j\in {\Omega }_i}{C}_{c,i,j,q_{k-1}}\le 1\forall c,i,q,m>1$$

(7)

$$\sum _i{C}_{c,i,q_m}\le 1\forall c,i,q,m>1$$

(8)

$$C_{c,i,q_m+1}\le \sum _{j\in {\Omega }_i}{C}_{c,j^{\prime },i,q_m}+C_{c,i,m}\forall c,i\notin {\mathcal{A}}_c,q,m\le {\tilde{m}}_q$$

(9)

$$C_{c,i,q_m}+\sum _{j^{\prime }\in {\Omega }_i}{C}_{c,j^{\prime },i,q_m}=C_{c,i,q_{m+1}}+\sum _{j\in {\Omega }_i}{C}_{c,i,j,q_m}\forall c,i\notin {\mathcal{A}}_c,q_m,m\le {\tilde{m}}_q$$

(10)

Equation (6) ensures that crew c is only allowed to enter node i once, including using node i as an access point. In addition, once crew c has left node i, the crew cannot be at node i in a future scenario (Equation (7)). If crew c is at node i in both stages $q_m$ and $q_{m+1}$, then Equation (8) forces crew c to be only at node i during the transition between decision stages. Equation (9) allows crew c to be at node i during the transition between stage $q_m$ and stage $q_{m+1}$ only if crew c moved to node i during stage $q_m$ or if crew c started stage $q_m$ at node i. To guarantee that crews travel in a continuous path, if crew c starts stage $q_m$ at node i, then Equation (10) requires that crew c must either leave node i for some adjacent node j during stage $q_m$ or stay at node i until after stage $q_{m+1}$ has started.

Equations (1)–(10) rely upon the crew work time equations (Equations (11)–(14) presented in the next section) to function properly; the timing and ordering set by those equations ensures that the model does not allow crews to work on nodes in stages after the crew has left the node or before the crew has entered the node.

2.2.2. Crew Arrival and Work Times

As crews move from node to node, they may build fireline or simply travel through the node. The crews’ work and travel time is tracked and linked to the decision stage in which the travel or work occurs. The timing of suppression actions is a crucial aspect of the suppression decisions, thus, the suppression constraints include equations that ensure the following temporal restrictions are met: limiting work time completed in each stage to no more than the stage length, calculating the time a crew leaves a node by adding the work time spent on that node to the time the crew entered the node, and connecting the time the crew leaves each node to the correct decision stage. A “work completion time” is designated for each node which, at smallest, must equal the time that the last crew finishes their work on that node. Like control line capacity, work completion time is subject to nonanticipativity constraints ensuring the work completion time occurs prior to fire arrival in each node for all weather scenarios.

$$W{T}_{c,j^{\prime },i,q_m}\le t_{q_m}{C}_{c,j^{\prime },i,q_m}\forall c,i,j^{\prime }\in {\Omega }_i,q,m$$

(11)

$$W{T}_{c,i,q_m}\le t_{q_m}{C}_{c,i,q_m}\forall c,i,q,m$$

(12)

$$W{T}_{c,i,q_m}\le (\sum _{k=1}^m{t}_{q_m}-a_{c,i})P_{c,i}\forall c,i\in {\mathcal{A}}_c,q,m$$

(13)

$$\sum _i\left(W{T}_{c,i,q_m}+\sum _{j\in {\Omega }_i}W{T}_{c,i,j,q_m}\right)\le t_{q_m}\forall c,q,m\in \{1,...,{\tilde{m}}_q-1\}$$

(14)

Equations (11)–(14) limit the work time completed in each stage to no longer than the stage lasts. A crew may spend up to the entire stage working on a node under two circumstances: (1) if they are leaving node $j^{\prime }$ for node i exactly at the start of stage m (Equation (11)) or (2) if they started the stage already at node i (Equation (12) and (13)). However, the total work they do on all nodes in a single stage must be less than or equal to the amount of time the stage lasts (Equation (14)).

$$C{T}_{c,i,q}\ge a_{c,i}^{\prime }{P}_{c,i}+\sum _{k=m}^{{\tilde{m}}_q-1}W{T}_{c,i,q_k}\forall c,i\in {\mathcal{A}}_c,q,m=a_{c,i}$$

(15)

$$\begin{array}{ccc}\hfill C{T}_{c,i,q}& \ge & \left(C{T}_{c,j^{\prime },q}+tr{t}_{c,j^{\prime },i}+\sum _{k=1}^{{\tilde{m}}_q-1}W{T}_{c,j^{\prime },i,q_m}+W{T}_{c,i,q_m}\right)-M(1-\sum _{k=1}^{{\tilde{m}}_q-1}{C}_{c,j^{\prime },i,q_m})\hfill \\ & & \forall c,i\notin {\mathcal{A}}_c,j\in {\Omega }_i,q\hfill \end{array}$$

(16)

Equations (15) and (16) track the time at which each crew leaves each node. A crew c must finish all work (if any) on the access point i before they leave it (Equation (15)). Equation (16) ensures that the time that a crew c can leave any non-access-point node i is determined by the path the crew c took to get to node i and the amount of work the crew did on the node; this equation is only binding when crew c leaves node $j^{\prime }$ for node i and given that the time at which crew c can leave node i is the time that crew c left node $j^{\prime }$ plus any work time and travel time spent on node i.

$$C{T}_{c,i,q}\ge \sum _{k=1}^{m-1}{t}_{q_k}-M\left(1-\sum _{j\in {\Omega }_i}{C}_{c,i,j,q_m}\right)\forall i,j\in {\Omega }_i,q,m\le \tilde{m}$$

(17)

$$C{T}_{c,i,q}\le \sum _{k=1}^m{t}_{q_k}+M\left(1-\sum _{j\in {\Omega }_i}{C}_{c,i,j,q_m}\right)\forall i,j\in {\Omega }_i,q,m\le \tilde{m}$$

(18)

Equations (17) and (18) link the time that the crew completes their work on a node with the correct stage; without these constraints the model could allow crews to work on nodes in stages after the crew has left the node or before the crew gets to the node. These equations ensure that if crew c is ever at node i, the time they leave node i matches the stage at which they leave (Equations (17) and (18)).

2.2.3. Control Line Capacity

The crews’ work time determines the quality of fireline they can put in. However, crew productivity rates are difficult to quantify. Previous research has reported direct and indirect attack line production rates for different types of crews by fuel type (e.g., [25,26,29]), but does not quantify how line construction time may influence line quality, particularly regarding the control of fires with different intensities. In theory, we would expect that the longer a crew works on a section of fireline, the higher the fireline intensity the line created could hold. We define a “control line capacity”, which is determined at each node and is defined as the maximum fireline intensity at which the fireline will hold. In the current formulation of our model the control line capacity at each node is proportional to the amount of time that the crews work on the node. If the final control line capacity at any given node equals or exceeds the fireline intensity when fire arrives at that node, then the suppression effort for that node is sufficient; i.e., the suppression actions at that node prevent the node from spreading fire to any of its neighbors. However, if the fireline intensity is higher than the control line capacity the node will still be able to spread fire to its neighbors. At very high fireline intensities no control line will hold; we do not include an upper bound on intensity at which suppression cannot be sufficient, but it could easily be added to the model. We also require that if any work is put into a node then the control line capacity of that node must be sufficient for all weather scenarios; thus we assume that if a crew puts any work into a node, it is because they want to ensure successful suppression in that node for all predicted future weather scenarios. Control line capacity as modeled in this paper only addresses fire crossing a line via radiant or short-range convective means; spotting, rolling firebrands, and other similar occurrences are not yet considered. Likewise, we do not yet address burnout or backfire operations. The fireline quality equations fall into two groups: equations that relate crew work times to control line capacity and equations that determine if the control line capacity is sufficient for suppression to be successful.

$$W_{i,q}=\sum _c\sum _{k=1}^{{\tilde{m}}_q-1}{l}_{c,i,q_k}(\sum _{j^{\prime }\in {\Omega }_i}W{T}_{c,j^{\prime },i,q_k}+W{T}_{c,i,q_k})\forall i,q$$

(19)

$$L{C}_{i,q}={\alpha }_i{W}_{i,q}$$

(20)

Equations (19) and (20) relate crew work time to final control line capacity. If multiple crews are working on a landscape, multiple crews may end up working on a single node. Since crews may work at different rates, the work time from all crews needs to be combined and translated into a control line capacity. Equation (19) allows us to linearly adjust the work time for different crews if they have differing productivity rates, resulting in a single “effective work time” for all the crews combined. Equation (20) uses the effective work time to calculate the line capacity for the fireline created in cell i for scenario q.

$$L{C}_{i,q}\ge I_{i,q}-M(1-Y_{i,q})\forall i,q$$

(21)

$$Y_{i,q}\ge \frac{1}{M}{W}_{i,q}\forall i,q$$

(22)

Equations (21) and (22) relate the control line capacity at each node to the success of the suppression action based upon the fireline intensity when fire first reaches that node by one of potentially many possible paths. Equation (21) allows suppression to be successful at node i in scenario q only if the control line capacity is greater than the fireline intensity ($I_{i,q}$). Equation (22) is necessary to ensure that if a crew c begins working on node i, then the control line capacity of node i must be sufficient for all weather scenarios.

2.2.4. Safety Constraints

Fireline is created using either “direct” or “indirect” tactics; i.e., crews may directly interact with the flames to put them out or they may create fireline to stop the fire without interacting with the flames [25]. Rather than modeling direct versus indirect attack as a binary choice, the safety constraints in this model determine what size buffer the crews must keep between themselves and the fire based on the predicted fireline intensities at each node. Larger buffer zones indicate that direct attack is considered unsafe. In this model, the safety buffer takes the form of the amount of time between when the crews finish their work on the node and when fire arrives at the node. The safety margin is controlled here by the fireline intensity: the more intense the fire when it arrives at a node the larger the safety margin must be at that node. While the fireline intensity at each node may vary between scenarios, the safety constraints are built such that the safety margin is always responding to the maximum fireline intensity of the scenarios in which the sub-scenario is a part. For example, given the multi-stage decision tree in Figure 2, the safety margins produced at each node for the crews during the second stage of scenarios a and b must reflect the maximum fireline intensity from scenarios a and b because the decision about when the crews must have completed the line is made before the actual fireline intensity is observed. Because Equation (22) requires that all fireline built must have a high enough capacity to hold against the highest resulting intensity, control line capacity can be used in the safety constraints instead of fireline intensity because control line capacity is, at a minimum, the maximum fireline intensity of the node for all scenarios. Using line quality instead of fireline intensity reduces the formulation and negates the need for a nonanticipativity constraint on safety margins. For testing, we assume that the function relating safety margin and control line capacity is linear.

$$W{C}_{i,q}\ge C{T}_{c,i,q}\forall c,i,q\forall i,q$$

(23)

$$S{M}_{i,q}=s{m}_{i}L{C}_{i,q}\forall i,q$$

(24)

$$W{C}_{i,q}+S{M}_{i,q}\le F_{i,q}\forall i,q$$

(25)

Because multiple crews may work on each node, a work completion time is designated for each node ($W{C}_{i,q}$), which, at smallest, must equal the time that the last crew c finishes their work on node i in scenario q (Equation (23)). For testing, we assume that the function relating safety margin and control line capacity is linear (Equation (24)). Equation (25) ensures that crews finish their work within the safety margin required.

2.2.5. Nonanticipativity and Decision Timing

A key feature of SMIP models is nonanticipativity regarding the conditions following when decisions are made [23]. Because uncertainty about how the weather will behave, in general, is unresolved at each decision point, the prescribed work plans for the crews must be feasible for all possible future weather streams, particularly regarding line quality and safety. At each decision point this model has explicit nonanticipativity constraints to ensure that the work accomplished and travel path taken by each crew is consistent across all future weather sub-scenarios that occur until the end of the stage. In this model, nonanticipativity ensures that the crews will keep the prescribed safety buffer between themselves and the fire regardless of which weather scenario occurs and ensures that optimal decisions are made regarding other priorities such as minimizing fire size. Nonanticipativity can produce assignments that anticipate the worst-case scenario but can still take advantage of opportunities provided by better scenarios. Nonanticipativity could be achieved implicitly by choosing to only create one set of decision variables for each set of non-anticipative sub-scenarios at each stage, but we include the explicit version in this formulation for clarity.

$$W{T}_{c,i,j,q_m}=W{T}_{c,i,j,q_k}\forall c,i,j,q_{m}and{q}_k\in {\Lambda }_p,p$$

(26)

$$W{T}_{c,i,q_m}=W{T}_{c,i,q_k}\forall c,i,j,q_{m}and{q}_k\in {\Lambda }_p,p$$

(27)

$$C_{c,i,j,q_m}=C_{c,i,j,q_k}\forall c,i,j,q_{m}and{q}_k\in {\Lambda }_p,p$$

(28)

$$C_{c,i,q_m}=C_{c,i,q_k}\forall c,i,j,q_{m}and{q}_k\in {\Lambda }_p,p$$

(29)

Equations (26) and (27) ensure that the time worked by crew c is non-anticipative. Equations (28) and (29) ensure that the crew path decisions are non-anticipative.

2.2.6. Objective Function

The final crucial equation in an SMIP is the objective function, which drives the model to produce solutions consistent with the manager’s priorities. The suppression assignments are strongly influenced by the objective function. In our test cases, to ensure the efficient use of resources with the smallest expected fire footprint, we added the total expected area burned to the total expected distance the crew travels with travel weighted lightly. If crews are scarce and their line production rates are limiting, the model is likely to use resources efficiently to minimize the expected area burned, but minimizing travel distance helps ensure that the solutions with shorter line construction requirements are optimal when resources are not scarce. The penalty coefficient on travel distance could be increased if crew travel distance was an important factor for the fire manager. In addition, other factors such as costs, work time, and values at risk could be added to this objective function. This paper specifically presents and tests the control constraints; we leave identifying and testing objectives for future research.

Let $L{L}_{c,q}$ be the distance traveled by crew c in scenario q.

$$L{L}_{c,q}=\sum _i\sum _{j\in {\Omega }_i}{d}_{i,j}{C}_{c,j^{\prime },i,q}\forall c,q$$

(30)

Equation (30) is a bookkeeping constraint that tracks the total distance traveled by each crew and $L{L}_{c,q}$ can be included in the objective function.

$$MinZ=\sum _q\left(\sum _{k\in {\Phi }_q}\sum _i{D}_{i,q_m}+\sum _{c}0.0001L{L}_{c,q}\right)$$

(31)

Equation (31) reflects minimizing expected area burned with the least distance traveled. Because crew work time and completion times are not in this objective function there may be slack in the crew and node work completion times. However, post-solution processing can easily remove such slack with no loss of optimality by recalculating completion times based on the amount of time worked.

2.3. Test Case Design and Parameterization

Test cases presented in this paper use the landscape shown in Figure 3 using the parameters outlined in

Table 3. The range of landscape values for the 11 × 12 landscape used in the test cases.

Characteristic	Value(s) Used
Cell Size	30 m × 30 m
Fuel Model	102, 122, 188
Elevation	1357–1397 m
Slope	0–19%
Aspect	generally northern
Canopy Cover	varies with fuel type
Fuel Moisture
(1 h–10 h–100 h–live)	11–20–26–100%
Southerly wind direction	180 degrees
Southwesterly wind direction	270 degrees
Westerly wind direction	225 degrees
Windspeed	3.58 m/s

; this landscape is modeled on a location in the Black Hills of South Dakota with spatial information from Landfire (LANDFIRE: Landscape (LCP) layer updated June 2013). This landscape includes three fuel types: grass, grass-shrub, and timber litter. Line production rates vary by fuel type. The fire behavior on this landscape, with weather patterns as indicated in Table 3 and Figure 2, consist of fireline intensities corresponding to flame lengths from about one to three and a half meters (approximately three to 12 feet). We designated 13 cells to be non-flammable in this landscape to demonstrate how the model functions; these are indicated in Figure 3 and the model is parameterized accordingly as non-flammable cells may not spread fire to any of their neighbors.

For simplicity, in these test cases we employ a single crew, although the formulation accommodates multiple resources. Because travel time is associated with each cell a crew moves through, the “effective line production rate” can be defined as the total amount of time a crew spends in a cell (i.e., work time plus travel time) to create a line with a specified control capacity. We constrained effective line production rates to be within the confidence intervals produced by Broyles [25] using both the line production parameter and the travel time parameter. Using the travel time parameter allowed us to adjust the effective line production rates more flexibly. The line production parameters used are presented in

Table 4. The line production, travel time, and safety margin parameters used in the test cases.

		Fuel Type
	Units	102	122	188	Non-Flammable
Line production	(BTU/ft-sec)(ft/min)	15,000	5000	14,000	NA
Travel time	min/ft	0.042	0.037	0.075	0.0167
Effective line production rate at:
0.91 m (3 ft) flame lengths	ft/min	21.852	20.427	12.596	NA
2.13 m (7 ft) flame lengths	ft/min	14.832	8.777	9.747	NA
3.35 m (11 ft) flame lengths	ft/min	9.062	4.120	6.730	NA
Safety margin:
Baseline	min/(BTU/ft-sec)	0.002	0.002	0.002	0.002
Higher	min/(BTU/ft-sec)	0.004	0.004	0.004	0.004

, along with examples of how these parameters translate into effective line production rates for three example fireline intensities. Crews were required to spend time walking through nodes even if they did not choose to construct line in those nodes, including non-flammable nodes in which travel time was the fastest.

The multi-stage decision tree used in all our test cases is shown in Figure 2. For simplicity, because this paper primarily examines the fire suppression constraints rather than fire spread, we placed the recourse decision point at a likely weather change; this occurs 30 min after the fire starts. More complex decision trees are demonstrated in Belval et al. [24]. While the decision trees in our test cases are two stages, the constraints have been designed to adapt to as many decision stages as needed. The initial decision on where to send fire suppression resources is made at the time of ignition. We predefined two possible access points on the landscape. For simplicity, we assumed crews can arrive at each access point at $t=0$.

We present three test cases in this paper. The first and second test cases, which we refer to as the “standard safety margin test case” and the “reduced decision space test case” respectively, use the same line production parameters, as shown in Table 4. The third test case, which we refer to as the “higher safety margin test case,” uses a higher safety margin than the first two test cases. We used the reduced decision space test case to explore ways to simplify the problem if candidate fire lines can be pre-identified. In this case study, we simplify the decisions by requiring the model to choose from groups of pre-selected nodes. Each group of nodes represents a possible fire containment line. We predefined eight containment lines (east to west rows); any two of the eight possible firelines were allowed to be selected. Keeping all the test cases simplistic allowed us to explore the results in detail, including looking at individual suppression node selections to describe strengths and weaknesses of this approach to determining suppression assignments. Test cases were parameterized using FlamMap to get fire behavior parameters (see [24] for further detail). The SMIP was built using Visual Studio 2010 and solved by calling the CPLEX 12.7.0.0 optimization library [30], a state-of-the-art software program used to solve optimization programs to optimiality. The program was run on an HP xw8600 Workstation with 32 GB of RAM.

3. Results

The results from model runs of the standard safety margin test case, the reduced decision space test case, and the higher safety margin test case are shown in Figure 4, Figure 5 and Figure 6, respectively. Columns a, b, and c in these figures correspond to the results from scenarios a, b, and c, respectively. Each of these figures shows the stage in which fire arrived at each node, the possible access points, the ignition point, non-flammable nodes, and the optimal crew path by stage as determined by the model.

In all three test cases the crews travel quickly through the non-flammable cells on the western edge of the ignition (C4, R4-8) and spend the majority of their time working at the nodes on the north, east and south edges of the fire. For each test case, the suppression actions are the same for the first 30 min in all scenarios, as required by first stage nonanticipativity constraints. After 30 minutes, the first and second scenarios still have identical suppression actions as required by second stage nonanticipativity constraints while the suppression actions in the third scenario differ.

In all of the scenarios for the standard safety margin and higher safety margin test cases (Figure 4 and Figure 6) the crews access but do not put any work into cell (C9, R6); they only travel through it. This is because the model assumes that putting suppression in a cell does not keep it from burning; rather, it prevents the cell from spreading fire to other cells. Thus, in all three scenarios, cells (C9, R7-9) and (C9, R3-5) are suppressed to keep fire from spreading into (C10, R8) and (C10, R4) respectively, but putting suppression effort in (C9, R6) would have no effect on the number of cells burned.

The results of the reduced decision space test case (Figure 5) compared with the results of the standard safety margin test case demonstrate some effects of using a reduced decision space. Because the suppression lines have been pre-identified, the crew path is more straightforward (i.e., straight lines rather than winding around cells with earlier fire arrival times). For example, the suppression path along the south flank of the fire runs straight along row 9 in the reduced decision test case, while in the standard safety margin case the path goes from (R8, C8) to (R9, C8). In addition, the suppression path is forced to follow the non-flammable cells more closely, resulting in less work for the crew, although the travel distance is slightly longer. For example, in Figure 4, the optimal solution places suppression activities in three cells (C9, R3-5) to keep one cell from burning. Placing suppression effort in only two cells (C10, R4) and (C9, R3) instead would result in nearly the same fire footprint but with less effort from the crew. This is evident in the reduced decision space test case (Figure 5). The crew travels an expected 3% further (18.3 meters), however, requires less work time to contain the fire. Only 2.67 extra cells are expected to burn (an 8% increase in expected burned area). The pre-identified paths such as those used in the reduced decision space test case may be appealing to managers as they create fire suppression plans and managers may decide the slightly larger expected burned area is worth the tradeoff of less suppression work along pre-identified control lines.

Because of the integer nature of the model and the specific test cases we chose, examples of binding completion times are few, i.e., there are no cells where the work completion time is exactly equal to the fire arrival time minus the safety buffer. However, there are numerous examples of cells that cannot have suppression placed in them due to work completion time and safety buffer requirements. For example, in the standard safety margin test case (Figure 4), scenarios a and b, the model places suppression in cells (C5-6, R8), which prevents cell (C5, R9) from burning. However, the crew must then avoid cells (C7-8, R8) because they would not arrive at these cells before fire has arrived, which forces the crews to move around these cells, taking their path through (C6-8, R9). Because these actions occur in the second stage of the model, scenario c is not bound by nonanticipativity to produce the same crew actions as scenarios a and b, and because the fire arrives later at (C7-8, R8) in scenario c, the solution for scenario c is to place line in cells (C7-8, R8), reducing the burned area by four cells as compared with scenarios a and b. These differing crew paths also demonstrate another interesting aspect of the model: it can deliberately add slack into the work time in order to delay the completion of work such that the next node in a path is no longer bound by the nonanticipativity constraints. When the slack is removed from the work completion times, the crew can finish their work at cell (C6, R8) by 29 min. However, the model chose a work completion time of exactly 30 min. Although this difference of less than a minute may seem minor, the model chose to have the crew pause here to transition to the second decision stage, which is not constrained by the first stage nonanticipativity constraints. After 30 min has passed, the paths and work times of scenario c may differ from those of scenarios a and b, allowing the crew to save four extra cells in scenario c. In reality, the crews could certainly see if the fire had reached a cell before they got there, and it would not be difficult to decide whether or not to go around. The model is planning crew work ahead of time, and thus waits until the uncertainty is resolved to make a decision about where the crew will go in the second stage.

In our test cases we identified one specific example of suppression actions affecting fire behavior. In scenario c, for all test cases, fire arrives in cell (C5, R3) in the second stage. However, when the model is run with no suppression, fire arrives in cell (C5, R3) in the first stage. In the no suppression test case, fire spreads from cell (C6, R3) into (C5, R3). Because suppression is placed in (C6, R3) in each of the test cases with suppression, fire can no longer spread from (C6,R3) to (C5, R3), forcing fire along a slower spread path. This delays fire arrival time to (C5, R3) from the first stage to the second stage. Interestingly, it also increases the fireline intensity from 398 BTU (ft-s)${}^{-1}$ to 423 BTU (ft-s)${}^{-1}$. While this does not substantially affect the crew paths or work times in these test cases, modeling such interactions between fire and suppression may affect the feasibility of fire suppression tactics in other cases.

The only difference in parameters between the models used to produce Figure 4 and Figure 6 is a higher safety margin parameter was used for Figure 6 (see Table 4). The higher safety margin parameter results in some interesting differences between solutions. Because of the higher safety margin parameter, the crew can no longer make it out of cell (C6, R8) in time in scenarios a and b, thus the crew path changes such that the crew no longer travels or works in (C6, R8). Similarly, because the crew cannot be in cell (C6, R8) in scenarios a and b, the crew cannot arrive in time to suppress fire in cell (C7, R8) in scenario c. Therefore, the model delays the crew at cell (C4, R5) so that it can make decisions for subsequent suppression without being bound by the nonanticipativity constraints. Because we know from the results in the standard safety margin test case (Figure 4) that the crew could have finished that work much sooner, we observe that there is enough slack in the work time and crew arrival time constraints to allow the model to delay at cell (C4, R5) even though the crew path would have allowed the delay to be as late as at (C4, R7); such solutions are alternative optima.

Finding an initial feasible solution for CPLEX can be challenging with this model. To get a feasible solution quickly, we first reduced the number of cells in which the crews could work, giving the crews only one option for a path around the fire. This reduced problem always solved within one minute of run time, providing us with an MIP start. When solving the full problem with the pre-identified MIP start, CPLEX typically found the optimal solution within ten minutes of run time. However, CPLEX often still reported a large MIP gap (anywhere from 30% to 70%) even after the optimal solution was initially found. For the results presented in this paper we allowed CPLEX to run until optimality was established. On a desktop computer with 32GB of RAM, it sometimes took days to reduce the MIP gap; in some cases (for results not presented in this paper) the gap could not be eliminated prior to the computer running out of memory.

4. Discussion

The suppression constraints presented in this paper incorporate detailed suppression considerations for ground-based firefighting resources combined with stochastic fire behavior to create a framework from which fire suppression decisions can be modeled. Spatial restrictions requiring continuous crew movements were enforced as were safety restrictions for crews. Fireline quality was modeled using control line capacity defined as the maximum fireline intensity at which the fireline will hold. The solutions to the model provide a map of the optimal path for each crew and determine the amount of work that needs to be done on each node. These constraints provide useful information to a manager.

In practice, a manager could pre-identify areas of the landscape that are of particular importance to protect; those areas could be heavily weighted in the objective function to encourage a solution that protects those areas. The solution presented by the model will provide a decision maker with a good sense for safe, feasible places to put fireline, even given variable future weather scenarios. If the prioritized areas remain unprotected by the solution the manager might re-examine why they are unprotected (i.e., not enough resources, the line will not hold in all scenarios, safety concerns). Then the solution may be adjusted by the manager to reflect any concerns that the model missed. Using this model or a similar one would provide a risk management-based process to help determine resource assignments. Additional research to investigate fire manager risk preferences and practices regarding risk management would be necessary. Current research indicates managers do explicitly consider expected and worst-case fire behavior [13,14], but very little work has been done to qualify, quantify or compare how this plays into the managers’ decision making process in practice.

This suppression model could be improved to better represent reality. For example, if fireline does not stop a fire, it may still slow the fire down. A delay could be incorporated when fire spreads across a fireline or retardant. In the results presented here, costs of line construction are not considered. However, explicit costs could be added; both the fixed cost associated with dispatching a crew to the fire and the variable costs of the work the crew produces could be added to the model. Some assumptions made to formulate our current constraints might also be relaxed. For example, one assumption integral to the spatial crew constraints is that each crew is only allowed at each node once. This model could be modified to include a second arrival at each node. Adding a second arrival would give crews more flexibility, especially in their recourse decisions, but it would increase model size and complexity. While the constraints presented in this paper are designed to examine crew line building tactics, they are not yet suited to examine burnout operations or aerial suppression, both of which are important fire suppression tactics. Similar constraints might be built for such tactics to integrate them into this SMIP framework.

An important parameter in this model is the fireline production rate. While we could tune our effective production rates to be consistent with Broyles [25], no studies have quantified the relationship between line production time and fireline capacity. Broyles [25] directly observed fire crews to obtain new estimates of fireline production rates; that study provided fireline production rates for nine of the 13 fuel models [31] for both direct attack and indirect attack along with upper and lower bounds on the rates. Other research to quantify fireline productions rates includes Fried and Gilless [26] and Hirsch et al. [29], who used expert opinion surveys to determine fireline production rates. Recently, Holmes and Calkin [32] attempted to quantify econometric relationships between fireline production rates and the level of suppression input using data gathered from large wildland fires in the US in 2008. While these are important studies that can help parameterize fire suppression models, they do not examine the spatially explicit interactions between fireline capacity and fireline production time.

Creating realistic, appropriately sized weather trees is another challenge. Weather trees reflecting a wide variety of weather scenarios will make the program quite large and may cause solution algorithm difficulties. Creating a smaller weather tree with fewer representative scenarios will keep the size of the program smaller, but will require using advanced statistical techniques to cluster the weather data appropriately. This task will be crucial to providing the program with realistic fire behavior parameters and will need to include sensitivity testing and validation.

Another important avenue of future work is to examine different fire suppression objectives. In our test cases, we employed a single crew and chose to minimize area burned and distance the crew traveled. However, these two performance measures may not always reflect incident management objectives. Work effort, work time, fire containment time, cost or other measures may better represent objectives for the crews. Minimizing line capacity created could provide an incentive to put work in cells with expected low fireline intensity, which is where fireline is most likely to hold. In some cases, fire in some cells may be deemed beneficial. Belval et al. [33] shows an example of including beneficial fire in this model framework. Adding crew work time or another measure of crew effort might also result in a balance between suppression and final fire footprint that is preferred by the fire manager; this could reduce the number of situations where a large amount of work is done to save a single cell (for example, the fireline in Figure 4, cells (C9, R3-5)). In addition, adding fixed or variable costs to the model through the objective function could add value to the solutions provided by the model. Given multiple objectives, analyses using tools such as multidimensional Pareto curves could help managers identify trade-offs associated with fire suppression decisions. More complex objective functions and weather trees would also likely lead to further sensitivity and persistence analyses.

Because finding an initial feasible solution was challenging and the solution time could be quite long, further work on solution speed would be crucial prior to implementation. Future work might include developing pre-processing or heuristic algorithms to provide the optimal solutions faster, or might use stopping criteria other than the MIP gap.

Given all the future work discussed above, this model requires substantial work to be ready for managers to use operationally. However, simplifying the problem using predefined potential operational delineations (PODs) presented in [34] could dramatically simplify the problem. Thus, managers or analysts could examine the landscape to identify reasonable containment line locations prior to determining assignments. Using such a framework of pre-identified lines would allow for faster solving times and more realistic containment lines. This would produce a model similar to [20,34], but would include detailed crew considerations that are neglected in those papers.

5. Conclusions

The model presented in this paper provides the framework for fire spread and realistic suppression actions that interact dynamically in a stochastic integer programming framework. The model incorporates spatial constraints, safety constraints, line production and quality concerns with stochastic fire spread predictions. Our test results show that it is feasible to incorporate nonanticipativity constraints in the model to produce solutions that are both efficient and robust to weather uncertainties. Suppression suggestions provided by the model solution are reasonable and support modeling fire suppression in a stochastic decision environment. While further work will be required to produce decision support on a fire, this model provides a basis upon which such a support system might be built.