Piecewise Linearization and Neighborhood-Structure-Based Heuristic for the Sensor-Weapon-Target Assignment Problem

Sensor-weapon-target assignment (S-WTA) problem is a widely known combinatorial optimization problem extended from weapon-target assignment (WTA) problem. There has been few research on how to solve S-WTA problem efficiently due to its highly nonlinear property and it takes an unacceptable long time to obtain an exact solution. Piecewise linearization (PL) with high precision can solve such nonlinear problems effectively, but it requires much time to achieve high precision. Multi-exchange neighborhood is effective for assignment problems, but has not been validated on S-WTA problems and requires a reliable initial solution for better performance. Therefore, a new structure combining PL and heuristic methods is proposed. The proposed approach utilizes low precision PL to obtain an initial solution within a short time. Moreover, a new reassign neighborhood is combined with an adapted multi-exchange neighborhood to construct the neighborhood-structure-based heuristic (NSBH) approach. The reliability of PL is first validated through experiments. Then the computational results indicates that the proposed method, PL-NSBH, well balance the solution quality and computational time, which validates the intuition of our strategy. Meanwhile, the results also reveal the effectiveness of our reassign neighborhood.