Solving Heterogeneous USV Scheduling Problems by Problem-Specific Knowledge Based Meta-Heuristics with Q-Learning

Zhenfang Ma, Kaizhou Gao (), Hui Yu and Naiqi Wu
Additional contact information
Zhenfang Ma: Macau Institute of System Engineering, Macau University of Science and Technology, Avenida Wai Long, Taipa 999078, Macau
Kaizhou Gao: Macau Institute of System Engineering, Macau University of Science and Technology, Avenida Wai Long, Taipa 999078, Macau
Hui Yu: Macau Institute of System Engineering, Macau University of Science and Technology, Avenida Wai Long, Taipa 999078, Macau
Naiqi Wu: Macau Institute of System Engineering, Macau University of Science and Technology, Avenida Wai Long, Taipa 999078, Macau

Mathematics, 2024, vol. 12, issue 2, 1-23

Abstract: This study focuses on the scheduling problem of heterogeneous unmanned surface vehicles (USVs) with obstacle avoidance pretreatment. The goal is to minimize the overall maximum completion time of USVs. First, we develop a mathematical model for the problem. Second, with obstacles, an A* algorithm is employed to generate a path between two points where tasks need to be performed. Third, three meta-heuristics, i.e., simulated annealing (SA), genetic algorithm (GA), and harmony search (HS), are employed and improved to solve the problems. Based on problem-specific knowledge, nine local search operators are designed to improve the performance of the proposed algorithms. In each iteration, three Q-learning strategies are used to select high-quality local search operators. We aim to improve the performance of meta-heuristics by using Q-learning-based local search operators. Finally, 13 instances with different scales are adopted to validate the effectiveness of the proposed strategies. We compare with the classical meta-heuristics and the existing meta-heuristics. The proposed meta-heuristics with Q-learning are overall better than the compared ones. The results and comparisons show that HS with the second Q-learning, HS + QL2, exhibits the strongest competitiveness (the smallest mean rank value 1.00) among 15 algorithms.

Keywords: unmanned surface vessel; scheduling; meta-heuristics; Q-learning (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2024
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.mdpi.com/2227-7390/12/2/339/pdf (application/pdf)
https://www.mdpi.com/2227-7390/12/2/339/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:12:y:2024:i:2:p:339-:d:1322843

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().