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...

Descripción completa

Detalles Bibliográficos
Autores principales: Ali, Hamid, Zaid Rafique, Muhammad, Shahzad Sarfraz, Muhammad, Malik, Muhammad Sheraz Arshad, Alqahtani, Mohammed A., Alqurni, Jehad Saad
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