A Sequence-Based Hyper-Heuristic for Traveling Thieves
A plethora of combinatorial optimization problems can be linked to real-life decision scenarios. Even nowadays, more diverse and complex problems are popping up. One of these problems is the traveling thief problem (TTP), which combines elements from the knapsack and traveling salesperson problems....
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-12-01
|
| Series: | Applied Sciences |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2076-3417/13/1/56 |
| _version_ | 1797626332158361600 |
|---|---|
| author | Daniel Rodríguez Jorge M. Cruz-Duarte José Carlos Ortiz-Bayliss Ivan Amaya |
| author_facet | Daniel Rodríguez Jorge M. Cruz-Duarte José Carlos Ortiz-Bayliss Ivan Amaya |
| author_sort | Daniel Rodríguez |
| collection | DOAJ |
| description | A plethora of combinatorial optimization problems can be linked to real-life decision scenarios. Even nowadays, more diverse and complex problems are popping up. One of these problems is the traveling thief problem (TTP), which combines elements from the knapsack and traveling salesperson problems. Hence, it is paramount to keep improving solvers to tackle combinatorial problems. Among recent proposals, hyper-heuristics have proven useful since they seek to combine the strengths of more straightforward solvers. This paper proposes a sequence-based selection hyper-heuristic and assesses its feasibility when solving the TTP. Our proposal can be represented by an array of operators selecting a city or an item. In the first case, the solution moves to a new city and thus advances the tour. In the second one, the <i>thief</i> agent picks an item within the current city and tries to store it in its knapsack. We generate several sets of TTP instances with different parameters to validate our approach and analyze the model’s performance. Our data reveal that the proposed approach outperforms randomly generated sequences. Moreover, our approach finds general sequences that surpass sequences specialized for each instance. We believe this is noteworthy and represents a stepping stone towards achieving a more robust solver for complex problems. |
| first_indexed | 2024-03-11T10:08:54Z |
| format | Article |
| id | doaj.art-6f3fc7fccde24dc7b18cfcce386b3fd8 |
| institution | Directory Open Access Journal |
| issn | 2076-3417 |
| language | English |
| last_indexed | 2024-03-11T10:08:54Z |
| publishDate | 2022-12-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Applied Sciences |
| spelling | doaj.art-6f3fc7fccde24dc7b18cfcce386b3fd82023-11-16T14:50:01ZengMDPI AGApplied Sciences2076-34172022-12-011315610.3390/app13010056A Sequence-Based Hyper-Heuristic for Traveling ThievesDaniel Rodríguez0Jorge M. Cruz-Duarte1José Carlos Ortiz-Bayliss2Ivan Amaya3School of Engineering and Sciences, Tecnologico de Monterrey, Monterrey 64849, MexicoSchool of Engineering and Sciences, Tecnologico de Monterrey, Monterrey 64849, MexicoSchool of Engineering and Sciences, Tecnologico de Monterrey, Monterrey 64849, MexicoSchool of Engineering and Sciences, Tecnologico de Monterrey, Monterrey 64849, MexicoA plethora of combinatorial optimization problems can be linked to real-life decision scenarios. Even nowadays, more diverse and complex problems are popping up. One of these problems is the traveling thief problem (TTP), which combines elements from the knapsack and traveling salesperson problems. Hence, it is paramount to keep improving solvers to tackle combinatorial problems. Among recent proposals, hyper-heuristics have proven useful since they seek to combine the strengths of more straightforward solvers. This paper proposes a sequence-based selection hyper-heuristic and assesses its feasibility when solving the TTP. Our proposal can be represented by an array of operators selecting a city or an item. In the first case, the solution moves to a new city and thus advances the tour. In the second one, the <i>thief</i> agent picks an item within the current city and tries to store it in its knapsack. We generate several sets of TTP instances with different parameters to validate our approach and analyze the model’s performance. Our data reveal that the proposed approach outperforms randomly generated sequences. Moreover, our approach finds general sequences that surpass sequences specialized for each instance. We believe this is noteworthy and represents a stepping stone towards achieving a more robust solver for complex problems.https://www.mdpi.com/2076-3417/13/1/56hyper-heuristictraveling thief problemcombinatorial optimization |
| spellingShingle | Daniel Rodríguez Jorge M. Cruz-Duarte José Carlos Ortiz-Bayliss Ivan Amaya A Sequence-Based Hyper-Heuristic for Traveling Thieves Applied Sciences hyper-heuristic traveling thief problem combinatorial optimization |
| title | A Sequence-Based Hyper-Heuristic for Traveling Thieves |
| title_full | A Sequence-Based Hyper-Heuristic for Traveling Thieves |
| title_fullStr | A Sequence-Based Hyper-Heuristic for Traveling Thieves |
| title_full_unstemmed | A Sequence-Based Hyper-Heuristic for Traveling Thieves |
| title_short | A Sequence-Based Hyper-Heuristic for Traveling Thieves |
| title_sort | sequence based hyper heuristic for traveling thieves |
| topic | hyper-heuristic traveling thief problem combinatorial optimization |
| url | https://www.mdpi.com/2076-3417/13/1/56 |
| work_keys_str_mv | AT danielrodriguez asequencebasedhyperheuristicfortravelingthieves AT jorgemcruzduarte asequencebasedhyperheuristicfortravelingthieves AT josecarlosortizbayliss asequencebasedhyperheuristicfortravelingthieves AT ivanamaya asequencebasedhyperheuristicfortravelingthieves AT danielrodriguez sequencebasedhyperheuristicfortravelingthieves AT jorgemcruzduarte sequencebasedhyperheuristicfortravelingthieves AT josecarlosortizbayliss sequencebasedhyperheuristicfortravelingthieves AT ivanamaya sequencebasedhyperheuristicfortravelingthieves |