Modelling and optimal solving of dependent sensor-weapon/threat assignment and scheduling problem by a metaheuristic algorithm based on GRASP

Document Type : Original Article

Authors

1 M.Sc. Student, Department of Industrial Engineering, Ferdowsi University of Mashhad

2 Associate professor, Department of Industrial Engineering, Ferdowsi University of Mashhad

3 Associate professor, Islamic Azad University, Gonabad Branch

4 Assistant professor, Imam Reza University

Abstract

Nowadays, smart systems are being widely used in combats because there exist a lot of applications for these systems which usually depend on sensors. Matching sensors to weapons and threats or in short sensor-weapon/threat assignment is a major challenge in modern wars and is classified as a complex resource assignment optimization problem. Consequently, the result of modern wars highly depends on effective usage of sensors and weapons. In this paper, the sensor-weapon/threat assignments and their scheduling problem have been formulated. The object of this model is maximizing the destruction of threats in a given time horizon subject to operational constraints. This model has been solved using CPLEX. Furthermore, a metaheuristic algorithm based on GRASP is developed. Finally, using a set of randomly generated test instances, the results of all developed solution approaches are reported and compared.

Keywords

References

[1]  N. Li, W. Huai, and S. Wang, “ The solution of target assignment problem in command and control    decision-making behaviour simulation,”  Enterprise Information Systems, vol. 11, pp. 1059-1077, 2017.##
[2]  Z. Bogdanowicz and N. Coleman, “ Advanced Algorithm for Optimal Sensor-Target and        Weapon-Target Pairings in Dynamic Collaborative Engagement,” Army Armament Research Development and Engineering Center Picatinny Arsenal NJ, 2008.##
[3]  Z. R. Bogdanowicz, “ A new efficient algorithm for optimal assignment of smart weapons to targets,”  Computers & Mathematics with Applications, vol. 58, pp. 1965-1969, 2009.##
[4]  S. Matlin, “A review of the literature on the        missile-allocation problem,”  Operations Research, vol. 18, pp. 334-373, 1970.##
[5]  R. K. Ahuja, A. Kumar, K. C. Jha, and J. B. Orlin, “ Exact and heuristic algorithms for the weapon-target assignment problem,”  Operations Research, vol. 55, pp. 1136-1146, 2007.##
[6]  P. A. Hosein, J. T. Walton, and M. Athans, “ Dynamic weapon-target assignment problems with vulnerable C2̳ nodes,” 1988.##
[7]  S. P. Lloyd and H. S. Witsenhausen, “Weapons allocation is NP-complete,” In 1986 Summer Computer Simulation Conference, pp. 1054-1058. 1986.##
[8]  Y. H. Cha and Y. D. Kim, “Fire scheduling for planned artillery attack operations under time-dependent destruction probabilities,” Omega, vol. 38, pp.        383-392, 2010.##
[9]  D. Lötter, I. Nieuwoudt, and J. Van Vuuren, “A multiobjective approach towards weapon assignment in a ground-based air defence environment,” ORiON, vol. 29, pp. 31-54, 2013.##
[10] O. Karasakal, “Optimal Air Defense Strategies for Naval Task Group,” METU, 2004.##
[11] T. Gülez, “Weapon-Target Allocation And Scheduling For Air Defense With Time Varying Hit Probabilities,” Middle East Technical University, 2007.##
[12] G. Cho, “Hybrid nested partition method with  intelligent greedy search for solving Weapon Target Assignment problem,” Iowa State University, 2009.##
[13] A. Turan, “Algorithms for the weapon-target allocation problem,” PhD diss., Middle East Technical University, 2012.##
[14] K. Kalyanam, S. Rathinam, D. Casbeer, and M. Pachter, “Optimal Threshold Policy for Sequential Weapon Target Assignment,” IFAC-Papers OnLine, vol. 49, pp. 7-10, 2016.##
[15]  Z. Mei, Z. Peng, and X. Zhang, “ Optimal dynamic weapon-target assignment based on receding horizon control heuristic,”  In Control & Automation (ICCA), 2017 13th IEEE International Conference, pp.      876-881, 2017.##
[16]  Y. Z. Chang, Z. W. Li, Y. X. Kou, Q. P. Sun, H. Y. Yang, and Z. Y. Zhao, “A New Approach to Weapon-Target Assignment in Cooperative Air Combat,” Mathematical Problems in Engineering, vol. 2017, 2017.##
[17]  Y. Li, Y. Kou, Z. Li, A. Xu, and Y. Chang, “A Modified Pareto Ant Colony Optimization Approach to Solve Biobjective Weapon-Target Assignment Problem,” International Journal of Aerospace Engineering, vol. 2017, 2017.##
[18]  R. Taghavi and M. Ranjbar, “Weapon Scheduling in Naval Combat Systems for Maximization of Defense Capabilities,” Iranian Journal of Operations Research, vol. 6, 2015.##
[19]  M. Peymankar, M. Ranjbar, A. Izadipour, and S. Balochian, “Modelling and Solving the Location Problem of Fire Launching Sites,” Journal of Electronical & Cyber Defence, vol. 6, no. 3, Serial no. 23, 2017. (In Persian)##
[20]  M. Peymankar, M. Ranjbar, A. Izadipour, and S. Balochian, “Modeling and Solution of Fire Allocation and Scheduling Problem of Distributed Sites,”  Journal of Advanced Defence Science and Technology, vol. 9, no. 4, Serial no. 34, 2018. (In Persian)##
[21] S. A. KhatoonAbadi and H. Shirazi, “Weapon Target Assignmnet using Distributed Constraint Optimization,” In 7th National Command and Control Conference, Tehran, 2013. (In Persian)##
[22]  H. Almasian and A. Shakibamanesh, “ littoral and floating Missle sites Layout for The Assignment of Weapons Againt Offshore Sea Targets,” In 8th National Command and Control Conference, Tehran, 2014. (In Persian)##
[23]  A. Okhravi, A. Pooya, S. Nazemi, and M. Kazemi, “ Designing an integrated model for assigning targets to headquarters in marine battle management regarding to  target classification,” Ph.D Thesis, Ferdowsi University of Mashhad, Mashhad, Khorasan Razavi, Iran, 2016. (In Persian)##
[24]  F. Feiznaei, M. B. Naghibisistani, and S. K. Hosseinisani, “Solving the problem of weapons allocation in defense systems,” M.S. Thesis, Ferdowsi University of Mashhad, Mashhad, Kharasan Razavi, Iran, 2015. (In Persian)##
[25]  Z. Bogdanowicz and N. Coleman, “Sensor-target and weapon-target pairings based on auction algorithm,”  in Proceedings of the 11th WSEAS International Conference on Applied Mathematics, pp. 92-96, 2007.##
[26]  L. Zi-fen, L. Xiang-min, D. Jin-jin, C. Jin-zhu, and Z. Feng-xia, “Sensor-weapon-target assignment based on improved SWT-opt algorithm,”  In Computing, Control and Industrial Engineering (CCIE), 2011 IEEE 2nd International Conference, pp. 25-28, 2011.##
[27]  H. Chen, Z. Liu, Y. Sun, and Y. Li, “ Particle swarm optimization based on genetic operators for       sensor-weapon-target assignment,”  In Computational Intelligence and Design (ISCID), 2012 Fifth International Symposium on, pp. 170-173, 2012.##
[28]  K. L. Ezra, D. A. DeLaurentis, L. Mockus, and J. F. Pekny, “Developing Mathematical Formulations for the Integrated Problem of Sensors, Weapons, and Targets,”  Journal of Aerospace Information Systems, 2016.##
[29]  L. Mu, X. Qu, and P. Wang, “Application of Sensor/Weapon-Target Assignment based on     Multi-Scale Quantum Harmonic Oscillator Algorithm,”  In Image, Vision and Computing (ICIVC), 2017 2nd International Conference on, pp. 1147-1151, 2017.##
[30]  T. A. Feo and M. G. Resende, “Greedy randomized adaptive search procedures,” Journal of global optimization, vol. 6, pp. 109-133, 1995.##
[31]  J. P. Hart and A. W. Shogan, “Semi-greedy heuristics: An empirical study,”  Operations Research Letters, vol. 6, pp. 107-114, 1987.##
[32]  T. A. Feo and M. G. Resende, “A probabilistic heuristic for a computationally difficult set covering problem,”  Operations research letters, vol. 8, pp.   67-71, 1989.##

Files

History

  • Receive Date: 05 September 2018
  • Revise Date: 27 May 2019
  • Accept Date: 18 June 2019
  • Publish Date: 21 May 2020

Share

How to cite

Statistics