# A Stochastic Integer Programming Model for Minimizing Cost in the Use of Rain Water Collectors for Firefighting

Authors: Luis A. Rivera-Morales; Neale R. Smith; Mario G. Manzano; David Garza-Ramírez
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

In this paper we propose a stochastic integer programming optimization model to determine the optimal location and number of rain water collectors (RWCs) for forest firefighting. The objective is to minimize expected total cost to control forest fires. The model is tested using a real case and several additional realistic scenarios. The impact on the solution of varying the limit on the number of RWCs, the RWC water capacity, the aircraft capacity, the water demands, and the aircraft operating cost is explored. Some observations are that the objective value improves with larger RWCs and with the use of aircraft with greater capacity.


---

## Body

## 1. Introduction

Currently, many forested areas are being destroyed due to an inefficient system for controlling fires. The problem is due to the absence of nearby water resources, the low availability of aircraft to transport water, and poor logistics. Additionally, because of the growth of urban municipalities, fires occur near populated municipalities. According to the Earth Policy Institute [1], as of November 2009 between 75 and 820 million hectares of land are lost to fire each year worldwide.The magnitude, speed, and difficulty to control fires cause loss of natural and economic resources. In Mexico, around 7,000 forest fires burned more than 340,000 hectares in 2012 and 413,216 hectares in 2013, according to the report of the National Forestry Commission of Mexico [2, 3]. In the state of Nuevo Leon, Mexico, every year large areas of vegetation are affected, damaging soil, wildlife, livestock, agriculture, hydrology, air, and scenic value (280 hectares in 2012, and 583 hectares in 2013, according to CONAFOR [2, 3]). The most affected areas are the pine-oak forests and piedmont shrub lands are located along the range mountain called Sierra Madre Oriental, one of the main forested areas at country level. Although Nuevo Leon was part of the Ten Mexican States having lowest burned surface in 2013, the problem is the cumulative effects that recurrent fires make to the matrix of soil, vegetation, water, and wildlife. The fire season extends from January to August with the months of highest incidence being March and April. Both the government and the local people traditionally cope with the forest fires with reactive measures, facing the problem with the available resources they have at the time that fire events come out. Forest fires are commonly suppressed through ground and aerial means. In the latter case airborne crafts, helicopters, take water from nearby localities, which do not always have enough water sources, nor are located close enough to the problem. This way to fight forest fires requires improvement for better efficiency. For this reason, it is extremely important to create and develop efficient strategies to control forest fires effectively and minimize aftermaths.The deployment of firefighters, pumper trucks, light vehicles, open firewall machines, and gondolas to transport bulldozers all contribute to the cost of extinguishing a forest fire. The list of human and material resources that can be mobilized to a forest fire is long and varied. A light vehicle used to combat fire costs approximately 288 euros an hour as discussed by Cáceres [4]. Additionally, Cáceres [4] calculated that sixty minutes of flight for a helicopter with more than 1,500 liters water discharge capacity exceeds 3,300 euros. Due to the magnitude of the potential ecosystem damage and the high cost of controlling fires, it is crucial to optimize the logistics of firefighting.Before a facility can be constructed, quality sites must be identified and proper facility capacity specifications must be determined. Facilities are expected to operate for prolonged times; therefore, defining locations for new facilities is an important strategic challenge as discussed by Weber and Friedrich [5]. The study of location theory models began when Weber and Friedrich [5] considered how to position a single warehouse so as to minimize the expected total distance between it and several customers. After this early exploration, the literature on location theory models attracted vast interest in operations research. Many location theory models with different objective functions have been formulated to better represent specific situations such as minimization of logistic costs, responsetime, or economic cost.Since the early 1960s facility location problems are often treated as minimization models for logistics costs. For instance, Hakimi [6] considered the problem of locating one or more facilities (switching centers) on a communication network to minimize expected total distance between customers and facilities. Other authors discussed the extensions to the minimization model for distance traveled represent situations such as deciding the placement of factories, warehouses, fire stations, and hospitals [7–10]. The opening of a new facility is typically a costly, time-sensitive project.On the other hand, research in the area of response-time minimization has gained importance in a market characterized by demanding customers and rigid competition among firms. Organizations often explore opportunities for customer satisfaction through response time minimization as a competitive strategy, which is evident in initiatives such as the lean philosophy as exposed by Womack and Jones [11], just in time presented by Monden [12], quick response by Lowson et al. [13], and time based competition by Stalk and Hout [14].As mentioned above, several different objective functions have been formulated to make location theory models tractable in numerous applications. Unfortunately, most problems are classified as NP hard; thus, the resulting models are exceptionally difficult to solve optimality. Moreover, most problems require integer programming formulations. Due to the complex formulations, computational requirements are elevated.As noted by Averbakh and Berman [15], the problem of input data uncertainty is addressed using sensitivity analysis. Specifically, as described by Labbe´ et al. [16], such research attempts to quantify the effect of changing a parameter on the optimal value of the objective function. These results help to evaluate the robustness of a solution after a model is solved. To validate the complexity and uncertainty intrinsic in real world problem instances it is necessary to employ models based on stochastic programming and scenario planning approaches. Stochastic programming models are often used to address ecological and environmental issues.Several types of water sources, such as hydrants in urban areas and lakes in rural areas, are used to control fires. Even nonconventional sources, such as swimming pools, are used in rare cases. In addition to these water resources, Garza-Ramirez [17] documents the use of rain water collectors (RWCs) as sources of water. These systems consist of installing or adapting physical structures to collect and store rainfall water appropriately to meet the demand for a particular use. According to Velasco Molina [18] construction costs for RWCs vary from $47,000 to $120,000 US dollars, which depends on the material construction and water storage capacity of the collectors.RWCs store rainwater for a specific use before it reaches the underground aquifers. Uses include water for gardens, livestock, irrigation, and even for human consumption. In this paper, the focus is on RWCs, which can be built to satisfy human water demand and also to serve as water sources for supplying firefighting helicopters. According to the report of the United States Environmental Protection Agency (EPA) [19] RWCs could serve as a primary method for rainwater harvesting as the western regions of the United States struggle to meet the water demands of their burgeoning populations. Additionally, since rain is a renewable resource at acceptable volumes despite climate change forecasts, RWCs operate at low cost. An example of a rain water collector is shown in Figure 1.Figure 1
Ground-level rain water collector (RWC) design. Source: Water and Life Program, Tecnológico de Monterrey, Mexico.Giroz and Julio [20] explain that success in combating fires depends on timely detection and rapid arrival of firefighting units. Aerial firefighting is a very common practice to fight forest fires. It involves the use of helicopters or airplanes to transport water from sources located at different sites. There are several reasons why helicopters are used for firefighting. These reasons include quick arrival, effective access, and simple transportation of firefighting chemicals as described by Villagrán [21]. The Ministerio de Hacienda y Administraciones Publicas [22] states that the most effective method to control large forest fires is by using aircrafts. There are many suitable aircrafts available, and their capacity is related to the time to control a fire because it determines how much water can be transported in a single trip. Aerial firefighting was first introduced in California in 1946. Amigo [23] discussed that the aircrafts used at the time were small, with a maximum capacity of 130 to 230 liters. According to Villagrán [21], during the 1980s, the capacity of helicopters increased; consequently, combating fires became more efficient. Nowadays, a common helicopter used to control fires is the Sokol/Bell 429, which can transport up to 1,500 liters in a single trip as approximated by the Ministerio de Agricultura, Alimentacion y Medio Ambiente [22]. With this, municipalities and regions prone to fires have benefited. In this paper, a municipality is defined as a population center and the surrounding geographical area, similar to a county in the US. A region is defined as a set of municipalities. This could be the totality of or part of the territory of a state in most cases.Different approaches to improve wildfire containment have been attempted. Many models that address aircraft routing for firefighting have been developed. In 1980, Paredes [24] proposed a model to optimize the quantity of aircraft units to be used based on fire size. Echeverría [25] solved a three-stage optimization problem for location of ground combat brigades. His model uses a network algorithm to combine arrival time and protection priority, allowing a value to be assigned to each coverage alternative. Next, he analyzed every combination of number of brigades and position to satisfy the combat of fires. In addition, his model proposed different locations for the brigades in order to maximize coverage. Pedernera et al. [26] proposed a localization method for terrestrial units. His model uses geographic information system (GIS) algorithms to calculate coverage and the number of units is optimized by an additive method.In this paper, we present a stochastic integer programming model to find the optimal number of RWCs to be constructed and their locations in order to minimize the expected cost to construct RWCs and to control fires. The costs considered are construction cost for RWCs, cost for ecosystem damage, and logistic costs. The model was applied to the state of Nuevo Leon, Mexico. Municipalities (customers) require water sources (facilities) to meet demand (quantity of water to control the fires). To date, no stochastic models found in the literature consider cost minimization for the use of rain water collectors for firefighting.The remainder of the paper is organized as follows: Section2 describes the mathematical model. Section 3 presents a numerical example. Section 4 presents numerical experiments and provides some managerial insights, and Section 5 provides conclusions and recommendations for further research.


