An Efficient Marginal-Return-Based Constructive Heuristic to Solve the Sensor–Weapon–Target Assignment Problem
针对网络中心战中传感器和武器的协同分配问题，提出一种基于边际收益的构造式启发式算法，仅通过简单查表操作快速生成分配方案，计算复杂度低，在多种规模实例上表现优于现有算法。
In network-centric warfare, the interconnections among various combat resources enable an advanced operational pattern of cooperative engagement. The operational effectiveness and outcome strongly depends on the reasonable utilization of available sensors and weapons. In this paper, a mathematical model for the coallocation of sensors and weapons is built, taking into account the interdependencies between weapons and sensors, the resource constraints, the capability constraints, as well as the strategy constraints. A marginal-return-based constructive heuristic (MRBCH) is proposed to solve the formulated sensor-weapon-target assignment (S-WTA) problem. MRBCH exploits the marginal return of each sensor-weapon-target triplet and dynamically updates the threat value of all targets. It relies only on simple lookup operations to choose each assignment triplet, thus resulting in very low computational complexity. For performance evaluation, we build a general Monte Carlo simulation-based S-WTA framework. Furthermore, we employ a random sampling method and an extension of the state-of-the-art algorithm Swt_opt as competitors. The computational results show that MRBCH consistently performs very well in solving S-WTA instances of different scales, and it can generate assignment schemes much more efficiently than its competitors.