In order to respond the question “Where to locate fuel breaks?”, a peculiar location model is presented involving stochastic mixed integer nonlinear optimization, Bayesian networks and directional statistic inference. From a first simple approximation to the large model, will be shown what motivates follow models and its complexity incorporated. Also, a case study with real data about Corsica region is presented.
2.1
The main idea is to split the region we want to consider in homogeneous areas, and define the connectivity between those areas with the probability of the fire to pass from one to other. With this idea in mind, the first problem is how to compute the probability of fire in a node known ignition probabilities and spread probabilities.
Given a network (N, A) with
N = {n1, . . . , nm}
A ⊂ N × N being N the set of all nodes representing homogeneous areas of the land and A the set of directed edges connecting N . Also we denote as aij = (ni, nj). The simplest way to compute the probability of fire in node ni (fi) is assuming independence on those events, this is: 1 − f1 = (1 − ig1) (1 − f2 · a21) . . . (1 − fm−1 · am−1,1) 1 − f2 = (1 − f1 · a12) (1 − ig2) . . . (1 − fm−1 · am−1,2)
... ... ... ... ... 1 − fm−1 = (1 − f1 · a1m−1) (1 − f2 · a2m−1) . . . (1 − igm−1) 1 − fm = (1 − f1 · a1m) (1 − f2 · a2m) . . . (1 − fm−1 · am−1m) (1 − fm · am1) (1 − fm · am2) . .
. (1 − fm · amm−1) (1 − igm) Being fi the probability of fire in node ni, aij the probability of spread between node ni and node nj and igi the probability of ignition in node ni.
Note 1. In order to facilitate the reading, we will use an abuse of notation. For example aij is defined as an arch of network (N, A), but in the previous system is used as a number (probability). Also we will see aij as an event (fire spread). In general, events and them probabilities are represented with same symbols, the context will give as the meaning in every case.
With this formulation we can solve the problem to compute the probability of fire in a node with a nonlinear model (NLP). Adding binary variables, the model is transformed into a decision model.
m min z = fi · vi
i=1 s.a
m 1 − fi = (1 − igi) · (1 − fj · aij · xij) for i = 1, . . . , m j=1 j∕=i (1) m xij · cij ≤ B i,j=1 i∕=j fi ∈ [0, 1], xij ∈ {0, 1}
Now suppose a12 = a21 = 0.8, ig1 = 0.1 and ig2 = 0. The solution of the system (1) minimize expected loss cost, being vi an estimation of the losses if ni burns. Also, xij represents the decision of build a FSZ in arch aij and cij costs of locate a FSZ there. Locations of xij must be bounded by a budget B.
In the case of a graph with cycles this approximation can be far from reality. Let us see an explanatory example.
Example 1. Consider the simple graph
G = (N = {n1, n2},
A = {a12 = (n1, n2), a21 = (n2, n1)}) n1
n2 a12 a21 1 − f1 = (1 − ig1) · (1 − f2 · a21) 1 − f2 = (1 − ig2) · (1 − f1 · a12) In this case it’s easy to see this result is far from the correct solution. Note that the probability of the region represented by G having a fire is 0.1.
Even more, if we consider the definition of event there is a fire in node ni as follows f1 = ig1 ∪ (f2 ∩ a21) f2 = (f1 ∩ a12) ∪ ig2 (2) i.e. fi burs if there is an ignition there or if its neighbor burns and fire can pass from it to fi.
The equation Boolean system doesn’t have unique solution, see [Levchenkov, 2000]. This is, there a couple of sets fi∗ satisfying (2). 2.2
One of the main problems is the existence of loops in G. In order to eliminate loops on the model we can consider wind scenarios. For every scenario the graph Gs to be optimize must be an acyclic graph.
Let’s suppose there are four relevant types of wind in region: S = {n, s, e, w} and for every wind Gs is acyclic. Then the Stochastic optimization model based on (1) would be m min z = fis · vi
i=1 s.a
m 1 − fis = (1 − igi) · 1 − fjs · aij · xij for s∈{n,s,e,w}
s for i=1,...,m j=1 j∕=i m xij · cij ≤ B i,j=1 i∕=j fis ∈ [0, 1], xij ∈ {0, 1} (3) Using meteorological data of the region, and fitting wind direction data on a density function, like in [Leguey et al., 2016], it is possible to provide a couple of wind scenarios, and provide a solution for the problem avoiding loop issues. The scenario are based on risky days, those days were humidity, temperature and wind velocity are favorable for fire appearance and propagation.
Even without loops, the independence assumption is too hard. It can be proved that random variable F = {f1, . . . , fm} is a Bayesian network. Using exact or approximation algorithms, it is possible to improve model formulation (3), this methodology is showed at [Cheng and Hadjisophocleous, 2009]. 3
Keeping the mind between the mathematical model and the real problem can be an effort, however, focusing only on one, the result could be useless. On one hand, this work faces several mathematical challenges. On the other hand, even being able to compute an exact solution for the complex model, it doesn’t have sense if the parameters are not realistic.
Input parameters, ignition probabilities and spread probabilities, are based on historical fire database from Corsica firefighters, and meteorological information. In future works, it is planned to use, topography and vegetation data as well as expert knowledge.
Finally, a sensitive analysis is required to claim imprecisions on the input data doesn’t change a lot optimize location.