A heuristic and metaheuristic approach to the static weapon target assignment problem
- PDF / 806,134 Bytes
- 22 Pages / 439.37 x 666.142 pts Page_size
- 50 Downloads / 197 Views
A heuristic and metaheuristic approach to the static weapon target assignment problem Alexander G. Kline1
· Darryl K. Ahner2 · Brian J. Lunday2
Received: 11 October 2017 / Accepted: 2 August 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract The weapon target assignment (WTA) problem, which has received much attention in the literature and is of continuing relevance, seeks within an air defense context to assign interceptors (weapons) to incoming missiles (targets) to maximize the probability of destroying the missiles. Kline et al. (J Heuristics 25:1–21, 2018) developed a heuristic algorithm based upon the solution to the Quiz Problem to solve the WTA. This heuristic found solutions within 6% of optimal, on average, for smaller problem instances and, when compared to a leading WTA heuristic from the literature, identified superlative solutions for larger instances within hundredths of a second, in lieu of minutes or hours of computational effort. Herein, we propose and test an improvement to the aforementioned heuristic, wherein a modified implementation iteratively blocks exiting assignments to an initial feasible solution, allowing superior solutions that would otherwise be prevented via a greedy selection process to be found. We compare these results to the optimal solutions as reported by a leading global optimization solver (i.e., BARON) and find solutions that are, at worst, within 2% of optimality and, at best, up to 64% better than the solutions reported to be optimal by BARON. To wit, the developed metaheuristic outperformed BARON in 25% of all instances tested, as BARON reported a suboptimal solution as being optimal for 21.1% of the instances, and it could not identify an optimal solution for the remaining 6.67% of the instances within 2 h of CPU time, a liberally imposed time limit that far exceeds practical usage considerations for this application. Keywords Weapon target assignment problem · Quiz problem · BARON
B
Alexander G. Kline [email protected] Darryl K. Ahner [email protected] Brian J. Lunday [email protected]
1
US Army, 700 Defense Pentagon, Washington, DC 20301, USA
2
WPAFB, 2950 Hobson Way, Dayton, OH 45433-7765, USA
123
Journal of Global Optimization
1 Introduction The Weapon Target Assignment (WTA) Problem has been studied extensively in the field of operations research since its introduction by Flood in 1957. It is the subject of many solution techniques that include exact algorithms, heuristic algorithms, and nature inspired metaheuristics. In much of the literature, a piecewise approximation of linear functions is used to transform the problem into one whose solution is more computationally accessible. While there are variants of the problem such as the dynamic WTA and two stage WTA, this paper focuses on the NP-complete Static WTA (SWTA) Problem. Given a set J = {1, . . . , n} of incoming targets, solving the problem results in assigning a set I = {1, . . . , m} of weapons to the targets so as to minimize the collective residual e
Data Loading...
