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 fin...

Full description

Saved in:
Bibliographic Details
Published in:Journal of heuristics 2019-06, Vol.25 (3), p.377-397
Main Authors: Kline, Alexander G., Ahner, Darryl K., Lunday, Brian J.
Format: Article
Language:English
Subjects:
Algorithms
Artificial Intelligence
Assignment problem
Calculus of Variations and Optimal Control
Optimization
Heuristic
Interceptors
Management Science
Mathematics
Mathematics and Statistics
Missiles
Operations Research
Operations Research/Decision Theory
Weapons
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1381-1231
1572-9397
DOI:10.1007/s10732-018-9401-1