## 2. Model Description

This section presents a stochastic optimization model to minimize expected cost derived from RWC constructions, ecosystem damages, and firefighting logistics such as helicopter flight costs. In this model, the objective is to minimize the expected total cost. The model utilizes discrete decision variables. Before proceeding, the assumptions for the model are as follows:(1) only one fire can occur at any given time, (2) RWCs are full at all times, (3) the total capacity of an RWC is consumed when it is used, and (4) water demand to control fires (this varies by municipality) is known.The notations are defined in notations section.The problem is as follows:(1)min⁡⁡∑k=1KAk·Costk+∑j=1JPj·FLC·Deficitj+∑j=1J∑k=1KPj·Yjk·Vjk*G
subject to
(2)∑k=1KYjk·Capk+Deficitj=Demj∀j(3)∑k=1KAk≤L(4)Yjk≤Ak∀j,k(5)Yjk∈{0,1},Ak∈{0,1}∀j,k.The first term of the objective function (1) represents the total cost for RWC construction; the second term represents the expected cost for ecosystem damage. In this model, it is represented by the cost per hectare of forest loss. The last term represents the logistic cost which considers the cost of covering the distance to control fires. Constraints (2) ensure that the demand of municipality j is satisfied by the RWCs assigned to that municipality; if the demand of municipality j is not satisfied, a deficit is determined. Constraint (3) limits the maximum number of RWCs that can be constructed. Constraints (4) enforce that Ak should be equal to one whenever Yjk is equal to one. These constraints, combined with the first and last terms of the objective function, allow constraint (3) to correctly account for all RWCs to be constructed. Constraints (5) impose binary values for variables Yjk and Ak.Our model and solution method has advantages over the current decision making method. Currently, the decision to place an RWC is based only on a municipality’s demand for water. The suitability of the location for firefighting purposes is not currently taken into account. RWCs located using this approach can be used for firefighting but might not be in an advantageous location for this purpose. In contrast, our model explicitly considers the suitability of the RWC location for firefighting. To take into account the municipalities’ needs for water, the candidate locations can be restricted to locations that satisfy these requirements.Our model also has advantages over a deterministic formulation. A deterministic formulation can be obtained by deleting thePj values from the model. Such a model will strive to locate RWCs near high demand municipalities but will fail to consider the probability of fire in that location. In contrast, our model takes into account both the water demand and the fire probability.In this paper, we use the approximation for forest loss cost per hectare proposed by Armando [27]. Thus, the total forest loss cost is calculated using
(6)ForestLossCost(FLC)=810dollars/hectare*Hectaresburnedbyfire.To calculate the distance from each potential RWC construction site to the fire location, we consider the potential site coordinates,Xk and Yk, and the fire’s positions, Xj and Yj. The distance is computed using
(7)Djk=(Xj-Xk)2+(Yj-Yk)².In order to compute the total distance traveled by an aircraft,Vjk, we calculate the distance from each RWC to each municipality, Djk, and multiply it by the number of trips required to use all the water in the RWC. The number of trips is calculated by dividing the RWC capacity, Capk, by the helicopter’s capacity, Caph. Since no fractional trips can be made, we applied the ceiling function to round the quotient to the smallest integer greater than Capk/Caph. This coefficient is multiplied by two because the helicopter does round trips between the RWC and fire location. One trip is subtracted because the helicopter starts at the RWC and ends its interaction with the RWC at the fire location. Therefore, Vjk is computed using
(8)Vjk=[(⌈CapkCaph⌉*2)-1]*Djk.This computation assumes that all water in the RWC is used. Although it is possible for demand to be satisfied in fewer trips, in practice it is more likely to require the full water capacity. In this way the model is conservative and plans for a maximal number of trips.The probability of a fire occurring,Pj, is computed for each municipality. The statistical data taken into account includes the number of fires that have occurred per municipality within a study region during a recent year with enough, official information.


