Efficient Heuristic Approach to the Weapon-Target Assignment Problem

Abstract

The weapon‐target assignment problem is a fundamental defense application of operations research. The problem consists of optimally assigning a given number of weapons to a set of targets, so that the post-engagement total expected survival value of the targets is minimized. Since the weapon‐target assignment problem is known to be nondeterministic polynomial time-complete, there are no exact methods to solve it. This paper presents two innovative heuristic algorithms based on simulated annealing and threshold accepting methodstosolvethegeneralweapon‐targetassignmentproblem.Ourcomputationalresultsshow that by using these algorithms, relatively large instances of the weapon‐target assignment problem can be solved near-optimally in a few seconds on a standard personal computer.