M.Sc Thesis
M.Sc Student Shukrun Ilan Predictive Model of Wildland Fire for Managing Rescue Resources in Changing Conditions Department of Industrial Engineering and Management Professor Shlomo Bekhor

Abstract

This study addresses the joint problem of finding (1) the best cutline(s) from a set of possible cutlines to which firefighting resources will be allocated and (2) the optimal allocation of firefighting resources to the chosen cutline(s). A cutline is defined as a physical separation of a moving fire from the fuel ahead of it with a line that has been cleared down to the earth.

The fire spread is modeled in a similar fashion to other studies in fire propagation, by modeling a stochastic process of a fire on a grid of spatial locations. The cutline is then modeled as a contour around the fire. The first problem to solve is to find the best position of the cutline, assuming that the fire spreads over time and the direction and rate of spread are known only stochastically. The second problem is to find the best allocation of the fire resources for this cutline. Few models in the literature consider the more general case of both fire propagation and resource allocation, and these models introduce simple restrictive assumptions to model the cutline over a plane.

This thesis accounts for multiple fire sources and therefore the possibility of multiple cutlines. The complexity of the problem increases rapidly with the number of possible cutlines and resources. This problem is shown to be NP-hard, and the thesis develops a heuristic to overcome issues pertaining to an exponentially growing number of feasible solutions with increasing problem size. The heuristic can be used to solve large problem instances arising in the real-world.

The heuristic is based on a two-step approach in which a tree is constructed that represents the feasible cutlines at a given time. In the first step, the resource allocation problem is solved for a given set of of feasible cutlines at a given point in time. This problem is a type of generalized assignment problem. The second step exploits the tree characterization that employs a reduced number of possible cutline combinations. Solutions are guaranteed to meet resource limitations.