## 3. Case Study

To validate the model, the state of Nuevo Leon, Mexico, was used as a case study. According to the National Forestry Commission, during 2011, Nuevo Leon suffered thirty-five fires which affected 707 hectares of forest [2]. The State Center for Forest Fire Control reported that the municipality of Galeana had the largest number of events of this type with seventy seven, while Santiago reported the highest affected surface area. Table 1 presents the probabilities of fire per municipality.Table 1
Probabilities of fire per municipality.
Municipality
Number of fires
P
j
Galeana
77
0.430
Santiago
32
0.179
Monterrey
21
0.117
Santa Catarina
16
0.089
Villaldama
9
0.050
Salinas Victoria
6
0.034
Bustamante
5
0.028
San Pedro Garza García
4
0.022
García
3
0.017
San Nicolás de los Garza
1
0.006
General Escobedo
1
0.006
Carmen
1
0.006
Abasolo
1
0.006
Hidalgo
1
0.006
China
1
0.006
Total
179
1.000LetFj be the number of fires in municipality j during the study period. Then, (9) describes the calculation:
(9)Pj=Fj∑i=1JFi.Water demand to extinguished fires can be obtained using Royer and Floyd [28] approach, which claims that a fire’s volume in cubic feet divided by 200 equals the required gallons of water to control it. Equation (10) shows the calculation:
(10)Waterdemand=(Volumeoffire)j200*3.785liters*1m31000liters.
For this case, the water demands per municipality were obtained from Garza-Ramirez [17]. The data used is presented in Table 2.Table 2
Water demand for each municipality.
Municipality
Demand (m3)
Santiago
88,307.8
Galeana
62,700
Villaldama
29,090
Salinas Victoria
22,640
Santa Catarina
3,442
China
2,700
Garcia
620
San Pedro Garza Garcia
412
Monterrey
401.6
Bustamante
232.02
San Nicolas de los Garza
40
Abasolo
40
Carmen
20
Hidalgo
20
General Escobedo
0.01
Total
210,665.43An important point is that this region of Nuevo Leon has nine existing water sources. These water sources are not RWCs and have different capacities. Real data for these sources is utilized as an input to our model. Potential sites for RWCs are generated at random within the study region. The region was delimited by the convex hull given by the outer municipalities.Using Velasco Molina [18] pricing list for RWC construction, the cost of a 3,000 cubic meter RWC is $110,991 USD.Based on historical data and using (6), we set FLC as shown in Table 3.Table 3
Forest loss cost per municipality.
Municipality
FLC (US Dollars)
Santiago
11,811.31
Santa Catarina
920.74
San Pedro Garza Garcia
440.85
Monterrey
81.85
Galeana
3,485.18
San Nicolas de los Garza
171.20
General Escobedo
0.04
Carmen
85.60
Garcia
884.54
Abasolo
171.20
Hidalgo
85.60
Salinas Victoria
16,150.06
Villaldama
13,834.08
Bustamante
198.61
China
11,556.14The cost per unit distance,G, was calculated using
(11)G=Cost(USD/liter)Fueleconomy(km/liters).
The cost ($2.91) and fuel economy (0.79) were obtained from IndexMundi and AircraftCompare [29, 30]. A value of G=3.68 was used for all scenarios.In order to gain insight into the behavior of the model, a numerical study was performed. The study consisted of solving the model with varying values ofL. The parameter was varied from 1 to 50 in increments of 1. To better understand the impact of L on the expected total cost (objective function), we present Figure 2.Figure 2
Varying the maximum number of RWCs for the case study.The number of water sources to be constructed in the optimal solution is 29. A total deficit of 12,665.43m3 of water is proposed. The objective value is 17,891,875. The solution variables indicate the best selection of RWC locations. In real life, this means an optimized strategic plan considering financial implications and human resources that enables more efficient firefighting.An analysis of the selected RWCs was performed. This is relevant information to consider because it reflects the possible layout for the construction and utilization of RWCs. Table4 shows which RWCs are selected in the model’s optimal solution.Table 4
Construction and selection of RWCs.
RWC
USE
1
1
2
1
3
1
4
1
5
1
6
1
7
1
8
1
9
1
10
1
11
1
12
1
13
1
14
1
15
1
16
1
17
0
18
0
19
0
20
0
21
0
22
0
23
0
24
0
25
1
26
1
27
1
28
0
29
0
30
1
31
1
32
0
33
1
34
0
35
0
36
1
37
1
38
0
39
0
40
0
41
1
42
1
43
1
44
1
45
0
46
0
47
0
48
1
49
0
50
0
Total
29Based on the RWCs selected in the optimal solution, the optimal layout for the construction of the RWCs is shown in Figure3. Each RWC is labeled to indicate its position.Figure 3
Optimal solution for the case study.As can be observed, the construction of RWCs is concentrated near Santiago and Galeana, which are the municipalities with greater demand. Table5 shows that RWCs are assigned to each municipality.Table 5
RWC assignments.
Municipality
RWCs assigned
Deficit (m3) per year
Abasolo
0
40
Bustamante
0
232.02
Carmen
0
20
China
0
2700
Galeana
1, 2, 3, 6, 7, 9, 10, 12, 13, 14, 25, 27, 30, 36, 37, 41, 42, 43, 48
2700
Garcia
0
620
General Escobedo
0
0.01
Hidalgo
0
20
Monterrey
0
401.6
Salinas Victoria
4, 15, 16, 26, 31, 33, 44
1640
San Nicolás de los Garza
0
40
San Pedro Garza García
0
412
Santa Catarina
11
442
Santiago
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 25, 26, 27, 30, 31, 33, 36, 37, 41, 42, 43, 44, 48
1307.8
Villaldama
4, 5, 11, 15, 16, 26, 31, 33, 44
2090Since FLC is an estimated value, it is important to understand the impact of its variation. For this, we lowered and increased FLC by 50% and 25%, respectively, with respect to the original data. All other values were kept unchanged. Figure4 shows the model’s behavior when varying FLC. Table 6 summarizes the results. When varying FLC, the optimum number of RWC to be constructed (29) was the same for each scenario. This indicates that, in this case, the optimal RWC configuration is not very sensitive to changes in FLC.Table 6
Experiments outcome.
FLC
Optimum L
Objective function
−50%
29
11,552,844
−25%
29
14,722,360
Original
29
17,891,875
+25%
29
21,061,390
+50%
29
24,230,905Figure 4
Varying FLC for the case study.An observation from the experiments is that no deficit exceeds the capacity of an RWC. This means that the construction cost plus the logistic costs involved in the assignment of a new RWC is higher than the forest loss cost associated with the water deficit. Another observation is that most of the RWCs are constructed near the municipalities with higher water demands. This is because greater demand increases the number of required round trips, which consequently increases logistics cost. Therefore, reducing the distance to higher demand municipalities reduces logistics costs. Another observation is that the objective value increases as FLC is increased, but the number of RWCs to be constructed does not increase. This means that, in this case study, the construction and logistics costs (keeping in mind that logistics costs depend on the location) for an additional RWC are higher than the increase in forest loss cost, even when FLC is increased by 50%.


