Self-organizing Maps and Large Neighborhood Search Based Task Assignment for Multiple Unmanned Surface Vehicles

This paper studies the task assignment for multiple Unmanned Surface Vehicles (USVs) to efficiently visit a set of target locations, which can be applied for ocean monitoring, search and rescue, and military surveillance. To minimize the total travel distance of all USVs to visit all the target locations while respecting the USVs’ limited operation time and communication range, a task assignment algorithm is proposed by integrating the Self-Organizing Map (SOM) with Large Neighborhood Search (LNS). First, considering the USVs’ limited operation time and communication range, the studied task assignment problem is formulated, which is a variant of the NP-hard vehicle routing problem. Secondly, the proposed SOM algorithm uses winning neuron selection and neuron ring updation to calculate an initial solution for the task assignment problem, where a neuron ring splitting mechanism is used to enable each USV to recharge at the base station before battery depletion. Thirdly, the LNS algorithm probabilistically selects removal and repair strategies to improve the routes for individual USVs as well as for pairs of USVs. Simulation results show that the proposed SOM-LNS-based task assignment algorithm has satisfying performance compared with the Minimum Marginal-cost Algorithm (MMA), MMA-LNS-based task assignment algorithm, and Variable Neighborhood Search algorithm.