Solving Heterogeneous USV Scheduling Problems by Problem-Specific Knowledge Based Meta-Heuristics with Q-Learning
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...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2024-01-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/12/2/339 |
| _version_ | 1797342980258922496 |
|---|---|
| author | Zhenfang Ma Kaizhou Gao Hui Yu Naiqi Wu |
| author_facet | Zhenfang Ma Kaizhou Gao Hui Yu Naiqi Wu |
| author_sort | Zhenfang Ma |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-08T10:41:03Z |
| format | Article |
| id | doaj.art-20f38781a95c44bdb883cd8205c33f87 |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-08T10:41:03Z |
| publishDate | 2024-01-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-20f38781a95c44bdb883cd8205c33f872024-01-26T17:34:06ZengMDPI AGMathematics2227-73902024-01-0112233910.3390/math12020339Solving Heterogeneous USV Scheduling Problems by Problem-Specific Knowledge Based Meta-Heuristics with Q-LearningZhenfang Ma0Kaizhou Gao1Hui Yu2Naiqi Wu3Macau Institute of System Engineering, Macau University of Science and Technology, Avenida Wai Long, Taipa 999078, MacauMacau Institute of System Engineering, Macau University of Science and Technology, Avenida Wai Long, Taipa 999078, MacauMacau Institute of System Engineering, Macau University of Science and Technology, Avenida Wai Long, Taipa 999078, MacauMacau Institute of System Engineering, Macau University of Science and Technology, Avenida Wai Long, Taipa 999078, MacauThis 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.https://www.mdpi.com/2227-7390/12/2/339unmanned surface vesselschedulingmeta-heuristicsQ-learning |
| spellingShingle | Zhenfang Ma Kaizhou Gao Hui Yu Naiqi Wu Solving Heterogeneous USV Scheduling Problems by Problem-Specific Knowledge Based Meta-Heuristics with Q-Learning Mathematics unmanned surface vessel scheduling meta-heuristics Q-learning |
| title | Solving Heterogeneous USV Scheduling Problems by Problem-Specific Knowledge Based Meta-Heuristics with Q-Learning |
| title_full | Solving Heterogeneous USV Scheduling Problems by Problem-Specific Knowledge Based Meta-Heuristics with Q-Learning |
| title_fullStr | Solving Heterogeneous USV Scheduling Problems by Problem-Specific Knowledge Based Meta-Heuristics with Q-Learning |
| title_full_unstemmed | Solving Heterogeneous USV Scheduling Problems by Problem-Specific Knowledge Based Meta-Heuristics with Q-Learning |
| title_short | Solving Heterogeneous USV Scheduling Problems by Problem-Specific Knowledge Based Meta-Heuristics with Q-Learning |
| title_sort | solving heterogeneous usv scheduling problems by problem specific knowledge based meta heuristics with q learning |
| topic | unmanned surface vessel scheduling meta-heuristics Q-learning |
| url | https://www.mdpi.com/2227-7390/12/2/339 |
| work_keys_str_mv | AT zhenfangma solvingheterogeneoususvschedulingproblemsbyproblemspecificknowledgebasedmetaheuristicswithqlearning AT kaizhougao solvingheterogeneoususvschedulingproblemsbyproblemspecificknowledgebasedmetaheuristicswithqlearning AT huiyu solvingheterogeneoususvschedulingproblemsbyproblemspecificknowledgebasedmetaheuristicswithqlearning AT naiqiwu solvingheterogeneoususvschedulingproblemsbyproblemspecificknowledgebasedmetaheuristicswithqlearning |