Solving Static Weapon-Target Assignment Problem using Multi-Start Late Acceptance Hill Climbing

Abstract

The Weapon-Target Assignment (WTA) problem is a complex optimization challenge in defense strategy, where weapons must be assigned to targets to minimize the expected value of surviving targets. This study addresses the static WTA (SWTA) problem, where assignments are made once and remain unchanged. Given the NP-complete nature of the SWTA problem, exact solution methods are often impractical due to computational complexity. This paper proposes a novel approach that combines multi-start and Late Acceptance Hill Climbing (LAHC) strategies to improve solution quality. Experimental results on various problem instances show that the Multi-Start Late Acceptance Hill Climbing (MLAHC) algorithm consistently achieves higher quality solutions with improved stability compared to the traditional LAHC algorithm, especially for larger problem instances. This approach represents a significant advance in the optimization of military resource allocation.

Keywords

• Combitonarial Optimization
• Late Acceptance Hill Climbing
• Weapon-Target Assignment Problem

References

1. R. K. Ahuja, A. Kumar, K. C. Jha, J. B. Orlin, Exact and heuristic algorithms for the weapon-target assignment problem, Operations research 55 (6) (2007) 1136–1146.
2. A. Kline, D. Ahner, R. Hill, The weapon-target assignment problem, Computers & Operations Research 105 (2019) 226–236.
3. S. P. Lloyd, H. S. Witsenhausen, Weapons allocation is np-complete., in: 1986 summer computer simulation conference, 1986, pp. 1054–1058.
4. E. Sonuc, B. Sen, S. Bayir, A cooperative gpu-based parallel multistart simulated annealing algorithm for quadratic assignment problem, Engineering Science and Technology, an International Journal 21 (5) (2018) 843–849.
5. Ö. Tolga, E. BOZKAYA, An evaluation on weapon target assignment problem, Journal of Naval Sciences and Engineer- ing 18 (2) (2022) 305–332.
6. H. Xing, Q. Xing, An air defense weapon target assignment method based on multi-objective artificial bee colony algorithm., Computers, Materials & Continua 76 (3) (2023).
7. E. Sonuc, B. Sen, S. Bayir, A parallel simulated annealing algorithm for weapon-target assignment problem, Interna- tional Journal of Advanced Computer Science and Applications 8 (4) (2017) 87–92.
8. B. Chopard, M. Tomassini, An introduction to metaheuristics for optimization, Springer, 2018.

9. A. Toet, H. de Waard, The Weapon-Target Assignment Problem, Citeseer, 1995.
10. C. Wang, G. Fu, D. Zhang, H. Wang, J. Zhao, et al., Genetic algorithm-based variable value control method for solving the ground target attacking weapon-target allocation problem, Mathematical Problems in Engineering 2019 (2019).
11. D. Guo, Z. Liang, P. Jiang, X. Dong, Q. Li, Z. Ren, Weapon-target assignment for multi-to-multi interception with grouping constraint, IEEE Access 7 (2019) 34838–34849.
12. M. D. Rezende, B. S. P. De Lima, S. Guimara˜es, A greedy ant colony system for defensive resource assignment problems, Applied Artificial Intelligence 32 (2) (2018) 138–152.
13. Exact and heuristic algorithms for the weapon-target assignment problem (2007). doi:10.1287/OPRE.1070.0440.
14. A new exact algorithm for the weapon-target assignment problem (2021). doi:10.1016/J.OMEGA.2019.102138. A. C. Andersen, K. Pavlikov, T. A. Toffolo, Weapon-target assignment problem: Exact and approximate solution algo- rithms, Annals of Operations Research 312 (2) (2022) 581–606.
15. E. Sonuc¸, A modified crow search algorithm for the weapon-target assignment problem, An International Journal of Optimization and Control: Theories & Applications (IJOCTA) 10 (2) (2020) 188–197.
16. S. Zou, X. Shi, S. Song, Moea with adaptive operator based on reinforcement learning for weapon target assignment, Electronic Research Archive 32 (3) (2024) 1498–1532.
17. E. K. Burke, Y. Bykov, The late acceptance hill-climbing heuristic, European Journal of Operational Research 258 (1) (2017) 70–78.
18. M. Terzi, T. Arbaoui, F. Yalaoui, K. Benatchba, Solving the unrelated parallel machine scheduling problem with setups using late acceptance hill climbing, in: Asian Conference on Intelligent Information and Database Systems, Springer, 2020, pp. 249–258.
19. A. Goerler, E. Lalla-Ruiz, S. Voß, Late acceptance hill-climbing matheuristic for the general lot sizing and scheduling problem with rich constraints, Algorithms 13 (6) (2020) 138.
20. S. Clay, L. Mousin, N. Veerapen, L. Jourdan, Clahc-custom late acceptance hill climbing: First results on tsp, in: Proceedings of the Genetic and Evolutionary Computation Conference Companion, 2021, pp. 1970–1973.
21. B. S. Shihab, H. N. Abdullah, L. A. Hassnawi, Improved artificial bee colony algorithm-based path planning of un- manned aerial vehicle using late acceptance hill climbing., International Journal of Intelligent Engineering & Systems 15 (6) (2022).
22. B. Chatterjee, T. Bhattacharyya, K. K. Ghosh, P. K. Singh, Z. W. Geem, R. Sarkar, Late acceptance hill climbing based social ski driver algorithm for feature selection, IEEE Access 8 (2020) 75393–75408.