Two-stage hybrid heuristic search algorithm for novel weapon target assignment problems. (December 2021) - Ma, Yingying; Wang, Guoqiang; Hu, Xiaoxuan; Luo, He
Highlights: We introduce a weapon target assignment problem with uncertain weapon adequacy. A non-linear integer programming model is formulated for the studied problem. A two-stage hybrid heuristic search algorithm is developed to solve the problem. Three different datasets are generated to test the algorithm. The algorithm can give a high-quality solution in a short time. Abstract: The objective of the weapon target assignment (WTA) problem is to maximize the total damage of targets or minimize the total consumption of weapons. However, the existing studies of the WTA problem did not consider the uncertainty of weapon adequacy in practical battlefield scenarios. In this paper, we study a novel WTA problem, called the WTA problem with uncertainty (WTAU), and the uncertainty refers to the uncertainty of weapon adequacy. The objective of the WTAU is to find a WTA scheme to maximize the total value of destroyed targets by using as few weapons as possible in situations where the adequacy of weapons is uncertain. To address the uncertainty of weapons adequacy, we formulate the WTAU problem as a nonlinear integer programming model. To improve the computing efficiency, we design a two-stage hybrid heuristic search (TSHHS) algorithm based on prior WTAU knowledge. In the first stage of the TSHHS algorithm, a logarithmic transformation method is employed to obtain the optimal target destruction (TD) scheme and an initial WTA scheme. In the second stage, a constructive heuristic method based on the maximum marginal return (MMRBH) and a simple optimization (SimpleO) method are developed to obtain a promising WTA scheme. Moreover, we perform extensive experiments to analyze the performance of the proposed method. The results of numerical experiments show that the proposed method can provide a high-quality WTA scheme with a short computing time in scenarios involving adequate or inadequate weapons.