Iterated local search for the placement of wildland fire suppression resources

被引:15
作者
Mendes, Andre Bergsten [1 ]
Alvelos, Filipe Pereira [2 ]
机构
[1] Univ Sao Paulo, Dept Engn Naval & Ocean, Ave Prof Mello Moraes 2231, BR-05508030 Sao Paulo, Brazil
[2] Univ Minho, Ctr Algoritmi, Dept Prod & Sistemas, P-4710057 Braga, Portugal
关键词
Metaheuristics; Wildfires; Fire suppression; Mixed integer programming; Iterated local search; INTEGER PROGRAMMING-MODEL; FIREFIGHTER PROBLEM; FOREST-FIRES; MANAGEMENT; CONTAINMENT; ALLOCATION;
D O I
10.1016/j.ejor.2022.04.037
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
We consider the problem of, given a landscape represented by a gridded network and a fire ignition lo-cation, deciding where to locate the available fire suppression resources to minimise the burned area and the number of deployed resources as a secondary objective. We assume an estimate of the fire propaga-tion times between adjacent nodes and use the minimum travel time principle to model the fire propa-gation at a landscape-level. The effect of locating a resource in a node is that it becomes protected and the fire propagation to its unburned adjacent nodes is delayed. Therefore, the problem is to identify the most promising nodes to locate the resources, which is solved by a novel iterated local search (ILS) meta -heuristic. A mixed integer programming (MIP) model from the literature is used to validate the proposed method in 32 grid networks with sizes 6x6, 10x10, 20x20 and 30x30, with two different number of fire suppression resources (64 problems). Our ILS produced optimal solutions in 40 cases out of 41 known optimal lower bounds. The proposed method's effectiveness is also due to its short computing times and small coefficients of variation of the objective function values.We also provide a categorised literature review on fire suppression deterministic optimisation models, from which we conclude that approximate collaborative approaches seldom have been applied in the past and, according to the results obtained, can successfully address the complexity of fire suppression, reaching good quality solutions even for large scale instances.(c) 2022 Elsevier B.V. All rights reserved.
引用
收藏
页码:887 / 900
页数:14
相关论文
共 55 条
[1]   Mixed Integer Programming Models for Fire Fighting [J].
Alvelos, Filipe .
COMPUTATIONAL SCIENCE AND ITS APPLICATIONS (ICCSA 2018), PT II, 2018, 10961 :637-652
[2]   Modeling Ground Firefighting Resource Activities to Manage Risk Given Uncertain Weather [J].
Belval, Erin J. ;
Wei, Yu ;
Bevers, Michael .
FORESTS, 2019, 10 (12)
[3]   A mixed integer program to model spatial wildfire behavior and suppression placement decisions [J].
Belval, Erin J. ;
Wei, Yu ;
Bevers, Michael .
CANADIAN JOURNAL OF FOREST RESEARCH, 2015, 45 (04) :384-393
[4]  
Blum Christian, 2014, Evolutionary Computation in Combinatorial Optimisation. 14th European Conference (EvoCOP 2014). Revised Selected Papers: LNCS 8600, P218, DOI 10.1007/978-3-662-44320-0_19
[5]  
Chi SD, 2003, LECT NOTES ARTIF INT, V2829, P487
[6]   Optimizing Fuel Treatments to Reduce Wildland Fire Risk [J].
Chung, Woodam .
CURRENT FORESTRY REPORTS, 2015, 1 (01) :44-51
[7]   Fire containment in grids of dimension three and higher [J].
Develin, Mike ;
Hartke, Stephen G. .
DISCRETE APPLIED MATHEMATICS, 2007, 155 (17) :2257-2268
[8]  
Dimopoulou M., 2001, International Transactions in Operational Research, V8, P523, DOI 10.1111/1475-3995.00330
[9]  
Donovan GH, 2003, FOREST SCI, V49, P331
[10]   Operational wildfire suppression modelling: a review evaluating development, state of the art and future directions [J].
Duff, Thomas J. ;
Tolhurst, Kevin G. .
INTERNATIONAL JOURNAL OF WILDLAND FIRE, 2015, 24 (06) :735-748