火力与制导资源联合分配的快速构造算法组合设计

The joint allocation problem of firepower and guidance resources is a typical NP-complete problem in military operation research, which has higher real-time requirement on solving performance. Exact algorithms are difficult to apply, while recently proposed constructive algorithms have significant time overhead, seriously affecting their practical application. To satisfy the need of real-time solving, a multi-stage sensor-weapon-target assignment (S-WTA) problem was formulated and decomposed into two sub-problems of combat resource allocation. In the weapon allocation phase, a fast constructive algorithm determining allocation priority based on threat values was adopted. In the sensor allocation phase, a new fast constructive algorithm determining allocation priority based on stage order was proposed, utilizing constraints fully and reducing time overhead substantially. Additionally, based on the two basic constructive algorithms and a constructive algorithm for sensor allocation based on marginal loss, a sequential combination of constructive algorithms was proposed to solve the multi-stage S-WTA problem. Some computational experiments were carried out to validate the rapidity of the newly proposed basic constructive algorithm for sensor allocation. Additionally, it was proven that the sequential combination of constructive algorithms could find much better solutions to the problem as compared to the basic constructive algorithms in most cases.