Distributed Neighborhood Search Algorithm for Target Assignment

This paper investigates the weapon-target assignment problem and a distributed neighborhood search algorithm is proposed to solve this problem. The proposed algorithm is developed based on the very large-scale neighborhood search (VLSN) algorithm, which is originally developed for centralized allocation among agents. We improve the construction of the improvement graph and the search process for valid cycles in the VLSN algorithm. This enables that the allocation algorithm can be deployed in a distributed way. Each missile maintains a local improvement graph by communicating with its neighbors and attempts to search for valid cycles. The valid cycle directs missiles to exchange their attack targets to achieve the distributed target assignment. Extensive numerical simulations demonstrate the effectiveness of the method.