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

Combinatorial design of fast construction algorithms for joint allocation of firepower and guidance resources

火力与制导资源联合分配问题是军事运筹学研究中典型的NP完全问题,其求解具有较高的实时性要求.精确求解算法难以适用,而近来提出的构造算法的时间开销也相对较大,严重影响算法的实际应用.为了解决该问题,本文将其建模为多阶段传感器–武器–目标分配(sensor-weapon-target assignment,S-WTA)问题,并分解成两类作战资源分配子问题.在武器分配阶段采用了一种基于威胁值确定分配优先级的快速构造算法,在传感器分配阶段提出了一种新的基于阶段顺序确定分配优先级的快速构造算法,该算法能充分利用约束条件,大幅度减小时间开销.本文在两种基本构造算法与基于边际损失的构造算法的基础上进一步提出了构造算法序列化组合,对多阶段S-WTA问题进行求解.计算实验验证了新提出的基本构造算法的快速性以及构造算法序列化组合相比于各种基本构造算法的性能优势.

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-weapontarget 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.