Ensemble meta-heuristics and Q-learning for solving unmanned surface vessels scheduling problems

This work addresses multiple unmanned surface vessel (USV) scheduling problems with minimizing maximum completion time. First, a mathematical model is developed with considering battery capacity and uncertain mapping time. Second, meta-heuristics and Q-learning are combined for solving the concerned problems. Based on the feature of USV scheduling problems, six heuristic rules are designed to obtain high-quality initializing solutions. According to the structure of solution space, six local search operators are designed. Q-learning is employed to select a premium local search operator in each iteration for improving the search efficiency of meta-heuristics. Finally, the performance of the proposed meta-heuristics with Q-learning based local search are verified by solving 10 cases with different scales. The experimental results and statistical tests demonstrate the competitiveness of the proposed algorithms for solving USVs scheduling problems. The particle swarm optimization with the first Q-learning strategy for local search selection is the best one among all compared algorithms.