Local search-based meta-heuristics combined with an improved K-Means++ clustering algorithm for unmanned surface vessel scheduling

Unmanned surface vessels (USVs) play an important role in marine field, which can improve the efficiency and safety of task execution in hazardous environments. The applications of artificial intelligence technologies on USV collaboration scheduling can guide the USV cluster intelligence. In this study, the scheduling problems of USVs are solved by five local search-based meta-heuristics combining with an improved K-Means++ algorithm. The objective is to minimise the maximum completion time of USVs. For task assignment of USVs, an improved K-Means++ clustering (IKC) algorithm is proposed. The assignment results are used to initialise the population of meta-heuristics. According to the characteristics of the concerned problems and the structure of the solution space, six local search operators are designed to improve the convergence of meta-heuristics. Finally, the proposed strategies are integrated to five meta-heuristics and their performance are verified by solving 40 instances with different scales. Experimental results and statistical tests prove the strong competitiveness of the proposed algorithms. From the statistical analysis, the local search-based harmony search with the IKC algorithm performs better than the compared ones for solving the concerned problems.