Improved solution of the Budget constrained Fuel Treatment Scheduling problem and extensions

This paper considers the budget constrained fuel treatment scheduling (BFTS) problem where, in the context of wildfire mitigation, the goal is to inhibit the potential of fire spread in a landscape by proper fuel treatment activities. Given a time horizon represented by consecutive unit periods, the landscape is divided into cells and represented as a grid graph where each cell has a fuel age that increases over time and becomes old if no treatment is applied in the meantime: this induces a potential high fire risk whenever two contiguous cells are old. Cells fuel ages can be reset to zero under appropriate fuel treatments but there is a limited budget for treatment in each period. The problem calls for finding a suitable selection of cells to be treated so as to minimize the presence of old contiguous cells over the whole time horizon. We prove that problem BFTS is strongly NP- complete on paths and thus on grid graphs and show that no polynomial time approximation algorithm exists unless ℘ =풩℘. We provide an enhanced integer linear programming formulation of the problem with respect to the relevant literature that shows up to be efficiently solved by an ILP solver on reasonably large size instances. Finally, we consider a harder periodic variant of the problem with the aim of finding a cyclic treatment plan with cycles of length T and propose a matheuristic approach capable of efficiently tackling those instances where an ILP solver applied to the ILP formulation runs into difficulties.