Efficient Adaptive Large Neighborhood Search for Sensor-Weapon-Target Assignment

We study a sensor-weapon-target assignment (S-WTA) problem that considers the desired probability of target destruction and aims to minimize the total cost of combat resources. Lower and upper bounds for the S-WTA problem are obtained by constructing linear approximation models. We also propose an adaptive large neighborhood search (ALNS) algorithm characterized by a model-driven repair phase to solve this problem. The destruction phase adaptively selects a destruction operator to remove partial resource assignments and produces an incomplete reference solution. For the destroyed solution, the repair phase generates a reduced subproblem that optimizes only the destroyed parts while keeping the other parts fixed. Each subproblem is formulated as a mixed integer programming model and solved by a general-purpose solver to repair the destroyed solution. Computational experiments show that the approximation formulations can obtain tight lower and upper bounds for most problem instances. Moreover, our proposed ALNS algorithm is competitive with the solver for small instances and effectively solves large instances. In addition, we experimentally demonstrate that our ALNS outperforms state-of-the-art algorithms in the literature, and the proposed model-driven solution repair phase outperforms the traditional heuristic repair operators.