Naval Air Defense Planning problem: A novel formulation and heuristics

Abstract This article focuses on air defense in maritime environment, which involves protecting friendly naval assets from aerial threats. Specifically, we define and address the Naval Air Defense Planning (NADP) problem, which consists of maneuvering decisions of the ships and scheduling weapons and sensors to the threats in order to maximize the total expected survival probability of friendly units. The NADP problem is more realistic and applicable than previous studies, as it considers features such as sensor assignment requirements, weapon and sensor blind sectors, sequence‐dependent setup times, and ship's infrared/radar signature. In this study, a mixed‐integer nonlinear programming model of the NADP problem is presented and heuristic solution approaches are developed. Computational results demonstrate that these heuristic approaches are both fast and efficient in solving the NADP problem.