Cargando…
A novel approach for solving travelling thief problem using enhanced simulated annealing
Real-world optimization problems are getting more and more complex due to the involvement of inter dependencies. These complex problems need more advanced optimizing techniques. The Traveling Thief Problem (TTP) is an optimization problem that combines two well-known NP-Hard problems including the 0...
Autores principales: | , , , , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
PeerJ Inc.
2021
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8022508/ https://www.ncbi.nlm.nih.gov/pubmed/33834093 http://dx.doi.org/10.7717/peerj-cs.377 |
_version_ | 1783674943456673792 |
---|---|
author | Ali, Hamid Zaid Rafique, Muhammad Shahzad Sarfraz, Muhammad Malik, Muhammad Sheraz Arshad Alqahtani, Mohammed A. Alqurni, Jehad Saad |
author_facet | Ali, Hamid Zaid Rafique, Muhammad Shahzad Sarfraz, Muhammad Malik, Muhammad Sheraz Arshad Alqahtani, Mohammed A. Alqurni, Jehad Saad |
author_sort | Ali, Hamid |
collection | PubMed |
description | Real-world optimization problems are getting more and more complex due to the involvement of inter dependencies. These complex problems need more advanced optimizing techniques. The Traveling Thief Problem (TTP) is an optimization problem that combines two well-known NP-Hard problems including the 0/1 knapsack problem and traveling salesman problem. TTP contains a person known as a thief who plans a tour to collect multiple items to fill his knapsack to gain maximum profit while incurring minimum cost in a standard time interval of 600 s. This paper proposed an efficient technique to solve the TTP problem by rearranging the steps of the knapsack. Initially, the picking strategy starts randomly and then a traversal plan is generated through the Lin-Kernighan heuristic. This traversal is then improved by eliminating the insignificant cities which contribute towards profit adversely by applying the modified simulated annealing technique. The proposed technique on different instances shows promising results as compared to other state-of-the-art algorithms. This technique has outperformed on a small and medium-size instance and competitive results have been obtained in the context of relatively larger instances. |
format | Online Article Text |
id | pubmed-8022508 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2021 |
publisher | PeerJ Inc. |
record_format | MEDLINE/PubMed |
spelling | pubmed-80225082021-04-07 A novel approach for solving travelling thief problem using enhanced simulated annealing Ali, Hamid Zaid Rafique, Muhammad Shahzad Sarfraz, Muhammad Malik, Muhammad Sheraz Arshad Alqahtani, Mohammed A. Alqurni, Jehad Saad PeerJ Comput Sci Algorithms and Analysis of Algorithms Real-world optimization problems are getting more and more complex due to the involvement of inter dependencies. These complex problems need more advanced optimizing techniques. The Traveling Thief Problem (TTP) is an optimization problem that combines two well-known NP-Hard problems including the 0/1 knapsack problem and traveling salesman problem. TTP contains a person known as a thief who plans a tour to collect multiple items to fill his knapsack to gain maximum profit while incurring minimum cost in a standard time interval of 600 s. This paper proposed an efficient technique to solve the TTP problem by rearranging the steps of the knapsack. Initially, the picking strategy starts randomly and then a traversal plan is generated through the Lin-Kernighan heuristic. This traversal is then improved by eliminating the insignificant cities which contribute towards profit adversely by applying the modified simulated annealing technique. The proposed technique on different instances shows promising results as compared to other state-of-the-art algorithms. This technique has outperformed on a small and medium-size instance and competitive results have been obtained in the context of relatively larger instances. PeerJ Inc. 2021-03-16 /pmc/articles/PMC8022508/ /pubmed/33834093 http://dx.doi.org/10.7717/peerj-cs.377 Text en © 2021 Ali et al. https://creativecommons.org/licenses/by/4.0/ This is an open access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0/) , which permits unrestricted use, distribution, reproduction and adaptation in any medium and for any purpose provided that it is properly attributed. For attribution, the original author(s), title, publication source (PeerJ Computer Science) and either DOI or URL of the article must be cited. |
spellingShingle | Algorithms and Analysis of Algorithms Ali, Hamid Zaid Rafique, Muhammad Shahzad Sarfraz, Muhammad Malik, Muhammad Sheraz Arshad Alqahtani, Mohammed A. Alqurni, Jehad Saad A novel approach for solving travelling thief problem using enhanced simulated annealing |
title | A novel approach for solving travelling thief problem using enhanced simulated annealing |
title_full | A novel approach for solving travelling thief problem using enhanced simulated annealing |
title_fullStr | A novel approach for solving travelling thief problem using enhanced simulated annealing |
title_full_unstemmed | A novel approach for solving travelling thief problem using enhanced simulated annealing |
title_short | A novel approach for solving travelling thief problem using enhanced simulated annealing |
title_sort | novel approach for solving travelling thief problem using enhanced simulated annealing |
topic | Algorithms and Analysis of Algorithms |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8022508/ https://www.ncbi.nlm.nih.gov/pubmed/33834093 http://dx.doi.org/10.7717/peerj-cs.377 |
work_keys_str_mv | AT alihamid anovelapproachforsolvingtravellingthiefproblemusingenhancedsimulatedannealing AT zaidrafiquemuhammad anovelapproachforsolvingtravellingthiefproblemusingenhancedsimulatedannealing AT shahzadsarfrazmuhammad anovelapproachforsolvingtravellingthiefproblemusingenhancedsimulatedannealing AT malikmuhammadsherazarshad anovelapproachforsolvingtravellingthiefproblemusingenhancedsimulatedannealing AT alqahtanimohammeda anovelapproachforsolvingtravellingthiefproblemusingenhancedsimulatedannealing AT alqurnijehadsaad anovelapproachforsolvingtravellingthiefproblemusingenhancedsimulatedannealing AT alihamid novelapproachforsolvingtravellingthiefproblemusingenhancedsimulatedannealing AT zaidrafiquemuhammad novelapproachforsolvingtravellingthiefproblemusingenhancedsimulatedannealing AT shahzadsarfrazmuhammad novelapproachforsolvingtravellingthiefproblemusingenhancedsimulatedannealing AT malikmuhammadsherazarshad novelapproachforsolvingtravellingthiefproblemusingenhancedsimulatedannealing AT alqahtanimohammeda novelapproachforsolvingtravellingthiefproblemusingenhancedsimulatedannealing AT alqurnijehadsaad novelapproachforsolvingtravellingthiefproblemusingenhancedsimulatedannealing |