Effective adaptive large neighborhood search for a firefighters timetabling problem

Every year, wildfires accentuated by global warming, cause economic and ecological losses, and often, human casualties. Increasing operational capacity of firefighter crews is of utmost importance to better face the forest fire period that yearly occurs. In this study, we investigate the real-world firefighters timetabling problem of the INFOCA institution, Andalusia (Spain). The main issue is to achieve maximum operational capability while taking into account work regulation constraints. This paper proposes an Integer Linear Programming (ILP) formulation that makes it feasible to solve small/medium instances to optimality. We put forward a matheuristic (ILPH) based on the ILP formulation, and we obtain solutions for larger instances. We propose an Adaptive Large Neighbourhood Search metaheuristic (ALNS) to obtain better results for larger instances and we use a version of the ILPH as one of the constructive methods. The ALNS obtains all the optimal solutions found by the ILP on small instances. It yields better solutions than the ILPH matheuristic on larger instances within shorter processing times. We report on experiments performed on datasets generated using real-world data of the INFOCA institution. The work was initiated as part of the GEO-SAFE project.