Real-Time Heuristic Algorithms for the Static Weapon-Target Assignment Problem

The problem of targeting and engaging individual missiles (targets) with an arsenal of interceptors (weapons) is known as the weapon target assignment problem. Many optimal solution techniques are applied to solve problem variants having linear approximations of the objective function, and their final solutions rarely yield optimal solutions to the original problem. Herein, we propose a nonlinear branch and bound algorithm to solve the untransformed problem. We also develop two heuristics respectively based on a branch and bound algorithm and the optimal solution to the quiz problem, and we compare them to a well-embraced heuristic from the literature. We test the three heuristics to solve a set of 15 problem sizes and 20 instances for each size, comparing their performance with respect to solution quality and required computational effort. The heuristic based upon the optimal solution to the quiz problem finds solutions within \(6\%\) of optimal for small problems and provides statistically similar results as one of the best heuristics found in the literature for larger problems, while solving these problems in ten thousandths of the time.