## 4. Additional Scenarios and Managerial Insights

In order to explore alternative scenarios, an additional set of instances was solved. These instances were based on the real case study but with changes to input values such as the RWC capacities, the aircraft capacities, and the water demands. Scenario 0 represents the real data used in the case study presented above. For scenarios 1 and 2, we lowered and increased demand to control fire by 20%, respectively. For scenarios 3 and 4, the RWC capacity was decreased and increased by 1,000 liters, respectively. For scenarios 5 and 6, the helicopter capacity was increased to 3,000 liters and lowered by 500 liters. Scenarios 7 and 8 vary the cost per unit distance by ±20%. To solve the proposed model, we used OPL to call Cplex 12.0. Table7 summarizes the changes to the original case study to obtain the additional six scenarios.Table 7
Numerical data used in each scenario.
Scenario
Number of cities
Capacity of RWC
Capacity of helicopters
Demand to control fire (Dj)
Cost per unit distance (G)
1
15
3,000 liters
1,500 liters
−20%
0%
2
15
3,000 liters
1,500 liters
+20%
0%
3
15
2,000 liters
1,500 liters
0%
0%
4
15
4,000 liters
1,500 liters
0%
0%
5
15
3,000 liters
3,000 liters
0%
0%
6
15
3,000 liters
1,000 liters
0%
0%
7
15
3,000 liters
1,500 liters
0%
−20%
8
15
3,000 liters
1,500 liters
0%
+20%Since Nuevo Leon has 9 existing water sources, it is set as lower bound to optimize strategic planning. The maximum number of RWCs allowed,L, in each scenario was set to 30, which allowed finding the optimal solution in every scenario. The model was also solved with an intermediate value of L=20. The results for the different scenarios are presented in Table 8.Table 8
Testing results.
Scenario
Maximum RWC allowed
Number of RWCs selected
Objective function
Deficit per year
Feasibility
0
9
9
188,864,744
105,665
YES
20
20
73,649,199
39,665
YES
30
29
17,891,875
12,665
YES
1
9
9
131,984,967
75,532
YES
20
20
33,624,708
21,532
YES
30
29
15,029,308
12,532
YES
2
9
9
248,165,989
138,798
YES
20
20
128,861,206
66,798
YES
30
29
49,648,355
21,798
YES
3
9
9
229,258,656
134,665
YES
20
20
144,908,486
76,665
YES
30
30
83,645,882
38,665
YES
50
44
77,669,925
6,665
YES
4
9
9
156,246,190
90,665
YES
20
20
29,897,080
22,665
YES
30
22
13,273,840
14,665
YES
5
9
9
187,425,499
105,665
YES
20
20
70,350,783
39,665
YES
30
29
14,374,364
12,665
YES
6
9
9
190,303,988
105,665
YES
20
20
76,947,615
39,665
YES
30
29
21,409,385
12,665
YES
7
9
9
188,432,970
105,665
YES
20
20
72,659,674
39,665
YES
30
29
16,836,621
12,665
YES
8
9
9
189,296,517
105,665
YES
20
20
74,638,723
39,665
YES
30
29
18,947,127
12,665
YESThe results from these instances yield some insights. One, which is to be expected, is that when there is a deficit of water, forest loss cost is incurred which yields higher objective values. This occurs because the FLC is much more than the construction cost of an RWC. A second insight is that an improved objective function is found for RWCs of greater capacity, and this is due to an increase of water availability from the RWCs that are selected. Thus, more water is available from the optimal locations, as opposed to having to construct RWCs in suboptimal locations in order to meet demand. Consequently, fewer RWCs need to be constructed. Another observation is that decreasing demand improves the objective function because logistic costs are reduced since fewer trips are needed to satisfy demand. It can also be observed that as the helicopter capacity increases, the objective function is improved due to the reduced number of required trips. Additionally, higher costs per unit distance yield higher objective values. This occurs because the logistic cost increases. A second insight is that a very high cost per unit distance inflicts logistic costs in such a manner that it is preferable to incur FLC. In other words, it is better, from a financial perspective, to let the forest burn.


## 5. Conclusions and Recommendations for Future Research

In this paper we propose an optimization model with the objective of minimizing expected total cost to control forest fires. A model is developed based on stochastic integer programming and solved using Cplex and OPL. The model is tested using a real case and several additional realistic scenarios. The impact of varying the limit on the number of RWCs, the RWC capacities, the aircraft capacities, and the water demands on the solution quality is explored. Some observations are that the objective value improves with larger RWCs and with the use of aircraft with greater capacity.Some recommendations for further research are to extend the model to consider multiple simultaneous fires. It is also possible that, due to location constraints, an RWC selected by the model cannot be placed in that particular position site. Therefore, models that consider ground topography such as mountains, streets, houses, buildings, and biodiversity, and property lines, among others, could be proposed. Updating of costs for forest lost and RWC is recommended in order to build more realistic cost-benefit scenarios. As well, models that consider social benefits associated to stored water in RWCs for local people in forest areas are necessary.



---

*Source: 983270-2014-07-22.xml*