Reformulation and valid inequalities for the disrupted asset protection problem during an escaped wildfire

Abstract During wildfires, community assets are at risk of being damaged or destroyed. Preventive actions can be carried out to protect these assets. The Asset Protection Problem (APP) aims at routing vehicles and teams in order to protect assets, under time windows and synchronization constraints. When a disruption occurs, vehicles need to be rerouted in order to take the consequences of the disruption into account. The disrupted version of the APP (D-APP) balances the maximization of the value of protected assets and the minimization of changes from the original routes. In this paper, we propose a reformulation of the original model together with several sets of problem-specific valid inequalities that rely on structural properties such as deviation, resources requirements and synchronization. We also show how these valid inequalities can be used for the mono-objective APP. Computational testing shows that we can solve instances of large sizes that were previously not consistently solved in the literature for D-APP, and highly reduce the time to obtain optimal solutions for small instances of APP. While exact resolution of very large instances remains out of reach, our contributions provide new structural insights and are a first step towards more scalable exact and heuristic methods for D-APP.