Efficient Heuristic Approaches to the Weapon-Target Assignment Problem

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 methods to solve the general weapon-target assignment problem. Our computational results show 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.