A spatial decomposition based math-heuristic approach to the asset protection problem. (2020)

• Record Type: Journal Article
• Authors: Nuraiman, Dian; Ozlen, Melih; Hearne, John
• Is Part Of: Operations research perspectives. Volume 7(2020)
• Publication Date: 2020
• Subjects: Wildfires -- Asset protection problem -- Emergency response vehicles -- Math-heuristic -- Spatial decomposition; Operations research -- Periodicals; Management science -- Periodicals; 658.403405
• DOI: 10.1016/j.orp.2020.100141
• Languages: English
• ISSNs: 2214-7160

Abstract

Highlights: A new solution approach to the asset protection problem (APP) is proposed. A spatial decomposition based math-heuristic (SDM) approach is introduced using a commercial solver. The proposed SDM approach outperforms the published ALNS algorithm. The SDM approach is applicable to similar problems where the time windows are spatially correlated. Abstract: This paper addresses the highly critical task of planning asset protection activities during uncontrollable wildfires known in the literature as the Asset Protection Problem (APP). In the APP each asset requires a protective service to be performed by a set of emergency response vehicles within a specific time period defined by the spread of fire. We propose a new spatial decomposition based math-heuristic approach for the solution of large-scale APP's. The heuristic exploits the property that time windows are geographically correlated as fire spreads across a landscape. Thus an appropriate division of the landscape allows the problem to be decomposed into smaller more tractable sub-problems. The main challenge then is to minimise the difference between the final locations of vehicles from one division to the optimal starting locations of the next division. The performance of the proposed approach is tested on a set of benchmark instances from the literature and compared to the most recent Adaptive Large Neighborhood Search (ALNS) algorithm developed for the APP. The results show that our proposed solution approach outperforms the ALNS algorithm on all instances with comparable computation time. We also see a trend with the margin of out-performance becoming more significant as the problems become larger.